автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Автоматическая разработка и моделирование структур потокового типа

■9 и | 9 0!

V

АКАДЕМИЯ НАУК СССР ОРДЕНА ЛЕНИНА СИБИРСКОЕ ОТДЕЛЕНИЕ ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

ЬИРБИЦКАЙТЕ Ирина Бонавентуровна

УДК 519.681

АВТОМАТИЧЕСКАЯ РАЗРАБОТКА И МОДЕЛИРОВАНИЕ СТРУКТУР ПОТОКОВОГО ТИПА

05.13.II - математическое и программное обеспеченно вычислительных машин, комплексов, систем н сетей

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск 1990

Работа выполнена в Вычислительном центра СО АН СССР.

Научный руководитель: доктор физико-математичаских наук, В.А.Вальковский.

Официальные оппоненты: доктор физико-математических наук,

профессор, А.В.Анисимов

кандидат технических наук С.Г.Седухиа

Ведущая организация: Московский электротехнический институт.

Завита состоится " 24 « _апреля_1990 года в _

часов на заседании специализированного совета Д.002.10.02 при Вычислительном центре СО АН СССР по адресу: 630090, Новосибирск, лр.ак.Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале отделения ГПНТБ СО АН СССР (пр.ак.Лаврентьева, 6).

Автореферат разослан марта 1990 года.

Ученый секретарь специализированного совета к.т.н.

Г.И.Забиняко

Г,:;.:Г' СЯСАЛ ХАРАКТЕРИСТИКА РАБОТЫ

Li! .^.актуальность теш. Потоковая {data j-tow ) организация

Стдишуеяий, позволяющая естественно выражать параллолизм.при-рэкаемым задачам, и вшзлять возможности параллельной обработки яа различных уровнях, является одной ез основополагающих при создании ЭЪМ петого поколения и языков параллельного программирования. Исследования в данной области ведутся в трах основных направлениях: модели потоковых вычислений, языковые средства, потоковые архитектуры.

Среди абстрактных потоковых моделей следует выделить модели с сигналами подтвэрздений и с тегироваяны?.я фишками. Первая модель ограничивает число фишек (максимально по одной) яа дугах потоковых схем (п-схем), что приводят к снижен® степени параллелизма вычислений. Наиболее перспективной представляется модель с тегированными фишкакз, которая предполагает эффективное выполнение массовых параллельных вычислений за счет возможности одновременной: обработки нескольких экземпляров одной и той же воршинн п-схема. Соотношение свойств тегированных п-схем 'с упреждением л их структурной организации требует разработки системы формальных понятий я дополнительного исследования.

К настоящему времени известен ряд аппликативных потоковых языков программирования высокого уровня, которым свойстваняо следующее: строгая функциональность, единственное присваивание, отсутствие побочных эффектов, использование имен значений вместо переменных. Программирование только посредством аппликативных языков хотя и упрощаэт процесс трансляции программных конструкций в потоковый код, однако на способствует использованию накопленного фонда последовательных программ, а также традиционной методологии программирования. Опыт разработки и использования методов преобразования императивных конструкций к потоковому виду показывает, что такие черты традицяоЕшых языков программирования, как глобальные паремен-ные, 6ото -операторы, поэлементное изменение структур данных, пседдоимена требуют наиболее сложной компиляционной техники и необходимы дальнейшие глубокие исследования данной проблемы.

"" На последнее десятилетие приходится пик научных и экспериментальных исследований в области развитая потоковых архитектур. Потоковые принципы обработки информации в той или иной форме положены в основу многих зарубежных и отечественных проектов. Особенно широкое щжмэЕвЕнэ потоковые архитектуры получили а таких областях, как вычислительные задачи, обработка сигналов, искусственный интеллект, логическое программирование. Ддй успешного использования потоковых машин необходимо ранить наряду с другими проблзгяу эффективно! потоковой реализации алгоритмов, предполагающих последовательные вычисления над структурированными данными (поиск, сортировка).

