Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

в системах с общей памятью
. В случае обработки доменов разными 
процессорами можно уменьшить взаимное влияние, вызванное обращением 
разных процессоров к данным, отображаемым в одни и те же строки в кэш
-
памяти. Если речь идет о системах с распределенной памятью, то данный 
подход
позволяет использовать нетрадиционную стратегию 
организации 
работ, предполагающую конечность скорости распространения сигналов в 
природе. При таком подходе обособленные домены (0—5) рассматриваются 
как невзаимодействующие на некотором небольшом интервале времени. 
Таким образом
, 
задача распадается на множество несвязанных. Каждая 
задача решается независимо на отдельном процессоре. Решения для доменов 
первого вида позволяют сформировать граничные условия для доменов 
Рис. 38. Декомпозиция сетки на домены

---

124 
второго вида, обработка которых выполняется на втором этапе. 
Декомпозиция, рассмотренная в данном примере
, 
называется двудольной. 
В общем случае, r
-
дольная декомпозиция графа позволит выполнить 
расщепление задачи на r последовательно обрабатываемых групп 
независимых подзадач. Каждому процессору назначается не один домен, а r 
доменов, по одному из каждой группы, что позволяет равномерно 
задействовать все процессоры на каждом из r этапов. 
Данная технология используется при решении задач неявными 
методами, предполагающими решение на каждом из шагов систем СЛАУ с 
помощью прямых или итерационных методов. Разбиение большой системы 
СЛАУ на множество систем меньшего размера способствует сокращению 
общего времени решения задачи.
3. Минимизация максимальной степени домена
 
Определим понятие макрографа декомпозиции. Макрограф состоит из 
p вершин, каждая из которых соответствует одному домену V
i
разбиения 
исходного графа:
Вес вершины макрографа равен суммарному весу вершин, входящих в 
домен i:
Вес ребра соединяющего
вершины i, j макрографа, равен суммарному 
весу ребер, соединяющих вершины доменов i и j:
Максимальная степень вершины макрографа ‒
число граничащих с ним 
доменов, служит критерием минимизации, который обеспечивает снижение 
(33) 
(34) 
(35) 

---

125 
числа актов обмена данными между процессорами на каждом шаге по 
времени:
где K —
максимально допустимая степень вершины макрографа, 
определяемая особенностями решаемой задачи. Минимизация позволяет 
снизить коммуникационные расходы за счет уменьшения потерь, вызванных 
латентностью каналов передачи данных. 
При использовании адаптивных сеток отсутствие треугольников сетки, 
вершины которых принадлежат трем разным доменам, позволяет упростить 
логику параллельного вычислительного алгоритма.
Например, время расчета на 63 процессорах при использовании
декомпозиции, показанной на рисунке 39 , составило 4,16 секунды, что 
гораздо меньше 10,56 секунд при расчете, использующем классическую 
декомпозицию, представленную на рис. 40. При расчетах использовалась 
одна и та же программа, но узлы вычислительной сетки были распределены 
по доменам разными способами. Выигрыш более чем в два раза получен 
исключительно за счет удачной декомпозиции сетки.
Рис. 39. Декомпозиция
(36)

---

126 
4.