ВУЗ:
Составители:
69
Для большинства практических задач при декомпозиции по данным вы-
числения в каждой области не могут быть полностью независимыми. В частно-
сти, после каждой итерации (проведения вычислений во всех точках области)
возникает потребность обмена результатами вычислений на границах соседних
областей. Это, например, характерно для большинства сеточных методов, в ко-
торых для вычисления значения функции в некотором узле используются ее
значения в нескольких соседних узлах. В этом случае выполнение указанных
выше требований: сбалансированность загрузки процессоров и минимизация
информационных обменов, зависит не только от размеров подобластей, но так-
же и от их формы.
Например, в случае дву-
мерной задачи наиболее часто
используется один из двух ти-
пов декомпозиции: область
может быть разделена на от-
дельные строки (или последо-
вательные группы строк) – так
называемая ленточная схема
разделения данных, либо на
прямоугольные наборы эле-
ментов – блочная схема разделения данных (см. рис. 5.3). Возникает естествен-
ный вопрос: какая из этих схем декомпозиции «лучше»?
Выбор одной из указанных схем декомпозиции диктуется требованием ми-
нимизации пересылок данных между процессорами. Рассмотрим эту задачу для
двумерного случая. Будем полагать, что области заданы в виде прямоугольни-
ков или квадратов, ширина полос данных в окрестности границ, которыми
должны обмениваться процессоры, не зависит от направления границ фрагмен-
тов, а объем передаваемых данных определяется длиной сопряженных границ
фрагментов. Приведем простой пример декомпозиции двумерной области,
Рис. 5.3
Разделение данных на области:
а – ленточная схема, б – блочная схема
Страницы
- « первая
- ‹ предыдущая
- …
- 67
- 68
- 69
- 70
- 71
- …
- следующая ›
- последняя »
