malyshkin_ve_korneev_vd_-_parallelnoe_programmirovanie_multikompyuterov

7.1.4.Генерация параллельных программ

После того как построен оптимальный по одному из критериев план P, требуется составить реализующую его программу (более точно, схему программы, так как интерпретация не задана). Рассмотрим три типа таких программ,

предписывающих параллельную обработку данных в соответствии с порядком, определяемым термами плана Р.

Первый тип - самая простая программа - представляет собой совокупность параллельных присваиваний переменным v i W вырабатывающих их термов плана Р.

Построение такой программы возможно в случае, если каждая операция, участвующая в термах t i , имеет ровно одну выходную переменную и после срабатывания “ обладает значением этой переменной”. Само собой разумеется, что запись (7.2) должна быть синтаксически правильна для языка,

в котором записана программа.

Например, для плана Р={a(t,g(x,t)), d(x,t,g(x,t))}

реализующая его программа типа (7.2) будет иметь вид

y:= a(t, g(x, t));

= .

v: d(x, t, g(x, t));

268

Второй тип программы - последовательно-параллельное задание вычисления с помощью операторов ветвления и слияния: fork, join. Считаем, что пара таких операторов задает автономное параллельное вычисление участков (ветвей),

лежащих между fork и join и разделенных запятой. Таким образом, все переменные локализованы в своих ветвях. Этот тип программ строится для операций общего вида, без ограничений на множество выходных переменных.

Пусть Р={t 1 , t 2 , ..., t k }. Тогда синтезированная программа имеет вид

В этих обозначениях а выполняется после выполнения всех ветвей S(ti), которые вычисляют входные переменные операции а.

Для завершенности предполагаем, что для х V, S(x)=ввод(х), где

“ ввод” - оператор, генерирующий значение переменной х.

269

Программа S(P) имеет структуру, подобную структуре терма.

Так, для рассмотренного примера - плана Р - имеем программу:

S(P)=fork S(a(t,g(x,t))), S(d(x,t,g(x,t))) join=

fork fork ввод(t), fork ввод(x), ввод(t)join; g join; a, fork

ввод(x),

ввод(t) fork ввод(x), ввод(t)join; g join; g join.

Третий тип - в качестве объектной программы взята асинхронная программа (A-схема), задающая вычисление с помощью спусковых функций. А-схема S, реализующая (V,W)-

план Р, строится следующим образом. Пусть P - множество всех подтермов множества P, не являющихся переменными из V.

Введем для каждого t P \P и x out(t) ячейку информационной

памяти x t , а в информационную память для x V W - ячейку с

тем же обозначением х. В качестве множества операций возьмем

out(a)=(y1,...,yn), то in(at)=( x1t1 ,..., xmtm ). Если t P, то out(at)=out(t),

если t P, то out(at)=( y1t ,..., ynt ). В управляющую память для

каждого at введем управляющую переменную a t , для каждого

270

7.2.Алгоритмы синтеза параллельных программ

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

(ССПП). Описанию базовых алгоритмов, необходимых для создания такой ССПП, посвящен этот параграф.

7.2.1.Общая схема синтеза параллельной программы

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

естественно, модифицироваться.

272

Рис.7.11.

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

определяющий множества входных V и выходных W переменных задачи.

Рассмотрим пример описания ПО геометрия и формулировки

273

задачи. Прежде всего описывается ПО геометрия.

Пусть геом: (треугольник: (х, у, z, a, s: real;

операция f1 in х, у, z out а;

операция f2 in х, у, s out а; );

окружность: (r, s: real;

операция f3 in r out s; ); );

Это описание (очень неполное) транслируется и заносится в библиотеку моделей геом. В ней появляются ПВМ (понятие)

треугольник (рис. 7.12), в которой геометрический объект

треугольник характеризуется длинами трех сторон х, у, z,

величиной угла а и площадью s (представлены в ПВМ одноименными переменными), а также операциями f1 и f2 для вычисления угла а.

f1

y

f2

s

Треугольник

Рис. 7.12.

Понятие окружность (рис. 7.13) определяется радиусом r

и площадью s, операция f3 вычисляет площадь s из радиуса r.

274

Понятно, что степень детальности описания каждой ПО зависит от задач, которые необходимо решать.

S

f3

T

окружность

Рис. 7.13.

Данное описание ПО геом позволяет сформулировать такую задачу: даны треугольник tr с известными длинами двух сторон и окружность k с радиусом r. Требуется определить угол а в треугольнике tr, если площади tr и k равны. Условие задачи описывается в ССПП как ПВМ:

Пусть задача: (tr : треугольник х=х0, у=y0; k: окружность r=r0, s=tr.s;);

на задача вычислить tr.а из k.r, tr.x, tr.y;.

275

Графическое представление ПВМ задача показано на рис. 7.14, состоит она из двух понятий: tr и k. Понятие tr строится с помощью понятия треугольник. Отличие состоит в том, что понятие треугольник определяет множество всех треугольников,

а понятие tr - множество всех треугольников, длина стороны х у

которых равна х0, а стороны y — y0 (в примере х0, y0 и r0 —

вещественные константы). Понятие k определяет окружность радиуса r0 и, кроме того, конструкция k.s=tr.s показывает, что переменная s в понятии tr и переменная s в понятии k должны быть отождествлены, т.е., площади круга и треугольника в задаче равны в корректной интерпретации.

f1

f2

f3

Задача

Рис. 7.14.

Оператор постановки задачи (конструкция на задача вычислить

276

tr.а из k.r, tr.х, tr.у) указывает, что дано (V={k.r, tr.х, tr.у}) и что требуется вычислить W={tr.а} на ПВМ задача.

Формулировка задачи (т.е. ПВМ и оператор постановки задачи) поступает на вход транслятора. При трансляции решаются следующие задачи:

-проверка синтаксической правильности формулировки задачи;

-формирование описания ПВМ в том внутреннем представлении, которое необходимо планировщику.

Первая задача традиционна, а вторая заключается в преобразовании ПВМ из текстового представления во внутреннее, табличное. Необходимые для решения этих задач алгоритмы достаточно очевидны.

Внутреннее представление ПВМ С=(X,F) состоит из двух таблиц: ТХ и OП. Каждая строка таблицы ТХ имеет вид

(х,А(х),соmр(x)), а таблицы ОП - (a,in(a),out(a)), где х X, а F,

А(х)={а F|х in(a)}, comp(x)={a F|х out(a)}.

Таким образом, каждая строка ТХ содержит описание всех дуг, входящих и выходящих в/из переменной х (в графическом представлении С), а каждая строка ОП — описание всех дуг входящих и выходящих в/из операции а. Структура понятий ПВМ в таблицах не сохраняется.

Задача планирования заключается в построении множества

TVW не избыточных термов. Конечность множества TVW

277