Среди направлений современного развития вычислительных средств таккэ слздует откатить СЕКС-архитектуры, организованные в Ецде систолических катриц. Больной интерес для исследований представляет автоматизация процессов анализа корректности и оптимизации систем такого типа.

Таким образом, из выше сказанного следует актуальность выбранной тематики исследований.

Педью ддсоэртвдяи является разработка системы формальных понятий, методов и средств для анализа, автоматического построения и моделирования-структур потокового типа. Достижение цели связывается о рассмотрением слэдущих вопросов:

1) определение способа нанболеа эффективней на различных уровнях организации потоковых вычислений;

2) введение и обоснование формального аппарата для установления и изучения взаимосвязи мезду наиболее важными свойствами потоковых схем с упреждением и налагаемым структурными ограничениями, а также для анализа систем систолического типа;

3) разработка методов автоматического построения широких классов потоковых схем;

4) создание экспериментальной системы потокового программирования (ЭСШ), поддерживающей процессы анализа,генерации в моделирования потоковых и систолических структур.

Методы исследований. Исследования проведены с использованием элементов теории схем программ и параллельной схемато-логил, теория сложности алгоритмов,организации потоковых и систолических структур. Данные для оценки, параметров произ-

водительности потоковой архитектуры получены с помощью имита- -ционных экспериментов в ЭСПП.

Научная новизна исследования состоит в разработке и применения оригинального комплексного подхода к решению задач формализации, анализа и автоматического построения шроких классов структур потокового твиа. Научную новизну раскрывают сле-дукпще результаты: введена и исследована иерархия формальных моделей, ориентированных как на неструктурированные, так и структурированные классы тогированных п-схем с упредцэяием; определена формальная систолическая модель, разработана алгоритмы анализа и оптимизации систолических структур; предложены и обоснованы методы преобразования стандартных операторных схем произвольной структуры, схем с массивами и процедурами в эквивалентные (в определенном нижа смысла) тегированные п-схемы о высокой степенью асшогронности.

Практическач ценность. Разработанные в диссертации матодн могут.быть положены в основу реальных трансляторов» осуществляющих генерацию потокового машинного кода. Многие предложенные алгоритмы доведен^ до экспериментальных программных реализаций в рамках ЭСПП, что мояат служить непосредственно основой для реальной потоковой системы. Анализ эффективности потоковой реализации алгоритмов сортировки, элементарных функций и полученные с помощью имитатора ЭСШ оценки характеристик производительности могут быть использованы на стадии проектирования при выбора оптимальной конфигурации потоковой архитектуры.

Апробация работы. Основные результаты работы докладывались и обсуждались на У1, УП Всесоюзных иколах-сэминарах "Распараллеливание обработки информации" (Львов, 1987, 1989), Втором региональном семинаре "Распределенная обработка информации" (Новосибирск, 1987), Всесоюзной конференции "Формальные модели параллельных вычислений" (Новосибирск, 1987), УШ семинаре "Однородные вычислительные среды и систолические структуры" . (Львов, 1988), Международной школе-семинарэ "Формальные модели параллельных вычислений" (Телава, 1989),на семинарах ИК АН УССР и КГУ (Киев, 1989), МЭИ (Москва, 1989), ВЦ СО АН СССР (Новосибирск, 1987, 1988, 1989).

Структура диссертации. Диссертация состоит из введения,

четырех глав, заключения, списка литературы и приложений. Объем 132 страниц основного текста, 36 страниц рисунков и таблиц. Список литературы содержат 118 наименований.

КРАТКОЕ СОДЕРЖАНКЕ РАБОТЫ

Ьо введении обосновывается актуальность рассматриваемых вопросов , формулируются цели исследований, представленных в диссертации. Описывается научная новизна результатов, практическая ценность работы. Приводится краткое содержание диссертации по главам.

