автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Методы проектирования подсистемы обработки проблемно-ориентированных систем потока данных

ВВЕДЕНИЕ

I. ИСПОЛЬЗОВАНИЕ АСИНХРОННЫХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

В ПРО БЛЕМНО ОРИЕНТИРОВАННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

1.1. Модели асинхронных параллельных вычислений

1.2. Базовая структура проблемно-ориентированных систем потока данных

1.3. Алгебраические методы исследования моделей, асинхронных параллельных вычислений

1.4. Постановка задач исследования

ВЫВОДЫ.

II. АЛГЕБРЫ СХЕМ ПОТОКА ДАННЫХ.

2.1. Базовая алгебра обобщенных схем потока данных

2.2. Алгоритм построения регулярной.формулы.СПД. в базовой алгебре

2.3. Акторная алгебра невзвешенных схем потока данных

2.4. Склейковая алгебра.невзвешенных схем. потока данных

2.5. Алгебра взвешенных,схем потока,данных

ВЫВОДЫ.*

III. ЭКВИВАЛЕНТНЫЕ. ПРЕОБРАЗОВАНИЯ СХЕМ ПОТОКА ДАННЫХ

3.1. Тождественные преобразования.формул схем потока данных.

3.2. Гомоморфные отображения & -формул.и & -формул схем потока данных

3.3. Эквивалентные преобразования,схем потока.данных . . 165 ВЫВОДЫ.

17. МЕТОДИКА ПРОЕКТИРОВАНИЯ ШШШО^ШШШРОВШШ СИСТЕМ ПОТОКА ДАННЫХ

4.1. Этапы проектирования подсистемы обработки проблемно-ориентированных систем потока данных

4.2. Этапы проектирования подсистемы управления проблемно-ориентированных систем.потока данных,

ВЫВОДЫ

