В.Ш. Кауфман - Языки программирования - концепции и принципы (1990) (1160787), страница 64

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

Текст из файла (страница 64)

py[0] <-- pa[0,0] <-- pa[0,1] <-- pa[0,2] <-- pb[0]

| | |

py[1] <-- pa[1,0] <-- pa[1,1] <-- pa[1,2] <-- pb[1]

| | |

py[2] <-- pa[2,0] <-- pa[2,1] <-- pa[2,2] <-- pb[2]

| | |

\|/ \|/ \|/

p0[0] p0[1] p0[2]

Рис. 17.1.

Таким образом, конфигурация процессов разработана. Стрелки указывают

направление потоков данных (им и должны соответствовать каналы).

Конечно, можно было бы для нашего случая описать каждый процесс (всего

их 21) в отдельности. Однако это громоздко и к тому же упустим главную цель

- показать Оккам-2 в действии. Поэтому опишем процесс каждого вида

процедурой с параметрами (с тем чтобы затем воспользоваться средствами

компоновки нужной конфигурации из таких процедур).

Начнем с процесса вида pa. Такой процесс должен воспринимать "сверху"

значение x[j], справа - частичную сумму b[i] с "правыми" произведениями

a[i,j] * x[j], и передавать вниз без изменений значение x[j], а налево -

модифицированное значение частичной суммы. Параметрами процесса pa,

следовательно, должны быть значения a[i,j] и четыре канала, два из которых -

для входных потоков, два - для выходных. Итак

proc pa (val real aij, chan real32 верх, низ, лево, право) =

real xj,yi,aij.xj :

seg

верх?xj

while true -- аналог loop

seg

par

низ!xj -- передать xj

aij.xj := aij * xj

право?yi -- запрос частичной суммы

par

лево!yi + aij.xj

верх?xj

В результате повторений цикла можно обрабатывать при необходимости

много векторов (в зависимости от того, сколько поступит). Напишем

параметрический процесс pb. Он служит источником значений вектора b[i].

proc pb(val real32 bi, chan of real лево) =

while true

лево ! bi

Вопрос. Зачем здесь бесконечный цикл?

Подсказка. Это единственный способ обеспечить значениями работающие в

аналогичном цикле процессы pa[i,j].

Процесс px поставляет значения вектора x[j].

proc px (val real j, chan of real низ) =

-- создать xj(j) - значения переменных xj каким-то способом --

вырабатываются в зависимости от j

while true

низ ! создать.xj(j)

Процесс py получает значения вектора y[i]

proc py (chan of real право) =

while true

...

право ? куда-то

...

Ясно, что два последних поцесса - своего рода заглушки. Они обязательно

нужны, чтобы у внутренних процессов были партнеры.

Вопрос. Что произойдет при отсутствии или остановке таких партнеров?

Содержательно эти два процесса могут представлять собой, например,

связь с внешним миром, для описания которой в Оккаме имеются специальные

средства (например, так называемые порты).

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

строке нашей структуры процессов могли стоять процессы вида pa (т.е. с

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

вида p0 также играют роль заглушек - они просто поглощают содержательно

лишние передачи вниз. Можно считать, что вместе с нижним рядом процессов

вида pa они должны образовать специальные процессы вида pa1 - без передачи

вниз.

proc p0 (chan of real верх) =

while true

...

верх ? куда-то

17.4.2. Коммутация каналов

Все процессы описаны. Осталось самое неприятное при программировании на

Оккаме - обеспечить их правильное "размножение" и правильную коммутацию

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

(размножителей), второе - за счет массивов каналов, связываемых затем

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

Сначала напишем, потом прокомментируем.

val n is 3 -- тип int опущен, подразумевается по умолчанию

[n][n] real a -- массив a[i,j], индексы с нуля

[n] real b -- массив b[i]

seq

... -- присваивание значений компонентам a и b

[n+1][n] chan of real верх.низ -- эти массивы локальны

[n][n+1] chan of real право.лево -- в ближайшем "par"

par

par j=0 for n -- max j=n-1!

px(j, верх.низ[0][j]) -- самые верхние каналы

par i=0 for n

pb(b[i], право.лево[i][n]) -- правые каналы

par i=0 for n

par j=0 for n

pa(a[i][j], верх.низ[i][j], -- верхние для (i,j)

верх.низ[i+1][j], -- нижние

право.лево[i][j], -- левые

право.лево[i][j+1]) -- правые

par j=0 for n -- max j=n-1

p0(верх.низ[n][j]) -- самые нижние

par i=0 for n

py(право.лево[i][0]) -- самые левые

Вопрос. Не заметили ли Вы нарушение принципа целостности по отношению к

массивам a и b?

Подсказка. Сколько раз пришлось указывать параметр n?

Итак, объявлены и инициализированы массивы постоянных, специфичных для

конкретного запуска программы (массивы a и в). Затем объявлены подходящих

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

массивах Оккама - с нуля.

Достаточно взглянуть на структуру наших процессов (рис. 17.1), чтобы

убедиться в правильности структуры массивов каналов - двенадцать стрелок-

каналов сверху-вниз и двенадцать стрелок справа-налево. Объявленные массивы

каналов локальны в ближайшем (непосредственно) следующем процессе

(начинающемся с открывающей скобки-комбинатора par).

Ключевой момент - согласовать репликацию (размножение) процессов со

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

нужный канал, причем в соответствии с ролями партнеров: одному - в качестве

входного канала-аргумента, второму - в качестве выходного.

Легко видеть, что именно так и делается. Например, самый нижний pb[2]

получил в качесве выходного канала право.лево[2][3]. Этот же канал получил в

качесве выходного справа процесс pa[2][2], что и требовалось.

Обратите внимание, что все размноженные процессы (всего их 21) работают

параллельно, хотя при их коммутации можно было совершенно не думать о

параллелизме.

Упражнение. Постарайтесь найти ошибки в приведенной программе на

Оккаме-2 (или обоснуйте ее правильность).

17.5. Монитор Хансена-Хоара на Оккаме-2

proc буф(chan of byte связь1, связь2)

[n] byte буфер:

seq

proc занести (val byte x)

... : -- конец объявления "занести"

proc выбрать (byte x)

... :

bool function полон

... :

bool function пуст

... :

byte z :

while true -- полный аналог loop в Аде

alt -- аналог select в Аде

not полон & связь1 ? z

занести(z)

not пуст & связь2 ! z

выбрать(z)

true & SKIP

Это полный аналог монитора в Аде. Пример полезен и тем, что позволяет

познакомиться еще с одной конструкцией Оккама - оператором alt (аналогом

select в Аде). В нашем примере в этом операторе три альтернативы. Аналогично

select рассматриваются сначала лишь те, где имеется заказ рандеву. Если

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

рандеву может состояться (партнер готов)), то выбирается одна из них и

