3.3.8. Язык Оккам для транспьютерных сетей и система их параллельного программирования.

Оккам (OCCAM) - это новый язык программирования, разработан­ный для реализации параллельной обработки информации на транспью­терных сетях. Он позволяет программисту представить сложную прог­рамму в виде множества параллельно-последовательных процессов, взаимодействующих друг с другом посредством пересылки сообщений по каналам связи. Для каждого из параллельных процессов обычно используется отдельный процессор. Язык разработан в Англии спе­циально для транспьютеров, но может быть использован и для парал­лельного программирования сетей ЭВМ /23.24/.

В Оккам поведение любого процесса прослеживается только по сообщениям, проходящим по его каналам связи. Внутренняя структу­ра процесса для языка Оккам безразлична, также как и в рассмотренных операторах взаимодействия системы "Минимакс". и может быть скрытой. Оккам - процесс определяется только следующими фазами:

1)начало;

2)обработка, при которой в пределах языка Оккам контролируются и осуществляются следующие процедуры: 2.1) присваивание: изменение значения переменной, например присваивание ей значений констант или идентификаторов каналов связи; 2.2)ввод - получение значения из входного канала связи; 2.3) вывод - засылка значения в выход­ной канал связи (для осуществления двунаправленного ввода-вывода требуется двухсторонняя, дуплексная связь):

3) завершение процесса.

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

В языке Оккам существенно упрощена синхронизация асинхрон­ных параллельных процессов. Любой процесс (ветвь) между своим на­чалом и завершением может только ожидать ввода требуемых для его продолжения значений из одного из входных каналов транспьютера. Вывод значений, подлежащих передаче другим процессам, осущес­твляется сразу же после их вычислений без дополнительной провер­ки события готовности к их приему в других процессах (ветвях).

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

С целью реализации этого принципа в языке Оккам отдельные процессы объединяются в сложные последовательно-параллельные про­цессы специальными процедурами их компоновки, которые называются конструкторы. Применяются следующие виды конструкторов:

1. Последовательный конструктор (SEQ) задает поочередное последовательное выполнение процессов и завершается с окончанием последнего процесса в последовательности. В этом случае каждый последующий процесс считается начатым и находится в режиме ожида­ния ввода значений от предыдущих процессов.

2. Параллельный конструктор (PAR) задает параллельное выпол­нение своих компонент и завершается лишь после окончания всех параллельных ветвей. Очевидно, что это не оптимальная организация, но существенно упрощающая синхронизацию. Она не оптимальна в том смысле, что в худшем случае время выполнения набора параллельные ветвей может оказаться равным времени их последовательного выпол­нения, если в большинстве ветвей ожидание ввода потребуется сра­зу же в их начале, а требуемые им значения будут вычисляться в других ветвях к моменту их завершения. Поэтому в конструктор PAR рекомендуется включать ветви программы, независимые по данным и управлению, аналогично ветвям Ярусно-параллельных форм (ЯПФ).

3.Альтернативный конструктор (ALT) выбирает для выполнения только один процесс из заданного их списка и завершается после завершения выбранного процесса. Применяется для ускорения выпол­нения ветвей программы, связанных между собой по данным или/и уп­равлению. Первым отыскивается из списка самый ранний процесс, уже готовый к выполнению по выводу предыдущих процессов, а из остав­шегося списка - второй самый ранний, ожидавший ввода значений от предыдущих процессов, и так далее.

4. Условный конструктор (IF) аналогичен ALТ, но в процессах вместо простого ожидания ввода дополнительно используются логи­ческие условия. Условия процессов, включенных в состав этого кон­структора, проверяются последовательно, и тот процесс, условие начала или продолжения которого оказывается истинным, поступает на выполнение. Если все условия всех процессов списка IF ложны, то выполнение конструктора IF завершается.

5. Условный конструктор (WHILE) повторяет свой процесс до тех пор, пока результат проверки логического условия его начала или продолжения не приобретет значение ложности.

Конструкторы можно размножать и повторять сколько угодно раз. Размножение применяется с использованием конструктора PAR, a повторением можно проимитировать условные циклы.

С помощью конструкторов при программировании осуществляется иерархическая последовательно - параллельная декомпозиция сложных программ подобно рассмотренному нами ранее отечественному ме­тоду разбиения задачи на крупноблочные параллельные ветви с мини­мизацией участия МОС и управлении их взаимодействием.

