    
Раздел: Документация
0 ... 31 32 33 34 35 36 37 ... 78 3.Структурное ветвление TESTE су Е1с2Е2... с„Е„ Если выражение Е разлагается с помощью продукции для конструктора су, то оно принимает значение соответствующего выражения Е;. 4.Выборка из памяти REFE Выражение Е должно давать значение типа имени ячейки. Содержимое указанной ячейки представляет собой значение выражения REF. 5. Хранение в памяти ФЕХ...ЕП(Р Каждое выражение Ej записывается в виде LET Е-Е где Е - имя ячейки, а Е - значение содержимого соответствующего типа (значение Ej имеет тип assgts), или в виде любого выражения, принимающего значение типа assgts. Значение всего выражения, ограниченного символами Q) (или каким-либо другим разделителем), является объединением значений Eg (т. е. тина assgts). Пример 0LETx= REF у Fz <f> Значением этого выражения является fx, равное содержимому у] и { значение F z \ , которое может быть представлено двоичным деревом (рис. 12.1) . В примерах выражений хранения в памяти также будем использовать конструкцию DO FOR i =m TO n BY d E(i) которая для m, dn эквивалентна E(m), h (md) , . . , E(m< (Ln/rfJ- Пустое выражение NIL удобно, например, использовать в записи TF В Е NIL Функция ОМ ЕС; А. Процессор (или функции перехода состояний) имеет стандартное имя OMEGA и является функцией с неявными аргументами (состояние является неявным аргументом каждой функции), определяемой выражением Е. Для каждого перехода Е принимает значение типа assgts. Тогда переход состоит в аппликации множества пар (имя ячейки, содержимое ячейки) к определенным ячейкам памяти. Только после того, как эта аппликация полностью завершена, выражение Е может вычисляться снова. Процесс перехода из состояния в состояние прекращается тогда, когда или список вычисляемых определений пуст (нет нового вычисленного состоя-208  Рис. 12.1 Рис. 12.2  ния), или выражение Е становится неопределенным (следующее состояние не определено). Функция LOAD. С помощью этой специальной функции вычисляется список пар (имя ячейки, содержимое) без побочных эффектов. Аппликация этой функции устанавливает пространство данных в начальное состояние. Замечание. Для облегчения чтения в следующих разделах будут произ-вольно использоваться некоторые разделители. Например, Е(х) вместо Fx, IF Е THEN Ex ELSE E2 для IF E Ex E2. Выражение IF В E NIL может быть записано как IF В THEN Е. Часто для разделения выражений будет использоваться абзацное выделение, в частности в операции TEST и в операциях с памятью, где ограничители, хотя технически и необходимы для корректного разделения, просто отвлекают внимание. 12.3. ГЛОБАЛЬНАЯ СИНХРОНИЗАЦИЯ Для иллюстрации спецификации систолических алгоритмов в терминах пространства данных выбрано два наиболее хорошо известных примера: свертка в линейной систолической структуре [11] и матричное умножение в волновой матрице [12] с использованием глобальной синхронизации. 12.3.1. Свертка Пусть даны две последовательности w,, . . . , и»д. и х, ,. .. ,хр. и пусть п > к. Необходимо вычислить Уг =wixi + w»*/+l + - - - + wkxi+ к ще г -1, . . . , и -fc+1. В работе [11 ] приведена диаграмма систолического процесса в виле, представленном на рис. 12.2. Предполагается, что п - к-2, и поэтому вычисляются три значения у/. На рис. 12.2 показано состояние после второго цикла работы. Вычисление каждого значения происходит на элементарном процессоре. Очень важно, чтобы входные значения от обоих последовательностей поступали только на каждом втором такте. Таким образом, в цикле, который должен начаться согласно схеме на рис. 12.1, накопление будет происходить только в ячейках для у, и у3. Конечно, пользователь такого процессора не должен вставлять пробелы во входные последовательности; это автоматически будет делать процессорная матрица. Неразумно также заставлять пользователя упорядочивать последовательность х в удобное для ввода положение. Ему необходимо только организовать подачу коэффициентов w ча правый порт и значений последовательности х - на левый. Более того, нужно иметь возможность подавать исходные данные для новой задачи на основные порты, не производя специальную перестройку процессора после предыдущей. В алгоритме, о-котором идет речь, предусмотрена организация вывода данных и подготовка к вычислению следующей свертки. С этой целью значения и»г- и Xf сопровождаются флагами, помечающими конец каждой последовательности. Если встречается конец последовательности w, то процессор начинает принимать через линии у вы- 209 ходные значения от левого от себя процессора. В то же время поступает последовательность х, и выходная фаза завершается, когда поступит последний элемент х. При этом процессор 1 сохраняет новую последовательность коэффициентов w до тех пор, пока не поступит последний элемент х, а затем обнуляет свои значения у, подготавливаясь к новой задаче. Заметим, что алгоритм будет выполняться до тех пор, пока длина последовательности х не превышает длины последовательности w на величину, равную числу процессоров, Глобальная синхронизация неявно задается условием, согласно которому каждое выполнение оператора OMEGA происходит в течение одного цикла каждого процессора. Процессоры не определены как явные синтаксические элементы, но присутствуют неявно в виде совокупности операций, выполняемых над элементами Xj,>?- для каждого конкретного значения индекса i. Синтаксическая конструкция для индивидуальных процессоров вводится в следующем разделе, посвященном локальной синхронизации. Дополнительно подчеркнем, что операторы LET не выполняются до тех пор, пока не кончится выполнение оператора OMEGA, и что они составляют, скорее, множество, а не последовательность операторов присваивания. Если два оператора LET будут сгенерированы для одной и той же цели, то результат их выполнения будет неопределенным (во время выполнения будет сделан произвольный выбор). CONVOLUTION TYPE value & flag-* val REAL flag BOOLEAN CELLS w INTEGER HOLD value & flag CELLS x INTEGER HOLD value & flag "начальная установка флага вовсе/ процессорах" "начальный сброс флага во всех процессорах" CELLS у INTEGER HOLD REAL CELLS state INTEGER HOLD accumulate output wait TYPE in out sequence-> empty I first value & flag rest in out sequence 11 CELLS x in wjny out HOLD in out sequence CELLS cycle HOLD even odd начальное ожидание, кроме процессора n, начальный вывод" "нечетные в исходном состоянии" Заметим, что в примере коэффициент w в определенной выше ячейке служит одновременно конструктором, селектором и именем типа данных. Это определение менее громоздко, чем эквивалентное ему: TYPE W-+WW INTEGER вместе с CELLS W HOLD значение & флаг FUNCTION new y 1 ( ) assgts = TEST REF state 1 accumulate LET у 1 = REF у 1 + val REF x 1 • val REF w 1 IF flag REF w 1 THEN IF flag REF x 1 THEN LET state 1 = wait ELSE LET state 1 = output output LETy 1 = REF у 2 wait NIL FUNCTION pass data 1 ( ) assgts = LET x 1 = REF x 2 TEST REF state 1 accumulate LET w 1 = first REF wjn LET wjn = rest REF wjn wait IF flag REF x 1 THEN LET w 1 = first REF wjn LET wjn - rest REF wjn LET у 1 =0 LET state = accumulate output IF flag REF x 1 THEN LET y out = in.out sequence (REF у 1, TRUE) REF y out TEST REF wjn empty LET state 1 = wait in out sequence LET w 1 = first REF wjn LET wjn = rest REF wjn LET state 1 = accumulate LET у 1 =0 ELSE LET y out = inout sequence (REF у 1. FALSE) REF y Out FUNCTION new y(i INTEGER "1 < i < n") assgts = TEST REF state i accumulate LET у i = REF у i + val REF w i * val REF x i IF flag REF wi THEN IF flag REF x i THEN LET state i = wait ELSE LET state i = output output LET у i = REF у i + 1 IF flag REF xi THEN LET state i = wait wait IF NOT flag REF wi THEN LET у i = val REPx"i * val REF w i LET state i = accumulate FUNCTION pass data(i : integer "1 < i < n") assgts = LET w i = REFwi-1 LET x i = REF x i + 1 FUNCTION new y n( ) assgts = TEST REF state n accumulate LET у n = REFу n + val REF x n • val REF w n IF flag REF w n THEN LET state n = wait wait. IF NOT flag REF w n THEN LET у n = val REF w n * val REF x n LET state n = accumulate output NIL FUNCTION pass dataji( ) assgts = TEST REF state n output DO FOR i = 2 TO n - 1 BY 2 pass.data(i) pass.data.n "предполагается, что n четно" LET cycle = even even pass.data.1 DO FOR i = 3 TO n BY 2 pass.data(i) DO FOR i = 2 TO n - 1 BY 2 new.y(i) new.y.n"предполагается, что n четно" LET cycle = odd TEST REF xjn empty NIL in out sequence LET x n = (0. TRUE) LET state n = wait wait LET w n = REFwn-1 TEST REF x.in empty LET x n = (0. FALSE) LET state n = output in.out.sequence LET x n = first REF xjn LET xjn = rest REF xjn accumulate same as wait Замечание. Состояние "output"процесорного элемента п специально предназначено для приема новой последовательности х. FUNCTION OMEGA = TEST REF cycle odd new y 1 DO FOR i = 3 TO n BY 2 new y(i) Элементы двух (иХи)-матриц А и В присутствуют на входных портах: каждая строка матрицы А поступает на каждый из и портов строк и каждый столбец матрицы В на каждый из п портов столбцов. Всего имеется п Хп процессорных элементов, расположенных в виде квадратной структуры. Строки матрицы А распространяются слева направо, а столбцы матрицы В - сверху вниз. Элемента встречает элемент Ъщ в (/,/)-м процессорном элементе, где накапливается произведение аЪщ. Процессорные элементы не представлены явно как синтаксические элементы, но присутствуют неявно в виде всех операций над с2у, Ъц и с« для данных /, /". Пространство данных имеет следующий вид: MA TRIX MUL TIPLICA TION CELLS a INTEGER INTEGER HOLD REAL CELLS b INTEGER INTEGER HOLD REAL CELLS с INTEGER INTEGER HOLD REAL "в исходном состоянии 0" TYPE input.sequence -» empty I first REAL rest input.sequence 11 CELLS a.in INTEGER bjn INTEGER HOLD "ввод последовательности" CELLS step HOLD fetch executestop"начальная выборка" CELLS k HOLD INTEGER"" исходном состоянии 1" FUNCTION OMEGA = TEST REF step fetch DO FOR ALL (i.j) SUCH THAT 1 <i<n & 1 <j<n & i+i < REF k + 1 IF j = 1 THEN IF i>k -n THEN LET a i j = first REF a in i LET a.in i = rest REF ajn i ELSE NIL ELSE IF i+j>k -n + 1 THEN LET a ij = REF a ij-1 ELSE NIL IF i = 1 THEN IF j>k -n THEN LET b i j = first REF bjn j LET bjn j = rest REF bjn j ELSE NIL ELSE IFi+j>k-n + 1 THEN LET b i j = REF fa i - 1 j ELSE NIL LET step = execute execute DO FOR ALL (i,j) SUCH THAT 1 <i<n & 1 <j<n & i+j < REF k + 1 IFi+j>k-n + 1 THEN LET с i j = REF с i j + REF a i j * REF b i j ELSE NIL 0 ... 31 32 33 34 35 36 37 ... 78 |
