Синтез параллельных программ на вычислительных моделях с массивами тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I. ВЫЧИСЛИТЕЛЬНЫЕ МОДЕЛИ С МАССИВАМИ

§ I.I Введение.

§ 1.2 Требования к представлению алгоритмов

§ 1.3 Основные понятия

§ 1.4 Интерпретация ВМ.

§ 1.5 Классификация ВМ

§ 1.6 Синтез асинхронной программы.

§ 2.2 Схема языка.45

§ 2.3 Примеры описания параллельных алгоритмов на языке ОПАЛ.55

§ 2.4 Конкретизация схемы языка .62

§ 2.5 Заключение . *.67 ГЛАВА 3. СИСТЕМА СИНТЕЗА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ НА ОСНОВЕ ВЫЧИСЛИТЕЛЬНЫХ МОДЕЛЕЙ С МАССИВАМИ

§ 3.1 Введение. .68

§ 3.2 Общая схема ССПП.68

§ 3.3 Алгоритмы трансляции.78

§ 3.4 Конструирование ПП.102

§ 3.5 Автоматизация проектирования дискретных систем . . 128

§ 3.6 Заключение.134

ВЫВОДЫ.135

ЛИТЕРАТУРА.136

ВВЕДЕНИЕ

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

Решение проблем массового программирования для МВК с произвольной архитектурой и конфигурацией возможно на пути значительного повышения уровня языков программирования при условии их эффективной реализации, создания средств автоматического либо автоматизированного конструирования программ и развития средств поддержи модульного программирования. Таким образом можно будет решить вопросы как повышения эффективности программирования и программ, так и обеспечения доступа к МВК непрофессиональным пользователям. Заметим, что непрофессиональным пользователем в данном контексте может оказаться квалифицированный программнот-математик, не знакомый с высокоэффективными параллельными алгоритмами в некоторой "смежной" ПО. Для такого пользователя наилучшей, по-видимому, системой программирования является система, в которой решение задачи заканчивается её точной формулировкой, т.е., пользователь должен уметь поставить задачу с требуемой степенью детализации, но не обязан зна^ть, как её решать. На построение тленно таких систем и ориентированы разработанные к настоящему времени методы синтеза программ [3,4,8,35,47-49,55,56,57,60] , однако только метод синтеза программ на основе вычислительных моделей доведен до практического использования и реализован в системе ПРИЗ . Как и все методы. , метод синтеза программ на основе вычислительных моделей основан на формализованном описании ПО. Знания об алгоритмах в ПО хранятся в виде множества готовых к выполнению модулей и способов их правильного использования и из них по заданию пользователя конструируются необходимые программы. Такой подход позволяет накапливать фонд реализованных алгоритмов для конкретного вычислителя и активно использовать его при программировании для МВК. Если учесть, что существующие методы программирования и распараллеливания программ [i,7,28,30,31,34j позволяют для любого конкретного процессора создавать качественные модули, то понятно, что метод синтеза программ на основе вычислительных моделей позволяет сделать следующий шаг на пути к системе автоматического синтеза параллельных программ (ПП).

Однако для целей синтеза ПП средств вычислительных моделей оказалось недостаточно, в первую очередь, из-за невозможности задавать "массовое" применение операций. Это приводит К тому, что, во-первых, все "массовые" вычисления приходится делать внутри модуля, а значит размер модуля не может быть сделан меньше некоторого предела (под размером модуля здесь понимается значение функционала, оценивающего качество программы и, в частности, модуля). Так как основное время решения многих задач приходится на "массовые" вычисления, то для уменьшения времени выполнения программы на МВК необходимо распараллеливание таких мо,нулей, что не всегда может быть сделано автоматически. Во-вторых, модуль, предназначенный ,для'кассового" применения, не может быть непосредственно включен в вычислительную модель, его обязательно надо включать в объемлющий модуль, который и должен содержать "массовое" вычисление. В-третьих, невозможность уменьшения размера модуля может создать трудности при распределении ресурсов МВК. И, в-четвертых, так как в вычислительных моделях определены только простые (не структурированные) переменные, то невозможно организовать конвейерное выполнение алгоритма, при котором, к примеру, вычисленное значение компонента массива немедленно используется в дальнейших вычислениях. Эти обстоятельства и обусловили необходимость в дальнейшем развитии названного метода.

Основной целью диссертационной работы является разработка метода синтеза ПП на основе вычислительных моделей с массивами (ВМ). Метод включает определение ВМ, в которые включены средства задания "массовых" вычислении, язык ОПМ для задания ВМ, алгоритмы синтеза Ш на основе ВМ, а также методику его приложений в различных ПО. Результаты диссертации в совокупности позволяют создавать проблемно-ориентированные системы синтеза параллельных программ (ССПП), в форме которых предлагается реализовать метод.

Содержание диссертации опубликовано в работах 0-12,22, 23,37-42| основные результаты получены в 1979-1984 г.г. в ВЦ СО АН СССР и докладывались на Всесоюзных конференциях в

Новосибирске, Киеве, Риге, Кишиневе, Львове, а также на научных семинарах ВЦ СО АН СССР и ИМ СО АН СССР (Новосибирск:), МЭИ и ИЛУ АН СССР (Москва), ИК АН УССР (Киев) и ИК АН ЭССР (Таллин).

- 7

ВЫВОДЫ

Сформулируем основные результаты диссертационной работы.

1. Введено понятие ВМ, её содержательной и структурной интерпретации, выделены практически важные классы ВМ. Разработан алгоритм синтеза асинхронной программы.

2. Определен язык ОПАЛ для задания ВМ. Для описания массовых операций в нем введено понятие множества, предусмотрены также средства задания структурной интерпретации ВМ. Выделены дга уровня описания языка: схема языка и конкретизация языка. Описана методика конкретизации ОПАЛа, которая позволяет учесть в языке особенности ПО.

3. Разработана общая схема ССПП, предложен проект ССПП, ориентированной на автоматизацию производства параллельных пакетов прикладных программ. Для трансляции произвольной ВМ в простую разработан алгоритм имитации планирования. Предложены также алгоритмы планирования, выбора (V}w) -плана и конструирования ПП. Учет особенностей ПО при реализации ССПП показан в цроекте ССПП, ориентированной на автоматизацию проектирования ДС .

