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

разделения данных, либо на прямоугольные наборы элементов - блочная схема 
разделения данных (см. рис. 4.3). Возникает естественный вопрос: какая из этих 
схем декомпозиции «лучше»? 
Выбор одной из указанных схем декомпозиции диктуется требованием 
минимизации пересылок данных между процессорами. Рассмотрим эту задачу 
для двумерного случая. Будем полагать, что области заданы в виде 
прямоугольников или квадратов, ширина полос данных в окрестности границ, 
которыми должны обмениваться процессоры, не зависит от направления границ 
фрагментов, а объем передаваемых данных определяется длиной сопряженных 
границ фрагментов. Приведем простой пример декомпозиции двумерной 
области, имеющей размеры 
𝐻 × 𝐿, 𝐻 ≥ 𝐿
. При декомпозиции области данных 
на четыре подобласти (процессора) общий объем передаваемых данных при 
ленточном разделении данных (вдоль стороны 
L
) пропорционален 
3L
, а при 
блочном (на равные прямоугольники) - 
H+L
. 
Объем максимального межпроцессорного обмена данными между парами 
процессоров, обрабатывающих соседние области, составит соответственно 
L
и 

---

49 
H/2
. Нетрудно заметить одинаковый общий и максимальный межпроцессорный 
обмены имеют место при 
H=2L
. Если 
H<2L
, выгоднее блочная декомпозиция, 
при 
H>2L
- ленточная. Ясно, что при другом числе процессоров (подобластей) 
результаты могут оказаться иными. 
Если оказалось, что выгоднее блочная декомпозиция, то следующий 
важный вопрос - выбор размеров блоков. С точки зрения минимизации 
отношения длины граничных областей к их площади (пропорционального 
отношению объема межпроцессорного обмена к объему вычислений в данной 
подобласти) представляется, что форму подобластей следует взять в виде 
квадратов или прямоугольников близким к квадратам. Однако при этом 
возникает еще одна проблема. 
При разбиении исходной области обработки данных на квадраты 
одинаковых размеров для фрагментов, расположенных на границах 
декомпозируемой области, длина границ, сопряженных с соседними 
фрагментами, а, следовательно, и объем передаваемых данных, будет меньше. 
Указанное различие во времени передачи данных может оказывать 
существенное влияние на эффективность использования процессоров, если 
скорость передачи данных низкая. Неэффективность использования 
процессоров более заметна, когда число областей, на которые разбивается 
изображение, невелико. 
Повышение эффективности использования процессоров может быть 
достигнуто увеличением размеров областей, находящихся на границах и в 
углах изображения. В следующем разделе этот вопрос будет детально 
рассмотрен для случая блочной декомпозиции.