Такой подход позволяет снизить затраты системных ресурсов на организацию выполнения параллельных программ по сравнению с рас­смотренными нами МОС-ми МПВС "Минимакс" и "Микрос", в частности упростить операторы группового и индивидуального взаимодействия и тем самым уменьшить требуемый объем ЛОП транспьютеров.

Этот подход достаточно эффективен в специализированных МПВС с ПС и прежде всего в транспьютерных акселераторах МПС, так как в них прикладное программирование выполняется весьма редко, чаше всего только на этапе их проектирования, и поэтому разумно пойти на увеличение его трудоемкости. За счет этого, применив языки, подобные Оккам, или наш аппарат крупноблочных параллельных вет­вей, можно существенно уменьшить затраты времени МОС на организа­цию взаимодействий ветвей и сэкономить расход памяти в ЭМ-ах. Последнее весьма актуально, так как из-за технологических ограни­чений емкость внутрикристальных встроенных ЛОП в ЭМ-ах пока неве­лика, например, в транспьютере Т800 до 4 Кбайт.

Достоинства языка Оккам:

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

2. Язык Оккам очень прост и краток, но в то же время с по­мощью названных пяти конструкторов он позволяет объединять мно­жество примитивных процессов в мощные иерархические парал­лельно-последовательные управляющие структуры.

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

4. Он пригоден на всех уровнях поддерживаемой им иерархической управляющей структуры. Например, его конструкции пригодны и для составления локальных программ в каждом из транспьютеров вы­числительной сети, и для описания главной глобальной программы всего параллельного вычислительного процесса в транспьютерной се­ти. Именованные локальные процессы ЭМ-ин естественно через опи­санные каналы связи входят в состав глобального процесса.

5. Логика работы его не зависит от того, реализуется ли он на одном процессоре или на нескольких. Компилятор Оккама может реализовать режим разделения времени, и поэтому все указанные в тексте программы параллельные процессы получают доступ к одному и тому же процессору. Поэтому все программы на Оккаме предвари­тельно транслируются и отлаживаются на ЭВМ общего назначения в режиме СРВ, а после этого дополняются необходимыми конструкциями, которые описывают способы их параллельной загрузки в транспьютер­ную сеть и расположения локальных именованных процессов в разных ЛОП разных транспьютеров.

6. Система параллельного программирования Оккам снабжена от­ладочными и оценочными средствами: экранным редактором, синтакси­ческим анализатором, средствами структурного редактирования. программами для оценки ожидаемой производительности параллельной программы и требуемой памяти.

Основные, примитивы и конструкции языка Оккам Конструкции:

1.Последовательная конструкция SEQ:

SEQ {база FOR количество }

: Р1

: Р2

: •

: •

: —> со сдвигом на один символ и пробел

:

Процессы Р1, Р2,. . . выполняются последовательно

2.Параллельная конструкция PAR:

PAR {база FOR количество}

: Р1

: Р2

: •

: •

: —> со сдвигом на один символ и пробел

:

Процессы Р1, Р2,. . . выполняются параллельно.

3.Конструкция альтернативного выбора ALT

ALT {база FOR количество }

: Р1

: Р2

: •

: •

:

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

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

WHILE <условие>

:

: процесс

:

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

IF <условие>

:

: процесс

:

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

Примитивы:

1.Объявление переменной (переменных):

VAR имя 1, имя 2,...:

2.Объявление массива переменных:

VAR имя [размер]:

3.Объявление каналов связи:

CHAN имя1, имя2. ...:

массива каналов

CHAN имя [размер]:

4.Объявление процессов:

PROC имя(<параметры>)=

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

5. Присваивание, которое изменяет значение переменной:

a:=b+с

6.Ввод - получение значения из поименованного канала и присваива­ние этого значения какой-либо указанной в примитиве переменной:

chan 1 ? а

Переменной а присваивается значение, полученное из канала

chan 1.

7.Вывод - это передача в поименованный канал значения переменной, указанной в этом примитиве:

chan 2! b+с

8. : - завершает примитивы объявления и текст программы (заверше­ние процесса).
Полезные подпрограммы:
1.Ввод (чтение) из одного канала и сразу же вывод(запись) в другой

канал (транзитная передача):

chan 1? x

chan 2! х

2. Если при вводе из одного канала и выводе в другой канал про­цесс использует промежуточную переменную, хранимую в ОП, необ­ходимо объявить ее имя и применить последовательный конструк­тор:

VAR x:

SEQ

chan.in ? х

