    
Раздел: Документация
0 ... 32 33 34 35 36 37 38 ... 78 !FREFk = 3n-2 THEN LET step = stop ELSE LET к = REF к + 1 LET step = fetch stop NIL Замечание. Выражение DO FOR ALL. .. SUCHTHAT. . . не является правильной записью в исполняемом синтаксисе. Оно используется для более ясного понимания того преобразования, которое выполняется синтаксически правильной конструкцией. 12.4. ЛОКАЛЬНАЯ СИНХРОНИЗАЦИЯ В предыдущих примерах процессорные элементы не были представлены явно, а подразумевались неявно только в виде операций, встречающихся в определенных группах ячеек. Теперь введем конструкции подпространство и синхронизируемая ячейка. Процессорные элементы будут отождествляться с подпространством. Это позволит выразить локальную синхронизацию. 12.4.1. Понятие подпространства Вначале дадим теоретическое определение понятия подпространства. Определение. Пространство данных с недетерминированной системой перехода (X, р), т. е. в случае; когда р есть отношение, а не функция на множестве X, называется недетерминированным. Пусть [х, &\ для недетерминированного пространства данных (X,р) элемента х множества X и подмножества jF множества ,Jf обозначает подмножество X вида \У !/(>) =/(-\) для всех /е - (Будем считать, что для z е \х, .?] и/G.F функции f(z) и /(а) совпадают, хотя по существу они разные из-за различия областей определения.) Пространство данных (X, р) считается подпространством пространства (X р), если. cj jF, X = \x,3F\ х е X, и если из соотношений у Ер (л), х=х, у=у и f(y)=f(x) для всех /<=.? - следует, что у Ер (х). Согласно определению каждый переход подпространства может быть сделан в общем пространстве без учета памяти вне подмножества. Замечание. В нашей предыдущей работе понятие подпространства играло важную роль в связи с разбиением больших пространств на части. Готовится к публикации более обширная теоретическая статья. Параллельные подпространства удобны при изучении алгоритмов, в которых предусмотрено обращение к общей (совместной) памяти. 12.4.2. Простой механизм связи Подмножество функций одного подпространства может иметь непустое пересечение с подмножеством функций JF" другого; ячейки в пересечении являются общими. Синтаксический механизм для построения основного пространства из отдельных подпространств имеет вид SPACE (имя) < определение пространства данных) Любые типы, типы ячеек и функций, заданные в определении пространства данных (за некоторым исключением содержащие новые инструкции, которые будут вскоре объяснены), являются строго локальными. Однако в подпространстве имеется доступ к описанию типа, но в общем случае не к описаниям ячейки или функции, которые являются по отношению к нему глобальными. Единственными разрешенными нелокальными описаниями являются описания ячеек, начинающиеся со слов SHARED или SYNCHRONIZED, например SYNCHRONIZED CELLS х HOLD REAL. Тогда при некоторых условиях, которые здесь полностью не перечисляются, на ячейку х подпространства S можно ссылаться за пределами подпространства, что обозначается выражением S .х. Каждая ячейка синхронизируемого типа может быть: 1)готова к считыванию; 2)готова к записи. Если любой оператор OMEGA подпространства или основного пространства- генерирует операцию REF выборки из ячейки, которая не готова для считывания, переход такого пространства (из состояния в состояние) задерживается до тех пор, пока ячейка не станет готовой к считыванию. После завершения перехода ячейка становится готовой к записи и, следовательно, не готова к считыванию. Аналогично, если в синхронизируемую ячейку предполагается записать информацию о результате выполнения некоторого оператора OMEGA, то переход такого пространства задерживается до тех пор, пока ячейка не подготовится к записи другим пространством. Ссылка вне пространства к ячейке, объявленной синхронизируемой, определяется новой конструкцией EQUIVALENT S1 a, S2.b согласно которой объявляется, что ячейки а кЬ подпространств 51 и 52 соответственно эквивалентны (представляют собой одну и ту же ячейку). Два типа ячеек, к которым относятся ячейки а и fe, должны хранить один и тот же тип данных. Еще раз подчеркнем, что данная запись не предназначена для доказательства корректности. Корректность недетерминированных алгоритмов доказать значительно труднее, чем детерминированных. Поэтому исполняемая спецификация, тема настоящей главы, еще более важна в случае локально синхронизируемых алгоритмов. 12.4.3. Алгоритм сортировки с локальной синхронизацией В качестве примера в терминах пространства данных определим процессорную матрицу, выполняющую алгоритм сортировки. Матрица образуется из подпространств Sj, 1 </ <и, и предназначена для сортировки входной последовательности длиной до п. Алгоритм выполняется следующим образом: подпространства S,- hSi+j связаны каналом связи, достаточным для передачи входных значений, флага и "бита подтверждения". Каждый входной сигнал пропускается через матрицу на основе простого сравнения в каждом процессорном элементе: если новый входной сигнал больше текущего содержимого, то пересылается входной сигнал, иначе пересылается содержимое, а входной сигнал сохраняется. Таким образом, процессорный элемент Sj в конечном счете активизируется от г-го входного сигнала извне. Последний входной сигнал помечается флагом TRUE. Флаг пересылается вместе с входным значением и, таким образом, достигает последнего элемента SV, где к - длина входной последовательности. Процессорный элемент Sk подготавливается для вывода путем выдачи содержимого, помеченного флагом TRUE, в свой канал влево вместе с подтверждением, затем ожидает подтверждения передачи и, наконец, возвращается в исходное состояние. В действительности каждый элемент Sj выполняет те же операции, за исключением того, что Sj, i f=k, помечает свои значения флагом FALSE. По получении подтверждения от правого процессорного элемента данные посылаются налево. Как только встретится флаг TRUE, вместе с элементами S{ бит подтверждения возвращается вправо; S,-е подтверждение сигнализирует во вне, что результат готов; последний выход в отсортированном массиве помечается как TRUE. Предполагается, что по получении его внешней агент возвращает бит подтверждения в исходное состояние. Формальное определение имеет следующий вид: SPACE S, TYPE value & flag > value REAL flag BOOLEAN CELLS contents HOLD REAL SYNCHRONIZED CELLS left right HOLD value & flag SYNCHRONIZED CELLS ack-left ack-right HOLD BOOLEAN CELLS state HOLD idie active send-contents wait-for-ack-left wait-for-ack-right outputting send-last-output Глобальными описаниями для всех подпространств при i = 1,. . . , п - 1 являются EQUIVALENT S,. right, S, +,. left EQUIVALENT S>. ack-right, Si+1 .ack-left Первоначально в переменной ack-left хранится значение FALSE, и это состояние является исходным для каждого элемента Sj. Входные значения подаются в элемент Si слева; последнее значение на входе помечается как TRUE. Вначале все синхронизируемые ячейки готовы к записи. Процессор каждого блока SPACE Sj определяется следующим образом: FUNCTION OMEGA = TEST state idle LET contents = value REF left IF flag REF left THEN LET ack-left = TRUE LET state = send-last-output ELSE LET state = active active IF REF contents > value REF left THEN LET right = (contents, flag REF left) LET contents = value REF left ELSE LET right = REF left IF flag REF left THEN LET state = send-contents ELSE NIL send-contents LET ack-left = TRUE LET left = (REF contents, FALSE) LET state = wait-for-ack-right wait-for-ack-right IF REFack-right THEN LET state = outputting ELSE NIL outputting LET left = REF right IF flag REF right THEN LET ack-right = FALSE LET state = wait-for-ack-left ELSE NIL send-last-output LET left = (REF contents. TRUE) LET state = wait-for-ack-left wait-for-ack-left IF NOT REF ack-left THEN LET state = idle ELSE NIL Это определение задает структуру, представленную на рис. 12.3. Такая конструкция характеризуется не только простотой записи, но и дополнительными преимуществами, состоящими в том, что ее можно снабдить глобальной синхронизированной ячейкой, скажем, input output, объявить ее эквивалентной ячейке SI . left, и тогда эту конструкцию можно будет вставлять в любое пространство данных как подпространство. В охватывающем пространстве одна из ячеек будет объявлена эквивалентной ячейке .input-output сортировщика. Рис. 12.3
ПРИЛОЖЕНИЕ Для алгоритма умножения матриц, представленного в подразд. 12.3.2, приводится распечатка определения пространства данных вместе с трассировкой программы. Для простоты определение OMEGA разбито на вспомогательные функции. В машине пространства данных, использованной для реализации, некоторые из синтаксических сокращений, упомянутых в подразд. 12.2.2, тем не менее не выполнены. Однако отличие в записи минимально. TYPE AJ . А А1 INTEGER А2 INTEGER : TYPE BIJ > В BI INTEGER B2 INTEGER : TYPE CIJ . С C1 INTEGER C2 INTEGER : : TYPE INPUT SEQUENCE > FIRST REAL REST INPUT SEQUENCE : type step > step : : type operation - fetch : execute : stop : : type int cell -» к : n : : type a bjn a in a in s integer : b in b in s integer : : cells aij hold real cells bij hold real cells cij hold real cells a b in hold input.sequence cells step hold operation cells int cell hold integer function a fun с (к integer n integer i integer j integer) assgts = if < i + n 1 if and <j + N1 < + i j + K2 :if = j 1 if > i - к n : let a i j = first ref a in i let ajn i = rest ref ajn i : skip if>+ij + -KN1 let a i j = ref a i - j 1 skip a func к n i + j 1 : a func к n + i 1 1 skip function b func (k integer n integer i integer j integer) assgts = if < i + n 1 if and <j + N1 <+ij + K2 : if = i 1 if > j - к n : let в i j = first ref b in j let bjn j = rest ref bjn j : skip if > + i j + - к n 1 let в i j = ref в - i 1 j skip b func к n i + j 1 : b func к n + i 1 1 skip function c func (k integer n integer i integer j integer) assgts = if < 1 + n 1 if and <j + N1 < + i j + K2 :if > + i j + - к n 1 let с i j = + ref cij * ref a i j ref в skip c func к n i + j 1 : c func к n + i 1 1 skip function cjnit help (n integer ind integer) assgts = if > ind 0 let с ind n = 0.0 let с n ind = 0.0 cjnitjhelp n - ind 1 : skip Волновая процессорная матрица, приведенная в [12], может быть теперь выражена в следующем виде (использование локальной синхронизации вместо глобальной позволяет искривлять волновой фронт). Для каждого /,/, 1<1, / <и, определим SPACE sn SYNCHRONIZED CELLS a.left aright b up b down HOLD REAL CELLS с HOLD REAL "В исходном состоянии О" FUNCTION OMEGA = LET с - REF с + REF a left * REF b.up LET a right = REF a left "за исключением Sln" LET b.down = REF b up"jff исключением S,n" Эквивалентными объявляются EQUIVALENT S.a right. S,jtl.ajeft. (j < n) Si,.b down, S,,, ,.b up (i < n) Процессор на самом деле не завершен, поскольку не обеспечены средства вывода и перестройки структуры для следующей задачи. Это может быть сделано так же, как в алгоритме сортировки. 0 ... 32 33 34 35 36 37 38 ... 78 |
||||||||||||||||||||||||
