=Paper=
{{Paper
|id=Vol-1482/583
|storemode=property
|title=Метод уменьшения сложности графа задержек коммуникационной среды вычислительного кластера
(Method for reducing graph of communication delays in for visual analysis)
|pdfUrl=https://ceur-ws.org/Vol-1482/583.pdf
|volume=Vol-1482
}}
==Метод уменьшения сложности графа задержек коммуникационной среды вычислительного кластера
(Method for reducing graph of communication delays in for visual analysis)==
https://ceur-ws.org/Vol-1482/583.pdf
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Ìåòîä óìåíüøåíèÿ ñëîæíîñòè ãðà à çàäåðæåê
êîììóíèêàöèîííîé ñðåäû âû÷èñëèòåëüíîãî êëàñòåðà
Í.Î. Æóêîâ, À.Í. Ñàëüíèêîâ
Ì Ó èìåíè Ì.Â. Ëîìîíîñîâà
 äàííûé ìîìåíò óùåñòâóåò ïðîáëåìà îòîáðàæåíèÿ èí îðìàöèè î çàäåðæêàõ â êîììó-
íèêàöèîííîé ñðåäå. Îòîáðàæåíèå òàêîé èí îðìàöèè â âèäå îðèåíòèðîâàííîãî âçâåøåííîãî
ãðà à äà¼ò âîçìîæíîñòè äëÿ âèçóàëüíîãî àíàëèçà õàðàêòåðèñòèê êîììóíèêàöèîííîé ñðå-
äû. Îäíàêî ïðè òàêîì ïîäõîäå ìû ïîëó÷àåì ãðà îãðîìíîãî ðàñìåðà, ñ î÷åíü áîëüøèì
÷èñëîì ð¼áåð.
Âàæíûì ñ ïðàêòè÷åñêîé òî÷êè çðåíèÿ ÿâëÿåòñÿ òî, ÷òî ÷åì áûñòðåå áóäåò ïîñòðîåí
ãðà òîïîëîãèè ñóïåðêîìïüþòåðà, ÷åì áîëåå íàãëÿäíà áóäåò âèçóàëèçàöèÿ, òåì áûñòðåå
áóäåò íàéäåíà îøèáêà èëè íåïîëàäêà â ðàáîòå âû÷èñëèòåëüíîãî êëàñòåðà. Òàê æå áóäåò
ïðîùå èñïîëüçîâàòü êëàñòåð ñ ìàêñèìàëüíîé ïðîèçâîäèòåëüíîñòüþ, òàê êàê áóäåò ïðîùå
ïîäîãíàòü ïðîãðàììó ïîä àðõèòåêòóðó êîíêðåòíîãî âû÷èñëèòåëüíîãî êëàñòåðà.
 ïðåäûäóùåé ðàáîòå [1℄ áûë ïðåäëîæåí ìåòîä, êîãäà ãðà çàäåðæåê â êîììóíèêà-
öèîííîé ñðåäå îòîáðàæàåòñÿ â òð¼õìåðíîì ïðîñòðàíñòâå ñëåäóþùèì îáðàçîì: æäîé âåð-
øèíå ñòàâèòñÿ â ñîîòâåòñòâèå òî÷êà ñ òð¼õìåðíûìè êîîðäèíàòàìè, à ðåáðî ïðåäñòàâëÿåòñÿ
â âèäå îòðåçêà, ñîåäèíÿþùåãî äâå ñîîòâåòñòâóþùèå âåðøèíû (òî÷êè). Äëèíû âñåõ îòðåç-
êîâ ïðîïîðöèîíàëüíû âåëè÷åíå çàäåðæêè ïðè ïåðåäà÷å. Îòîáðàæåíèå ñòðîèòñÿ ïðè ïîìî-
ùè ìåòîäà ìíîãîìåðíîãî øêàëèðîâàíèÿ. Ïðåäëîæåííûé ìåòîä èíòåãðèðîâàí ñ ïðîãðàììó
network_viewer2 [2℄.
Ïðåäïîëàãàåìûé â äàííîé ðàáîòå ìåòîä îñóùåñòâëÿåò ïðåäâàðèòåëüíîå ñæàòèå ãðà-
à, Ñæàòèå âûïîëíÿåòñÿ â íåñêîëüêî ýòàïîâ. Âíà÷àëå ãðà ðàçáèâàåòñÿ, èñïîëüçóÿ ñïåöè-
àëüíûå àëãîðèòìû ðàçáèåíèÿ ãðà îâ, çàòåì ïîäãðà âñå âåðøèíû êîòîðîãî ïðèíàäëåæàò
îäíîé ãðóïïå ñæèìàþòñÿ â âåðøèíó. Àëãîðèòì ïàðàìåòðèçîâàí ïàðàìåòðîì ¾ñòåïåíü ñæà-
òèÿ¿, êîòîðûé çàäà¼ò äîïóñòèìóþ ðàçíèöó ìåæäó ðàññòîÿíèìè âíóòðè ãðóïïû âåðøèí è
ìåæäó ãðóïïàìè. Â èíòåð åéñå ïðîãðàììû network_viewer2 äëÿ áîëåå äåòàëüíîãî ïðî-
ñìîòðà ãðà à ðåàëèçóåòñÿ âîçìîæíîñòü ðàñêðûòèÿ âåðøèíû, ñîîòâåòñòâóþùåé ãðóïïå â
êîòîðóþ áûë ñæàò ïîäãðà . Ê ìåòîäó ïðåäúÿâëÿþòñÿ ñëåäóþùèå òðåáîâàíèÿ:
1. ñîõðàíåíèå îòíîñèòåëüíîé äëèíû äóã ãðà à;
2. ðàçáèâàåòñÿ ãðà òàêèì îáðàçîì, ÷òî ñóììà âåñîâ ðåáåð âíóòðè ïîäãðà à ìåíüøå,
÷åì ìåæäó ïîäãðà îì è äðóãèìè ðåáðàìè ãðà à;
3. âåñ ðåáðà ìåæäó äâóìÿ âåðøèíàìè â ñæàòîì ãðà å åñòü ñðåäíåå àðè ìåòè÷åñêîå âñåõ
âåñîâ ðåáåð, ñîåäèíÿþùèõ âñå âåðøèíû â äàííûõ ïîäãðà àõ.
Òàê æå äëÿ âûÿâëåíèÿ èåðàðõè÷åñêîé ñòðóêòóðû ãðà à ðåàëèçóåòñÿ ìåòîä ñæàòèÿ, îñíî-
âàííûé íà èåðàðõè÷åñêèõ àëãîðèòìàõ êëàñòåðèçàöèè.
Àëãîðèòì ðàáîòàåò íà ïîñòðîåíèè èåðàðõè÷åñêèõ ìíîæåñòâ. Íà êàæäîì øàãå ïðîèç-
âîäèòñÿ ðàçáèåíèå ãðà à íà ìíîæåñòâî ïîäãðà îâ. Çäåñü ñòðîèòñÿ ìàññèâ, ãäå ýëåìåíò
ýòî íîìåð êëàñòåðà â ñëåäóþùåé èåðàðõèè. Ïðîöåññ ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà ÷èñëî
âåðøèí íå äîñòèãíåò óêàçàííîãî ïîëüçîâàòåëåì â ïàðàìåòðàõ àëãîðèòìà. Â äàëüíåéøåì, â
ðàìêàõ ïðîöåäóðû ¾ðàñêðûòèÿ âåðøèíû¿ â ãðà äîáàâëÿþòñÿ âåðøèíû äëÿ êëàñòåðà èç
ïðåäûäóùåé èåðàðõèè.
åàëèçàöèÿ àëãîðèòìîâ âûïîëíåíà íà ÿçûêàõ Ñ, C++, ãðà è÷åñêèé ïîëüçîâàòåëüñêèé
èíòåð åéñ íàïèñàí ñ èñïîëüçîâàíèåì êðîññïëàò îðìåííîé áèáëèîòåêè Qt. Âèçóàëèçàöèÿ
ãðà îâ ïðîèñõîäèò ñ ïîìîùüþ áèáëèîòåêè OpenGL, óíêöèîíàë êîòîðîé ïðåäîñòàâëåí Qt-
ìîäóëåì QtOpenGL.
583
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
àáîòà ïðîãðàììû îïðîáîâàíà íà äàííûõ çàäåðæåê ïîëó÷åíûõ ñ ñóïåðêîìïüþòåðà ¾Ëî-
ìîíîñîâ¿ äëÿ 1000 óçëîâ, ÷òî ñîîòâåòñòâóåò ÷åòâ¼ðòîé ÷àñòè âñåõ óçëîâ îáùåäîñòóïíîé
î÷åðåäè ¾regular4¿.
Ïðîãðàììà âðåìåííûå õàðàêòåðèñòèêè ðàáîòû ïðåäñòàâëåíû â òàáëèöàõ 1 è 2.
Òàáëèöà 1: âðåìÿ ðàáîòû ïðîãðàììû â çàâèñèìîñòè îò ÷èñëà ð¼áåð
×èñëî ðàçáèåíèé ÷èñëî ð¼áåð âðåìÿ (ìñ.)
0(ïîëíûé ãðà ) 123064 1968254
100 4465 > 400
50 1225 > 100
10 45 > 10
Òàáëèöà 2: âðåìÿ ðàáîòû àëãîðèòìà êëàñòåðèçàöèè â çàâèñèìîñòè îò ñîîòíîøåíèÿ
ðàçíîñòè ðàññòîÿíèé âíóòðè êëàñòåðà è ñíàðóæè
ðàçíîñòü % ÷èñëî ð¼áåð âðåìÿ (ìñ.)
40 2211 29640
20 2080 27520
7 105 3230
3 3 10
Ëèòåðàòóðà
1. Bannikov P.S, Salnikov A.N. Retrieving topology of inter onne tions in omputational
luster based on results of MPI ben hmarks // Mos ow University Computational
Mathemati s and Cyberneti s. 2014. Vol. 38, no. 2. P. 7382. DOI:
10.3103/S0278641914020022
2. Ñàéò ïðîåêòà ïî òåñòèðîâàíèþ âû÷èñëèòåëüíûõ êëàñòåðîâ ¾ClustBen h¿:
URL: https://github. om/ lustben h/network-tests2 (Äàòà îáðàùåíèÿ 15.06.2015)
584
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Method for reducing graph of communication delays in for visual
analysis
Alexey Salnikov and Nikolay Zhukov
Keywords: weighted graphs, clustering algorithm, communications delays, compute cluster
There discussed methods for visualizing huge graphs where edges marked by distances
between vertices. The goal is to reduce graph complexity of huge graph in context of visual
analysis of delays. There we have used some methods of clusterization which save egde
distances. This method usability has been tested on data about delays arrived in
communications of Lomonosov supercomputer.