Лекции по параллельным вычислениям. Гергель В.П - 68 стр.

UptoLike

Составители:

Рубрика:

разделе 5.1. Если задача допускает реализацию в классе алгоритмов с распреде-

лением данных (Data Partitioning), распараллеливание на подзадачи существен-

но облегчается. В данном случае одна операция или совокупность операций

выполняются над всеми элементами массива данных, а задача сводится к раз-

биению массива исходных данных на фрагменты, обработка которых ведется

независимо на различных процессорах. При этом обычно предъявляются требо-

вания обеспечить:

- примерно равный объем вычислений в выделяемых подзадачах;

- минимальный информационный обмен данными между процессорами.

Рассмотрим выполнение этих требований при различных условиях.

Простейший и наиболее благоприятный с точки зрения организации па-

раллельных вычислений случай, когда вся область исходных данных задачи

может быть разделена на непересекающиеся области любых размеров, а вычис-

ления в каждой области могут вестись независимо. Ясно, что в этом случае за-

дача декомпозиции чрезвычайно проста: необходимо всю область разбить на

подобласти, число которых равно числу доступных процессоров, а размеры по-

добластей подобрать так, чтобы обеспечить их равномерную загруженность, с

учетом производительности каждого.

С точки зрения организации вычислений обычно более удобной является

декомпозиция на области, с границами в виде прямых линий и плоскостей. На

рис. 5.2 приведены примеры наиболее широко используемых регулярных

структур базовых подзадач, при декомпозиции по данным.

Рис. 5.2 Регулярные одно-, двух- и трехмерные структуры

базовых подзадач после декомпозиции данных