ВУЗ:
Составители:
71
5.5 Блочная декомпозиция с учетом локализации подобластей
Известно, что весьма широкий класс задач реализуется в классе алгорит-
мов с распределением данных (Data Partitioning), в которых пространство дан-
ных может быть разделено на непересекающиеся области, а вычисления могут
осуществляться независимо и требуется лишь редкий обмен между этими про-
цессами. В частности, при моделировании на основе метода конечных элемен-
тов, секционной свертке изображений и др. после каждой итерации осуществ-
ляется обмен данными, полученными на границах соседних областей. Ясно, что
в случае, когда размеры областей, на которые разбивается вся область значе-
ний, одинаковы, объемы пересылаемых данных будут различаться в зависимо-
сти от места расположения области.
Решим задачу такого разбиения исходной области на квадратные блоки с
учетом локализации подобластей, при котором время работы всех процессоров
с учетом пересылок максимально сбалансировано. Для простоты рассмотрим
случай, когда исходная область квадратная: XX, где X – число отсчетов одной
стороны области. Будем полагать, что для заданных: вычислительного алго-
ритма и вычислительной системы, известны константы:
р
– время расчета при
обработке одного отсчета (точки) области и
п
– среднее время, затрачиваемое
на передачу информации, необходимой для одной точки области.
Обычно, с точки зрения удобства организации вычислений, всю область
данных разбивают на прямоугольные фрагменты. Пусть x - сторона фрагмента,
численно равная числу точек. Потребуем, чтобы величина x удовлетворяла не-
равенству
2
4 4
доп n p
x x x
, (5.1)
где
рп
/
– отношение отрезков времени, необходимых для пересылки
данных к времени обработки в расчете на одну точку области, а
доп
- допус-
тимая величина отношения времени пересылок к времени обработки внутрен-
ней области, задаваемая из условия эффективной загрузки процессоров.
Страницы
- « первая
- ‹ предыдущая
- …
- 69
- 70
- 71
- 72
- 73
- …
- следующая ›
- последняя »