В В Е Д Е Н И Е Одним из перспективннх направлений развития средств вычислительной техники является создание новых высокопроизводительных ЭВМ и систем с асинхронным способом реализации параллельных вычислений. Данное направление, связанное с развитием ЭВМ с нетрадиционной структурой и архитектурой /53/, сформировалось как альтернативное направлению, связанному с разработкой, улучшением и усовершенствованием ЭВМ и систем, основанных на архитектурных принципах построения ЭВМ, предложенных Да. фон Нейманом, которое развивается на протяжении последних тридцати с лишним лет и носит в основном эволюционный характер. Один из подходов к созданию ЭВМ и систем с нетрадиционной архитектурой состоит в разработке ЭВМ, реализующих потоковые модели параллельных вычислений, такие, например, как схемы потока данных Дж.Б.Денниса {data ными сети Дейвиса daia 40, 52, 59, 76, 92/: Идея управления ходом вычислений с помощью потока данных была предложена давно /26/, однако интерес к созданию реальных ЭВМ и систем, основанных на потоковых моделях, появился сравнительно недавно и с каждым годом все более увеличивается /54, 56, 78, 90, 96/. Потоковый принцип управления позволяет в максимальной степени выявить и реализовать естественный параллелизм, присущий решаемой задаче, поэтому требует создания вычислительной системы, структура которой в максимальной степени адекватна временным и структурным особенностям алгоритма задачи, представленного в форме потоковой модели /80/. Это требование предполагает построение вычислительных потоковых систем с большим числом f£ocu dHin schemes neicoofis) управляемые дани др. I 3, 26, 30, процессоров. Появление шкропроцессоров и других БИС в качестве мощной, гибкой и относительно дешевой элементной базы создало реальные возможности построения потоковых систем. В настоящее время в этом направлении ведутся интенсивные исследования в нашей стране /6-9, 13-21, 23, 32, 37, 38, 46-50, 56, 59, 61, 62/ и за рубежом /54, 78/. Наибольший вклад в разработку теории потоковых вычислений и в создании проектов потоковых языков и машин внесла группа Дж.Б.Денниса из Массачусеттского технологического института /73, 79/. Потоковые машины и системы объявлены одними из наиболее перспективных для разработки ЭВМ пятого поколения в национальной программе по вычислительной технике в Японии /54, 100/; создание потоковых ЭВМ и систем отмечалось как новое направление в развитии средств вычислительной техники на европейских международных конференциях /54, 96/. Принципиальное отличие машин потока данных от обычных ЭВМ заключается в следующем. Програглмы классической ЭВМ организованы линейно: команды программы упорядочены в памяти ЭВМ в соответствии с порядком предшествования команд, задаваемым управляющим графом алгоритма, и выбираются для выполнения с помощью счетчика команд, содержимое которого инкрементируется после выполнения очередной команды. Изменение порядка выполнения производится с помощью специальных команд условного и безусловного переходов. В отличие от указанного порядка выполнения, который реализуется в виде последовательного потока управления, организация вычислений в машинах потока данных предполагает, что команды выбираются для выполнения, как только получены их операнды, что необходимо фиксировать специальными средствами. Таким образом, команды могут быть расположены в памяти потоковой машины в произвольном порядке, наличие счетчика команд не обязательно /77, 93/. Следствием такой организации вычислений является одновременное выполнение нескольких команд потоковой программы. Упрощение задания и верификации программ, ориентация на мультимикропроцессорные и мультимикромашинные системы, эффективность работы в реальном масштабе времени эти особенности потоковых машин вызывают большой интерес /56/. Основное требование к системам потока данных, которое заключается в адекватности структуры системы структурным и временным характеристикам алгоритмов решаемых задач, предполагает создание эффективных средств представления, исследования и оптимизации структурных и временных характеристик алгоритма, представленного в форме той или иной модели параллельных программ. В связи с этим большое прикладное значение имеет использование алгебраических методов, которые широко используются при решении задач, связанных с распараллеливанием вычислительных алгоритмов, созданием языков параллельного программирования, исследованием моделей параллельных вычислений и созданием параллельных вычислительных систем. Глубокое развитие алгебраические методы получили в работах по параллельному программированию и параллельным вычислительным системам, проводимых в Вычислительном центре и Институте математики СО АН СССР I 14, 30, 31, 39-45, 50-52, 62/, Институте кибернетики им.В.М.Глушкова АН УССР /6-9, 23-25, 63/, и других работах. Настоящая работа посвящена исследованию вопросов проектирования проблемно-ориентированных систем потока данных и является логическим цродолжением исследований в области разработки высокопроизводительных проблемно-ориентированных вычислительных систем, проводимых на кафедре Вычислительной техники ЛЭТИ им.В.И.Ульянова

