20150422_mipt11_GraphPart (Лекции)

Рациональная декомпозициясетокЯкобовский М.В.lira@imamod.ruwww://lira.imamod.ruОграничения• ЗаконАмдаля100%90%80%Эффективность1S  p 1 aap1E p 1  a p  1a=.0001a=.001a=.01a - доля последовательных действий70%60%50%40%30%20%10%0%025050075010001250150017502000Число процессоров••••Пакетный режим исполнения и отладки приложенийПроцедуры авторизованного доступа к удаленным системамВысокая динамика изменения конфигурации суперкомпьютеровНесоизмеримость ресурсов рабочей станции пользователя исуперкомпьютера2Статическая балансировказагрузки• Критериидекомпозиции• Инкрементныйалгоритмдекомпозиции• Иерархическаяобработкабольших сеток3Простое разбиение на 32 доменаРациональное разбиениена 32 доменаРациональное разбиениена 8 доменов• Статическая балансировка загрузкиG  V , E , V  vi , V  nRV   V1 ,,V ppV  Vk , Vi V j  , i  jk 1min  J  max   wvi     wvi , v j R V k 1,, pvi Vk v j Vk8Критерии декомпозиции графов• Равномерноераспределение суммарноговеса узлов/рёбер• Минимизациямаксимального весаисходящих из доменаребер / Минимизациясуммарного весаразрезанных ребер9Критерии декомпозиции графов• Исключение связей междудоменами• Минимизация суммарноговеса разрезанных реберTHREAD 134560THREAD 01245THREAD 13THREAD 0601210Критерии декомпозиции графов• Минимизациямаксимальной степенидоменовА.Н.

Андрианов, А.В. Жохова, Б.Н. ЧетверушкинПроцессоров 11314763New_sort13.595.594.384.16METIS13.61 11.00 11.10 10.5611Критерии декомпозиции графов• Обеспечение связностидоменов• Обеспечение связностимножества внутреннихузлов доменов1225/4 = 4 ? 6 ? 9• Разрезать решетку 5 х 5 на 4 части13Декомпозиция сетки из 25 узлов на 4части1425/4 = 4 ? 6 ? 9• Декомпозиция решетки 5 х 5 на 4домена46• Дисбаланс 9/4=2.25156925/4 = 4 ? 6 ? 9• Декомпозиция решетки 5 х 5 на 2домена• Дисбаланс 13/12 : 8%1625/4 = 4 ? 6 ? 9• Декомпозиция решетки 5 х 5 на 4домена• Дисбаланс 7/6 : 17%1725/4 = 4 ? 6 ? 9• Декомпозиция решетки 5 х 5 на 4домена46• Дисбаланс 9/4=2.256925/4 = 4 ? 6 ? 9• Декомпозиция решетки 5 х 5 на 4домена46• Дисбаланс 9/4=2.256925/4 = 4 ? 6 ? 9• Декомпозиция решетки 5 х 5 на 4доменаПотери4669• Дисбаланс 9/4=2.259/6.25=1.44Потери9/7=1.29Декомпозиция сетки 25х25 на 7 частейРазрезано ребер107Пакеты декомпозиции графовChacoBruce HendricksonRobert LelandParMETISGeorge KarypisVipin KumarPARTYRobert Prais, et al.JOSTLEChris Walshaw, et al.SCOTCHFrancois Pellegrini23Иерархический алгоритмОгрублениеДекомпозиция24Огрубление графаСпектральный метод1010  2 0111  0 3 0 10 3 011 A10 2 01  0 111030 01110  3 2  1364152x2   2,  1, 1,  2, 1,  1s   4, 2, 6, 3, 5, 126Спектральная бисекцияПустьq[i]={-1,1}потребуем, что быТогда число разрезанных реберСпектральный методНормировкадля собственных значений ивекторов число разрезанных ребер будетравноРазбиение вершин на два множестваДля минимизацииследует найтиминимальное собственное число исоответствующий ему собственный вектор– вектор ФидлераОн ортогонален вектору соответствующемунулевому- единичному векторуСледовательно- множества{-1} и {1} содержат одинаковое число вершинРекурсивная бисекцияБинарное дерево разрезовМетод спектральной бисекции32Локальное уточнение63163122774545Kernighan-Lin (KL)и Fiduccia-Mattheyses (FM)33Инкрементный алгоритмдекомпозиции графа1.

