20150422_mipt11_GraphPart (1185574)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Рациональная декомпозициясетокЯкобовский М.В.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.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций