Лекции по параллельным вычислениям. Гергель В.П - 85 стр.

UptoLike

Составители:

Рубрика:

Далее обновляют матрицу L . Новую i-ю строку в матрице L формируют на

основе ее старого значения и вновь сформированной строки i

с помощью опе-

рации дизъюнкции i=ii

После обновления очередной строки матрицы L i-й столбец матрицы L

полагают равным вновь сформированной i-й строке. Далее с использованием

обновленной матрицы формируют очередную строку i

по правилу, описанно-

му выше. Процесс формирования продолжается до исчерпания строк.

На рис. 6.7 для используемого здесь сквозного примера показано построе-

ние матрицы L логической несовместимости операторов с транзитивными свя-

зями в соответствии с описанными правилами. Матрица логической несовмес-

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

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

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

а) б) в)

Рис. 6.7 Дополнение матрицы логической несовместимости транзитивными

связями: а – матрица S с исключенными входами; б – матрица, составленная из

строк i

; в – обновленная матрица логической несовместимости

При распределении работ между процессорами важно установить множе-

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

ливания выполнения операторов. Для этого необходимо объединить информа-

цию о логической несовместимости операторов и их информационно-

логической связи по следующим правилам.