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

Глава 8. 
Базовые методы построения параллельных алгоритмов: 
метод сдваивания, геометрический параллелизм
 
8.1. 
Базовые методы построения параллельных алгоритмов
 
Параллельные алгоритмы не всегда показывают более высокую, чем 
последовательные алгоритмы, степень эффективности. Несмотря на это 
имеется достаточно большой набор задач, решение которых возможно 
улучшить за счет применения параллельных вычислений. 
Правильность этих методов подтверждена многолетней практикой и 
дает возможность обеспечивать
их применимость для решения самых разных 
задач. Рассмотрим последовательно следующие методы:
- 
метод сдваивания;
- 
метод геометрического параллелизма;
 
Пример
. Определение суммы элементов массива a, содержащего n 
элементов [2]. На рис. 26 приведен пример нахождения суммы 8
-
ми 
элементов массива, используя 4 процессора.
Рис. 26. Нахождения суммы 8
-
ми элементов массива чисел на четырех процессорах 
методом сдваивания

---

79 
Последовательный алгоритм:
 
s=a[1]; 
for(i=2;i<=n;i++) 
s=s+a[i]; 
Будем учитывать только операции сложения чисел, пренебрегая 
операциями, связанными с организацией цикла суммирования, чтением 
элементов массива из памяти и им подобными. Данные операции не важны с 
точки зрения оценки свойств рассматриваемого метода.
Пусть 
τ
А
- 
время выполнения операции сложения двух чисел; 
T
1
- 
время 
работы последовательного алгоритма, тогда: 
Степень параллелизма алгоритма равна 1. 
8.2. Построение параллельного алгоритма методом сдваивания
 
Предположим, что размер массива составляет n = 2
q
. 
В этом случае
количество этапов выполнения алгоритма сдваивания составит q = log
2
n: 
1-
й этап 
- 
n/2 действий, 
2-
й этап 
- n/4, 
…
q-
й –
1. 
Пусть k –
некоторый этап выполнения алгоритма. Тогда степень 
параллелизма на этом этапе составит n/2
k
. Ускорение 
S
p
параллельного 
алгоритма по сравнению с наилучшим последовательным, достигаемое в 
системе из p процессоров, при p = n/2:
где 

‒
доля операций алгоритма, выполнение которых невозможно 
одновременно с другими операциями (операции со степенью параллелизма 
1); E
p 
‒
сверхлинейное ускорение, которое превышает вычислительные 
возможности системы (число процессов для решения вычислительной 
(1)
(2)

---

80 
задачи) 
S
p
> p
. Причины появления сверхлинейного ускорения –
особенности, используемых вычислительных систем, неудачный выбор 
последовательного алгоритма
Метод обеспечивает высокое ускорение и низкую эффективность. При 
n
= 1024 ускорение равно 102, эффективность ‒
20%. Причина низкой 
эффективности в простаивании большей части процессоров на всех стадиях. 
Так как вычисления выполняются на всех стадиях только на первом 
процессоре. Алгоритм предполагает
использование 
n/2
процессоров для 
обработки n элементов. Разобьем массив
, состоящий из n на p одинаковых 
частей. При условии уменьшения количества процессоров, вычисления в 
каждой части будут выполняться двумя этапами на отдельном процессоре: