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

Обеспечение связности множества внутренних узлов доменов 
На рисунке 41 показаны две части домена, состоящего из разрозненных 
фрагментов сетки. Формирование таких доменов является одним из 
существенных 
недостатков, 
присущих 
иерархическим 
методам 
декомпозиции графов. 
Рис. 40. Классическая декомпозиция 
Рис. 41. Две части домена, состоящего из разрозненных фрагментов сетки 

---

Граф такого домена ‒ фрагментирован. Формирование подобных разбиений 
характерно для пакетов, подобных ParMetis (или его последовательной 
версии Metis). Это бесплатный пакет и библиотека функций, широко 
используемые на практике для решения задач декомпозиции сеток. Но при 
большом числе доменов и процессоров, полученные с помощью стандартных 
пакетов решения содержат артефакты, в том числе пустые домены и 
несвязные домены. Фрагментированные домены снижают эффективность 
проводимых на их основе расчетов. Так как вершины макрографа, 
соответствующие несвязным доменам имеют большую, чем остальные, 
степень. Следовательно, процессоры, обрабатывающие фрагментированные 
домены, затрачивают большее время на обмен данными в связи ростом 
объема передаваемых данных, и числа актов приема-передачи данных. 
Фрагментированность домена может приводить к снижению эффективности 
компрессии сеточных функций (уменьшения объема данных, описывающих 
исходную функцию).
Декомпозиция на основе исходной нумерации узлов 
Данный метод позволяет получать декомпозицию, удовлетворяющую 
соответствующим критериям. Метод используется при первоначальном 
распределении по процессорам больших сеток для последующего решения 
самой задачи декомпозиции. 

---

128 
Нерегулярная сетка представляет ‒ множество последовательно 
пронумерованных узлов, между которыми определены некоторые связи ‒ 
ребра. Рассмотрим распределения узлов по процессорам ‒ распределение по 
исходной нумерации. При разбиении сетки, содержащей n узлов на p 
доменов, в домен с номером k можно отнести узлы с номерами от kn/p до 
(k+1) n/p – 1. Это гарантирует равномерность распределения узлов, но 
приводит к тому, что границы между доменами проходят по большому числу 
ребер (рис. 42 ). 
Отдельные точки, на рис. 42, имеющие соседние номера, будут 
назначены одному процессору. В результате, при расчете каждого шага по 
времени потребуется передача информации обо всех узлах домена между 
процессором обрабатывающим этот домен и практически всеми остальными 
процессорами. В этом случае оценка времени выполнения алгоритма:
Этот метод, полезен для предварительного распределения узлов. 
Рис. 42. Границы между доменами, проходящие по большому числу ребер 
(37) 

---

129