malyshkin_ve_korneev_vd_-_parallelnoe_programmirovanie_multikompyuterov

переменных алгоритма, а также потоковое управление. Это просто языки выражений.

Языки программирования единственного присваивания

(single assignment) не имеют таких средств распределения памяти,

которые бы позволили присвоить разные значения одной переменной. В них нет средств для задания вычислений типа x:=x+1 (напомним, что этот оператор присваивания размещает значения двух разных переменных алгоритма в одной переменной программы). Это присваивание записывается только в виде xi+1:=xi+1. Программа в языках единственного присваивания, не обремененная информацией о распределении ресурсов, гораздо легче поддается формальному анализу.

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

компиляторе/интерпретаторе необходимо применять некоторую стратегию использования участков памяти, ранее занятых одними переменными, которые уже выполнили свою роль и более не будут востребованы в программе, для размещения значений других переменных, т.е. выполнять распределение ресурсов.

Важная стратегия состоит в нахождении такого порядка выполнения операций, при котором выработанные значения переменных как можно быстрее потребляются другими

58

операциями и далее не требуется, допуская повторное использование ячеек памяти. При ручном программировании программист обычно делает это довольно эффективно и часто почти не задумываясь.

Языки, в которых дополнительно к функциональным средствам есть ещё и средства для задания прямого управления и распределения ресурсов, называются процедурными языками.

Существует целый спектр языков разной степени непроцедурности от императивных языков типа С с жестким прямым управлением, допускающем единственную реализацию,

до максимально непроцедурных (собственно уже функциональных) языков.

2.2.Требования к представлению параллельного алгоритма.

Примеры показывают, что к представлению S алгоритма A

для последующей реализации предъявляются противоречивые

требования.

Содной стороны, необходима непроцедурность S, так как она уменьшает зависимость S от свойств конкретного мультикомпьютера, позволяет качественно реализовать алгоритм на различных мультикомпьютерах, а значит, есть возможность накапливать программный фонд для них.

Сдругой стороны, есть потребность в таком уменьшении непроцедурности S, при котором в множестве P(A,S) остаются лишь оптимальные относительно некоторого критерия

59

реализации, так что уменьшение непроцедурности S будет способствовать улучшению рабочих характеристик программы

(уменьшатся затраты на реализацию управления, которые имеют тенденцию стремиться к 100%).

Противоречие может быть разрешено, если конструирование параллельной программы решения задачи проводить в два этапа:

1).Вывод (конструирование) алгоритма решения задачи и его непроцедурное представление. Таким базисным представлением алгоритма в параллельном программировании является множество функциональных термов.

2).Конструирование по непроцедурному представлению алгоритма и описанию мультикомпьютера прямого управления и распределения ресурсов такой степени непроцедурности, которая позволит эффективно реализовать алгоритм на этом именно мультикомпьютере. Конструирование заключается в «свертке» множества функциональных термов в желаемую конечную программу, с должными управлением и распределением ресурсов.

При этом в программном фонде хранятся алгоритмы,

представленные в непроцедурной форме, которая перед выполнением алгоритма на конкретном мультикомпьютере с конкретными входными данными дополняется соответствующим прямым управлением и не тождественным распределением

60

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

В такой общей постановке задача конструирования эффективной параллельной программы (конструирования C и M)

в целом не имеет приемлемого решения, хотя к настоящему времени разработано много алгоритмов конструирования M (M-

алгоритмов). Слишком велико оказалось разнообразие различных типов и структур алгоритмов и оборудования.

Какую систему параллельного программирования (СПП)

хотелось быть иметь для мультикомпьютеров? Прежде всего,

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

например С, в который необходимо добавить непроцедурные средства представления A таким образом, чтобы усилия пользователя и СПП взаимно дополняли бы друг друга в попытках организовать эффективные параллельные вычислений.

Термин ‘’ эффективный’’ используется, конечно,

неформально. Он может пониматься, например, так, что выгоды от использования мультикомпьютера компенсируют прикладному пользователю затраты на разработку параллельной программы, а потери производительности мультикомпьютера от

61

использования СПП высокого уровня оказываются приемлемыми за счет повышения производительности труда программистов.

Задача отображения алгоритма A на ресурсы мультикомпьютера может решаться статически, до начала вычислений. В этом случае все принятые решения по распределению вычислительных ресурсов, в первую очередь процессоров, фиксируются в тексте программы.

Такой подход, однако, неприемлем во многих случаях.

Так, мультикомпьютер может иметь много ресурсов и далеко не каждая программа все их использует. Следовательно,

вычислительные ресурсы мультикомпьютера надо разделять динамически, т.е. реализовать мультипрограммирование на вычислительных ресурсах мультикомпьютера.

