Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 100 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

функциональных устройств либо эквивалентной цепочкой быстро
работающих функциональных устройств, либо совокупностью па-
раллельно работающих функциональных устройств с циклической
подачей на них обрабатываемых данных.
Синхронный режим наиболее целесообразен, поэтому будем
считать в дальнейшем, что безусловный конвейерный вычислитель
работает синхронном режиме с циклом 1, а данные поступают на
входы безусловных конвейерных вычислителей единовременно в
последовательные моменты времени (с шагом 1).
Таким образом, начиная с установления режима безусловного
конвейерного вычислителя реализация алгоритма происходит с по-
лучением в каждый момент времени данных на входы и выдачей
результатов на все выходы.
Для того чтобы вывести безусловный конвейерный вычисли-
тель на режим счета, необходимо обеспечить данными все его функ-
циональные устройства. Это производится в период загрузки без-
условного конвейерного вычислителя. В отличие от работы в уста-
новившемся режиме, в период загрузки данные поступают не толь-
ко через входы безусловного конвейерного вычислителя (которые
будем называть основными), но и через так называемые дополни-
тельные входы, работающие только в период загрузки. В частности,
если безусловный конвейерный вычислитель имеет контуры, то без
дополнительных входов обойтись невозможно, ибо нельзя для них
подать информацию через основные входы.
Опишем процесс загрузки, который в дальнейшем будем на-
зывать стандартным. Каждой дуге графа поставим в соответствие
число, равное длине элементарного минимального пути графа из
какого-либо входа безусловного конвейерного вычислителя в ту
вершину, для которой эта дуга является выходной. Для j-й верши-
ны рассмотрим множество целых чисел, соответствующих ее вхо-
дам; наименьшее из них обозначим через m
j
. Пусть l
ij
— входная
дуга, а M
ij
— соответствующее ей число. Если M
ij
> m
j
, то дугу l
ij
разомкнем и по образовавшемуся дополнительному входу подадим
данные последовательно M
ij
− m
j
раз, после чего дополнительный
вход устраним (дугу замкнем). Подобную закачку данных произве-
дем для всех дуг с указанным свойством M
ij
> m
j
. Процесс разре-
зания дуг и подключения дополнительных входов фактически озна-
чает уравновешивание использующихся неуравновешенных циклов.
Таким образом, имеется общее между процессом загрузки и процес-
101

Страницы