В совокупности результаты диссертации обеспечивают создание ССПП, в которой пользователю для решения своей задачи необходимо лишь точно её сформулировать, а параллельная программа решения будет конструироваться автоматически либо автоматизированно из. модулей, накопленных в библиотеках каждого из процессоров конкретного МВК. ССПП позволяет в некоторой ПО накапливать в непроцедурной форме фонд ПП, которые могут быть затем выполнены на различных МВК. Такой подход к конструированию ПП значительно повышает уровень языков программирования с сохранением их эффективной реализации и обеспечивает доступ к МВК непрофессиональным пользователям.

3.6. Заключение

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

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

2. Альфа-система автоматизации программирования. Г.И.Бабецкий, М.М.Бежанова, Ю.И.Волошин и др. Новосибирск.: Наука, Сиб. отд-ние, 1967, - 308 с.

3. Барздинь Я.М. Один подход к проблеме индуктивного вывода. -В кн.: Применение методов математической логики: Тез. докл. Шконф., Таллин, 1977, с. 16-28.

4. Барздинь Я.М. Некоторые правила индуктивного вывода и их применение. В кн.: Семиотика и информатика. Вып. 19. - М.: ВИНИТИ, 1982, с.59-89.

5. Барбан А.П. Разработка и исследование алгоритмов блочного распараллеливания и диспетчеризации структурированных программ. Автореф. дис. на соиск. учен, степени канд. физ.-мат. наук (05.13.II). -М., ИПУ, 1983. 18 с.

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

7. Быстров А.В., Дудоров Н.Н., Котов В.Е. 0 базовом языке. В кн.: Языки и системы программирования. Новосибирск, 1979, с.85-106.

8. Вальковокий В.А. 0 синтезе оптимальных программ на вычислительных моделях. Программирование, 1980, Ж>, с.27-36.