chan.out ! х

3.Параллельное чтение (ввод) из двух входных каналов с присваива­нием считанных из этих каналов значений объявленным переменным:

VAR for-vote, against-vote:

PAR

For ? for-vote

Against ? against-vote

4.Полезно применение конструкции ALT для реализации повторений :

ALT 1=[O FOR 100] | групповое

inp[l] ? х | транзитное

oup ! х : | взаимодействие

Этот процесс читает значение из первого доступного (передающего) канала в массиве входных каналов inp[l], присваивает его перемен­ной х и передает в канал oup , и так далее, пока не обслужит все доступные каналы с номерами от 0 до 100. Завершается после обслу­живания доступных к этому моменту каналов (передающих какие-либо значения по наличии стартовых посылок: 11 в каждом передаваемом байте).
3.3.9.Программирование в транспьютерной сети на языке ОККАМ матричного волнового процессора.

Напомним суть двумерного волнового алгоритма умножения двух матриц. Одна матрица поступает в квадратный матричный процессор слева по столбцам, другая сверху - по строкам. По мере продвиже­ния векторов данных вправо и вниз они попарно встречаются в нуж­ных транспьютерах, их компоненты перемножаются и суммируются с накоплением частичных сумм в каждом транспьютере. После того, как все элементы исходных матриц волна за волной за n шагов (nхn: раз­мер матриц) будут загружены в матрицу транспьютеров и пройдут ее, в каждом из них накопятся суммы произведений пар элементов как результирующие элементы искомой матрицы. На каждом волновом фронте каждый транспьютер выполняет одинаковую задачу - чтение

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

Программа транспьютерной сети составляется как иерархичес­кая двухуровневая /24/.

На нижнем уровне в каждом транспьютере выполняется следую­щая локальная программа на языке Оккам:

РROС mult(CHAN up, down. left, right)=

V
Определяется, что подчиненный процесс А может повторяться n-раз на фронте каждой волны. где 0 соответствует начальной установке


AR ass,a,b:

SEQ

ass:=0

SEQ 1=[0 FOR n]

S

I Три процесса в составе A, которые

выполняются последовательно.

EQ

PAR

up?a

A left?b

ass:=аss+а*b II

PAR

down!a III

right!b:

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

На втором высшем уровне иерархии программы транспьютерной сети должны выполняться главная (глобальная) организующая прог­рамма на языке Оккам, т.е. структурная программа, которая в нашем примере должна установить связи между транспьютерами и вызывать указанный выше локальный PROC mult... nxn раз на каждой из n волн.

СHAN vertical[ n*(n+1)]:

