2 Continue

Искомая конструкция создает для каждого набора K_i…K_n параллельную ветвь, представляющую собой вложенный цикл с шагами исполнения P₁ ….P_n. (1≤ K_j≤ P_j)

Для эквивалентности исходного и полученного цикла достаточно, чтобы в каждом из P₁*P₂…*P_n параллелепипедов не содержалось конкуренционно зависимых итераций, а так же порядок выполнения итераций группами, состоящими из параллелепипедов, был таков, чтобы все использования выполнялись после соответствующих генераций.

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

Замечание: если не требовать выполнения условия прямоугольности параллелепипедов, то этот метод является естественным методом гиперплоскостей (гиперплоскость получается как параллелепипед, одна из сторон которого имеет длину =1 , а все остальные совпадают с границей R_k).

Данный метод может использоваться для простых циклов.

МЕТОД ПИРАМИД.

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

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

Для этого:

1. в цикле выбираются все результирующие итерации. Каждая такая итерация служит основой отдельной параллельной ветви.

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

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

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

Рассмотрим следующий пример.

DO 10 I₁=1,R₁

DO 10 I₂=1,R₂

<ТЕЛО ЦИКЛА>

10 CONTINUE

После использования метода пирамид получаются конструкции вида:

DO 10 CONC FOR ALL K{1,…,R_r}

DO 10 I₁=1,R₁

DO 10 I₂=MAX{1,K-[(R₁-I₁)G₂/G₁]}, MIN{R₂,K+[(R₁-I₁)H₂/H₁]}

<ТЕЛО ЦИКЛА>

10 CONTINUE

Замечание: для векторно-конвейерной системы (SIMD) метод пирамид очень неэффективен.

ЯЗЫКИ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ

25/10

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

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

• СУММА

• ОККАМ

• ОККАМ-2

• PASCAL CONCURRENT

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

• ОВС-ЛЯПАС

• ОВС-АЛГОЛ

• ОВС-ФОРТРАН

• ФОРТРАН 90…

Непроцедурные языки

• НОРМА

ФОРТРАН 90.

Операции над массивами.

Все операции в языке Фортран 90 выполняются над векторами покомпонентно и фактически являются расширениями соответствующих операций над скалярами.

В языке вводятся понятия:

Ранг массива – размерность в диапазоне от 1 до 7. Ранг скаляра считается равным нулю.

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

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

Все операции над массивами требуют согласованности операндов.

Конструктор массивов.

Конструктор массивов дает возможность построить одномерный массив (вектор), имеющий следующий формат:

(/С₁, С₂, … С_n/)

где C_i – элемент конструктора.

В свою очередь элемент конструктора может иметь один из следующих форматов:

• скалярное выражение,

• векторное выражение

• неявный цикл.

Пример 1	(/2, 1, 1, 3, 1/)	скалярное выражение
Пример 2	(/A1+A2/)	векторное выражение
Пример 3	(/(2.9, С(N), N=1,3), 8.2/) что эквивалентно: (/2.9, С(1), 2.9, С(2), 2.9, С(3), 8.9/)	неявный цикл

Тип конструктора определяется типом входящего в него выражения.

Конструктор можно использовать в качестве:

• операнда в выражении в качестве

• фактического параметра процедуры

• элемента списка вывода.

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

В языке имеется возможность преобразовывать массив в массив другой размерности. Например:

INTEGER MAT (3,2)

INTEGER VEC (6)

VEC = (/1,10,100,1000,10000,100000/)

MAT = RESHARE (SHARE=(3,2), SOURCE = VEC)

В этом примере функция RESHARE преобразует исходный вектор VEC в двумерный массив MAT.

Секция массива.

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

Формат секции массива:

b (i₁, i₂, … , i_n)

где

b – имя исходного массива

i_k - индексы секции.

Каждый индекс может быть скалярного типа, векторного типа или индексным триплетом. Скалярный индекс – скалярное выражение целого типа.

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

Формат индексного триплета:

[l₁] : [l₂] [:l₃]

где:

l₁ – нижняя граница

l₂ – верхняя граница

l₃ – шаг

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

DINSION ROW (N), COL (M)

DINSION Z (M, N)

……………

ROW=Z(3,:)

COL=Z(:,J)

CALL SUB1(Z(M:1:-2,1:N:2))

В этом примере массиву CALL присваивается J-й столбец массива Z. Массиву ROW присваивается 3-я строка массива Z.

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

