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


Обеспечение связности множества внутренних узлов доменов



Download 5,19 Mb.
Pdf ko'rish
bet75/101
Sana16.10.2022
Hajmi5,19 Mb.
#853454
TuriУчебное пособие
1   ...   71   72   73   74   75   76   77   78   ...   101
Bog'liq
fel20E533

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


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


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


129 

Download 5,19 Mb.

Do'stlaringiz bilan baham:
1   ...   71   72   73   74   75   76   77   78   ...   101




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish