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

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; 
} 
Для выполнения параллельного алгоритма около 
10
n/4,75
процессоров. 
Оценка числа операций этого алгоритма составляет 
(n 
–
2).
Глубина самой 
длинной ветви рекурсии составит 
(n-2).
Выполнение 
(n-2)
операций 
осуществляется последовательно. 
Параллельный алгоритм должен выполняться быстрее, чем самый 
оптимальный из последовательных алгоритмов, реализующих решение 
задачи.
 

---

73 
7.1. Классификация алгоритмов по типу параллелизма
 
1. Алгоритмы, использующие параллелизм данных (Data Parallelism). 
Этот тип параллелизма характерен для численных алгоритмов обработки, 
имеющих дело с большими массивами, представляемыми, например, в виде 
векторов и матриц. Простейшим примером такой задачи является, например, 
процедура перемножения двух матриц. 
2. Алгоритмы с распределением данных (Data Partitioning). Это 
разновидность параллелизма данных, при котором пространство данных 
может быть разделено на непересекающиеся области, с каждой из которых 
связаны независимые процессы, оперирующие каждый со своими данными. 
Требуется лишь редкий обмен между этими процессами. 
3. Релаксационные алгоритмы (Relaxed Algorithm). Алгоритм может 
быть представлен в виде независимых процессов без синхронизации связи 
между ними, но процессоры должны иметь доступ к общим данным. 
4. Алгоритмы с синхронизацией итераций (Synchronous Iteration). 
Многие из стандартных численных итерационных параллельных алгоритмов 
процессоры завершили предыдущую итерацию. 
Самовоспроизводящиеся задачи (Replicated Workers). Для задач этого 
класса создается и поддерживается центральный пул (хранилище) похожих 
вычислительных задач. Параллельно реализуемые процессы осуществляют 
выбор задач из пула, выполнение требуемых вычислений и добавление 
новых задач к пулу. Вычисления заканчиваются, когда пул пуст. Эта 
технология характерна для исследований графа или дерева. 
Конвейерные вычисления (Pipelined Computation). Этот тип 
вычислений характерен для процессов, которые могут быть представлены в 
виде некоторой регулярной структуры, например, в виде кольца или 
двумерной сети. Каждый процесс, находящийся в узле этой структуры, 
реализует определенную фазу вычислений.