(Ленина) под научным руководством заслуженного деятеля науки и техники РСФСР, доктора технических наук, профессора В.Б.Смолова. Целъто работы является разработка методов проектирования проблемно-ориентированных систем потока данных, которые могут служить основой создания автоматизированной системы проектирования проблемно-ориентированных систем потока данных. С этой целью в работе решались следующие основные задачи: разработка основ методики проектирования проблемно-ориен- тированных систем потока данных; анализ моделей параллельных программ, методов их представления и средств исследования и оптимизации; разработка эффективных методов представления и средств исследования и оптимизации схем потока данных. В диссертационной работе использовались методы теории схем программ, теории множеств и отношений, элементы теорий универсальных алгебр, полугрупп, векторных пространств, методы сетевого планирования и управления, теории графов; в работе сочетаются формальный и содержательный подходы. Научная новизна проводимых исследований состоит в том, что: предложены алгебры схем потока данных, позволяющие представлять в текстовой форме схемы потока данных, проводить исследования их структурных и временных характеристик, а также осуществлять их оптимизацию с помощью алгебраических методов; предложена система эквивалентных преобразований схем потока данных, отличающаяся тем, что она позволяет улучшать структурные и временные характеристики схемы потока данных алгоритма, реализуемого в проблемно-ориентированной системе потока данных (ПОС ПД); 8 предложена методика проектирования ПОС ПД, базовая структура которых подобна структуре компьютера потока данных Дж.Б.Денниса, отличающаяся тем, что она основана на анализе представленной в текстовой форме СПД алгоритма, рассматриваемой как информационный граф, а также на использовании результатов анализа для построения структуры ПОС ЦЦ, соответствующей структурным и временным характеристикам схемы потока данных алгоритма. Практическая ценность полученных результатов заключается в следующем: предложенные алгебры схем потока данных позволяют представлять СПД в текстовой форме и проводить анализ и оптимизацию схем потока данных с использованием алгебраических методов, а также могут быть положены в основу автоматизированного анализа и оптимизации программ потока данных; предложенные эквивалентные преобразования схем потока данных позволяют улучшать временные и структурные характеристики схем потока данных с целью сокращения затрат памяти на хранение программы потока данных, приведения СПД к некоторому стандартному виду, а также уменьшения длительности реализации программы потока данных в ПОС ПД; предложенная методика проектирования позволяет выбирать структуру ПОС ПД наиболее адекватную временным и структурным характеристикам схемы потока данных алгоритма, который будет реали-. зован в проектируемой системе, Диссертационная работа состоит из четырех глав и двух приложений. В первой главе рассмотрены модели асинхронных параллельных вычислений, в частности схемы потока данных (СПД), которые могут 9 служить основой асинхронного способа организации параллельного вычислительного процесса в высокопроизводительных ПОС ПД; описана базовая структура потоковой вычислительной системы; проведен анализ алгебраических методов представления и средств исследования и оптимизации параллельных программ. Во второй главе произведено построение альтернативных акторных и склейковых алгебр невзвешенных обобщенных и обыкновенных схем потока данных; сформулированы основные теоремы о возможности представления СПД в виде формул в построенных алгебрах; разработаны алгоритмы построения минимальных алгебраических формул СЦЦ по матричному представлению схем; предложены акторные и склейковые алгебры взвешенных схем потока данных. В третьей главе построены тождественные преобразования формул СПД; предложено гомоморфное отображение акторной и склейковой алгебр невзвешенных СПД, которое может быть положено в основу создания трансляторов формул СПД; предложены эквивалентные преобразования схем потока данных, представленных в текстовом (формульном) виде; рассмотрены условия целесообразности проведения различных эквивалентных преобразований СПД, В четвертой главе сформулированы этапы проектирования подсистем обработки и управления, которые составляют методику проектирования ПОС ПД; предложены методы решения вопросов, возникающих на отдельных этапах проектирования. В приложения включены доказательства теорем и лемм, сформулированных в диссертации; описан пример проектирования подсистемы обработки специализированной системы потока данных для цифровой обработки сигналов.I. ИСПОЛЬЗОВАШЕ АСИЕХРОННЫХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В ПРОБШЛНО-ОРИЕНТИРОВАННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТШШС В данной главе рассматриваются модели асинхронных параллель ных вычислений, которые могут быть положены в основу организации вычислительного процесса в высокопроизводительных проблемно-ориентированных вычислительных системах; описывается базовая структура потоковой вычислительной системы, подобная компьютеру потока данных Дж.Б.Денниса; анализируются алгебраические методы представления и средства исследования и оптимизации параллельных программ, I.I. Модели асинхронных параллельных вычислений В данном

Результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

- Ш-й Всесоюзной научно-технической школе-совещании молодых ученых и специалистов "Совершенствование устройств и методов приема, обработки и передачи информации", Ростов-Ярославский, апрель 1982 г.,

- ХХУ-й областной научно-технической конференции, посвященной Дню радио, Новосибирск, апрель 1982 г.,

- научно-технической конференции "Методы и средства обработки информации в системах управления", Киев, декабрь 1982 г.,

- республиканской научно-технической конференции "Применение вычислительной техники и электронного моделирования в народном хозяйстве", Хмельницкий, ноябрь 1982 г.,

- 1У-й Всесоюзной школе-семинаре "Распараллеливание обработки информации", Верховина, апрель 1983 г.,

