Помощь в учёбе, очень быстро...
Работаем вместе до победы

Синтез параллельных программ на вычислительных моделях с массивами

Диссертация: Синтез параллельных программ на вычислительных моделях с массивами
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • ГЛАВА 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: dreamsprograms. IEEE Transactions on Software Engineering, 1979, v. SE-5, IT 4, p. 294−398.
Заполнить форму текущей работой

Пора сдавать?