Введение к работе
Li! МяШ
уальность темы. Потоковая ( data }tow ) организация
Стдллпслэяий, позволяющая естественно выражать параллелизы.прп-'са>ЩЩ 1рат"аош..т» задачам, и вшздять возможности параллельно! обработки яа различных уровнях, является одной кз основополагающих при создании ЭЬМ пятого поколения и языков параллельного программирования. Исследования в данной области ведутся в трах основных направленнях: модели потоковых вычислений, языковые средства, потоковые архитектуры.
Среди абстрактных потоковых моделей слодует выделить модели с сигналами подтвэрзденнй в с тегированными фншкамп. Первая модель ограничивает число фишек (максимально по одной) яа дугах потоковых схем (п-схем), что приводят к снижении степени параллелизма вычислений. Наиболее перспективной представляется модель с тегированными фишками, которая предполагает эффективное выполнение массовых параллельных вычислений за счет возможности одновременной обработки нескольких экземпляров одной п той же воршинн п-схе?,ы. Соотношение свойств тегированных п-схеїі о упреждением и их структурной организации требует разработки системы формальных понятий я дополнительного исследования.
К настоящему времени известен ряд апшшкатявных потоковых языков программирования высокого уровня, которым свойственно следующее: строгая функциональность, единственное прксваива-нкз, отсутствие побочных эффектов, использование имен значений вместо переменных. Программирование только посредством алшшкагивных языков хотя и упрощаэт процесс трансляции прэг-раминых конотруїщЕй в потоковый код, однако не способствует использованию накопленного фонда последовательных программ, а также традиционной методологии программирования. Опыт разработки и использования методов преобразования императивных конструкций к потоковому виду показывает, что такие черты традициоЕіннх языков программирования, как глобальные переменные і Soto -операторы, поэлементное'изменение структур данных, пседдоимена требуют наиболее сложное компиляционной техники и необходимы дальнейшие глубокие исследования данной проблемы.
"" На последнее десятилетие приходится пик научных и экспериментальных исследований в области развития потоковых архитектур. Потокошэ принципы обработки информации в той клн иной форме положены в основу многих зарубежных и отечественных проектов. Особенно широкое щжшеєееє потоковые архитектуры получили а таких областях, как вычислительные задачи, обработка свгналов, искусственный интеллект, логическое программирование. Ддн успешного использования потоковых машин необходимо решать наряду с другими проблзгяу эффективно! потоковой реализации алгоритмов, првдаолаганцих последовательные вычисления над структурированными данными (поиск, сортировка).
Среди направлений современного развития вычислительных средств также слэдуе? откатить СБЙС-архнтекгуры, организованные в виде систолических катриц. Больной интерес для'исследований представляет автоматизация процессов анализа корректности и оптимизации систем такого типа.
Таким образом, из выше сказанного следует актуальность выбранной тематики нсоладований.
Целью ддсоэртвдаи является разработка системы формальных понятий, методов и средств для анализа, автоматического построения и моделирования-структур потокового типа. Достижение цели связывается о рассмотрением следующих вопросов:
-
определенно способа наиболеа эффективней на различных уровнях организации потоковых вычислений;
-
введение и обоснование формальнего аппарата для установления и изучения взаимосвязи мезду наиболее важными свойствами потоковых схем с упреждением и налагаемыш структурными ограничениями, а также для анализа систем систолического типа;
-
разработка методов автоматического построения широких классов потоковых схем;
-
создание экспериментальной системы потокового программирования (ЭСПП), поддерживающей процессы анализа,генерации и моделирования потоковых и систолических структур.
Методы исследований. Исследования проведены с использованием элементов теория схем программ и параллельной схемато-логяи, теория сложности алгоритмов,организации потоковых и систолических структур. Данные для оценки, параметров произ-
водитедьности потоковой архитектуры получены с помощью имита- -ционных экспериментов в ЭСШ.
Научная новизна исследования состоит в разработке и применения оригинального комплексного подхода к решению задач формализации, анализа и автоматического построения шроких классов структур потокового твиа. Научную новизну раскрывают следующие результаты: введена и исследована иерархия формальных моделей, ориентированных как на неструктурированные, так и структурированные классы тегированных п-схєм с упредцэнием; определена формальная систолическая модель, разработаны алгоритмы анализа и оптимизации систолических структур; предложены и обоснованы глетодц преобразования стандартных операторных схем произвольной структуры, схем с массивами и процедурами в эквивалентные (в определенном нижа смысла) тегированные п-схемы с высокой степенью асинхронности.
Практическая ценность. Разработанные в диссертации методы могут.быть положены в основу реальных трансляторов, осуществляющих генерацию потокового малинного кода. Многие предложенные алгоритмы доведены до экспериментальных программных реализаций в рамках ЭСПП, что моаэт служить непосредственно основой для реальной потоковой системы. Анализ эффективности потоковой реализации алгоритмов сортировки, элементарных функций и полученные с помощью имитатора ЭСШ оценки характеристик производительности могут быть использованы на стадии проектирования при выбора оптимальной конфигурации потоковой архитектуры.
Апробация работы. Основные результаты работы докладывались и обсуадались на УІ, УП Всесоюзных гаколах-сэмннарах "Распараллеливание обработки информации" (Львов, 1987, 1989), Втором региональном семинаре "Распраделенная обработка информации" (Новосибирск, 1987), Всесоюзной конференции "Формальные модели параллельных вычислений" (Новосибирск, 1987), УШ семинаре "Однородные вычислительные среды и систолические структуры" . (Львов, 1988), Международной школа-семинарэ "Формальные модели параллельных вычислений" (Телава, 1989),на семинарах Ж АН УССР и КГУ (Киев, 1989), МЭИ (Москва, 1989), ВЦ СО АН СССР (Новосибирск, 1987, 1988, 1989).
Структура диссертации. Диссертация состоит из введения,
четырех глав, заключения, списка литературы и приложений. Объем 132 страниц основного текста, 36 страниц рисунков и таблиц. Список литературы содержат 118 наименований.
Ьо введении обосновывается актуальность рассматриваемых вопросов, формулируются цели исследований, првдставленяьа в диссертации. Описывается научная новизна результатов, практическая ценность работы. Приводится краткое содержание диссертации по главам.
В первой главе дан аналитический обзор состояния исследований в области архитектуры мелкоблочных ( їпе yixttn.) ЭВМ, управляемых потоками данных.
Рассмотрены общие принципы организации машин такого типа. Описаны механизмы, обеспечивающие корректные реентерабельные вычисления, - блокирование фишек, сигналы подтверждений, копирование кода, тегирование фишек, очередей. Определены подхода к организации потоковых вычислений над структурами данных. Приведена классификация потоковых ЭВМ, в основу которой положена классификация Вана. В качестве принципов классификации выбраны тип организации процессорного.элемента (ПЭ) и тип реализуемых взаимодействий ыэвду ПЭ. В основополагающую классификацию были внесены некоторые изменения: добавлены ветви, уточняющие механизмы обеспечения реентерабельных вычислений; число приведенных проектов расширено примерно вдвое.
На основа анализа проектов потоковых систем, выполненного в главе, установлено, что динамические тегированные ЭВМ, в состав которых включена распределенная память 1-структур, способны достигать наибольшей производительности вычислений. Поэтому такая организация потоковых вычислений была выбрана в качестве предмета исследований диссертационной работы.
Ьо второй главе вводится и исследуется иерархия формальных моделей тегированных потоковых вычислений. П-схема с тегированными фишками определяется как система DP - < To&as, Тар, Ports, A/odes; idge), где
Tcfens - счетное множество фишек данных, состоящее из подмножеств информационных {Xtoiens ) и управляющих ( Cto&ens )
фишек. 7аа:Тс^е/?~У> TRQ ^ - множество натуральных чисел. Считается, что /V разбито на непересекающиеся интарналы целочисленных значений (тегов). Ports - счетное множество портов, состоящее из подмножеств информационных {Xports ) и управляющих (Cports ) портов. Хпри , Output с- Ports - божества входных и выходных портов, соответственно. /Vcdes -счетное множество вершин, состоящее из подмножеств операционных ( Орег ), условных ( ConcL ) вершин, клапанов {Gat}, вар-шин модификации тегов {Tmod). ~%dge; \Lp(f/odes) о Output)—*-CopWcd&s) f Тарифі ) , где Lp(tfcdes) и ср(Modes) - множества входных и выходных портов вершин из Modes, соответственно.
Интерпретация I п-схемн задается обычным образом. I- множество возможных интерпретаций. Состоянием п-схемы DP при интерпретации X называется функция' 5 , которая сопоставляет:
а) комплекты информационных фишек информационным портам,
б) комплекты управляющих фишек управляющим портам. С кавдым
типом вершин связано определенное правило срабатывания, кото
рое представляет собой пару функций <ХР,ор> таких, что ХР
определяет, какие фишки с каких входных портов потребляются,
а функция ср - какие множества фишек к каким выходным пор
там добавляются при срабатывании вершины данного типа.
Срабатывание с тэгом Г вершины // - это пара состояний
Историей вычислительного процесса при интерпретации 2" называется последовательность состояний < Sf, . .., $4> таких, что V fit і. : < $:) SiH > - срабатывание вершины /V'єA/odes,
Вычислительным процессом при интерпретации X называется последовательность варпіил пз Орег- и tend, выписанных в том порядке, как они следуют в истории вычислительного процесса. Через МР(Р) обозначил множество вершин, входящих в процесс Р , через Nl(/V,p) - число вхождений вершины Л/ в процесс Р. Если PftOCfDF, iy - множество вычислительных процессов п-схемн DP при интерпретации I , то P/?OC0PJ= u(Pf
Состояние S п-схеш DF называется
- ВХОДНЫМ, ЄСЛИ р& Ports -Tnput'. S(j>)-0; - выходным («W).
если YpeOutput: S(p)i 0 ; - выходным "очищенным", если ЧрєРоі~і$ - Outpu.t', S(p)-0\ - бесконфликтным относительно порта р , осла 5(р) на содержит двух и более фишок с идентичным тегом; - баоконфликтным, если Yp^Pofts'. S - бесконфликтное относительно порта р ; -живым, если Ёла^&С*)-?.
TA7(J)F) и SlATcut(dFi обозначают множества всех возможных состояний и всех выходных состояний п-схемы DP , соответственно.
Процесс Р называется
- В--эквивалентным- процессу Р (P~PJ , если их информацион
но-логические графы (ШГ-графы) совпадают; - включающий про
цесс Р'(Р'<=Р) , если a) fl/fi
//I(KP') ^JVr(A/,P).
П-схема 2)F называется -бесконфликтной, если YSsS7ATWF): $ - бесконфликтное; -живой, если YSe&TA7-ST*TClji(>p-)\ S -живое; - "очищаемой", если S-S>TA7mll)f): 5 -"очищенное"'; - -эквивалентной п-охемэ Ж' (DP ~Df) , если VJeX : fi'еPROC(3F,J) в P^PROCCJf', І)і Р ~ Р' ;- максимально асинхронной в классе iDF'lDP'^DFJ, есла УІеі; YP є Рйос(Щі) в р'еРЯ0С(1)Р\ 1} : />' /О ; _ абсолютно асинхронной в классе І DP'lDF'~DFj, если" Y р&Ряос(2Р) и Р'єРХОсСРҐ);
Структурированная п-схема с тегированными фишками ЭРЯ определяется как ацякличаскяі ориентированный граф, построенный на входных и выходных портах структурированных конструкций из множества Consir-s. Структурированная конструкция - это либо операционная вершина, CSC (условная), / (циклическая), JSC (ациклическая) структурированная конструкция. Синтаксис конструкций определяет потоковые вычисления с упреждением3^.
Теорема 2.1. Структурированная л-схема SDfi- является
*' Amsmiya М., Hasegawa R. Dataflow, computing and eager
and lazy'evaluations//Ne-R Gener.Comput. - 1985. - Vol.
2, И 2. - P. 105-130.- .
бесконфликтной живой "очищаемой" и абсолютно асинхронной в классе %DP\3f~SBF).
Далее определяется п-схема с массивами DFA- как расширение п-схемы д? за счет: а) добавлення счетного множоства имен массивов (-A/iames ); б) разбиения множества информационных фишек {Ltoiens) на непересекающиеся подмнояества фишек с именами массивов (.Hciens^ ), с индексными значениями {ZiohnsI ), со значениями массивов ( X-6o4ens ); в) аналогичного разбиения множества информационных портов (Tpor-ts = Tpor-ts^ ulpcr-lsz ujporis ) ' г) введения в множество вершин подмножества вершин модификации индексных значений {2тссС ) и подмножества вершин обработки массивов, в свою очередь состоящее из непересекающихся подмножеств вершин порождения массива ( CREATE), выбора значения из массива (SfAfCT), модификации значения в массиве {ЯРРЕМВ ).
Структурированная п-схема с массивами SDFJ представляет собой расширение п-схемы' SDF за счет добавления к множеству Consirs подмножеств вершин обработки массивов и модификации индексных значений. Дополнительные структурные ограничения состоят в следующем: Vjf <=Апате$ : а) существует ровно одна вершина аррелсієДррВФ б) существует ровно одна вершина t/Glmod,
Теорема 2.2. Структурированная п-схема с массивами SDF/r является бесконфликтной живой "очищаемой" и абсолютно асинхронной в классе \1)РЛ-\1>?Д ~S2FJJ.
П-схема с процедурами" dFP состоит из главной п-схемы и множества п-схем процедур, с каждой из которых связано некоторое уникальное имя. Главная п-схема представляет собой расширение п-схемы BF за счет введения в множество вершин подмножества вершин вызова процедур (^РРІУ ). П-схема процедуры - это п-схема того же типа, что и главная п-схема.
Структурированная п-схема SDFP - это структурированная главная п-схема и ілножество структурированных п-схвм процедур, для построения которых используется множество Const^s, дополненное вершинами вызова процедур.
Теорема 2.3. Структурированная п-схема с процедурами SPFP является бесконфликтной живой "очищаемой" и абсолютно асинхронной в классе {DFPIDFP^SDFP},.
Ь конца главы вводится формальная модель систолических вычислений. С-сеть определяется как система М - < Tokens , Ports, Ixodes, Weight, 'edge, CfoeJ>, где ftbofes - счетное множество однотипных варшан; функдия Ъ/еСвЬ-t сопоставляет вершине /V<= f/cdes некоторое целочисленное значение - вес вершины, то есть время ее срабатывания. С каждой дугой, определяемой функцией icfoe , также связано целочисленное значение - вес дуги. В отличие от асинхронных п-схем в синхронную систему включена функция СёосЛ .определяющая множество вершин, срабатывающих на такте defoT-*/), где Т - период тактирования с-сети. Далзе определяются путь, вес пути, свойства корректности тактирования и микаиальности с-сети St/, Предлагаются алгоритмы анализа корректности тактирования, основная идея которых состоит в установлении для каддой вершили соответствия между реальными весами путей в нее и тактом начала срабатывания, определяемого функцией СбхЯ. Такие представлен алгоритм минимизации числа задержек в с-сети. Даны асимптотические оценки сложности предложенных алгоритмов.
В третьей главе представлены алгоритмы, осуществляющие преобразование стандартных операторных схем (с-схем) произвольной структуры к обогащенных с-схем (с массивами и с процедурами) з абсолютно (в некоторых алгоритмах максимально) асинхронные п-схемы с тегированными фишками.
Введем ряд вспомогательных определений и обозначений.Бер-шнна а с-схемы SS называется
- информационно узловой по переменной -х , если в SS су
ществует несколько вершин 4» / 4п і от которых вершина
а зависит информационно по переменной х Вершина с -квазираспознаватель вершины а. , если с - последний распознаватель из 0С/У%,а)1/ззт) на любом пути в о., где /2>* - транзитивное замыкание отношения логической зависимости.
- логически узловой, если в SS существует несколько
распознавателей %} .« , &m , от которых вершина а, за
висит логически. vc - экран вершины а . Вершина с —
обобщенный распознаватель.вершины а , если с. - послед
ний распознаватель из Я ($^(,0.)1/si$/г?) на любом пути в а.
С-схема 5 S является б—эквивалентной п-схеме DP , ;
если при любых интерпретациях ИЛ-графы любых процессов Ре pCC(SS,J) и Ре PROC(fif,i) совпадают.
Алгоритм ТІ, предназначенный для преобразования ациклической с-схемы SS в потоковый вид, предварительно осуществляет анализ информационно-логических зависимостей б с-схеме и элиминацию логически узловых вершин посредством их расклейки. Ь процессе преобразования'с-схемы происходит последовательный переход от одной вершины к другой, при .атом каждая условная конструкция рассматривается как единая вершина, преобразование которой б потоковую структурированную условную конструкцию осуществляет вспомогательный рекурсивный алгоритм. Какдому преобразователю с-схемы ставится в соответствие операционная вершина п-схемы, каждому распознавателю - условная вершина. При преобразовании информационных зависимостей по переменной Z-i вершины о. с-схеш необходимо установить порт />' в п-схеме такой, что если а- информационно зависит по л\ от вершины ввода с-схемы, то /э* - входной порт п-схемы-, передающий значение переменной х\ ; если о. информационно зависит по Z'; от преобразователя 6 , то />'- выходной порт операционной вершины, соответствующей $ ; если d -информационно узловая по - то />L - выходной порт потоковой условной конструкции с условной вершиной, соответствующей квазираспознавателю вершины О. . Преобразование условной конструкции с распознавателем ґ осуществляется в два приема. Сначала выполняется преобразование вершин и информационных сЕязей таким же образом, как и в основном алгоритме, и только затем - преобразование логических зависимостей. При этом для каждой выходной переменной строятся Т- и F- клапан, имеющие общий выходной порт и управляемые условной Еер-шиной, соответствующей г".
Теорема 3.1. П-схема T-Z(SS) является С -эквивалентной с-схеме SS ациклической структурированной.
Ъ алгоритме Т2 , осуществляющем преобразование ациклической с-схемы >S в потоковый вид, элиминации подлежат только логически узловые распознаватели. Для каждого логически узлового преобразователя о и каждого его экрана d определяется множество p%ia,) = /LD*(a,^)-{ f)(lD*(a,Pi \ {zi. sm } — {СІ ) . где С - обобщенный распознаватель
вертиш а.. При преобразовании вершин с-схеш sr их информационных зависимостей выполняются такие же действия, что и в алгоритме ТІ - Однако для преобразования условных конструкций используется рекурсивный алгоритм, в котором если условная конструкция с распознавателем f, содержат логически узловой преобразователь о. , то при преобразовании его информационных зависимостей по входным переменным дополнительно для каждого распознавателя tf?eERR (о., г.- ) строится соответствукщий клапан. Таким образом, преобразование логических зависимостей в условной конструкции осуществляется при преобразовании логически узловых преобразователей и при завершении построения потоковой конструкции.
Теорема 3.2. П-схема TZ(SS) является 9 -эквивалентной с-схеме SS ациклической бесконфликтной максимально асинхронной в классе ~TISS)J,
Алгоритм ТЗ является развитием алгоритма ТІ на случай' с-схем со структурированными вложенными циклическими конструкциями. При анализе с-схемы и построении л-схемы выполняются действия, аналогичные соответствующим действиям алгоритма ТІ . Дополнительно при преобразовании циклических конструкций применяется рекурсивный алгоритм, который состоит из следующих шагов. Для каждой входной переменной: строятся ntw и nett -вершина, имеющие обший выходной порт, что позволяет различать итерации цикла посредством присваивания нового уникального тега соответствующим входным фишкам. При преобразовании вершин и информационных зависимостей выполняются те же действия, что и в основном алгоритме. Для каадой выходной переменной строятся Т-, F - клапан, o&t -вершина, порты которых связаны дугами таким образом, чтобы обеспечить передачу фишек, предназначенных для слэдущай итерации, и восстановление старого тега для выходных фишек.
Теорема 3.3. П-схема T$(SS) является & -эквивалентной исходной с-схеме SS структурированной.
Алгоритм Т4 осуществляет построение неструктурированной п-схемы с тегироваенымя фишками. При анализе исходной с-схемы, содержащей неструктурированные циклические'конструкции, преобразовании вершин и информационных зависимостей с-схемы. выполняются действия, аналогичные соответст$увдим действиям
алгоритма Т2 . При преобразовании логических зависимостей циклических конструкций генерируемые клапаны соединяются дугами таким образом, чтобы обеспечить бесконфликтность вычислений в потоковых конструкциях.
Теорема 3.4. П-схема T4(SSJ является -эквивалентной исходной с-схеме SS бесконфликтной максимально аспнхрон-аой в классо 'Ї2Р- \ЪР SfqcsS)}.
Алгоритм Т5 является развитием алгоритма ТЗ на случай с-схем с массивами. Исходя из ограничения, налагаемого на структуру исходной с-схемы (для каждого имени массива существует ровно одна вершина кодификации соответствующего индекса), в случае если указанные вершины или вершины модификации элемента массива являются логически условными достаточно осуществить их расклейку и переименование массивов, чтобы предотвратить многократные присваивания одному и тому же элементу массива. Преобразование вершин обработки массивов осуществляет вспомогательный алгоритм, в котором для каздого имени массива строится ct-eaie -вершина, кадцой вершине модификации элемента массива ставится в соответствие append -вершина, а каждой вершине выбора элемента массива - вершина s-e&ei . Преобразование информационных зависимостей для вершин такого типа требует действий, аналогичных соответствующим действия алгоритма ТЗ .
Алгоритм-Т6 предназначается для построения тегированных п-схем с процедурами. Преобразование вершин главной п-схемы и информационно-логических зависимостей осуществляется аналогично алгоритму Т5 . Дополнительно каддой вершине вызова процедур ставится в соответствие вершина арру~. Строгая функциональность и отсутствие побочных эффектов, свойственные ПОТОКОВЫМ вычислениям, требуют явного задания интерфейсов мевду процедурами, поэтому глобальные переменные с-схем процедур при преобразовании представляются в виде параметров. С каждым входным параметром связывается порт из $лігу и new -вершина, а с каждым выходным параметром - порт из &tit и n*tt -вершина. Преобразование вершин с-схемы процедуры осуществляется также, как и верпйн главной с-схемы.
В четвертой главе разработана и реализована экспериментальная система потокового программирования (ЭСПП), предназначвн-
ная для анализа, генерации и моделирования конструкций к,устройств потокового и систолического типа. В состав ЭСПП входят комплекс инструментальных программ (компилятор, анализаторы, конфигуратор, имитатор); экспериментальные языки программирования; системные таблицы, содержащие информацию о конфигурации и характеристиках моделируемых устройств. На входы системы могут поступать последовательные, потоковые, систолические конструкции, представленные на экспериментальных языках программирования.
Компилятор системы осуществляет преобразование последовательных конструкций в код моделируемого потокового процессора. Анализаторы I и П выполняют лексико'-синтаксический разбор и генерацию внутреннего представления потоковых и систолических конструкций. Дополнительно анализатор П осуществляет анализ корректности тактирования и оптимизацию систолических конструкций. Конфигуратор системы позволяет в диалоге настраивать модуль имитации на каздую новую версию моделируемого вычислителя и заполняет системные таблицы. Имитатор системы функционирует в режимах систолических и потоковых вычислений.
Б данной глава предпринята попытка в рамках ЭСШ1 исследовать возможность повышения эффективности потоковой реализации алгоритмов сортировки к некоторых элементарных функций, С этой целью в состав моделируемого процессора включен модуль последовательной обработки (ПО), что приводит к следующим изменениям в организации вычислений. Последовательный программный фрагмент рассматривается как единый вычислительный процесс, для которого достаточно единожды определить условие готовности и ФУ, на которое он будет распределен для исполнения. Следовательно, при выполнении программ с невысокой степенью параллелизма может быть значительно уменьшена нагрузка на СО-модуль, который является узким местом тегированных потоковых ЭВМ. А также при последовательном выполнении итеративных вычислений над структурами данных отпадает необходимость использования вершин модификации тегов и копирования структур данных.
Аналитические исследования показывают, что в моделируемом процессоре могут быть достигнуты ускорения вычислений на 60-7(. Измерения, проведенные в ЭСПП над алгоритмами сорти-
ровки (методы Шелла, пузырька, двухпутевого слияния) и некоторыми элементарными функциями показывают, что нагрузка на ПС-модуль уменьшается на 50-60$, увеличение числа ФУ в П0-модуле не дает заметного роста ускорения вычислений.
В заключении кратко излагаются осноеныо результаты работы.
В приложениях представлены рисунки и таблицы, формальная модель последовательных вычислений, примеры входных текстов и протоколов функционирования ЭСПП.