- научно-технических конференциях профессорско-преподавательского состава ЛЭТИ им.В.И.Ульянова (Ленина), 1981, 1982, 1983 годы.

По материалам диссертационной работы имеется 5 публикаций.

Можно указать следующие возможные направления дальнейших исследований:

1. В части работы, касающейся проектирования проблемно-ориентированных систем потока данных:

- автоматизация анализа СЦЦ, представленных в алгебраической форме;

- автоматизация процедуры определения количества элементов обработки каждого типа при проектировании подсистемы обработки ПОС ЦЦ;

- имитационное моделирование различных вариантов структур ПОС ЦЦ, а также конкретных потоковых вычислительных систем, предназначенных, например, для полунатурного моделирования сложных динамических объектов, цифровой обработки сигналов в реальном масштабе времени;

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

2. В части работы, связанной с алгебраическим представлением схем потока данных:

- построение полной системы тождеств предложенной алгебры и доказательство полноты системы;

- автоматизация выполнения тождественных преобразований формул схем потока данных;

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

3. В части работы, связанной с оптимизирующими алгебраическими эквивалентными преобразованиями схем потока данных:

- расширение системы оптимизирующих алгебраических эквивалентных преобразований СЦЦ;

- автоматизация проведения эквивалентных алгебраических преобразований схем потока данных.

- 229 -ЗАКЛЮЧЕНИЕ

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

1. Предложена методика проектирования проблемно-ориентированных систем потока данных (ПОС ЦЦ), базовая структура которых подобна структуре компьютера потока данных, предложенного

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

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

2. Предложены акторные алгебры невзвешенных схем потока данных и CL -взвешенных схем потока данных (СЦЦ), позволяющие представлять схемы в алгебраической текстовой форме, определять временные и структурные характеристики схем, а также проводить эквивалентные преобразования СЦЦ с целью их оптимизации или приведения к некоторому стандартному виду; показана возможность построения альтернативных склейковых алгебр невзвешенных и £ -взвешенных схем потока данных; предложены алгоритмы построения минимальных & и S -формул схем потока данных в акторной и склейковой алгебрах, соответственно; предложено гомоморфное отображение склейковых и акторных алгебр, позволяющее транслировать CL -формулы СГЩ в 6 -формулы и наоборот.

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

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

1. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под ред. В.Е.Котова и И.Мик-лошко. - М.: Наука, 1982. - 336 с.

2. Анишев П.А. Редуцируемость сетей Петри. Программирование, 1982, № 4, с.36-43.

3. Апериодические автоматы / Под ред. В.И.Варшавского. М.: Наука, 1976.

4. Артамонов Г.Т; Анализ производительности ЦВМ методики теории массового обслуживания. М.: Энергия, 1972. - 175 с.

5. Барский А.Б. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980. - 192 с.

6. Борисенко В.И. Алгоритм построения схемы потока данных. Кибернетика, 1978, № 6, с.46-52.

7. Борисенко В.И. Трансляция схем программ в схемы потока данных / ИК АН УССР. Киев, 1979. - (Препринт № 79-42). - 41 с.

8. Борисенко В.И. О трансляции последовательных схем программ в схемы потока данных. Кибернетика, 1980, № 4, с.41-47.

9. Борисенко В.И. Эквивалентные преобразования схем потока данных / Ж АН УССР. Киев, 1981; - (Препринт № 81-24). - 48 с.

10. Варшавский В.И., Мараховский В,Б., Песчанский В.А., Розен-блюм Л.Я. Асинхронные процессы. Изв. АН СССР; Техническая кибернетика, 1980, № 4, с.137-142; № 5, с.138-143.

11. Визинг В.Г. Некоторые нерешенные задачи в теории графов. -Успехи математических наук, т.ХХШ, вып.6(144), 1968, с.117--134.

12. Ван дер Варден Б. Алгебра. М.: Наука, 1979.

13. Вишневский Ю.А., Котов Е.Е., Марчук А.Г. Проблема создания модульной асинхронной развиваемой системы (МАРС). В кн.: Многопроцессорные вычислительные структуры. - Таганрог: ТРТИ, 1981, вып.З (ХП), с.15-17.