9. Вальковокий В.А. 0 синтезе надежных вычислений на вычислительных моделях. В кн.: Теоретические вопросы параллельного программирования и многопроцессорные ЭВМ. Новосибирск, 1983,с.76-90.

10. Вальковский В.А., Малышкин В.Э. О синтезе надежных программ в системе ПРИЗ. В кн.:.Трансляция и модели программ.' Новосибирск, 1980, с.119-128.

11. Вальковский В.А., Малышкин В.Э. Диалоговая система автоматизированного синтеза программ на основе вычислительных моделей. -В кн.: Интерактивные системы, I книга: Тез.докл. второй республиканской школы-семинара. Тбилиси.: Мецниереба, 1980,с.102-104.

12. Вальковский В.А., Малышкин В.Э. К уточнению понятия непроцедурное ти языков программирования. Кибернетика, 1981, J53, с.55.

13. Вольдман Г.Ш., Задыхайло И.Б. Некоторые соображения об определении степени непроцедурности языков программирования: Препринт J®I. М., 1977. - 28с. - В надзаг.: ШЕЛ АН СССР.

14. Глушков В.М., Капитонова Ю.В., Летичевский А.А. Теоретические основы проектирования дискретных систем. Кибернетика, 1977,т, с.5-20.

15. Глушков В.М., Капитонова Ю.В., Летичевский А.А. Автоматизация проектирования вычислительных машин. Киев.: Наукова думка, 1975, - 232 с.

16. Глушков В.М., Цейтлин Г.Е., Ющенко Ю.Л. Многоуровневое структурное проектирование программ: формализация метода-сфера приложений. Кибернетика, 1981, JS4, с.42-65.

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

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

19. Гэри М., Джонсон Д. Вычислительные машины и трудноразрешаемые задачи. М.: Мир, 1982. - 416с.

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

21. Ершов Л.П. Вычислимость в произвольных областях и базисах. -Семиотика и информатика. М.:. .ВИНИТИ., 1982, вып. 19, с.3-58.

22. Засыпкин А.В., Малышкин В.Э., Параллельное планирование вычислении на вычислительных моделях. В кн.: Методы и программы решения оптимизационных задач на графах и сетях. Тез.докл.

23. П Всесоюзного совещания. Новосибирск, 1982, с.73-75.

24. Засыпкин А.В., Малышкин В.Э. Параллельный алгоритм планирования вычисления на вычислительных моделях. В кн.: Многопроцессорные вычислительные системы и их математическое обеспечение. Новосибирск, 1982, с.51-58.

25. Кахро М.И., Мяннисалу М.А., Саая Ю.П., Тйугу Э.Х. Система программирования ПРИЗ. Программирование, 1976, И, с.38-46.

26. Кахро М.И., Калья А.П., Тыуту Э.Х. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). М.: Финансы и статистика, 1981. - 158 с.

27. Кербель В.Г. Вопросы мультиобработки и параллельного программирования на однородных вычислительных системах. Автореф.дис. на соиск.учен.степени канд. физ.-мат. наук (05.13.13). Новосибирск, ИМ СО АН СССР, 1979. - 17 с.

28. Кербель В.Г. Реализация экспериментального распараллеливателя алгоритмов. В кн.: Математическое обеспечение вычислительных систем. Вычислительные системы. Вып.78, Новосибирск, 1979, с.54-69.

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

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

31. Котов В.Е. Параллельное программирование с типами управления. -Кибернетика, 1979, J&2, с.1-13.31.- Котов В.Е. О параллельных языках. Кибернетика, 1980, ЖЗ, . с.1-12; М, с.1-10.

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

33. Кутепов В.П., Кораблин 10.П. Язык граф-схем параллельных алгоритмов. Программирование, 1978, Н, с.

34. Кутепов В.П. Функциональные схемы и параллельные вычисления. Автореф. дис.на соиск. учен, степени доктора техн. наук (05.13.13). М., МЭИ, 198I, - 40 с.

35. Лавров С.С. Синтез программ. Кибернетика, 1982, J£6, c.II-16.

