Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

6.3. Концепция неограниченного параллелизма
 
Необходимость реализации решения задач на параллельных 
вычислительных системах способствовала развитию математической 
концепции 
построения 
параллельных 
алгоритмов 
‒
концепции 
неограниченного параллелизма. Концепция основана на предположении о 
том, что реализация алгоритма на параллельной вычислительной системе, не 

---

68 
накладывает 
на 
алгоритм 
никаких 
ограничений. 
Предполагается 
использование неограниченного числа процессоров, их универсальности и 
работа в синхронном режиме, наличие общей памяти, передача информации 
осуществляются мгновенно и без конфликтов. В рамках концепции 
предполагается реализация алгоритмов минимальной высоты.
Пример
. Вычисление произведения 
n
чисел 
а
1
, а
2
, ..., а
n
, в котором 
отчетливо видна идея, играющая большую роль в построении алгоритмов 
малой высоты [1].
Пусть 
n = 8.
Обычная схема, реализующая процесс последовательного 
умножения, выглядит следующим образом:
Данные а
1
а
2
а
3
а
4
а
5
а
6
а
7 
а
8
Ярус 1 а
1
а
2
Ярус 2 (а
1
а
2
) а
3
Ярус 3 (а
1
а
2
а
3
) а
4
Ярус 4 (а
1
а
2
а
3
а
4
) а
5
Ярус 5 (а
1
а
2
а
3
а
4
а
5
) а
6
Ярус 6 (а
1
а
2
а
3
а
4
а
5
а
6
) а
7 
Ярус 7 (а
1
а
2
а
3
а
4
а
5
а
6
а
7
) a
8
Высота параллельной формы равна 7, ширина равна 1. При данной 
схеме вычисления и наличии более одного процессора, на каждом шаге 
вычисления все процессоры кроме одного будут простаивать. Рассмотрим 
параллельную форму другого алгоритма решения данной задачи:
Данные а
1
а
2
а
3
а
4
а
5
а
6
а
7 
а
8
Ярус 1 а
1
а
2
а
3
а
4
а
5
а
6
а
7
a
8
Ярус 2 (а
1
а
2
) (а
3
а
4
) (а
5
а
6
) (а
7
a
8
) 
Ярус 3 (а
1
а
2
а
3
а
4
) (а
5
а
6
а
7
a
8
) 
Высота параллельной формы равна 3, ширина равна 4. Повышение 
загруженности процессоров работой привело к снижению высоты. Процесс 
построения чисел каждого яруса по описанной схеме называется процессом 

---

69 
сдваивания. На каждом ярусе осуществляется максимально возможное число 
произведений непересекающихся пар чисел, взятых на предыдущем ярусе. В 
общем случае высота параллельной формы равна