INTEGER A(10,10), U(3), U(4)

INTEGER MAT (3,4), VNEW(4)

V=(/1,3,2/)

U=(/2,1,1,3/)

VNEW=A(3,V) à A(3,2), A(3,1), A(3,3)

MAT=A(U,V)

à

A(1,2), A(1,1), A(1,1), A(1,3)

A(3,2), A(3,1), A(3,1), A(3,3)

A(2,2), A(2,1), A(2,1), A(2,3)

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

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

Оператор присваивания в среде операций над массивами.

Рассмотрим следующий пример.

REAL X(10,10), Y(40), Z(-9:10)

…

X(10,:) = 2.9 + Y(2:40:2) + SQR(Z)

X(:,3) = 3.5

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

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

Пример:

REAL X(10)

…………

X(1:10)=X(10:1:-1)

В этом примере оператор присваивания называется встроенным и имеет особенности выполнения:

• сначала выполняются все операции в правой части над элементами исходных массивов,

• затем все операции в индексной части слева

• после этого происходит непосредственно присваивание.

В результате элементы массива X будут размещены в обратном порядке.

Присваивание по маске.

Рассмотрим следующий пример

WHERE (Y.NE.0)

X(10,:) = 4.1 + Z/Y

ELSE WHERE

X(10,:) = 0.0

END WHERE

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

Для тех элементов, для которых значение логического выражения истинно, над соответствующими элементами массивов Z, X, Y выполняется первая часть конструкции, а для остальных – вторая часть конструкции.

Конструкция WHERE может не содержать вторую часть ELSE WHERE.

В языке ФОРТРАН 90 имеются функции, возвращающие в качестве результата массив. Кроме того есть возможность использовать традиционные функции в суперскалярном режиме.

ЯЗЫК ОККАМ.

30/10

Этот язык относится к языкам с явным описанием параллелизма.

OKKAM – явное описание взаимодействия параллельных процессов.

Транспьютер (Transistor Computer)

Однокристальный компьютер Iumos T9000.

Хоар «Взаимодействие последовательных процессов».

Дэвид Мэт – автор ОККАМ.

Отлич.особенности:

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

При реализации на конкретной вычислительной системе программные каналы отображаются на физические link-и. Это даёт возможность составлять программу без предварительного учёта числа транпьютеров.

Взаимодецствие параллельных процессов через программные каналы осуществляется по принципу РАНДЕВУ.

Принцип Рандеву – процесс, передающий информацию другому процессу, ожидает от последнего сигнала готовности приёма; процесс, принимающий информацию, ожидает от первого сигнала готовности передачи.

Передача при наличии 2-х сигналов.

Процесс – одна из допустимых конструкций. Каждая конструкция состоит их элементарных процессов:

• присваивание (:=)

• ввод информации (?)

• оператор вывода информации (!)

• SKIP – пустой процесс. Ничего не делает, мгновенно начинается и мгновенно завершается.

• фиктивные процессы:

• STOP – начинается, ничего не делает, никогда не завершается.(тяжёлый астероид)

КОНСТРУКЦИИ ОККАМ.

SEQ

--	процесс 1
	…………
	процесс n

Все процессы выполняются строго последовательно. Работа заканчивается, когда заканчивается последний из процессов.

Пример.

1. SEQ	2. SEQ
Index := 0	in ? Num
Limit := 100	Out!Num
Left :=Limit - Index

PAR

--	процесс 1
	…………
	процесс n

Все процессы начинаются одновременно и выполняются независимо.

Пример.

PAR

Comm1 ? Item1

Comm2 ? Item2

Comm3 ? Item3

ALT

--	input 1
	process 1
	…………
	input n
	process n

input 1…n – сторожа (охрана). Каждый сторож – процесс ввода. Сторож открыт, если в соответствующий канал уже передано сообщение.

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

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

1. вычисляется логическое выражение перед сторожем

2. указывается приоритет PRI <число>

Пример.

ALT

inchan1 ? Data1

Outchan ! Data1

Вложенные конструкции.

Пример.

1. PAR	2. PAR
SEQ	SEQ
Index := 0	Chan1 ! Data1
Chan ! Index	Chan2 ! Data2
SEQ	SEQ
Limit := 100	Chan2 ! Item2
Chan2 ! Limit	Chan1 ! Item1

Типы данных.

BYTE REAL 32

INT 16 REAL 64