В первой главе дан аналитический обзор состояния исследований в области архитектур и мелкоблочных ( SLl?e ф^л-) ЭВМ, управляемых потоками данных.

Рассмотрены общие принципы организации машин такого типа. Описаны механизмы, обеспвчивакщие корректные реентерабельные вычисления, - блокирование фишек, сигналы подтверздений, копирование кода, тегирование фишек, очередей. Определены подхода к организации потоковых вычислений над структурами данных. Приведена классификация потоковых ЭВМ, в основу которой положена классификация Вана. В качестве принципов классификации выбраны тип организации процессорного.элемента (ПЭ) и тип • реализуемых взаимодействий шаду ПЭ. Б основополагающую классификацию были внесены некоторые изменения: добавлены ветви, уточняющие механизмы обеспечения реентерабельных вычислений; число приведенных проектов расширено примерно вдвое.

На основа анализа проектов потоковых систем, выполненного в главе, установлено, что динамические тегированные ЭЬМ, в состав которых включена распределенная память I-структур, способны достигать наибольшей производительности вычислений. Поэтому такая организация потоковых вычислений была выбрана в качестве предмета исследований диссертационной работы.

Ьо второй главе вводится и исследуется иерархия формальных моделей тегированных потоковых вычислений. П-схема с тегированными фишками определяется как система 2F -< To&ñs, Tag, Ports, Modes; idg£>> где

Tokens - счетное множество фишек данных, состоящее из подмножеств информационных (Ttoíens ) и управляющих ( Ctoßeas )

филюк. Tag.: TcJens-~-/V» ГД9 ^ - множество натуральных чисел. Считается, что /V разбито на непересекающиеся интервалы целочисленных значений (тегов). Poris - счатноэ множество портов, состоящее из подмножеств информационных {Tports ) и управляющих (CpOrts ) портов. Xrtput , Ouipu-t с- Ports - МНО-яэства входных и выходных портов, соответственно. /Vedes -счетное множество вершив, состоящее из подмножеств операционных ( Oper ), условных ( ConcL ) вершин, клапанов (Gat), вар-шин модификации тегов {Tmod). lidge-, ¡¿p (f/odes) v Output)—«-cop (Modes > и Iпри- i ) , где Lp ('Vedes) и op (Vödes) - множества входных и выходных портов вершин из P/cd es, соответственно.

Интерпретация X п-схемн задается обычным образом. I - множество возможных интерпретаций. Состоянием п-схемы 2>F при интерпретации л называется функция' S , которая сопоставляет:

а) комплекты информационных фишек информационным портам,

б) комплекты управляющих фишек управляющим портам. С кавдым типом вершин связано определенное правило срабатывания, которое представляет собой пару функций <IF,of> таких, что ZF определяет, какие фишки с каких входных портов потребляются, а функция ср - какие множества фишек к каким выходным портам добавляются при срабатывании варшины данного типа.

Срабатывание с тэгом Т вершины У - это пара состояний <S, 5> таких, что: a)V-pe¿p(w) : I. J Ftp) s Sip) (условие готовности к срабатывании) и 2. S'(pi -Sip) -Jfipjj, б) Ypecp(W¡\ s'(pJ и OF (р). ■ s.-za.Sé'iíS) обозначает множество вершин, для которых выполняется условие готовности в состоянии

Историей вычислительного процесса при интерпретации Т называется последовательность состояний < S/p ■ ■ 5,,> таких, что У /i i < ti. : < $t, S¿H > - срабатывание вершины //sK'ades.

Вычислительным процессом при интерпретации X называется последовательность вершин пз Oper и tend, выписанных в том порядке, как она следуют в истории вычислительного процесса. Через МР(Р) обозначил множество вершин, входящих в процесс Р , через ¡Yl(/V,pj - число вхождений вершины Л/ в процесс Р. Если PftOC(J)F, ту - множество вычислительных процессов п-схемн JDfi при интерпретации j , то PR(X(BF)= U(PXCC(2F,I) I I&.I).

Состояние S п-схеш DF называется

- входным, если Yp<= Por-ts -Tnput' 0; - выходным ), если Yp £ Output: Sip) i 0 ; - выходным "очищенным", если VpePoris ~ Output 1 Slp)-0\ - бесконфликтным относительно порта р , если 5(р) не содержит двух и более фишек с идентичным тегом; - бесконфликтным, если ¥p^fbfts'. S - бесконфликтное относительно порта р ; - живым, если is)-Л

£TA7(J)F) и S~lATcut(i)F) обозначают множества всех воз-мошшх состояний и всех выходных состояний n-схемы DF , соответственно.