14. Власов В.В., Крайников А.В. Алгебраическое представление схем потока данных. Л.: ЛЭТИ, 1983. - 25 с. - (Рук. деп. в ВИНИТИ, № 4258).

15. Водяхо АШ., Легалов А.И. Особенности архитектуры и структуры специализированных процессоров потока данных. В кн.:1У Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов и сообщений. Часть Ш. Львов, 1983, с.160.

16. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980. - 519 с.

17. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983. - 272 с.

18. Глушков В.М., Анисимов А.В. Преобразователи Черча-Россера. -Кибернетика, 1978, $ 6, с.46-52.

19. Глушков В.М., Цейтлин Г.Е., Кщенко Е.Л. Алгебра. Языки. Программирование. Киев: Наук, думка, 1978. - 318 с.

20. Глушков В.М., Цейтлин Г.Е., Юценко Е.Л. Методы символьной мультиобработки. Киев: Наук, думка, 1980. - 242 с.

21. Деннис Дж.Б., Фоссин Дж.Б., Линдерман Дж.П. Схемы потока данных. В кн.: Теоретическое программирование. Часть 2. Труды симпозиума. Новосибирск: ВЦ СО АН СССР, 1972, с;7-43.

22. Дийкстра Э. Взаимодействие последовательных процессов. В кн.: Языки программирования. - М.: Мир., 1972, с.9-86.

23. Дубров Я.А. Алгебраические свойства временных характеристик распараллеливания. В кн.: 1У Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов и сообщений. - Львов, 1983, с.47^48.

24. Дубров Я.А. Метод взвешенных графов в распараллеливании обработки информации. В кн.: 1У Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов и сообщений. - Львов, 1983, с.49-50.

25. Ершов А.П. Современное состояние теории схем программ. Проблемы кибернетики, 1973, вып.27, с.87-110.

26. Ершов А.П. Введение в теоретическое программирование. М.: Наука, 1977, 228 с.

27. Зуховицкий С.И., Радчик И.А. Математические методы сетевого планирования. М.: Наука, 1965. - 296 с.

28. Зыков А.А. Теория конечных графов. Новосибирск: Наука, 1969. - 543 с.

29. Карп P.M., Миллер Р.Е. Параллельные схемы программ. В кн.: Кибернетический сборник (новая серия). М.: Мир, 1975,вып.13, с.5-61.

30. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979. - 438 с.

31. Колумбай С.К., Шумейко В.М. Применение потокового метода синхронизации при распараллеливании по циклам. В кн.: Многопроцессорные вычислительные структуры. - Таганрог: ТРТИ, 1981, вып. 3(ХП), с.59-63.

32. Колумбай С.К. Схемы параллельных потоков управления и методы их реализации на основе параллельных процессоров и мультипроцессоров. Харьков: ХИРЭ, 1982. - 117 с. - (Рук. деп. в ВИНИТИ № 6189).

33. Котов В.Е., Нариньяни А.С. Асинхронные вычислительные процессы над памятью. Кибернетика, 1966, № 3, с.64-71.

34. Котов В.Е. Введение в теорию схем программ. Новосибирск: 1978. - 256 с.

35. Котов В.Е. Алгебра регулярных сетей Петри / ВЦ СО АН СССР. -Новосибирск, 1978. (Препринт № 98). - 33 с.

36. Котов В.Е. Алгебра регулярных сетей Петри. Кибернетика, 1980, J* 5, с.10-18.

37. Котов В.Е. О практической реализации асинхронных параллельных вычислений. В кн.: Системное и теоретическое программирование / ВЦ СО АН СССР. - Новосибирск, 1972, с.ИО-125.

38. Котов В.Е. Теория параллельного программирования. Прикладные аспекты. Кибернетика, 1974, № I, с.1-16; № 2, с.1-18.

39. Котов В.Е. Параллельное программирование с типами управления. Кибернетика, 1979, № 3, с.1-13.