В этом случае, M-алгоритм должен состоять их двух частей: статической, которая реализуется в трансляторе и производит распределение той части ресурсов мультикомпьютера, которая может быть отведена программе до начала вычислений (часть оперативной памяти, регистры и т.п.),

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

62

2.3. Простейшая программа, реализующая алгоритм

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

Пусть алгоритм А задан конечным множеством термов {t1, t2,…, t n}, в термах используются переменные {x1, x2, …, x m} и

операции {a1, a2, …, a k,}. Значения всех входных переменных известны, значения остальных вырабатываются операциями алгоритма. Все переменные xi, i=1,2,…,m , объявляются глобальными. Обозначим Ti имя процедуры, реализующей терм ti. Тогда искомая программа выглядит так (процедуры Ti могут выполняться в любом порядке):

var x1, x2, …, x m; var y1, y2, …, y n:=0; var z1, z2, …, z k:=0;

fork

if y1 = 0 then (call T1; y1 := 1); if y2 = 0 then (call T2; y2 := 1);

. . . . . .

if yn = 0 then (call Tn; yn := 1);

n - управляющие переменные, которые инициируются значением 0. Каждой процедуре Tj соответствует управляющая переменная yj, j=1,2, …, n.

63

Каждой процедуре ai сопоставляется управляющая переменная zi, i=1,2, …, k, нулевое значение которой означает,

что операция ai еще не выполнялась. Предикат Pin(ak) принимает значение True (истина), если значения всех входных переменных

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

2.4.Сравнительная непроцедурность языков программирования.

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

Прежде всего отметим, что одной и той же конструкции языка, определенного некоторой грамматикой, можно сопоставлять разные правила реализации, т.е. задавать для нее разные операционные семантики.

Наоборот, для разных конструкций языка могут быть определены правила исполнения, порождающие одно и то же множество реализаций.

64

И в третьих, при сравнении языков с разными правилами порождения языковых конструкций и с разными правилами их реализации следует исходить из некоторого соответствия между

конструкциями языка. Уточним теперь эти три концепции.

Пусть L - язык программирования, для которого заданы две операционные семантики S1 и S2, определенные как множества реализаций Si(k), i=1,2, где k L - конструкция языка

L. Операционная семантика определяет, собственно, возможные реализации конструкций языка. Именно операционная семантика выражает процедурность языка L, в отличие от семантики

математической, связанной с непроцедурностью. Будем считать,

что семантика S1 более непроцедурна, чем S2, если "kÎL

(S1(k)ÉS2(k)), что соответствует нашему определению понятия непроцедурности представления алгоритма.

65

независимых итераций1 цикла. Тогда семантика S2 более непроцедурна, чем S1 . В частности, цикл

x[1]:=c1; x[2]:=c2; for i =1 to 100 do

(x[i+2]:=a(x[i]); x[i+3]:=b(x[i+1];)

определяет выполнение операций a и b в следующем порядке: a(x[1]), b(x[2], a(x[3]), b(x[4]... . Так как в семантике S2

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

1:a(x[1]), b(x[2]

2:a(x[3]), b(x[4]

3:. . .

Если дополнить язык С циклом вида x X|P(x)::A; где X

- массив, A – тело цикла, операционная семантика оператора цикла не фиксирует порядок выполнения итераций и допускает выполнение итерации, если вычислены все ее аргументы. Тогда мы скажем, что введенный оператор цикла более непроцедурен,

чем цикл типа for.

Пусть теперь L1 и L2 - языки программирования с семантиками S1 и S2 соответственно, f - отношение

1 Итерацией цикла называется исполнение тела цикла с некоторым конкретным значением параметра цикла

66

функциональной эквивалентности, заданное на K(L1)´ K(L2), где

K(L) - множество конструкций (операторов) языка

программирования L. Дадим определения сравнительной

непроцедурности языков L1 и L2.

Определение 1. Язык L1 более непроцедурен, чем L2 ,

если

f

"k2 L2 k1 L1 ((k1 k2)&(S1(k1)ÉS2(k2)))

Всоответствии с определением 1 язык L1 считается более непроцедурным, чем L2, если любая программа на языке L2

может быть записана на языке L1 в более непроцедурной форме.

Определение 2. Язык L1 более непроцедурен, чем L2 ,

если

f

" k2 L2 "k1 L1 ((k1 k2)®(S1(k1)ÉS2(k2)))

Согласно определению 2 язык L1 более непроцедурен,

чем L2 в случае, если любая программа на L2 неизбежно записывается на L1 (алгоритм представляется в L1) в более непроцедурной форме.

Определение 3. Пусть задано некоторое отображение конструкций h : K(L1)®K(L2). Если

f

" k2 L2 k1=h-1(k2) ((k1 k2)&(S1(k1)ÉS2(k2)))

то язык L1 более непроцедурен, чем L2 в смысле h.

67