Процесс Р называется

- В- -эквивалентным процессу Р (P~PJ , если их информационно-логические графы (ШГ-графы) совпадают; - включающий процесс Р'(р'<=р) , если a) tffi(P') Ql А/Р(Р)* бР)'. г/KKP'l HNT(,V,P).

П-схвт 2)F называется -бесконфликтной, если У S а 57A~(DF)\ ¿.-бесконфликтное; -живой, если V 5 е ¿ТА1-$TATCcji (£>Ч: S - живое; - "очищаемой", если У- Se.SJA7mlI>fy. 6 - "очищенное"'; - С -эквивалентной п-схемэ ' (DP , если VJ^X Р gPROClIP, Т) ■Е Р G-PROCCJt', IJ: Р ~ Р' ; - максимально асинхронной в классе [Pf'I DF-'£ DF], если Vlei: ¥-Р е PROCOF,!) в р'е рЯОС (DPj) : p'i=p ; - абсолютно асинхронной в классе {DF'¡Df'-Sdf], если" V р е Proc(DF) и Р'еР$ОсС№')\

й'еР.

Структурированная п-схема с тегированными фишкаии 5DF определяется как ациклически! ориентированный граф, построенный на входных и выходных портах структурированных конструкций из множества Consfrs. Структурированная конструкция - это либо операционная вершина, CSC (условная), (циклическая), JSC (ациклическая) структурированная конструкция. Синтаксис конструкций определяет потоковые вычисления с упреждением3*^.

Теорема 2.1. Структурированная л-ехема SDF является

Amamiya М., Hasegawa R. Dataflow computing and eager and lazy'evaluationsZ/Ne-R Gener. Gomput. - 1985. - Vol. 2, и 2. - p. 105-130.~ .

бесконфликтной живой "очищаемой" и абсолютно асинхронной в классе %DF IDF ~ SDFJ .

Далее определяется п-схема с массивами J3FA как расширение п-схемы за счет: а) добавления счетного мшшэства имен массивов (-Anames ); б) разбиения множества информационных фишек {Ztciens) на непересекающиеся подмножества фишек с именами массивов (Hc¿ens¿ ), с индексными значениями (X£ohnst ), со значениями массивов ( líofañs^ ); в) аналогичного разбиения множества информационных портов (Tports = Tpor-ts„ и IpcAsz uIporisv) < г) ведения в множество вершин подмножества вершин модификации индексных значений {2mcc¿ ) и подмножества вершин обработки массивов, в свою очередь состоящее из непересекающихся подмножеств вершин порождения массива ( CREATE), выбора значения из массива (SEÁ.ECT), модификации значения в массиве {ЯРРЕМй ).

Структурированная п-схема с массивами SDFJ представляет собой расширение п-схемы' SDF за счет добавления к множеству Ccnsífs подмножеств вершин обработки массивов и модификации индексных значений. Дополнительные структурные ограничения состоят в следующем: Vjf <=Jfñai7ie$ : а) существует ровно одна вершина аррелс[£з$ррвф б) существует ровно одна вершина /У Glmod,

