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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

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

Страницы