CHAN horizontal [n*(n+1):

PAR I=[0 FOR n]

PAR J=[0 FOR n]

mult( vertical [ ( n*1+J],

vertical[(n*1)+j+l),

horisontal[(n*l)+J],

horisontal [(n*(I+1))+j]):

Этот сравнительно простой текст несет в себе большую смысло­вую нагрузку .

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

Иерархическая структура программы поддерживается в ОККАМЕ тем, что именованные процессы(например mult) могут быть использо­ваны в тексте как и любые другие процессы. В нашем примере на верхнем уровне в глобальной программе указано с помощью двух кон­струкций РАД, что процесс mult нижнего уровня реализуется в каж­дой IJ ячейке. При этом соответствие между общими наименованиями каналов связи в транспьютерной сети на глобальном уровне и час­тными наименованиями четырех каналов в локальной программе ij-го транспьютера устанавливается по месту занимаемому ими в описании параметров процесса mult, например, vertical[(n*i)+j] - это ка­нал up в ij-ом транспьютере.

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

R глобальной программе процесс mult инициализируется ( начи­нается) параллельно и одновременно по всем парам

Vertical[(n*i)+J] и horisontal[(n*i)+j]

входных каналов каждого ij-го транспьютера. Однако в связи с тем. что процесс А по локальным программам транспьютеров выполняется в транспьютерах

последовательно по i от 0 до n и, видимо, со сдви­гом во времени, равным такту ot, процесс передачи исходных опе­рандов вправо и вниз развивается во времени по мере их использо­вания в предыдущих (левой и верхней) соседних ячейках. Поэтому процесс mult в следующей ячейке может выполниться и завершиться только после появления в обоих ее входных каналах up и left обоих исходных данных И(а), И(Ь), а до того он будет приостановлен из -за отсутствия передач данных хотя бы от одного соседа слева или сверху.

Следовательно, несмотря на заложенную в глобальной програм­ме потенциальную возможность одновременного выполнения вычислений:

асc := асc + a*b

во всех NxN ячейках, эти вычисления по матрице будут развиваться последовательно по мере продвижения волновых Фронтов по направле­нию главной диагонали, начиная с левого верхнего угла, синхронно с загрузкой столбцов данных слева и строк данных сверху. Причем, по мере продвижения одного за другим n волновых Фронтов в каждой ij-ой ячейке локальный процесс А последовательно повторится n раз со сдвигом во времени, равным конвейерному такту t, что и опре­деляется предыдущей конструкцией:

SEQ1=[0 FOR n]

| A:

|___
Таким образом, удалось на языке ОККАМ запрограммировать в типовой однородной транспьютерной сети архитектуру волнового матричного процессора.
3.3.10. Программирование в транспыотерной сети на языке ОККАМ FIFO - буфера.

В транспьютерах фирмы Инмос(типа Т...) и в языке ОККАМ от­сутствуют буферные памяти, встроенные в каналы связи (адаптеры последовательный интерфейсов) между транспьютерами. В то же вре­мя при программировании в транспьютерных сетях потоковых и волно­вых архитектур требуется создавать в каналах входные очереди, ко­торые должны ожидать других еще не готовых операндов. Например, напомним, что в волновом алгоритме умножения двух матриц требует­ся вводить в вертикальные каналы ячеек, расположенных выше глав­ной диагонали, и в горизонтальные каналы ячеек, расположенных ни­же главной диагонали, дополнительные буферы одного из входных операндов, емкости которых линейно возрастают от 0 до n-1 вправо от главной диагонали в вертикальных каналах и вниз от главной диагонали в горизонтальных каналах.

Такие буферы можно ввести программно в локальные программы транспьютеров /24/. Для этого необходимо модифицировать текст программы процесса А, введя в процесс I перед процессом II соот­ветствующие подпрограммы, имитирующие буферные линии задержкм(FIFO-буфер), емкости которых должны линейно зависить по каналу up? от номера столбца 1, а по каналу left? от номера стро­ки J с учетом местоположения ij-й ячейки относительно главной диагонали.

Принцип составления программы FIFO-буфера с емкостью n ячеек ОЗУ. имитирующей линию задержки, состоит в следующем.

Такой FIFO - буфер можно рассматривать как цепочку последо­вательно соединенных ячеек ОЗУ (Рис. 3.6.6.).

Рис.3.6.6.

На рис.3.6.6. приняты следующие обозначения:

X - переменная, продвигающаяся по линии задержки с конвейерным тактом t:

Cli] - обозначение условного канала связи между (i-1)-й и 1-й ячейками ОЗУ, соответствующего передаче слова значения переменной к из одной ячейки ОЗУ в другую через регистр процессора в транспьютере под управлением УУ.

Если подпрограмма, имитирующая буфер, поименована следующим образом:

=>,

то все имена каналов С[1] интерпретируются транспьютером по име­ни buffer как внутренние пересылки из одной ячейки ОЗУ в другую. Например, -конструкция С[1]?x интерпретируется так: "считать ка­кое-то значение из i-ой ячейки ОЗУ и присвоить его переменной х", а конструкция С[i+1]!x -"записать значение переменной x в [i+1)-ю ячейку ОЗУ". Если i-я ячейка пустая, т.е. значение переменной в ней х:=0, то продвигать нулевое слово бессмысленно. Аналогично начальной установкой содержимого буфера является обнуление содержимых всех ячеек памяти, и в начальной установке буфер заторможен. Это соответствует логике работы конструкции C[i]?x , так как в ОККАМе процесс всегда приостанавливается, пока в канале C[i] не появится стартовая синхропосылка 11... передаваемого значения. Внутри же транспьютера она отсутствует. Поэтому в имитирующей программе процесс буфера следует начинать с конструкции

WHILE TRUE

: процесс,

:

которая повторяет выполнение подчиненного процесса, пока усло­вие не станет ложным. Ложным считается нулевое содержимое ячейки, и тогда оно не будет продвигаться. Кроме того по процедуре buffer после считывания из ячейки значения 0 ее содержимое обнуляется.

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

PROC buffer =

СНАN с[п+1]:

PAR i=[О FOR n]

WHILE TRUE

VAR x:

SEQ

с[i]?x

с[i+1]!x:
Конструкция PAR i-[0 FOR n] интерпретируется в транспьютере, как псевдопаралельное выполнение процесса В для веек i в режи­ме разделения времени.

Программный буфер можно ввести между двумя внешними канала­ми ввода-вывода транспьютера. В этом случае имена внешних кана­лов транспьютера указываются в качестве параметров буфера:

bufferCcl.c2) ,