Теорема 2.2. Структурированная п-схема с массивами -SВ^Л является бесконфликтной живой "очищаемой" и абсолютно асинхронной в классе

П-схема с процедурами' DFP состоит из главной п-схемы и множества п-схем процедур, с каждой из которых связано некоторое уникальное имя. Главная п-схема представляет собой расширение п-схемы DFJ- за счет введения в множество вершин подмножества вершин вызова процедур {?"PPL У ). П-схема процедуры - это п-схема того же типа, что и главная п-схема.

Структурированная п-схема SDFP _ это структурированная главная п-схема и множество структурированных п-схем процедур, для построения которых используется множество Constas, дополненное вершинами вызова процедур.

Теорема 2.3. Структурированная п-схема с процедурами SPFP является бесконфликтной живой "очищаемой" и абсолютно асинхронной в классе {DFPIBFP &SDFP}t ■

Ь конца главы вводится формальная модель систолических .вычислений. С-сеть определяется как система - < ТоЗе/ц-,

УссдЬЛ, ёс/ре, С/сф, где - счетное

множество однотипных вершин; функция Ъ/еСв№ сопоставляет вершине /V<= !/сс!е$ некоторое целочисленное значение - вес вершины, то есть время ее срабатывания. С каддой дугой, определяемой функцией "б</ое , также связано целочисленное значение - вас дуги. В отличие от асинхронных п-схем в синхронную систему включена функция Сёос-Л .определяющая тожество вершин, срабатывающих на такте где Т - период

тактирования с-сети. Далее определяются путь, вес пути, свойства корректности тактирования и мвк'лшльиости с-сети ¿Ж. Предлагаются алгоритмы анализа корректности тактирования, основная идея которых состоит в установлении для каддой Ьарпш-лы соответствия между реальными весами путей в нее и тактом начала срабатываяЕя, определяемого функцией СеЬс$. . Также представлен алгоритм минимизации числа задержек в с-сети. Даны асимптотические оценки сложности предложенных алгоритмов.

В третьей главе представлены алгоритмы, осуществляющие преобразование стандартных операторных схем (с-схем) произвольной структуры к обогащенных с-схем (с массивами и с процедура,®) з абсолютно (в некоторых алгоритмах максимально) асинхронные п-схеш с тегированными фишками.

Введем ряд вспомогательных определений и обозначений.Вершина а с-схемы называется

- информационно узловой по переменной х , если в 55 существует несколько вершин 4' • • • > 4 . от которых вершина а зависит информационно по переменной х . Вершина с -квазираспознаватель вершины а , если с - последний распознаватель нз а>1/£С* я>) на любом пути в <2, где /2>* - транзитивное замыкание отношения логической зависимости.

- логически узловой, если в существует несколько распознавателей %} • .« } , от которых вершина а, зависит логически. - экран вершины а . Вершина с — обобщенный распознаватель.вершины а , если е. - последний распознаватель из Я ■ на любом пути в а.

С-схема 5 5 является б—эквивалентной п-схеме ОР , '

если при любых интерпретациях ИЛ-графы любых процессов Ре РЯСС^,!) и Ре Р№С(ы,1) совпадают.

