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

4.4. Декомпозиция в задачах с параллелизмом по данным 
Способ разделения вычислений на независимые части зависит от того, 
насколько полно решаемая задача обладает свойством декомпозируемости по 
данным, определяемого местом алгоритма в классификации, приведенной в 
разделе 4.1. Если задача допускает реализацию в классе алгоритмов с 
распределением данных (Data Partitioning), распараллеливание на подзадачи 
существенно облегчается. В данном случае одна операция или совокупность 
операций выполняются над всеми элементами массива данных, а задача 
сводится к разбиению массива исходных данных на фрагменты, обработка 
которых ведется независимо на различных процессорах. При этом обычно 
предъявляются требования обеспечить: 
o
примерно равный объем вычислений в выделяемых подзадачах; 
o
минимальный 
информационный 
обмен 
данными 
между 
процессорами.
Рассмотрим выполнение этих требований при различных условиях. 

---

47 
Простейший и наиболее благоприятный с точки зрения организации 
параллельных вычислений случай, когда вся область исходных данных задачи 
может быть разделена на непересекающиеся области любых размеров, а 
вычисления в каждой области могут вестись независимо. Ясно, что в этом 
случае задача декомпозиции чрезвычайно проста: необходимо всю область 
разбить на подобласти, число которых равно числу доступных процессоров, а 
размеры подобластей подобрать так, чтобы обеспечить их равномерную 
загруженность, с учетом производительности каждого. 
С точки зрения организации вычислений обычно более удобной является 
декомпозиция на области, с границами в виде прямых линий и плоскостей. На 
рис. 4.2 приведены примеры наиболее широко используемых регулярных 
структур базовых подзадач, при декомпозиции по данным. 
Рис. 4.2 Регулярные одно-, двух- и трехмерные структуры базовых 
подзадач после декомпозиции данных 
Для большинства практических задач при декомпозиции по данным 
вычисления в каждой области не могут быть полностью независимыми. В 
частности, после каждой итерации (проведения вычислений во всех точках 
области) возникает потребность обмена результатами вычислений на границах 
соседних областей. Это, например, характерно для большинства сеточных 
методов, в которых для вычисления значения функции в некотором узле 
используются ее значения в нескольких соседних узлах. В этом случае 
выполнение указанных выше требований: сбалансированность загрузки 
процессоров и минимизация информационных обменов, зависит не только от 
размеров подобластей, но также и от их формы. 

---

48 
Рис. 4.3 Разделение данных на области: а – ленточная схема, б – блочная 
схема 
Например, в случае двумерной задачи наиболее часто используется один 
из двух типов декомпозиции: область может быть разделена на отдельные 
строки (или последовательные группы строк) - так называемая ленточная схема