40. Легалов А.И. Организация высокопроизводительных спецпроцес-copoBi Изв.ЛЭТИ. Науч. тр. / Ленингр.электротехн. ин-тим.В.И.Ульянова (Ленина), 1983, вып.324. Организация и проектирование вычислительных структур на БИС, с.6-9.

41. Легалов А.И. Организация управления вычислениями в процессорах потоков данных: Автореф. дис. . канд.техн. наук. Ленинград, ЛЭТИ, 1983, 14 с.

42. Легалов А.И. Организация управления вычислениями в процессорах потока данных: Диссерт. . канд.техн.наук. Ленинград, ЛЭТИ, 1983,

43. Марчук Г.И., Котов В.Е. Модульная асинхронная развиваемая система / ВЦ СО АН СССР. Новосибирск, 1978. - (Препринт № 86, № 87).

44. Методы параллельного микропрограммирования / Под ред.О.Л.Ван-дман. Новосибирск: Наука, 1981. - 178 с.

45. Нариньяни А.С. Теория параллельного программирования. Формальные модели. Кибернетика, 1974, № 3, с.1-15; № 5, с.1-14.

46. Оре 0. Теория графов. М.: Наука, 1980. - 336 с.

47. Параллельная обработка (обзор) Электроника,1983, т.56, !£ 12, с. 25-39.

48. Подловченко Р.И. Моделирование программ схемами и построение систем преобразований схем. Кибернетика, 1982, № 6,с.23—29.

49. Прангишвили И.В., Стецюра Г.Г. Современное состояние проблемы создания ЭВМ с нетрадиционной структурой и архитектурой, управляемых потоком данных. Измерения, контроль, автоматизация, 1981, № 1(35), с.36-48.

50. Розенблюм Л.Я. Сети Петри. Изв.АН СССР. Техническая кибернетика, 1983, № 5.

51. Специализированные ЦВМ /Смолов В.Б., Барашенков В.В., Бай-ков В.Д. и др.; Под ред.В.Б.Смолова М.: Высш.школа, 1981. - 279 с.

52. Строева Т.М., Фальк В.Н. Асинхронные вычислительные сети: ABC-модель и ABC-система параллельного программирования. -Кибернетика, 1981, № 3, с.90-96.

53. Танкелевич Р.Л. Моделирующие микропроцессорные системы. М.: Энергия, 1979. - 120 с.

54. Хохловский В.Н. Исследование методов организации вычислительного процесса в микро-ЭВМ с вычислительными средами: Автореф. дис. . канд.техн.наук. Ленинград, ЛЭТИ, 1981. 18 с.

55. Элементы параллельного программирования /В.А.Вальковский, В.Е.Котов, А.Г.Марчук, Н.Н.Миренков; Под ред.В.Е.Котова. -М.: Радио и связь, 1983. 240 с.

56. Ющенко Е.Л., Цейтлин Г.Е. Многоуровневый синтез структурированных программ. Кибернетика, 1982, № 5, с.11-21.,

57. Янов Ю.И. 0 логических схемах алгоритмов. В кн.: Проблемы кибернетики. - М.: Физматгиз, 1958,вып.I, с.75-127.

58. Arvind, K.P. Gostelow. A computer capable of exchanging processors for time. In: Information Processing 77, North-Holland Publ. Co., Amsterdam, 1977, P- 849-853.

59. Barton R.S., Davis A.L. System and method for concurrent and pipeline processing employing a data driven network. US Patent, No 3.978.452, August, 31, 1976.

60. Backus J. Can programming be liberated from the von Neumann style ? A functional style and algebra of programs. -Communications of ACM, 1978, v. 21, No 8, p. 613-641.

61. Baudet G.M., Brent R.P., Kung H.T. Parallel execution of tests on a asynchronous multiprocessor. Australian Computer

62. Journal, 1980, v. 12, No 3, p. 105-112.

63. Bic L. A protection model and its implementation in a data flow system. Communications of ACM, 1982, v. 25, No 9, p. 650-658.