INT 32 BOOL

INT 64

INT

Запись чисел:

11.273 #FC

32767 #1FFF

1.3E3

В ОККАМ имеется возможность преобразовывать литеральные константы к указанному типу:

Epsilon := 1.0E-6 (REAL 64)

Double := 1.0 (REAL 32) + single

Описание констант. VAL <тип> <константа> IS <константное выражение> :

Пример:

VAL BYTE Limit IS 255 :

VAL REAL64 EPSILON IS 1.0E-8:

VAL INT У IS 999 :

Описание переменных. <тип> <переменная> :

Пример:

BYTE char :

INT index :

REAL 32 Average :

Примеры:

VAL Pi IS 3.14159 (REAL32) :

VAL TwoPi IS 2.0 (REAL32) * Pi :

Описание каналов. СHAN OF <тип> <имя> :

Пример:

CHAN OF BYTE chan:

CHAN OF INT error:

CHAN OF BOOL flag:

C каждым каналом связан определенный тип данных, которые могут вводиться/выводиться в определённых направлениях (Тип передаваемых по каналу данных=протоколы канала). Протоколы могут быть простые и сложные.

Пример:

CHAN OF BYTE chan;

PAR

BYTE Data:

SEQ

Data := 100 (BYTE)

Chan ! Data

BYTE value:

SEQ

Chan ? value

Операции в языке ОККАМ. + - * /

REM – остаток от деления на целое число.

Операции по модулю, PLUS, MINUS, TIMES.

Замечания:

1) В языке ОККАМ нет старшинства операций. Порядок следования явно определяется круглыми скобками ().

( А + В ) + С, но А+В+С – не верно.

2) Перед операндом можно задавать явное преобразование типа.

Пример:

REAL 64 Double1, Double2 :

REAL 32 Single :

SEQ

Single := 3.144 (REAL32) :

Double1 := 4.44 (REAL64) :

Double2 := (REAL64 Single) * Double1 :

Логические операции: AND, OR, NOT

что соответствует (= <> ≤ ≥ < >)

Операции над битами.

BIT AND

BIT OR

>< исключающее «или»

BITNOT

<< сдвиг влево

>> сдвиг вправо

Операция сдвига: <операнд> << <число сдвигов>

МАССИВЫ.

[<размер>]<тип ><идентификатор>:

Пример:

[50] REAL 32 Reading :

[10] BOOL Flag :

[17][15] REAL 232 Grid :

[8][8][8] REAL 32 Cube :

Число размерностей не ограничено, индексы нумеруются с «0».

Описание массивов – каналов.

Пример:

[10] CHAN OF INT CHAN1:

CHAN OF [10] INT CHAN2:

В этом примере описаны:

- массив каналов с именем CHAN1 из 10 элементов

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

ПРОГРАММИРОВАНИЕ ПРОСТРАНСТВЕННО-ВРЕМЕННЫХ СТРУКТУР

НА ЯЗЫКЕ ОККАМ

6/10

Пример 1:

«1» (единица) передается по каналу С в переменную «а»

CHAN OF INT C:

INT A:

PAR

C ! 1

C ? A

Данные процессы выполняются параллельно.

Пример 2:

WHILE TRUE

ALT

LEFT.CHAN ? X

OUTPUT ! X

RIGHT.CHAN ? X

OUTPUT ! X

В этом пример происходит объединение информации, поступающей по каналам LEFT.CHAN и RIGHT.CHAN в произвольном порядке, и передача этой информации в канал OUTPUT.

Пример 3:

[4] CHAN OF INT CHANS :

PAR I=0 FOR 3

PIPE.EL( CHANS[I], CHANS[I+1])

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

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

Пример 4:

[3][2] CHAN OF INT X.CHANS:

[2][3] CHAN OF INT Y.CHANS:

PAR I=0 FOR 2

PAR J=0 FOR 2

GRID.EL (X.CHANS[I,J], Y.CHANS[I,J],

X,CHANS[I+1],J, Y.CHANS[I,J+1])

В этом примере реализована двумерная пространственно-временная структура, в которой имеются два двумерных массива каналов X.CHANS и Y.CHANS, и реализована параллельная вложенная конструкция PAR, в которой процессы создаются при вызове процедуры GRID.EL.

ОПЕРАЦИОННЫЕ СИСТЕМЫ ДЛЯ ТРАНСПЬЮТЕРНЫХ СБОРОК