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

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

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

программирванию.

Еще одно перспективное направление, которое интенсивно развивается -

современные "языки представления знаний". Заинтересованного читателя

отсылаем к литературе [27,28].

17. Параллельное программирование в Оккаме-2 (модель О).

17.1. Принципы параллелизма в Оккаме.

Одно из наиболее значительных достижений последнего времени в области

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

для объединения в высокопроизводительные вычислительные среды и получивших

название транспьютеров. Характерно (а для нас особенно интересно) что

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

программирования (ЯПП) и его реализацию, обеспечивающую возможность

абстрагироваться от реального набора доступных процессоров. Другими словами,

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

количества транспьютеров (его можно учесть при трансляции программы -

транслятор выполнит подходящую конкретизацию).

Важнейшая цель такого ЯПП - преодолеть представление о том, что

программировать асинхронные процессы исключительно сложно. Иначе трудно

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

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

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

Тони Хоаром. Язык получил название "Оккам" в честь средневекового философа

Уильяма Оккама (ок.1285 - 1349), известного, в частности, так называемой

"бритвой Оккама". Этот принцип логических построений можно сформулировать

так: делай как можно проще, но не более того. Бритва Оккама отсекает все

лишнее в ЯП столь же успешно, как принцип чемоданчика.

И если Оберон Вирта можно рассматривать в качестве минимального

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

под руководством Хоара, можно считать минимальным современным ЯПП. Этим он

для нас и интересен.

Как обычно в этой книге, представим модель Оккама (модель О),

подчеркивая ключевые концепции и принципы. Основной источник сведений -

фирменное руководство по программированию на ЯПП Оккам-2 и сообщение о ЯПП

Оккам-2 [31].

Поскольку параллелизмом мы уже занимались, перейдем сразу к

особенностям ЯПП Оккам-2. Сначала сформулируем эти особенности, а затем

проиллюстрируем их примерами.

1. Программа - это статически определенная иерархия процессов.

2. Процесс - это элементарный процесс или структура процессов.

Допустимы, в частности, последовательные, параллельные, условные и иные

структуры процессов.

3. В каждой структуре четко распределены роли как самих компонент, так

и средств их взаимодействия. Единый принцип этого распределения таков:

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

4. Общие переменные допустимы только у компонент некоторой

последовательной структуры. (Общие константы допустимы и у компонент из

различных параллельных структур).

5. Канал Оккама - это простейший вариант асимметричного рандеву,

дополненный усовершенствованными средствами связывания партнеров. Но можно

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

двойственность зависит от того, рассматривается ли канал с точки зрения

одного процесса (асимметрия) или пары процессов-партнеров (симметрия).

Подчеркнем, что канал не обладает какой-либо памятью (обмен через канал

возможен только при взаимной готовности партнеров-процессов к такому

обмену).

6. Каждый канал в программе обслуживает только одну пару партнеров по

обмену сообщениями. Связывание канала с парой партнеров происходит

статически. При этом один партнер определяется как источник сообщений, а

второй - как приемник. Партнерами по обмену могут быть только различные

компоненты некоторой параллельной (асинхронной) структуры процессов. Другими

словами, партнерами по обмену могут быть только параллельные процессы.