36. Лельчук Т.И., Марчук А.Г. ПОЛЯР язык параллельного асинхронного программирования. - Программирование, 1983, М, с.59-68.

37. Малышкин В.Э. Синтез параллельных программ на структурированных вычислительных моделях. В кн.: Синтез, тестирование, верификация и отладка программ: Тез.докл. Всесоюзной конференции, Рига, 1981, с.149.

38. Малышкин В.Э. Имитационное моделирование дискретных систем на основе вычислительных моделей. В кн.: Параллельные вычислительные и программные системы. Новосибирск, 1981, с.68-80.

39. Малышкин В.Э. Представление алгоритмов в вычислительных моделях с массивами. В кн.: Параллельное программирование и высокопроизводительные системы, часть 2: Тез. докл. Всесоюзной школы-семинара, Киев.: Наукова думка, 1982, с.46-49.

40. Малышкин В.Э. Система синтеза параллельных программ на.основе вычислительных моделей с массивами; Препринт 1S505, -Новосибирск, 1984. с.44. - В надзаг.: ВЦ СО АН СССР.

41. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1965, - с.392.

42. Марчук Г.И., Котов В.Е. Модульная асинхронная развиваемая система: Препринты J£ 86,87. Новосибирск, 1978. - 99 с. -В надзаг.: ВЦ СО АН СССР.

43. Миренков Н.Н. Алгоритмы планирования для диспетчера однородной вычислительной системы. В кн.: Вычислительные системы. Вып. 42, Новосибирск, 1970, с.34-46.

44. Мяннисалу М.А., Тыуту Э.Х., Унт М.И., фуксман А. Л. Язык УТОПИСТ. Алгоритмы и организация решения экономических задач. М., 1977, вып.10, с.80-118.

45. Непейвода Н.Н. О построении правильных программ. Вопросы кибернетики, М., 1976, вып.46, с.88-122.

46. Непейвода Н.Н., Свириденко Д.И. Программирование с логической точки зрения: Препринт .£ T-I. Новосибирск, 1981. - 50 с. -В надзаг.: ИМ СО АН СССР.

47. Непейвода Н.Н., Свириденко Д.И. Логическая точка зрения на программирование: Препринт Т-2. Новосибирск, 1981. - 48 с. - В надзаг.: ИГЛ СО АН СССР.

48. Плакс Т.П. Синтез параллельных программ на вычислительных моделях. Программирование, 1977, М, с.55-63.

49. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Советское радио, 1972, 280 с.

50. Рябов Г.Г., Лакшин Г.Л. Поэлементное моделирование вычислительных систем: Препринт М8. М.; 1978. - 90 с. - В надзаг.: ДОМ и ВТ АН СССР.- 141

51. Теория расписании и вычислительные системы. Под ред. Э.Г.Кофемана. - М.: Наука, 1984. - 336 с.

52. Тиц П.Г. Организация параллельных вычислений на многомашинных (многопроцессорных вычислительных системах.Автореф.дне. на соиск.учен.степени канд.тех.наук (05.1Ъ.1ъ ). М., МЭИ, 1975.

53. Тыугу Э.Х. Решение задач на вычислительных моделях. Журн. вычисл.математики и мат.физики, 1970, т.10, ЖЗ, с.38-46.

54. Тыугу Э.Х. Решатель вычислительных задач. Журн.вычисл. математики и мат.физики, 1971, т.II, М, с.992-1004.

55. Barzdin J.M. On inductive syntesis of programs. In: Lecture Notes in Computer Science, 1979, v.122, p. 234-254.

56. Coffman E.G., Garey H.R., Jonson D.S. Dynamic tin packing. -- SIAIJ J. Comput., 1983, v. 12, IT 2, p. 227-258.

57. Kafura D.G., Shen V.Y. Task sheduling on a multiprocessor system with independent memories. SIAM J. Comput., v. 6, IT 1, 1977, p. 167-187.

58. Manna Z., Waldinger R. Synthesis: dreams ^programs. IEEE Transactions on Software Engineering, 1979, v. SE-5, IT 4, p. 294-398.