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

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). Этот тип 
вычислений характерен для процессов, которые могут быть представлены в 
виде некоторой регулярной структуры, например, в виде кольца или 
двумерной сети. Каждый процесс, находящийся в узле этой структуры, 
реализует определенную фазу вычислений.