7. С каждым каналом связывется тип передаваемых по нему сообщений (так

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

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

8. Коллективы (структуры) взаимодействущих процессов создаются

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

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

9. Связывание процессов с аппаратурой отделено от описания логики их

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

конфигурации (размещения процессов в процессорах).

17.2. Первые примеры применения каналов.

1. Буфер-переменная.

byte лок: -- байтовая переменная "лок"

seq -- последовательный комбинатор "seg"

источник ? лок -- получить из канала "источник" в "лок"

приемник ! лок . -- передать из "лок" в канал "приемник"

2. Простейший фильтр - процесс (процедура) с двумя параметрами-

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

proc фильтр (chan of byte источник, приемник)

while true -- бесконечный цикл

byte лок:

seq

источник ? лок

приемник ! лок .

proc поставщик (chan of byte выход)

while true

byte X:

seq

выработать (Х)

выход ! Х

proc потребитель (chan of byte вход)

while true

byte X:

seq

вход ? Х

потребить (Х)

3. Можно теперь организовать из этих процессов параллельную структуру и

связать их напрямую через канал:

chan of byte связь: -- объявление байтового канала "связь"

par -- параллельный комбинатор "par"

поставщик (связь) -- компоненты такой структуры работают

потребитель (связь) -- параллельно (асинхронно)

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

chan of byte связь1, связь2:

par

поставщик (связь1)

фильтр (связь1, связь2)

потребитель (связь2)

4. Но самое красивое - можно организовать буфер любого нужного размера

без особого труда (вспомним наши заботы о переполнении или исчерпании буфера

и т.п.).

val int N is 50: -- в буфере будет 50 ячеек

[N] chan of byte связь: -- массив из N каналов

par

поставщик (связь[0])

par i = 0 for N -- комбинатор с репликатором

фильтр(связь[i], связь[i+1] -- работает N фильтров

потребитель(связь[N]) -- (i от 0 до N-1)

Буфер составляется из N процессов-фильтров, способных принять очередной

байт тогда и только тогда, когда предыдущий передан дальше. В результате в

таком "живом" буфере каждый байт автоматически проталкивается вперед, если

впереди есть место.

Итак, благодаря каналам-посредникам с их встроенной синхронизацией-

обменом-без-очередей удается работать с процессами с полной абстракцией от

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

17.3. Сортировка конвейером фильтров

Интересно, что описываемая техника программирования асинхроненых

процессов позволяет легко превратить цепь простейших фильтров (буфер) в

цепь, сортирующую поток из заданного количества чисел (например, по

возрастанию).

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

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

Ясно, что цепь из N таких элементов способна отсортировать

последовательность из N чисел.

Напишем элемент цепи - процесс фильтр.мин.

proc фильтр.мин(chan of INT источник, приемник) =

INT мин, след:

seq

источник ? мин

seg i = 0 for N -- комбинатор с репликатором

источник ? след

IF

мин <= след

приемник ! след

мин > след

seg

приемник ! мин

мин := след

приемник ! мин

Если заменить фильтр в предыдущей программе на фильтр.мин, получим

требуемую сортировку. (Заметим, что каждый ее элемент пропускает через себя

всю последовательность чисел, но общее время сортировки линейно, так как она

работает по конвейерному принципу).

17.4. Параллельное преобразование координат (умножение вектора на

матрицу)

[Идеи заимствованы из [29], но там Оккам старый.]

При работе с графическими устройствами часто требуется выполнять

линейные преобразования n-мерного пространства по формуле

y = Ax+b

где А - квадратная матрица размера n*n, а y,x,b - n-мерные векторы (x -

исходный, b - постоянное смещение начала координат, y - результат

преобразования).

Такие преобразования требуются, например, при отображении на экране

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

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

преобразований в секунду (если желательно создать эффект кинофильма или по

крайней мере не раздражать пользователя).

Будем рассматривать трехмерное пространство (n=3), нумеруя координаты с

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

Итак, наша программа долхна вычислить координаты вектора y по формуле

y[i] = SIGMA(a[i,j] * x[j]) + b[j] (*)

где SIGMA - сумма по j от 0 до 2 (т.е. n-1).

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

то имеет смысл обратить внимание на полную независимость всех нужных

умножений (их ровно n**2 - в нашем случае 9).

Если бы удалось поручить каждое умножение отдельному исполнителю

(процессору), то можно было бы ускорить вычисления (в принципе) в n**2 раз!

На абстрактном уровне ЯПП исполнители представлены процессами и при наличии

физических исполнителей компилятор позаботится сам о размещении различных

процессов на различных физических процессорах (или учтет явные пожелания

программиста). Во всяком случае именно так работает компилятор Оккама-2.

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

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

используемого ЯПП (в нашем случае главное из них то, что канал может

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

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

17.4.1. Структура коллектива процессов

Из формулы (*) видно, что каждому элементу a[i,j] матрицы А естественно

сопоставить отдельный процесс pa[i,j], выполняющий умножение на этот элемент

значения x[j].

Если принять за основу эту идею (обеспечивающую требуемое ускорение в

n**2 раз), то остается вторая ключевая проблема - обеспечить подходящую

коммутацию процессов pa[i,j]. Нужно ввести подходящие процессы-партнеры и

связать их подходящими каналами (по одному на пару партнеров!).

Понятно, что все pa[i,j] должны рано или поздно (лучше раньше) получить

по каналам значения x[j] и b[i]. Дисциплина "один канал на пару партнеров"

требует создать по процессу px[j] на каждый элемент вектора x и по процессу

pb[i] на каждый элемент вектора b[i].

С другой стороны, эта же дисциплина не позволяет передавать x[j] сразу

нескольким pa[i.j] по одному и тому же каналу. Естественно желать, чтобы

число каналов, связанных с процессом, было фиксировано (это упрощает и его

представление на физическом уровне). Поэтому приходится применить сквозную

передачу данных через pa[i,j]. Этот характерный для Оккама элемент стиля

программирования можно назвать технологией фильтров. В нашем случае

фильтрами служат pa[i,j].

Замечание (о фильтрах). В технологии фильтров каждый процесс

рассматривается как некоторый преобразователь потока данных (действие

которого полностью сводится к преобразованию потока). Название "фильтр"

связано с тем, что в проходящем через преобразователь потоке подвергается

обработке только вполне определенный класс данных - остальные передаются в

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

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

в исходном потоке.

Технология фильтров помогает "нанизывать процессы на потоки данных" как

бусинки, собирая из относительно элементарных бусинок разнообразные

программы-сети. Полная аналогия с электрическими сетями, собираемыми из

стандартных элементов.

Важны отсутствие побочных эффектов и простота коммутации. Сравните с

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

беспокоиться о глобальных ресурсах. Впрочем, анаогичная технология успешно

применяется и в последовательном программировании (на Фортране, Паскале,

Форте и др.) на основе процедур-фильтров. Этот стиль применяется в командном

языке ОС UNIX и в программировании на ЯП Си.

Наконец, следует заготовить процессы py[i], получающие компоненты

результирующего вектора y[i], а также процессы p0[j], назначение которых

станет ясным чуть позже. Получается следующая картинка (рис.17.1):

px[0] px[1] px[2]

| | |

\|/ \|/ \|/

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

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