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

i
, 
k.
Элемент 
c
kj
рассылается по всем вершинам, имеющим те же самые 
координаты 
k, j.
Для 
n = 2
эти рассылки показаны на рис. 24 б. Все вершины 
соответствуют операциям вида 
а + bc
. 
 
Глава 7. Параллельные алгоритмы 
Параллельный алгоритм – алгоритм, предназначенный для реализации 
на параллельной вычислительной системе. Рассмотрим
задачу вычисления 
чисел Фибоначчи, решение которой реализовано в виде последовательного и 
параллельного алгоритмов.
Математическая модель
Пример [2]. Пусть последовательность Фибоначчи задана рекурентным 
соотношением 
F(n) = F(n – 1) + F(n – 2), при F(0) = 1 и F(1) = 1
. Определить 
значение элемента n (для n>1). 
Последовательный рекурсивный алгоритм 
F(n) 
{ 
if(n<2) return 1; 
return F(n-2)+F(n-1); 
} 
Обозначим как 
G(n)
число операций для вычисления числа 
F(n).
G(n) = G(n – 1) + G(n – 2) + 1,
где

---

72 
G(n – 1) 
– количество операций, необходимое для вычисления чисе
л F(n – 1), 
G(n – 2) - количество операций, необходимое для вычисления чисел F(n – 2),
1 – одна операция для нахождения суммы. 
Определяем: 
G(0) = 0, G(1) = 0. G
A1
(n) = F(n) – 1 
И получаем оценку: 
0
 
 
 
 
Параллельный рекурсивный алгоритм 
Предположим, что каждая из функций 
F(n – 2)
и 
F(n – 1)
обрабатывается на отдельном процессоре [2].
F(n) 
{ if(n<2) return 1; 
Процессор 1 Процессор 2 
a= F(n-2) b= F(n-1) 
return a+b; 
} 
Для выполнения параллельного алгоритма около