64. Computation structures group. In: Laboratory for computer science progress report 17. Massachussetts Institute of Technology for computer science progress report, 1979-1980, No 17, p. 19-35.

65. Davis A.L. The architecture and system method of DDM1; A recursively structured data driven machine. In: Proc. Fifth Symp. Computer Architecture, New York, 1978, p. 210-215.

66. Dennis J.В., Misunas D.P. Data processing apparatus for highly parallel execution of stored programs. US Patent G 06

67. F 3/oo, 15/00, G 06 К 17/00, No 5962706, June, 8, 1976.

68. De Franchesco N., Vaglini G., Vannechi M. Implementation of parallel computation schemata. In: Proc. Second EUROMICRO Symp. Microprocess. and Microprogramm., Venice, 1976. -North- Holland Publ. Сотр., Amsterdam, 1977, P- 157-163.

69. Dhas R.C. Estimation of instrinsic parallelism in high level programs using data flow execution. In: COMPCON Fall 80: 21st IEEE Comput. Soc. Int. Conf. : Distrib. Comput.

70. New York, 1980, p. 313-320.

71. Dhas R.C. A ring-based data-Flow multiprocessor. In: COMPCON Spring 82: 24th IEEE Comput. Soc. Int. Conf., San-Francisco,

72. Calif., Eebr. 22-25, 1982, Dig. Pap. New York. 1982, p. 218-223.

73. Estrin G., Turn R. Automatic Assignment of computation in a variable structure computer system. IEEE Trans, on Electronic Computers, 1963, v. 12, No 6, p. 755-773.

74. Hoare C.A.R. An Axiomatic basis for computing programming.-Communs. ACM, 1969, v. 12, p. 576-580.

75. Jaffe J.M. The use of queues in the parallel data flow evaluation of "if-then-while" programs. MIT, Lab. Comput. Sci., 1978. - 12 p . (Techn. Memo. No 104).

76. Jaffe J.M. The equivalence of R.E. programs and data-flow schemes. MIT, Lab. Comput. Sci., 1979 - 35 P- (Techn. Memo.1. No 121).

77. Jaffe J.M. Parallel computation : synchronization, scheduling and schemes. MIT, Lab. Comput. Sci., 1979- - 264 p. (Techn. Memo. Rept. No 231).

78. Johnson D. Data-flow machines threaten the program counter. -Electronic Design, 1980, v. 22, November, p. 255-258.

79. Kasai J., Miller R.E. Homomorfism between models of parallel computation. Journal of Computer and System Sciences, 1982, v. 25, p. 285-331.

80. Miller R.E., Kassai J. Comparing models of parallel computation- 243 by homomorfisms. In: COMPSAC 79. Proc. LEEE Comput. Soc.'s Third Int. Comput. Software and Appl. Conf., Chicago, 111.,1979, p. 794-799.

81. Misunas D.P. A computer architecture for the data-flow computation. MIT, Lab. Comput. Sci., 1975 - 107 p. (Techn. Memo. No 100).

82. Organick E.I. New directions in computer systems architecture.- Proc.: EUROMICRO Symp. Microprocess. and Microprogramm.: Large Scale Integration. North-Holland Publ. Co., Amsterdam, 1978, p. 6-8.

83. Rosen B.K. A lubricant for data flow analysis. SIAM J. Comput., 1982, v. 11, No 5, p. 495-511.

84. Schindler M. New architectures keep pace with throughputneeds.- Electronic Design, 1981, May, No 14, p. 97-Ю6.

85. Simmons G.H. TDMP: a data-flow processor. In: Proc. IEEE Int. Conf. Circuits and Computers, ICCC 808 Port Chester N.Y., 1980 - New York, 1980, p. 757-741.

86. Suzuki Jatsuo, Kurihara Ken, Janaka Hidehiko, Moto-oka Johru. Procedure level data flow processing on dynamic structure multiprocessor. J. Information Processing, 1982, v. 5, No 1, p. 11-16.