Алгоритм Т1, предназначенный для преобразования ациклической с-схеш 55 в потоковый вид, предварительно осуществляет анализ информационно-логических зависимостей б с-схеме и элиминацию логически узловых вершин посредством их расклейки. Ь процессе преобразования с-схемы происходит последовательный переход от одной вершины к другой, при .атом каждая условная конструкция рассматривается как единая вершина, преобразование которой б потоковую структурированную условную конструкцию осуществляет вспомогательный рекурсивный алгоритм. Кавдому преобразователю с-схеш ставится в соответствие операционная вершина п-схемы, каздому распознавателю - условная вершина. Пря преобразовании информационных зависимостей по переменной вершины о. с-схеш необходимо установить порт р"~ в п-схеме такой, что если а- информационно зависит по от вершины ввода с-схемы, то /э* - входной порт п-схемы-, передающий значение переменной х\ ; если о. информационно зависит по от преобразователя 6 , то />'- выходной порт операционной вершины, соответствующей $ ; если ¿г -информационно узловая по то р' - выходной порт потоковой условной конструкции с условной вершиной, соответствующей квазираспознавателю вершины О. . Преобразование условной конструкции с распознавателем Л осуществляется в два приема. Сначала выполняется преобразование вершин и информационных сЕязей таким же образом, как и в основном алгоритме, и только затем - преобразование логических зависимостей. При этом для каждой выходной переменной строятся Т- и Я- клапан, имеющие общий выходной порт и управляемые условной Еер-шиной, соответствующей г'.

Теорема 3.1. П-схема Т4($$) является С -эквивалентной с-схеме ациклической структурированной.

Ь алгоритме Т2 , осуществляющем преобразование ациклической с-схеш ¿5' в потоковый вид, элиминации подлежат только логически узловые распознаватели. Для каждого логически узлового преобразователя о и каждого его экрана £ определяется множество = £)—( П(1д*(а,& |

{! т ) — {Сj ) > где С - обобщенный распознаватель

вершины ■ о.. При преобразовании вершин с-схеш и* их информационных зависимостей выполняются такие же действия, что и в алгоритма Т1 . Однако для преобразования условных конструкций используется рекурсивный алгоритм, в котором если условная конструкция с распознавателем г*/ содержат логически узловой преобразователь о. , то при преобразовании его информационных зависимостей по входным переменным дополнительно для каддого распознавателя РКЦ (а, г- ) строится соответствуюций клапан. Таким образом, преобразование логических зависимостей в условной конструкции осуществляется при преобразовании логически узловых преобразователей и при завершении построения потоковой конструкции.

Теорема 3.2. П-схема TZ(SS) является 9 -эквивалентной с-схеме 55 ациклической бесконфликтной максимально асинхронной в классе \dFlDF~ 72. ($5)},

Алгоритм ТЗ является развитием алгоритма Т1 на случай' с-схем со структурированными вложенными циклическими конструкциями. При анализе с-схемы и построении л-схемы выполняются действия, аналогичные соответствующим действиям алгоритма И . Дополнительно при преобразовании циклических конструкций применяется рекурсивный алгоритм, который состоит из следующих шагов, Ддя каждой входной переменной строятся пе^ и пекй -вершина, имеющие общий выходной порт, что позволяет различать итерации цикла посредством присваивания нового уникального тега соответствующим входным фишкам. При преобразовании вершин и информационных зависимостей выполняются те же действия, что и в основном алгоритме. Для каздой выходной переменной строятся Т-, Р - клапан, -вершина, порты которых связаны дугами таким образом, чтобы обеспечить передачу фишек, предназначенных для следующей итерации, и восстановление старого тега для выходных фишек.

Теорема 3.3. П-схема Т3($5) является & -эквивалентной исходной с-схеме в5 структурированной.

Алгоритм Т4 осуществляет построение неструктурированной п-схемы с тегироваенымя фишками. При анализе исходной с-схемы, содержащей неструктурированные циклические'конструкции, преобразовании вершин и информационных зависимостей с-схемы. выполняются действия, аналогичные соответствующим действиям

алгоритма Т2 . При преобразовании логических зависимостей циклических конструкций генерируемые клапаны соединяются дугами таким образом, чтобы обеспечить бесконфликтность вычислений в потоковых конструкциях.

Теорема 3.4. П-схема является £-эквивалентной

исходной с-схеме 35 бесконфликтной максимально асинхронной в классо I дР .