где с1 - имя входного внешнего канала,

с2 - имя выходного внешнего канала ( Рис.3.6.7).

ввод в вывод из

буфер буфера

С1 С2

0 1 n-2 n-1

С.in C[0] C[1] C[n-3] C[n-2] C.out

внешний (n-2) ячейки внешний

входной выходной

канал (п-1) внутренних ложных канал

каналов

Рис.3.6.7

Программа модернизируется к виду:

PROC buffег (СНАN С.1n,С.out) = CHAN С[ n-1]:

WHILE TRUE

PAR

VAR x: Ввод в

SEQ буфер

С.1n?х

C[O]!x

PAR 1=[0 FOR n-2]

VAR x: буфер

SEQ

C[1]?x

C[1+1]!x

VAR x:

SEQ Вывод из

C[n-2]?x буфера

C.out!x:
Она дополнена двумя дополнительными процессами ввода из внешнего канала и вывода во внешний выходной канал.
3.3.11. Учет в программах на языке Оккам событий синхронизации параллельный асинхронных вычислительных процессов.

Как указано выше, синхронизация параллельных процессов в языке Оккам существенно упрощена тем, что любой процесс между своим началом и завершением может приостанавливаться по ожиданию ввода требуемого для его продолжения значения из одного из вход­ных каналов транспьютера. Вывод значений, требуемых другим про­цессам для их продолжения, осуществляется в выходные каналы сра­зу же после их вычисления в транспьютере. Однако в некоторых слу­чаях требуется блокировка (приостановка) одного процесса по ини­циативе другого. Наиболее простой способ такой блокировки в Оккаме это прекращение передачи данных из одного канала в другой, ко­торые связывают два подпроцесса блокируемого процесса. Это можно осуществить по специальному сигналу останова, ожидаемому с выхо­да третьего входного канала транспьютера. В качестве третьего ка­нала может быть использован любой свободный из четырех последова­тельных дуплексных каналов транспьютера или пятый его канал stop, специально предназначенный для передачи сигналов о свершении со­бытий синхронизации /24/.

Напишем текст программы на Оккаме, по которой данные копи­руются из одного канала С1 в другой С2 в стыке двух подпроцессов до тех пор, пока не поступит управляющий сигнал (ANY) останова из третьего канала под именем stop:
VAR running:

SEQ

running: =TRUE

WHILE running

VAR x:

ALT

stop ? ANY I

running: = FALSE

C1?x

C2!x: II

По TRUE и ALT всегда выполняется I процесс чтения канала stop, и, если по каналу stop поступает сигнал типа ANY, читается из канала С1 значение переменной х в канал С2 и данный процесс завершается (блокируется).

В противном случае, если сигнал ANY не получен, по ALT всег­да выполняется II второй процесс копирования значения из канала C1. в C2. По присвоению условию ложного значения конструкция WHILE приводит к завершения процесса после передачи значения пе­ременное! к из канала C1 в канал С2. В противном случае, если сиг­нал ANY не получен, то пo ALT всегда выполняется II процесс копирования значения из канала C1 в С2. Тем самым какой-то большой процесс, в который встроена эта транслирующая конструкция, может быть либо приостановлен, либо продолжен.

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

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

3.7.Инженерные методы метрической теории однородных МПВС с ПС. Формулы для вычисления показателей производительнос­ти, надежности живучести.

В связи с высокой степенью однородности удалось для МПВС с ПС получить на основе теории массового обслуживания сравнительно простые выражения для инженерный оценок значений показателей эф­фективности с учетом введения резервных ЭМ-ин и затрат на восста­новление работоспособности прикладной подсистемы /17/.

Формулы показателей производительности, надежности и живу­чести:
1.Среднее значение производительности с учетом ненадежности ЭМ-ин

где - номинальная производительность одной ЭМ-ны:

N - общее количество ЭМ-ин в МПВС с ПС;

- интенсивность отказов одной ЭМ-ны;

- интенсивность восстановления одной ЭМ-ны одним

восстанавливающим устройством;

А - коэффициент затрат ресурсов МПВС на системные функции (на МОС и надежностный резерв).