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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Высота такой параллельной формы равна 3, ширина — 4. Про-
цесс подобного вида называется схемой сдваивания. Для его реали-
зации нужно на каждом ярусе осуществлять максимально возмож-
ное число попарно не пересекающихся перемножений чисел, полу-
ченных на предыдущем ярусе.
§ 7. О концепции неограниченного параллелизма
Концепция неограниченного параллелизма предполагает ис-
пользование идеализированной модели неограниченной параллель-
ной вычислительной системы.
Неограниченной параллельной вычислительной системой бу-
дем называть систему, работа которой производится в течение неко-
торого количества единиц дискретного времени, называемых так-
тами, и которая обладает следующими свойствами:
1) система имеет любое нужное число идентичных процессо-
ров;
2) система имеет произвольно большую память, одновременно
доступную всем процессорам;
3) каждый процессор за упомянутую единицу времени может
выполнить любую унарную или бинарную операцию из некоторого
априори заданного множества операций; операции из этого множе-
ства будем называть основными;
4) время выполнения всех вспомогательных операций (т.е. опе-
раций, не являющихся основными), время взаимодействия с памя-
тью и время, затрачиваемое на управление процессором, считаются
пренебрежимо малыми;
5) никакие конфликты при общении с памятью не возникают;
6) все входные данные перед началом работы системы записа-
ны в память;
7) после окончания вычислительного процесса все результаты
остаются в памяти.
§ 8. О схеме сдваивания
В дальнейшем символом dae обозначаем ближайшее к a целое
число не меньшее числа a .
Теорема 8.1. Высота h параллельной формы умножения n
чисел, соответствующей схеме сдваивания равна dlog
2
ne, а ее ши-
рина w не превосходит dn/2e.
21

Страницы