Алгоритм Т5 является развитием алгоритма ТЗ на случай с-схем с массивами. Исходя из ограничения, налагаемого на структуру исходной с-схеш (для каждого имени массива существует ровно одна вершина кодификации соответствующего индекса), в случае если указанные вершины или вершины модификации элемента массива являются логически условными достаточно осуществить их расклейку и переименование массивов, чтобы предотвратить многократные присваивания одному и тому же элементу массива. Преобразование вершин обработки массивов осуществляет вспомогательный алгоритм, в котором для каждого имени массива строится сг-еа!е -вершина, каждой вершине модификации элемента массива ставится в соответствие аррерс/ -вершина, а каждой вершине выбора элемента массива - вершина .

Преобразование информационных зависимостей для Бврчшя такого типа требует действий, аналогичных соответствующим действия алгоритма ТЗ .

Алгоритм-Тб предназначается для построения тегированных п-схем с процедурами. Преобразование вершин главной п-схемы и информационно-логических зависимостей осуществляется аналогично алгоритму Т5 . Дополнительно каждой вершине вызова процедур ставится в соответствие вершина аррСтрогая функциональность и отсутствие побочных эффектов, свойственные потоковым вычислениям, требуют явного задания интерфейсов между процедурами, поэтому глобальные переменные с-схем процедур при преобразовании представляются в виде параметров. С каждым входным параметром связывается порт из ^»¿гу и пг^ -вершина, а с каждым выходным параметром - порт из ¿£¿1 и п*к{: -вершина. Преобразование вершин с-схемы процедуры осуществляется также, как и вврпйн главной с-схемы.

В четвертой главе разработана и реализована экспериментальная система потокового программирования (ЭСПП), предназначен-

ная для анализа, генерации и моделирования конструкций к,устройств потокового и систолического типа. В состав ЭСПП входят комплекс инструментальных программ (компилятор, анализаторы, конфигуратор, имитатор); экспериментальные языки программирования; системные таблицы, содержащие информацию о конфигурации и характеристиках моделируемых устройств. На входы системы могут поступать последовательные, потоковые, систолические конструкции, представленные на экспериментальных языках программирования.

Компилятор системы осуществляет преобразование последовательных конструкций в код моделируемого потокового процессора. Анализаторы I и П выполняют лексико'-синтаксический разбор и генерацию внутреннего представления потоковых и систолических конструкций. Дополнительно анализатор П осуществляет анализ корректности тактирования и оптимизацию систолических конструкций. Конфигуратор системы позволяет в диалоге настраивать модуль имитации на каждую новую версию моделируемого вычислителя и заполняет системные таблицы. Имитатор системы функционирует в режимах систолических и потоковых вычислений.

В данной глава предпринята попытка в рамках ЭСШ1 исследовать возможность повышения эффективности потоковой реализации алгоритмов сортировки к кокоторых элементарных функций, С этой целью в состав моделируемого процессора включен модуль последовательной обработки (ПО), что приводит к следующим изменениям в организации вычислений. Последовательный програл:-мный фрагмент рассматривается как единый вычислительный процесс, для которого достаточно единожды определить условие готовности и ФУ, на которое он будет распределен для исполнения. Следовательно, при выполнении программ с невысокой степенью параллелизма может быть значительно уменьшена нагрузка на СО-модуль, который является узким местом тегированных потоковых ЭВМ. А также при последовательном выполнении итеративных вычислений над структурами данных отпадает необходимость использования вершин модификации тегов и копирования структур данных.

Аналитические исследования показывают, что в моделируемом процессоре могут быть достигнуты ускорения вычислений на 60-70$. Измерения, проведенные в ЭСПП над алгоритмами сорти-

ровки (методы Шелла, пузырька, двухпутевого слияния) и некото-риг-ш элементарными функциями показывают, что нагрузка на ПС-модуль уменьшается на 50-60$, увеличение числа ФУ в ПО-модуле не дает заметного роста ускорения вычислений.

В заключении кратко излагаются осноеныо результаты работы.

В приложениях представлены рисунки и таблицы, формальная модель последовательных вычислений, примеры входных текстов и протоколов функционирования ЭСПП.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Введена и исследована иерархия формальных моделей потоковых вычислений с тегированными фишками. Формально определены тегированная п-схема, включающая вершины модификации тегов, тегированные обогащенные (с массивами и с процедурами) п-схемы. Сформулированы структурные ограничения для данных классов п-схем. Исследованы такие их свойства, как бесконф-ликтноств, живость, "очшцаемость", абсолютная асинхронность.

2. Разработаны формальная систолическая модель и алгоритмы анализа и оптимизации систем такого типа. Даны асимптотические оценки сложности данных алгоритмов.

3. Предложены и обоснованы алгоритмы преобразования императивных конструкций в адекватные потоковые. А именно, алгоритмы построения тегированных п-схем произвольной структуры, структурированных тегированных п-схем с массивами, структурированных тегированных п-схем с процедурами.

4. Разработана и реализована экспериментальная система потокового программирования (ЭСПП), предназначенная для анализа, генерации'и моделирования конструкций и устройств потокового

и систолического типа (общий объем 4 тыс. ПЛ-строк). С помощью инструментальных средств ЭСПП исследована возможность повышения эффективности потоковой реализации некоторых алгоритмов сортировки и элементарных функций. Получены оценки характеристик производительности и загруженности оборудования потокового процессора при подключении специального модуля последовательной обработки.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Вальковский В.А., Вирбицкайте И.Б. Об одной системе моделирования потоковых конетрукц,Ей//Мэтоды параллельного и теоретического программирования. - Новосибирск, 1987. -с.63-71.

2. Вальковский В.А.; Вирбщкайте И.Б. Анализ и моделирование потоковых структур//Распараллеливание обработки информации: Тр./У1 Всесоюз. школы-сешнара, Львов, май 1987. -Львов, 1987. - с.18-19.

3. Вальковский В.А.. Вирбицкайте И.Б. Об экспериментальной системе проектирования программных конструкций и устройств потокового типа//Распределенная обработка информации: Тр./ Второй региональный семинар, Новосибирск, июль 1987. - Новосибирск, 1987. - с.31.

4. Вирбицкайте И.Б. О программной реализации системы имита-. циенного моделирования потоковых Бычислений//Распаралле-ливанде обработки информации: Тр./У1 Всесоюз. школы-семинара, Львов, май 1987. - Львов, 1987. - с.20.

5. Вирбицкайте И.Б. 0 преобразовании схем программ в потоковые ыодели//Высокопроизводительные вычислительные системы и их программное обеспечение. - Новосибирск, 1987. -с.115-129.

6. Вирбицкайте И.Б. Рекурсивный алгоритм конструирования потоковых схем//Теория и методы параллельной обработки информации. - Новосибирск, 1988. - с.65-82.

7. Вирбицкайте И.Б. Комплекс программ для экспериментов над потоковыми вычислениями/Архитектура и программное обеспечение многопроцессорных вычислительных комплексов. - Новосибирск, 1989. - с.105-116.

8. Вирбицкайте И.Б. ЭВМ, управляемые потоками данных. - Новосибирск, 1989. - 59 с. - (Препринт/АН СССР. Сиб.отд-ние, ВЦ, 822)

9. Вирбицкайте И.Б. Потоковые вычисления над структурированными данными. - Львов, 1989. с.9-13. - (Препринт/АН УССР, ИМИ, № 239).

10. Вирбицкайте И.Б. Обработка последовательных фрагментов на устройствах потокового типа//Распараллеливание обработки

информации: Тр./Л1 Всвсоюз. школы-семинара, Львов, октябрь 1989. - Львов, 1989. - с.75.

II, Virbitakaite I.B. Towards formalization of data flow schemata with colored tokens//Msthocls of Theoretical and Experimental Computer Science. - Novosibirsk, 1989. - P. 142-157-