выполняется. Иначе выполняется всегда открытая альтернатива со SKIP.

Обратите внимание, что задержка (оператор ожидания) не используется -

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

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

рандеву (по двум каналам), то можно воспользоваться разновидностью оператора

alt с заголовком pri alt. В нем высшим приоритетом обладает та альтернатива,

которая расположена ближе к заголовку. Так, в нашем случае нужно было бы

написать

pri alt

not пуст & связь2 ! z

выбрать(z)

not полон & связь1 ? z

занести(z)

true & SKIP

Стоит подчеркнуть, что выигрыш в скорости достигается только при

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

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

исполнения.

17.6. Сортировка деревом исполнителей

Чтобы закрепить "новое параллельное мышление", продолжим серию

примеров. Опишем сортировку слиянием, рассчитанную на потенциально

неограниченный массив сортируемых чисел.

Общий замысел. Коллектив исполнителей представляет собой двоичное

сбалансированное дерево (как увидим, сбалансированность нужна только для

идентификации каналов). Дерево исполнителей воспринимает сортируемый поток

чисел через свой корень и возвращает обратно отсортированный поток.

Предполагается, что общее количество чисел в потоке ограничено, однако

коллективу неизвестно. Вместе с тем листьев в дереве достаточно для

размещения всех чисел потока.

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

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

дереве и, во-вторых, сливает отсортированные потомками обратные потоки,

направляя результат своему предку.

Детали. Во-первых, как и в задаче о перемножении векторов, важно удачно

занумеровать каналы. Наше дерево будет иметь вид, показанный на рис.17.2.

влево слева вправо справа

|_3_| |_4_| |_5_| |_6_| /\ || /\ ||

\ / \ / ||_____\/____||_____\/

|_1_| |_2_| |______ _узел_ ____|

\ / /\ ||

|_0_| || \/

снизу вниз

Структура дерева Шесть каналов одного узла

Рис. 17.2.

Из рисунка ясно, что у каждого внутреннего процесса (т.е. не листа и не

корня) - шесть каналов (два для связи с предком, четыре - для связи с

потомками). Имеется два вида каналов - для передачи вверх и вниз по дереву.

Каналов каждого вида ровно столько, сколько исполнителей, а именно 2n-

1, где n - число листьев в дереве. Если нумеровать их с корня, то

получается, что процесс с номером i связывают с предком каналы с номером i,

а с потомками - каналы с номерами 2i+1 и 2i+2. На этих расчетох и строится

коммутация каналов.

Во-вторых, нужно учесть неопределенность длины потока. Обычный прием -

завести признак конца потока. Так мы и поступим, однако придется решить еще

один вопрос.

Дело в том, что по многим причинам желательно добиваться однородности

потока. Другими словами, его элементы должны иметь фиксированный тип. Если

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

возможность иметь признак конца потока - представить элемент потока объектом

комбинированного типа, т.е. парой, состоящей из собственно числа и признака,

(например, булевого) продолжения потока.

Поэтому примем, что поток состоит именно из таких пар, причем ложь в

поле продолжения означает, что мы имеем дело с последним элементом потока.

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

Вопрос. Откуда возьмется много потоков?

Подсказка. Исходный поток распределяется по ветвям дерева.

Собственно программа. Итак, нужны три вида процессов - предкорневой

(драйвер, представитель внешней среды, откуда поступает исходный поток и

куда отправляется отсортированный), сортировщик (рядовой процесс-узел) и

лист (терминальный процесс, способный лишь получать и возвращать числа,

поворачивая поток вспять). Вот как организовать из них дерево:

val INT колич.чисел is 250 : -- константы-параметры потока

val INT глубина is 8 : -- и дерева

val INT число.листьев is 1<<глубина, -- 2**глубина = 256

INT число.узлов is число.листьев-1,

INT число.процессов is число.листьев + число.узлов,

INT число.каналов is число.процессов,

INT корень is 0,

INT первый.узел is корень,

INT первый.лист is первый.узел + число.узлов :

PROTOCOL пары is bool; real : -- именованный протокол "пары"

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

-- тем каналам, при спецификации которых указан такой протокол

[число.каналов] chan of верх, низ : -- два массива каналов

... -- объявления нужных процессов

par

Характеристики

Список файлов книги