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

Пример
. Вычисление произведения 
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 
сдваивания. На каждом ярусе осуществляется максимально возможное число 
произведений непересекающихся пар чисел, взятых на предыдущем ярусе. В 
общем случае высота параллельной формы равна 
log
2
n.
Эта параллельная 
форма реализуется на 
n/2
процессорах, и загруженность процессоров 
уменьшается от яруса к ярусу. На рис. 23 для 
n = 8
представлен граф 
последовательного применения операции, внизу ‒ граф для принципа 
сдваивания. Начальные вершины символизируют ввод данных. 
Таким образом, если какая-нибудь задача определяется 
n
входными 
данными, то в общем случае не существует алгоритма ее решения с высотой 
менее 
log
2
n.
Если получен алгоритм высоты порядка 
log
a 
n 
, где 
а > 0
, то 
такой алгоритм считается эффективным с точки зрения времени его 
реализации на параллельной вычислительной системе при исключении иных
аспектов реализации. 
Идея абстракции относительно реальной работы параллельных систем, 
допускаемая 
концепцией, 
была 
использована 
в 
математических 
исследованиях и обеспечила появление ряда изобретений в численных 
методах. 
Концепция получила развитие в 1950-1960 годы. Алгоритмы, 
построенные на основе концепции, оказались несостоятельными, в связи с 
действительной сложностью информационных связей между операциями, 
Рис. 23. Последовательный граф и граф сдваивания
 

---

70 
численной неустойчивостью, наличием большого количества конфликтов в 
памяти. Однако, несмотря на недостатки концепции, предельная степень 
абстракции от реальной ситуации в вычислительных системах позволила 
проводить математические исследования, что привело к появлению 
отдельных изобретений в области численных методов.