Учебное пособие Казань 018 удк

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

---

43 
сети. Каждый процесс, находящийся в узле этой структуры, реализует 
определенную фазу вычислений. 
Нетрудно заметить, что некоторые алгоритмы из приведенного списка 
обладают явно выраженными свойствами параллелизма задач или 
параллелизма по данным. Вместе с тем ряд алгоритмов в той или иной мере 
обладают обоими указанными свойствами. Это следует учитывать при выборе 
способа и схемы декомпозиции задачи на подзадачи. Далее рассматривается 
основанная на разумных предположениях схема этапов построения 
параллельного алгоритма, основанного на декомпозиции данных.