ВУЗ:
Составители:
63
(data parallel). Если алгоритм основан на параллелизме задач, вычислительная
задача разбивается на несколько, относительно самостоятельных подзадач, ка-
ждая из которых загружается в "свой" процессор. Каждая подзадача реализует-
ся независимо, но использует общие данные и/или обменивается результатами
своей работы с другими подзадачами. Для реализации такого алгоритма на
многопроцессорной системе необходимо выявлять независимые подзадачи, ко-
торые могут выполняться параллельно. Часто это оказывается далеко не оче-
видной и весьма трудной задачей. Методика решения этой задачи будет рас-
смотрена в следующем разделе.
При наличии в алгоритме свойства параллелизма данных, одна операция
может выполняться сразу над всеми элементами массива данных. В этом случае
различные фрагменты массива могут обрабатываться независимо на разных
процессорах. Для алгоритмов этого типа распределение данных между
процессорами обычно осуществляется до выполнения задачи на ЭВМ.
Построение алгоритма, обладающего свойством параллелизма данных, и
подбор подходящей архитектуры компьютера для него могут выполняться с
использованием достаточно простых методик, не требующих применения
сложного математического аппарата.
Для того чтобы в полной мере использовать структурные свойства
алгоритма, необходимо прежде всего выявить, к какому типу он относится.
Ниже приводится общая классификация алгоритмов, с точки зрения типа
параллелизма, заимствованная из работы [10].
1. Алгоритмы, использующие параллелизм данных (Data Parallelism). Этот
тип параллелизма характерен для численных алгоритмов обработки, имеющих
дело с большими массивами, представляемыми, например, в виде векторов и
матриц. Простейшим примером такой задачи является, например, процедура
перемножения двух матриц.
2. Алгоритмы с распределением данных (Data Partitioning). Это разновид-
ность параллелизма данных, при котором пространство данных может быть
Страницы
- « первая
- ‹ предыдущая
- …
- 61
- 62
- 63
- 64
- 65
- …
- следующая ›
- последняя »