инициализация доменов2. распределение вершин по доменамметодом инкрементного роста3. локальное уточнение границсформированных доменов4. анализ связности ядерсформированных доменов и окончаниеработы, если заданный уровеньсвязности достигнут5. перенос части закрепленных задоменами вершин в группу свободныхвершин и переход к этапу 2.34Связность ядер доменовd i   min : A k vi  B  kTk 1  ATk \ Tk \ Tk 1 , T1  35Связность ядер доменовd i   min : A k vi  B  kTk 1  ATk \ Tk \ Tk 1 , T1  36Связность ядер доменовd i   min : A k vi  B  kTk 1  ATk \ Tk \ Tk 1 , T1  37Оболочки38Инкрементныйалгоритмдекомпозицииграфа39Инкрементныйалгоритмдекомпозицииграфа40Инкрементныйалгоритмдекомпозицииграфа41Инкрементныйалгоритмдекомпозицииграфа42Редуцирование доменоводин доменасвободные вершиныб43Инкрементный алгоритм, Dm=2544Kmetis, Dm=25Треугольная сетка из 75790 вершин(пространство вокруг крыла)результат геометрическойдекомпозиции на 5 групп(в дальнейшем каждый процессорсчитывает свою группу вершин)результат перераспределениямалых блоков вершинФрагмент треугольной сетки из 75790вершинрезультат геометрическойдекомпозициирезультат перераспределениямалых блоков вершинИнкрементный алгоритм, Dm=25Результат локального разбиения сетки из 75790 вершинна 50 доменов на 5 процессорахРезультат сбора плохих групп доменов и их повторногоразбиенияРазбиение тетраэдральной сетки, содержащей 2∙108узлов, на 125 процессорах•вычисления производились на кластере СКИФ МГу (1250 4-хядерныхпроцессоров, 60 TFlop/s)геометрическаядекомпозицияParMETISчисло доменов80 00020 000время21 сек.10 сек.число вершин в домене2612мин.261310 9322 328макс.среднее число связей ссоседними доменами1414число некомпактныхдоменов229364Формирование макрографаСетка микродоменов51 538 микродоменв каждом около20 узловСетка микродоменоввесчисло% отн.

число1230.01%1330.01%14150.03%15330.06%162280.44%171 3732.66%185 43310.54%1911 71322.73%2014 21827.59%2111 06921.48%225 73711.13%231 5052.92%241920.37%25130.03%2620.00%2710.00%51 538 микродоменДвухуровневое разбиениеIIIВершины макрографаСетка предварительнораспределяются по процессорамразбивается на большое числомикродоменов,образующих макрографМетод эффективен для сверхбольших сетокЛитература1.

Якобовский М.В. Введение в параллельные методы решения задач: Учебноепособие / Предисл.: В. А. Садовничий. – М.: Издательство Московскогоуниверситета, 2013. – 328 с., илл. – (Серия «Суперкомпьютерное образование»)ISBN 978-5-211-06382-22. Fiedler M. Eigenvectors of aciyclic matrices // Czechoslovak Mathematical Journal,25(100) – Praha, 1975. – Pp. 607–618.3. Fiedler M. A property of eigenvectors of nonnegative symmetric matrices and itsapplication to graph theory // Czechoslovak Mathematical Journal. – 25(100) – Praha,1975. – Pp.

619–633.4. George Karypis Family of Graph and Hypergraph Partitioning Software URL:http://glaros.dtc.umn.edu/gkhome/views/metis/5. Bruce Hendrickson, Rob Leland Chaco: Software for Partitioning Graphs. URL:http://www.cs.sandia.gov/~bahendr/chaco.html6. Chris Walshaw JOSTLE — graph partitioning software. URL:http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/7. François Pellegrini Software package and libraries for sequential and parallel graphpartitioning, static mapping, and sparse matrix block ordering, and sequential meshand hypergraph partitioning. URL: http://www.labri.u-bordeaux.fr/~pelegrin/scotch/8. Головченко Е.Н., Якобовский М.В. Библиотека параллельной декомпозициибольших сеток. 2013.

URL: http://lira.imamod.ru/FondProgramm/Decomposition/56Литература9. Евстигнеев В.А. Применение теории графов в программировании / Под ред.А.П. Ершова. – М.: Наука, Главная редакция физико-математическойлитературы, 1985. – 352 с.10. B. Hendrickson, R. Leland. Multilevel Algorithm for Partitioning Graphs //Supercomputing '95 Proceedings. – San Diego, CA, 1995.11. Hendrickson B.

and Leland R. A Multi-Level Algorithm for Partitioning Graphs, Tech.Rep. SAND93-1301, Sandia National Laboratories, Albuquerce, October 1993.12. Hendrickson B. and Leland R. An Improved Spectral Partitioning Algorithm forMapping Parallel Computations. // SIAM J. Comput. Phys.

–March 1995. –Vol. 16. –№ 2. – P. 452–469.13. G.Karypis, V.Kumar. Multilevel k-way partitioning scheme for irregular graphs,Journal of Parallel and Distributed Computing, 48 (1998), pp. 96-129.14. K. Devine, E. Boman, R. Heaphy, B. Hendrickson, and C. Vaughan Zoltan DataManagement Services for Parallel Dynamic Applications. Computing in Science andEngineering, Vol. 4, No. 2, March/April 2002, pp. 90-97.57.