Суперкомпьютерные дни в России 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.