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

• Автор: Малышкин, Виктор Эммануилович
• Шифр специальности: 01.01.10
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Новосибирск
• Количество страниц: 142 c. : ил

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

§1.1 Введение

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

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

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

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

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

§ 1.7 Заключение

ГЛАВА 2. ОПАЛ - ЯЗЫК ОПИСАНИЯ ПАРАЛЛЕЛШЫХ АЛГОРИТМОВ

§ 2.1 Введение

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

§ 2.3 Примеры описания параллельных алгоритмов на
языке ОПАЛ
§ 2.4 Конкретизация схемы языка
§ 2.5 Заключение
* ГЛАВА 3. СИСТЕМА СИНТЕЗА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ НА ОСНОВЕ ВЫЧИСЛИТЕЛШЫХ МОДЕЛЕЙ О МАССИВАМИ
§ 3.1 Введение
§ 3.2 Общая схема СОПЛ
§ 3.3 Алгоритмы трансляции
§ 3.4 Конструирование ПП
§ 3.5 Автоматизация проектирования дискретных систем
§ 3.6 Заключение
ВЫВОДЫ
ЛИТЕРАТУРА

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

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

простая-переменная :: тт! . •
переменная-с-шздексом ::
имя1 [ номер-компонента ] ;
<—• , I
Крайний справа идентификатор в имя1 определен в опи-сании-переменной-с-ицдексом. !
подстановка-операции :: имя-операции / — (раскрытие-операции)
.—— и 1 , и«* I—(
раскрытиечоперавди ::
. .план-вычислений [ подстановка-операции^ .. ^ план-вычислений :: ..
^на объект.вычислить, список-переменных-1хз список-переменных-!
Первый список-переме.нных-1. определяет, множество выходных, а второй - входных переменных. План-вычислении, задает структурную интерпретацию операции, входные и выходные переменные плана-вычислений и операции соответствуют друг другу в порядке перечисления., список-переменных-1 -: переменная-1 ,
переменная-1 :: ( переменная 1 С имя-массива ]
имя-массива идентификатор ...
Идентификатор в.имя-массива должен совпадать с идентификатором в описание-переменной-с-индексом.
об лас т ь-применимости :: Г описание-шдекс ов С
( .описание-набора-индексов }
описание-индексов :: индекс £- множество
индекс :: идентификатор
Индекс - это вспомогательная переменная,, пробегающая
значения из множества,, заданного в описании индекса,
будет использоваться для указания элементов множества
и элементов семейства множеств. Индекс тлеет смысл