Содержание к диссертации
Введение
ГЛАВА I. Вычислительные модели с массивами
1.1 Введение 7
1.2 Требования к представлению алгоритмов . 7
1.3 Основные понятия 13
1.4 Интерпретация ВМ 20
1.5 Классификация ВМ 29
1.6 Синтез асинхронной программы 34
1.7 Заключение 43
ГЛАВА 2. Опал - язык описания параллельных алгоритмов
2.1 Введение 44
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
Литература 15
- Требования к представлению алгоритмов
- Синтез асинхронной программы
- Примеры описания параллельных алгоритмов на языке ОПАЛ
- Конструирование ПИ
Требования к представлению алгоритмов
Первая глава посвящена формальному описанию метода синтеза параллельных программ на основе вычислительных моделей с массивами. Во втором параграфе вводится понятие представления алгоритма .формулируются требования к нему в случае, когда алгоритм необходшло вьшолнять на ШК, обосновьгоается необходимость задавать алгоритм в форме множества термов. Далее определяются понятие ВМ, которое является расширением понятия вычислительной модели посредством введения массивов, предикатов и массовых операций, а также структурная и содержательная интерпретация ВМ. В пятом параграфе выделяются практически важные классы ВМ, доказываются. теоремы о классах представших в них алгоритмов. В шестом параграфе определяется понятие программы, реализующей множество термов, и предлагается алгоритм синтеза асинхронной программы.
Требования к представлению алгоритмов.
Целью параграфа является неформальное обсуждение требований к представлению алгоритма, который необходимо выполнить на ШК, и иллюстрация целесообразности этих требований на примерах. При этом вводится рдц понятий, которые в программировании были известны и ранее и рассматриваются здесь для недвусмысленности изложения. То обстоятельство, что понятия не новы, позволяет использовать в основном содержательные определения.
Пусть А - некоторый алгоритм, вычисляющий частично рекурсивную функцию (ч.р.ф.) -J- . . Алгоритм А может быть изображен многими различными способами. В дальнейшем будут рассматриваться только такие представления алгоритма, в которых в явном віще используются преобразователи значений входных переменных в значении выходных. Каждый преобразователь (будем впредь называть его операцией) ее вычисляет ч.р.ф. J , значение которой получается в результате выполнения операции
Представлением алгоритма И назовем набор V, W) , где ХЧ ,!М,.. . ] - конечное множество переменных; г- "= ( Х, о, с, х s,) _ конечное множество операций, с каждой операцией (X F связаны входной ъ(&.) и выходной ои(ы.) наборы переменных из - управление, т.е. множество ограничений на порядок выполнения операций из г ; л- - функция, задавшая отображение множества X U г в физические устройства МВК, т.е. $. задает распределение ресурсов МВК; V С X - множество входных переменных, \д/ С X - множество выходных переменных алгоритма А . Часть ограничений управления С t определенных информационной зависимостью между операциями, называется потоковым управлением, остальные ограничения С задают пряглое управление, связанное обычно с распределением ресурсов и оптимизацией вычислений. Отображение R- назовем тождественным, если оно ставит в соответствие каждой переменной алгоритма отдельную ячейку памяти, а каждой операции - собственный, ни с кем не разделяемый процессор. Реализацией алгоритма А , при заданных значениях переменных из множества V , представленного в форме S , называется выполнение операций в некотором произвольном допу-с титлом порядке, который не противоречит управлению , при этом; может быть получена некоторая история вычислений, которая называется вычислительным процессом ("28J. Предполагается, что при любой реализации алгоритма А вычисляется функция 4 д . Множество всех вычислительных процессов обозначим PCA,s).
Будем говорить, что алгоритм г\ представлен в параллельной срорме - параллельный алгоритм), если в существует вычислительным процесс, в котором две или более операций выполняются одновременно, в противном случае О есть последовательное представление А .
Аналогично ГІ2,ІЗ"] введем понятие сравнительной непро-цедурности представлений 0А и О алгоритма А . Скажем, что представление о і более непроцедурное, чем Од, » если
Очевидно, что представление $ алгоритма /\ с потоковым управлением С и тождественным распределением ресурсов R является максимально непроцедурным представлением А . Такое представление для краткости будем называть просто непроцедурным.
Синтез асинхронной программы
Приведенные в 4 примеры показывают, что программы, реализующие ( V W) -план / могут быть очень разными по форме. В настоящем параграфе рассматривается алгоритм синтеза асинхронной программы. А-схема [28, 32 ] состоит из конечного множества А-блоков (4ккб/4Д..03}» определенных над информационной М и управляющей Q- памятями, каждый из которых содержит спусковую функцию Tf- ajc) , управляющий оператор . С (QYJ) И операцию сне , 3vc6 F± . А-программа это интерпретированная А-схема [32] , причем каждой опе рации СІК соответствует функция -f-avc -Тсаи ) , кото рую вычисляет в А-программе модуль HooL . Выпол нение А-блока AJC может быть инищшровано в некоторый момент, если /-{йь)- L\ ue, при текущем состоянии памяти MU Сг . Выполнение А-блока Ак состоит в испол - 35 нении ooi(XAt_ с теми входными значениями, которые имеют переменные из ім с мс) в текущий момент, при этом вычисляются значения переменных из оиЛС&ьс-) , и исполнении управляющего оператора CCOLM-) . А-программа считается завершенной, когда ни один блок не выполняется и ни один А-блок не может быть инициирован.
В соответствии:- с определением функции Q&L понятие "А-программа /7 реализует множество термов Т ", l ly , определим так, чтобы П вычисляла функцию именно:
а) пусть г-О-С і ,,, тс ,) у іь(оі) 0; \/ . .. Тогда м .реализует , , если выполнение // состоит только из реализации. вхождения .операции Q, , а реализация вхождения ос,, в свою очередь, состоит из проверки VQwL _ условий для вхождения о и, еолщ они выполнились, испол-. нения.модуля od-cc с входными. переменными bh(Ct) , при исполнении 0с (х, вычисляются значения переменных из ouyt (OL) ... . Если оъА, -условия для ос не выполняются, то переменные из сооЬ(сь) получают значение SL ;
б) пусть І Г9 -йХ-Ьі. ч - -6ь)їіьСб) = ( і- іх» ) ои() = (іі, .,,% «) - Тогда/7 реализует .-1, если /7 сначала реализует =с- = ,.. v , а затем реали зует вхождение операции & ; в) программа / реализует / , если // реализует все термы из т. Таким образом, спусковая функция ih(6) должна, содержать два конъюктивных члена, один .из.которых проверяет VOX- -условия для вхождения ь , а другой проверяет, реализованы ли подтермы ii ..., -Lh
Свойство корректности интерпретации позволяет сущест- і венно упростить это определение. Действительно, так как 1 все термы, вычисляющие переменную ягбЛ 2 , должны вырабатывать одно и то же значение, то при реализации вхождения ь достаточно проверить, что значения всех входных переменных, отличные от -Я- , .вычислены при.реализации каких-то (все равно каких) .подтермов из / . Далее, если в программе.( допускать единственную реализацию каждого вхождения всех используемых в операций, то отпадает необходимость проверять для счетчика х ьїи(ск) , ее -массовая операция, вычислено ли его значение при реализации некоторого вхождения операции из множества Ра). Условие это выполнится в этом.случае автоматически.в. силу свойств выделенных классов ЕМ. Ясно, что и в этом случае., программа будет вычислять функцию IPxL . Итак, спусковая функция где предикат (%ъ ( ) проверяет {їїо -условия для вхождения ъ , fth (4) - готовность аргументов, т.е. вычислены ли отличные от Si значешш всех переменных из реализовалось ранее вхождение о или нет.
Если &к - массовая операция, то выполнение А-блока .. Дк уточняется.. Уточнение связано с определением реали зации всех вхождений ак?, f е А4ис .Итак:
а) значение w- awc) проверяется,для всех невыпол няющих вхождений . Ож. , j б- lvaic (т.е. ooLai L не вы полняется на входных наборах ьиСоск ) ) таких, что Lhfak. )UоиЛ (олс ) не содержит компоненты некоторого массива 7 и при текущем состоянии памяти. Эти наборы определяются с помощью функций Ч .и %к_ . .. Спусковую функцию Ьг(ьк ) с конкретными входными перемен - 37 ными, позволяющими определить возможность реализации (XY?. , обозначим та 6я у . Тот же смысл имеет обозначение сСалс ) .
б) модуль Mod может начать исполняться на всех входных наборах си(аіс! )}д ьЩис , для ко торых истинна спусковая функция & (actc ) ; в) после завершения №оса(с с входными переменными Lh(oikJ) получают значения переменные из ои (ецс. ") , затем выполняется управляющий оператор c(cucd) . Переменные out t Xic.«J , определяются функцией
В дальнейших рассуждениях нигде не используется интерпретация ВМ и конструируется фактически алгоритм синтеза А-схемы, которая при соответствующей интерпретации реализует IK W) -план / . Именно в этом смысле следует далее понимать утверждение, что А-схема реализует
Для конструирования h(aio) и с(ссю) в программе понадобятся специальные средства. Для каждой переменной _Х , используемой в / , в управляющей памяти Сг заводится ячейка q. , в которой хранится значение О ., если значение СС не вычислено ни одним модулем, и значение I, если сС вычислено. Тогда предикат fi fo 4) есть конъюнкция предикатов вида х = 4 , где осе еІУ\ (оыс )
Примеры описания параллельных алгоритмов на языке ОПАЛ
Примеры описания параллельных алгоритмов на языке ОПАЛ В схеме языка оказались недоопределенными ряд понятий, необходимых для задания ВМ, к примеру, выражение, номер-компонента и так далее, что связано с желанием не закрыть, те.или иные возможности уточнения схемы при конкретизации. Поэтому при.записи различных .примеров параллельных алго- . ритмов будут сделаны нужные доопределения, снабженные краткими пояснениями. Входные и выходные переменные алгоритмов в примерах.определяются очевидным образом и явно не указываются, т.е. как .правило,, не указывается tl Wy-план. Символы языка подчеркиваются..,
Рассмотрим алгоритм сложения двух векторов ос ж ч с вещественными компонентами. В нем необходимо, применить операцию плюс ко всем компонентам..о: и У с одинаковыми номерами, чтобы получить соответствующие компоненты результирующего вектора .Для этого необходимо.задать множество номеров компонентов, .векторов х , и , , к которым применима операция плюс. Сложение-векторов операция плюс Элементарный-описатель принимает здесь значения из . множества [ вещ, цел .. J ., а описание вида . Он : массив [ 2 вещ ; определяет массив он , счетчик {х и. операцию ( oc. sku ). ВМ сложение-векторов задает бесконечное множество термов вида iuroc, ou/L (плюс) - WV: ,,., . Номер-компонента и число-компонентов задаются выражением. Предполагается, что тля-операции "плюс" есть имя модуля, вычисляющего функцию I (плюс).
В примере используется способ.задания интерпретации . операщш фрагментом программы, записанной на объектном языке (язык, на котором записывается синтезированная программа). Модули, вычисляющие функции 2($) должны иметь виц:
В примере описан двумерный массив., При доопределении .. предполагалось, что выражение, задающее число-компонентов в описании массива, есть набор (арифметическое-вы-ражение, арис&летическое-выражение), каждое.. арифметиче-скре-выражение определяет величину.соответствующей координаты. Считается кроме того,, что все строки (столб--цы) двумерного массива шлеет одно и то же число компонентов, поэтому для описания структуры массива достаточно двух счетчиков (по одному на каждую координату). Описание ОС : массив [ rn , L«C -i)J вещ ; определяет массив ее , счетчика Joe и. Нос и операции / х := hr ; // ос; s. 9, С т 4-) (присвоение начальных значений счетчикам).. В описании семейства множеств -п L ] для определения множества значений индекса "К " использовано .выражение. Такой способ, описания множеств часто будет использоваться и в дальнейшем вместо эквивалентного ему описания и N]
В предшествующем параграфе, были даны, примеры конкретизации схемы языка, которая здесь будет рассмотрена более детально. Конкретизация языка в первую очередь .состоит в определении средств задания.интерпретации ВМ, доопределении неопределенных символов. Кроме того, ..при.конкретиза- -ции желательно добавление в.язык средств, расширяющих возможности .пользователя при создании ПП, в том числе средств задания дополнительной информации об объектах ВМ для целей последующей оптимизации синтезированной программы...Конкретизация языка зависит, .от многих факторов и в частности .от целей реализации метода,, от класса МВК, на.которых должна выполняться синтезированная программа, от свойств объектного языка (язык, на котором записываются синтезированные программы), от свойств операционной системы и т.д. Поэтому конкретизация языка должна предварять каждую реализацию языка.
Конструирование ПИ
Кроме выделенных типов моделирования можно определить и другие, например, тепловое моделирование, если сопоставить каждой операции функцию, значение которой задает количество выделившегося при выполнении функционального элемента ДС тепла. Необходимые в каждом типе моделирования средства (задание Т , распределение ресурсов и т.д.) должны быть добавлены в ОПАЛ при конкретизации.
Реализация системы автоматизации проектирования ДС (САПР) в виде открывает следующие пути улучшения качества проектируемых ДС . Прежде всего в допускается модификация множеств переменных и операций: посредством расщепления и соединения операций, выделения и соединения подоперации структурированных операций, чему в ДС соответствует модификация ее структуры. Такие модификации делаются по директивам человека либо автоматически в попытках найти оптимальную относительно какого-либо критерия структуру ДС . На улучшение рабочих характеристик САПР (время моделирования, требуемые ресурсы и т.п.) повлияет тот факт, что ССПП для каждой ДС синтезирует свою специальную Ш, реализующую тот или иной тип модели ДС , вместо универсальной программы интерпретирующего типа. В синтезированной ПП уже учтены особенности ШК, его ресурсы используются максимально при выполнении ЇЇП, все изменения в структуре МВК будут также учитываться. Это обеспечивает переносимость САПР без потери производит ельности при разумных ограничениях. Выделение типов моделирования позволит поэтапно отлаживать ИМ, выявляя последовательно логические, временные и ресурсные ошибки, а это ускорит отладку ИГЛ. И наконец, ССШ обеспечивает функциональное проектирование ДС , при котором ДС конструируется из функциональных блоков, внутреннее устройство которых задается при структурной интерпретации. При этом каждому функциональному блоку (структурированной операции ВМ) CL соответствует ВМ Cq_ , определяющая всевозможные алгоритмы вычисления 4 си » из которых при раскрытии а-выбирается с использованием "подсказок" человека лучший.
В главе предлагается проект ССШ как основы приложения метода синтеза ПП на основе ВМ. Приводится общая схема ССПП, выделяющая основные этапы (работы) на пути от формулировки задачи к Ш ее решения. Сформулирована задача трансляции, разработан алгоритм трансляции описания ВМ с линейными областями-применимости, на основе анализа этого алгоритма сформулированы правила записи массовых операций с не линейными областями-применимости, использование которых позволяет автоматически перевести произвольную ВМ в простую. Приводятся алгоритмы планирования и раскрытия структурированных операций, предлагаются методы компиляции ПП. В последнем параграфе рассматривается проект ССШ, ориентированной на автоматизацию проектирования ДС , показывается, как при реализации ССШ учитываются особенности
Сформулируем основные результаты диссертационной работы.
1. Введено понятие ВМ, её содержательной и структурной интерпретации, выделены практически важные классы ВМ. Разработан алгоритм синтеза асинхронной программы.
2. Определен язык ОПАЛ для задания ВМ. Для описания массовых операций в нем введено понятие множества, предусмотрены также средства задания структурной интерпретации ВМ. Выделены два уровня описания языка: схема языка и конкретизация языка. Описана методика конкретизации ОПАЛа, которая позволяет учесть в языке особенности ПО.
3. Разработана общая схема ССШІ, предложен проект ССШІ, ориентированной на автоматизацию производства параллельных пакетов прикладных программ. Для трансляции произвольной ВМ в простую разработан алгоритм имитации планирования. Предложены также алгоритмы планирования, выбора (V}w) -плана и конструирования ПП. Учет особенностей ПО при реализации ССПП показан в проекте ССШ, ориентированной на автоматизацию проектирования ДС .
В совокупности результаты диссертации обеспечивают создание ССПП, в которой пользователю для решения своей задачи необходимо лишь точно её сформулировать, а параллельная программа решения будет конструироваться автоматически либо автоматизированно из. модулей, накопленных в библиотеках каждого из процессоров конкретного ШК. ССПП позволяет в некоторой ПО накапливать в непроцедурной форме фонд, которые могут быть затем выполнены на различных МВК. Такой подход к конструированию ПП значительно повышает уровень языков программирования с сохранением их эффективной реализации и обеспечивает доступ к МВК непрофессиональным пользователям.
