=Paper=
{{Paper
|id=Vol-1482/572
|storemode=property
|title=Метод декомпозиции области для суперкомпьютерного моделирования гравитирующих систем
(Domain decomposition method for supercomputer simulation of gravitating systems)
|pdfUrl=https://ceur-ws.org/Vol-1482/572.pdf
|volume=Vol-1482
}}
==Метод декомпозиции области для суперкомпьютерного моделирования гравитирующих систем
(Domain decomposition method for supercomputer simulation of gravitating systems)==
https://ceur-ws.org/Vol-1482/572.pdf
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Ìåòîä äåêîìïîçèöèè îáëàñòè äëÿ
ñóïåðêîìïüþòåðíîãî ìîäåëèðîâàíèÿ ãðàâèòèðóþùèõ
ñèñòåì ∗
Í.Â. Ñíûòíèêîâ, Â.À.Âøèâêîâ
Èíñòèòóò Âû÷èñëèòåëüíîé Ìàòåìàòèêè è Ìàòåìàòè÷åñêîé åî èçèêè ÑÎ ÀÍ
Ïðåäñòàâëåí íîâûé ïàðàëëåëüíûé àëãîðèòì äëÿ ñóïåðêîìïüþòåðíîãî ìîäåëè-
ðîâàíèÿ áåññòîëêíîâèòåëüíûõ ãðàâèòèðóþùèõ ñèñòåì. Îí êîìáèíèðóåò ìåòîä
÷àñòèö â ÿ÷åéêàõ (PIC) äëÿ ðåøåíèÿ óðàâíåíèÿ Âëàñîâà è ìåòîä ïàðàëëåëüíîãî
âû÷èñëåíèÿ ãðàâèòàöèîííîãî ïîòåíöèàëà èçîëèðîâàííûõ ñèñòåì íà îñíîâå ìåòî-
äà ñâåðòêè.
Àëãîðèòì èñïîëüçóåò ñïåöèàëüíûé ñïîñîá äåêîìïîçèöèè îáëàñòè, äèíàìè÷åñêè
íàçíà÷àþùèé ïðîöåññîðû ïîäîáëàñòÿì è îáåñïå÷èâàþùèé ðàâíîìåðíóþ áàëàí-
ñèðîâêó çàãðóçêè. Îí ó÷èòûâàåò èçè÷åñêèå îñîáåííîñòè çàäà÷ ìîäåëèðîâàíèÿ
íåñòàöèîíàðíûõ âðàùàþùèõñÿ äèñêîâ (äâóìåðíûõ è òðåõìåðíûõ). Â ýòîì ñëó-
÷àå PIC-÷àñòèöû, îïèñûâàþùèå äèíàìèêó áåññòîëêíîâèòåëüíîãî âåùåñòâà, ìîãóò
ïåðåìåùàòüñÿ ïî âñåé âû÷èñëèòåëüíîé îáëàñòè è, òàêèì îáðàçîì, ìíîãîêðàòíî
ïåðåõîäèòü ìåæäó ïîäîáëàñòÿìè è ñîîòâåòñòâóþùèì èì ïðîöåññîðàì. Ïàðàë-
ëåëüíûé àëãîðèòì ìîæåò áûòü èñïîëüçîâàí íà ñóïåðêîìïüþòåðàõ ñ ðàçíûìè òè-
ïàìè àðõèòåêòóðû: òðàäèöèîííûìè (CPU), è ãèáðèäíûìè (CPU ñ âèäåîêàðòàìè
NVIDIA GPU è Intel Xeon Phi).
 ñòàòüå ïîäðîáíî îïèñàíà òåîðåòè÷åñêàÿ ÷àñòü àëãîðèòìà. Ïîäðîáíûå ðåçóëü-
òàòû ÷èñëåííûõ ýêñïåðèìåíòîâ áóäóò ïðåäñòàâëåíû â îòäåëüíîé ïóáëèêàöèè.
1. Ââåäåíèå
Ñóïåðêîìïüþòåðíîå ìîäåëèðîâàíèå äèíàìèêè ãðàâèòèðóþùèõ ñèñòåì (òàêèõ êàê ãà-
ëàêòèêè èëè îêîëîçâåçäíûå äèñêè [1℄) ÿâëÿåòñÿ îäíîé èç íàèáîëåå òðóäíûõ è àêòóàëüíûõ
ïðîáëåì â ñîâðåìåííîé âû÷èñëèòåëüíîé àñòðî èçèêå. Õîòÿ îäíîïðîöåññîðíûå ÷èñëåííûå
ìåòîäû áûëè ñîçäàíû è óñïåøíî èñïîëüçóþòñÿ óæå áîëåå 30 ëåò [26℄, ðàçðàáîòêà ñîîò-
âåòñòâóþùèõ èì ïàðàëëåëüíûõ àëãîðèòìîâ òðåáóåò çíà÷èòåëüíûõ ìîäè èêàöèé.  ïåðâóþ
î÷åðåäü ýòî ñâÿçàíî ïîñòîÿííûì ðàçâèòèåì àïïàðàòíîãî îáåñïå÷åíèÿ ñóïåðêîìïüþòåðîâ
óâåëè÷èâàåòñÿ îáùåå ÷èñëî ïðîöåññîðîâ, èçìåíÿåòñÿ ñêîðîñòü ìåæïðîöåññîðíûõ êîììóíè-
êàöèé, ïîÿâëÿþòñÿ ìàññèâíî ïàðàëëåëüíûå àðõèòåêòóðû (òèïà GPU èëè Phi) ïîýòîìó
ïàðàëëåëüíûå àëãîðèòìû è ïðîãðàììíûé êîä, ñîçäàííûé äëÿ àðõèòåêòóð ïðåäûäóùåãî ïî-
êîëåíèÿ, óñòàðåâàåò è íóæäàåòñÿ â ïîñòîÿííîé ïåðåðàáîòêå. Äðóãîé îñîáåííîñòüþ ÿâëÿåòñÿ
ðàçíîîáðàçèå ìîäåëèðóåìûõ àñòðî èçè÷åñêèõ ïðîöåññîâ [79℄, êîòîðûå äîëæíû áûòü òåñ-
íî ñîïðÿæåíû äðóã ñ äðóãîì. Çäåñü âîçíèêàåò åùå îäíà òðóäíîñòü â èñïîëüçîâàíèè óæå
ñîçäàííûõ ïðîãðàììíûå êîìïëåêñîâ è êîäîâ çà÷àñòóþ îíè ïðåäíàçíà÷åíû äëÿ ðåøåíèÿ
îïðåäåëåííûõ òèïîâ çàäà÷ (íàïðèìåð, çàäà÷ êîñìîëîãèè [1012℄) è íå ìîãóò áûòü ý åê-
òèâíî èñïîëüçîâàíû â äðóãèõ êîíòåêñòàõ.
 äàííîé ñòàòüå ìû ïðåäëàãàåì ïàðàëëåëüíûé àëãîðèòì äëÿ ìîäåëèðîâàíèÿ âðàùàþ-
ùèõñÿ áåññòîëêíîâèòåëüíûõ ãðàâèòèðóþùèõ ñèñòåì ìåòîäîì ÷àñòèö â ÿ÷åéêàõ. Îí îñíîâàí
íà äåêîìïîçèöèè îáëàñòè äëÿ ðàíåå ðàçðàáîòàííîé ìîäåëè [13℄. Àëãîðèòì ìîæåò áûòü ïðè-
ìåíåí êàê äëÿ ìîäåëè òîíêîãî äèñêà (êîãäà îòñóòñòâóåò äâèæåíèå âåùåñòâà â âåðòèêàëüíîì
íàïðàâëåíèè), òàê è äëÿ ïîëíîñòüþ òðåõìåðíîé ìîäåëè. Íîâûì â ýòîì ïîäõîäå ÿâëÿåòñÿ
ìåòîä äèíàìè÷åñêîé áàëàíñèðîâêè çàãðóçêè ïðîöåññîðîâ ïðè âû÷èñëåíèè òðàåêòîðèè ìî-
∗
àçðàáîòêà òåîðåòè÷åñêèõ îñíîâ àëãîðèòìà ïàðàëëåëüíîãî ìåòîäà äåêîìïîçèöèè îáëàñòè äëÿ ìåòîäà
÷àñòèö â ÿ÷åéêàõ âûïîëíåíà ïðè ïîääåðæêå îññèéñêîãî Íàó÷íîãî Ôîíäà, ãðàíò 14-11-00485. Ïðîãðàìì-
íàÿ ðåàëèçàöèÿ àëãîðèòìîâ âûïîëíåíà ïðè ïîääåðæêå ÔÔÈ, ãðàíòû 14-01-31088, 14-01-00392.
572
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
äåëüíûõ ÷àñòèö, êîòîðûå â ñëó÷àå âðàùàþùèõñÿ ñèñòåì ìîãóò ìíîãîêðàòíî ïåðåõîäèòü
ìåæäó ïîäîáëàñòÿìè (è ñîîòâåòñòâóþùèì èì ïðîöåññîðàì).
åøàåìàÿ ñèñòåìà óðàâíåíèé ñîñòîèò èç óðàâíåíèÿ Âëàñîâà (èçâåñòíîãî òàêæå êàê
áåññòîëêíîâèòåëüíîå óðàâíåíèå Áîëüöìàíà) äëÿ óíêöèè ðàñïðåäåëåíèÿ âåùåñòâà f =
f (t, r, u), çàâèñÿùåé îò âðåìåíè t, ïðîñòðàíñòâåííîé êîîðäèíàòû r è âåêòîðà ñêîðîñòè u, ñ
çàäàííûì íà÷àëüíûì çíà÷åíèåì f 0 (r, u) (â âèäå íåêîòîðîãî âðàùàþùåãîñÿ äèñêà):
∂f ∂f ∂f
+u − ∇Φ(t, r) = 0, f (0, r, u) = f 0 (r, u)
∂t ∂r ∂u
è óðàâíåíèÿ Ïóàññîíà äëÿ ãðàâèòàöèîííîãî ïîòåíöèàëà Φ = Φ(t, r) ñ êðàåâûìè óñëîâèÿìè
äëÿ èçîëèðîâàííûõ ñèñòåì:
∆Φ(t, r) = 4πGρ(t, r), Φ(t, r)||r|→∞ = 0,
ãäå G ãðàâèòàöèîííàÿ ïîñòîÿííàÿ.
Çàìûêàåò ñèñòåìó ñëåäóþùåå óðàâíåíèå äëÿ ïëîòíîñòè ρ = ρ(t, r), êîòîðîå ñâÿçûâàåò
åå ñ óíêöèåé ðàñïðåäåëåíèÿ f :
Z
ρ(t, r) = f (t, r, u)du.
u
Äëÿ ðåøåíèÿ óðàâíåíèÿ Âëàñîâà èñïîëüçóåòñÿ ìåòîä ÷àñòèö â ÿ÷åéêàõ [2, 3℄, à äëÿ
ðåøåíèÿ óðàâíåíèÿ Ïóàññîíà ïàðàëëåëüíûé ìåòîä ñâ¼ðòêè. Îäíîïðîöåññîðíûé àëãîðèòì
îïèñûâàåòñÿ ñëåäóþùèìè øàãàìè:
1.  èñõîäíîé âû÷èñëèòåëüíîé îáëàñòè ââîäèòñÿ ðàâíîìåðíàÿ ñåòêà â äåêàðòîâûõ êî-
îðäèíàòàõ. åíåðèðóåòñÿ íà÷àëüíîå ðàñïðåäåëåíèå ìîäåëüíûõ ÷àñòèö (èõ ïðîñòðàí-
ñòâåííûå êîîðäèíàòû è ñêîðîñòè).
2. åøàåòñÿ óðàâíåíèå Âëàñîâà ñ ïîìîùüþ ìåòîäà ÷àñòèö. Ïîñêîëüêó PIC-÷àñòèöû âçà-
èìîäåéñòâóþò äðóã ñ äðóãîì òîëüêî ÷åðåç ãðàâèòàöèîííîå ïîëå, òî èõ êîîðäèíàòû è
ñêîðîñòè íà ñëåäóþùåì øàãå ìîãóò âû÷èñëÿòüñÿ íåçàâèñèìî äðóã îò äðóãà. Âìåñòå ñ
òåì êàæäàÿ ÷àñòèöà äîëæíà äëÿ ýòîãî ¾çíàòü¿ ãðàâèòàöèîííîå ïîëå, âêëàä â êîòîðîå
âíîñÿò âñå îñòàëüíûå ÷àñòèöû.
3. Âû÷èñëÿåòñÿ ñåòî÷íûé ãðàâèòàöèîííûé ïîòåíöèàë ñ èñïîëüçîâàíèåì ìåòîäà ñâåðòêè
(íà îñíîâå óíäàìåíòàëüíîãî ðåøåíèÿ óðàâíåíèÿ Ïóàññîíà è áûñòðîãî ïðåîáðàçîâà-
íèÿ Ôóðüå).
Ñîîòâåòñòâóþùèé ïàðàëëåëüíûé àëãîðèòì äîëæåí îáëàäàòü ñëåäóþùèìè ñâîéñòâàìè:
(à) ïîäðàçäåëÿòü èñõîäíóþ âû÷èñëèòåëüíóþ îáëàñòü íà òàêèå ïîäîáëàñòè, ÷òî êàæäàÿ èç
íèõ ìîãëà áû áûòü îáðàáîòàíà îäíèì âû÷èñëèòåëüíûì óñòðîéñòâîì ñ 1-4 Á ïàìÿòè, è
(á) ðàñïðåäåëÿòü PIC-÷àñòèöû ìåæäó ïðîöåññîðàìè òàê, ÷òîáû îíè ìîãëè èìåòü äîñòóï ê
çíà÷åíèÿì òðåáóåìûõ ñåòî÷íûõ óíêöèé â ïîäîáëàñòÿõ, ñâîáîäíî äâèãàòüñÿ ìåæäó ïîäîá-
ëàñòÿìè, è îáùåå êîëè÷åñòâî ÷àñòèö, ïåðåäàâàåìûõ ìåæäó ïðîöåññîðàìè, áûëî ìèíèìàëü-
íûì.
 òèïè÷íîì ñëó÷àå ìàêñèìàëüíîå êîëè÷åñòâî ÷àñòèö, êîòîðîå ìîæíî ïîìåñòèòü â îä-
íî âû÷èñëèòåëüíîå óñòðîéñòâî (CPU, GPU, Intel Phi), ñîñòàâëÿåò 8-16 ìèëëèîíîâ, à ìàê-
ñèìàëüíûå êîëè÷åñòâî óçëîâ ñåòêè ñîñòàâëÿåò 256 × 256 × 256 äëÿ òðåõìåðíûõ çàäà÷ è
4096 × 4096 äëÿ äâóìåðíûõ. Ýòî îçíà÷àåò, ÷òî áîëüøèå âû÷èñëèòåëüíûå îáëàñòè (òàêèå
êàê 1024 × 1024 × 1024) äîëæíû ïîäðàçäåëÿòüñÿ íà ìåíüøèå ïîäîáëàñòè. Â òî æå ñàìîå
âðåìÿ PIC ÷àñòèöû ìîãóò ìíîãîêðàòíî ïåðåëåòàòü èç îäíîé îáëàñòè â äðóãóþ çà âðåìÿ
îäíîãî ðàñ÷åòà (íàïðèìåð, åñëè ìû ðàññìàòðèâàåì ìîäåëèðîâàíèå äèñêîâ íà âðåìåííûõ
ìàñøòàáàõ ïîðÿäêà äåñÿòêîâ îáîðîòîâ, ãäå êàæäàÿ ÷àñòèöà äâèãàåòñÿ ïî ýëëèïòè÷åñêîé
573
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
èëè ýïèöèêëè÷åñêîé îðáèòå âîêðóã îáùåãî öåíòðà ìàññ), ÷òî ñîçäàåò ïðîáëåìó ïåðåñûëîê
äàííûõ íà êàæäîì âðåìåííîì øàãå.
Ýòà ïðîáëåìà óñóãóáëÿåòñÿ èç-çà òîãî, ÷òî ÷àñòèöû ìîãóò áûòü ðàñïðåäåëåíû íåðàâ-
íîìåðíî ìåæäó ïîäîáëàñòÿìè. Âî âðàùàþùåìñÿ äèñêå ìîãóò âîçíèêàòü ãðàâèòàöèîííûå
íåóñòîé÷èâîñòè, êîòîðûå ïðèâîäÿò ê ïîÿâëåíèþ ðàçíîîáðàçíûõ ñòðóêòóð ñãóñòêîâ âå-
ùåñòâà èëè ñïèðàëüíûõ âîëí, êîòîðûå ñïîñîáíû ïåðåäâèãàòüñÿ ïî âñåé âû÷èñëèòåëüíîé
ïîäîáëàñòè. Ïëîòíîñòü âåùåñòâà (è êîëè÷åñòâî ÷àñòèö) â ýòèõ ñòðóêòóðàõ ìîæåò áûòü íà
ïîðÿäêè áîëüøå îíîâûõ çíà÷åíèé. Ñëåäîâàòåëüíî, êîëè÷åñòâî ÷àñòèö â êàæäîé ïîäîáëà-
ñòè ìîæåò òàê æå îòëè÷àòüñÿ íà ïîðÿäêè è ìåíÿòüñÿ ñî âðåìåíåì, îñîáåííî â òåõ ñëó÷àÿõ,
êîãäà ñãóñòîê, ñîäåðæàùèé áîëüøîå êîëè÷åñòâî ÷àñòèö, äâèãàåòñÿ âîêðóã öåíòðà ìàññ.
àçðàáîòàííûé íàìè ïàðàëëåëüíûé àëãîðèòì, íàöåëåííûé íà ðåøåíèå óêàçàííûõ âî-
ïðîñîâ, îñíîâàí íà ñëåäóþùèõ ïðåäïîëîæåíèÿõ:
• Òðóäîåìêîñòü ðåøåíèÿ óðàâíåíèÿ Âëàñîâà (ò.å. èíòåãðèðîâàíèå òðàåêòîðèé PIC-÷àñòèö)
ñóùåñòâåííî âûøå (îò 10 äî 100 ðàç), ÷åì òðóäîåìêîñòü âû÷èñëåíèÿ ãðàâèòàöèîííîãî
ïîòåíöèàëà. Ýòî ïðåäïîëîæåíèå îáîñíîâûâàåòñÿ òåì, ÷òî âû÷èñëèòåëüíàÿ ñëîæíîñòü
äëÿ ðåøåíèÿ óðàâíåíèÿ Ïóàññîíà ñîñòàâëÿåò O(n log n) (ãäå n ýòî îáùåå êîëè÷åñòâî
ñåòî÷íûõ óçëîâ), â òî âðåìÿ êàê ñðåäíåå ÷èñëî PIC-÷àñòèö íà îäíó ÿ÷åéêó ñåòêè (èëè
îäèí ñåòî÷íûé óçåë) â òèïè÷íûõ ðàñ÷åòàõ íàõîäèòñÿ â äèàïàçîíå 10 ÷ 100. Êðîìå
òîãî, êîëè÷åñòâî àðè ìåòè÷åñêèõ îïåðàöèé âûïîëíÿåìûõ äëÿ âû÷èñëåíèÿ êîîðäè-
íàò è ñêîðîñòåé îäíîé ÷àñòèöû áîëüøå, ÷åì ÷èñëî îïåðàöèé, âûïîëíÿåìûõ äëÿ îäíîé
ÿ÷åéêè. Ïîýòîìó âîçìîæåí àëãîðèòì, êîãäà PIC-÷àñòèöû îáðàáàòûâàþòñÿ ñ ïîìîùüþ
ìàññèâíî ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ óñòðîéñòâ (GPU, Phi), â òî âðåìÿ êàê ãðà-
âèòàöèîííûé ïîòåíöèàë âû÷èñëÿåòñÿ íà CPU.
• Ïîñêîëüêó âðåìåííîé øàã, èñïîëüçóåìûé äëÿ ìåòîäà èíòåãðèðîâàíèÿ òðàåêòîðèé ÷à-
ñòèö, äîëæåí óäîâëåòâîðÿòü óñëîâèþ Êóðàíòà (â ïðîòèâíîì ñëó÷àå ÷èñëåííûé ìåòîä
áóäåò âû÷èñëèòåëüíî íåóñòîé÷èâûì), òî ÷àñòèöà ìîæåò ïåðåëåòåòü çà îäèí øàã íå
äàëåå, ÷åì â ñîñåäíþþ ÿ÷åéêó. Ýòî îçíà÷àåò, ÷òî ÷èñëî ÷àñòèö, êîòîðûå äîëæíû ïåðå-
ìåùàòüñÿ ìåæäó ñìåæíûìè ïîäîáëàñòÿìè, íàìíîãî ìåíüøå, ÷åì îáùåå ÷èñëî ÷àñòèö
â ñìåæíûõ ïîäîáëàñòÿõ. Ýòî ÷èñëî ìîæåò áûòü îöåíåíî êàê 10 · ny äëÿ 2D çàäà÷ è
10 · ny nz äëÿ 3D çàäà÷, ãäå êîý èöèåíò 10 ñîîòâåòñòâóåò îöåíî÷íîìó ÷èñëó ïåðåëå-
òàþùèõ ÷àñòèö, à ny , nz ýòî ÷èñëî âñåõ ãðàíè÷íûõ óçëîâ ìåæäó ïîäîáëàñòÿìè.
Îáùàÿ ñõåìà ïàðàëëåëüíîãî àëãîðèòìà ïðåäñòàâëåíà íèæå êàê Àëãîðèòì 1. Îí ðàçáèò
íà íåñêîëüêî îòäåëüíûõ ïðîãðàììíûõ ïðîöåäóð, êîòîðûå ñ îðìóëèðîâàíû â âèäå Àëãî-
ðèòìîâ 2-6.
2. Ìåòîä äåêîìïîçèöèè îáëàñòè
Àëãîðèòì 1. Îáùàÿ ñõåìà ìåòîäà äåêîìïîçèöèè îáëàñòè äëÿ ïàðàëëåëüíîãî ðåøåíèÿ.
Èñõîäíàÿ âû÷èñëèòåëüíàÿ îáëàñòü (2D èëè 3D) ðàâíîìåðíî ïîäðàçäåëÿåòñÿ íà K ïîä-
îáëàñòåé îäèíàêîâîãî ðàçìåðà S1, S2, .., SK â íàïðàâëåíèè X. ðóïïà ïðîöåññîðîâ Gk íàçíà-
÷àåòñÿ êàæäîé ïîäîáëàñòè Sk . Êîëè÷åñòâî ïðîöåññîðîâ â ãðóïïå Gk ðàâíî Pk , Pk ≥ 1. Îáùåå
êîëè÷åñòâî ïðîöåññîðîâ ðàâíî P = P Pk . Êîëè÷åñòâî óçëîâ (ÿ÷ååê) â êàæäîé âû÷èñëèòåëü-
íîé ïîäîáëàñòè âûáèðàåòñÿ òàêèì îáðàçîì, ÷òî âñå ñåòî÷íûå óíêöèè (ãðàâèòàöèîííûé
ïîòåíöèàë, ïëîòíîñòü, ñèëà) äîëæíû ïîëíîñòüþ ïîìåùàòüñÿ â îïåðàòèâíóþ ïàìÿòü îäíîãî
âû÷èñëèòåëüíîãî óñòðîéñòâà è îñòàâèòü â ïàìÿòè äîñòàòî÷íî ìåñòà äëÿ õðàíåíèÿ ìàññèâîâ
ñ ÷àñòèöàìè (ò.å. èõ ïðîñòðàíñòâåííûõ êîîðäèíàò è ñêîðîñòåé). Îáû÷íî ýòî ÷èñëî ðàâíî
0.5 ÷ 2 ìèëëèîíîâ óçëîâ (ñîîòâåòñòâóåò ñåòêå 1283 èëè 10242 ). Êîëè÷åñòâî ïðîöåññîðîâ â
ãðóïïå Gk âûáèðàåòñÿ òàê, ÷òîáû îáåñïå÷èòü ïðèáëèçèòåëüíî îäèíàêîâîå êîëè÷åñòâî ÷à-
ñòèö íà îäíîì ïðîöåññîðå (ñì. Àëãîðèòì 2). Ýòî îçíà÷àåò, ÷òî åñëè ïîäîáëàñòü Sk ñîäåðæèò
áîëüøå ÷àñòèö, ÷åì ïîäîáëàñòü Sk , òî ÷èñëî ïðîöåññîðîâ Pk â ãðóïïå Gk áóäåò áîëüøå
1
2 1 1
574
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
èëè ðàâíî êîëè÷åñòâó Pk â ãðóïïå Gk .  êàæäîé ãðóïïå ïðîöåññîðîâ Gk è ñîîòâåòñòâó-
þùåé ïîäîáëàñòè Sk èìååòñÿ ãëàâíûé ïðîöåññîð gk0, êîòîðûé íå ìîæåò áûòü ïåðåíàçíà÷åí
2 2
ëþáîé äðóãîé ïîäîáëàñòè âî âðåìÿ âû÷èñëèòåëüíîãî ýêñïåðèìåíòà (äàæå â òîì ñëó÷àå,
êîãäà ïîäîáëàñòü Sk íå ñîäåðæèò ÷àñòèö).
1. Â íóëåâîé ìîìåíò âðåìåíè (t = 0):
(a) äëÿ êàæîé ïîäîáëàñòè Sk âû÷èñëÿåòñÿ îáùåå êîëè÷åñòâî ÷àñòèö, ñîîòâåòñòâóþ-
ùåå ÷èñëó ïðîöåññîðîâ â ãðóïïå Gk , è êîëè÷åñòâî ÷àñòèö, íàçíà÷åííîå êàæäîìó
èç ïðîöåññîðîâ (ñì. Àëãîðèòì 2),
(b) íà êàæäîì ïðîöåññîðå âûäåëÿåòñÿ ïàìÿòü äëÿ ìàññèâîâ êîîðäèíàò è ñêîðîñòåé
÷àñòèö,
( ) âûïîëíÿåòñÿ ãåíåðàöèÿ íà÷àëüíûõ êîîðäèíàò è ñêîðîñòåé PIC ÷àñòèö â îáëà-
ñòè (íà êàæäîì ïðîöåññîðå) â ñîîòâåòñòâèè ñ çàäàííîé ïîëüçîâàòåëåì óíêöèåé
ðàñïðåäåëåíèÿ.
2. Âû÷èñëÿåòñÿ ñåòî÷íàÿ óíêöèÿ ïëîòíîñòè äëÿ PIC ÷àñòèö (ñì. Àëãîðèòì 3).
3. Âû÷èñëÿåòñÿ ãðàâèòàöèîííûé ïîòåíöèàë ñ ïîìîùüþ ïàðàëëåëüíîãî ìåòîäà ñâåðòêè
(ñì. Àëãîðèòì 6).
4. Äëÿ êàæäîãî ïðîöåññîðà âû÷èñëÿþòñÿ íîâûå êîîðäèíàòû ÷àñòèö äëÿ ñëåäóþùåãî øà-
ãà (ñì. Àëãîðèòì 4).
5. Âû÷èñëÿåòñÿ êîëè÷åñòâî ÷àñòèö, êîòîðîå äîëæíî íàõîäèòüñÿ â êàæäîé ïîäîáëàñòè
Sk íà ñëåäóþùåì øàãå. Âû÷èñëÿåòñÿ êîëè÷åñòâî ïðîöåññîðîâ, êîòîðîå äîëæíî áûòü
íàçíà÷åíî êàæäîé ïîäîáëàñòè (ñì. Àëãîðèòì 2). Ïåðåðàñïðåäåëÿþòñÿ ÷àñòèöû ìåæäó
ïðîöåññîðíûìè ãðóïïàìè (ñì Àëãîðèòì 5).
6. Èíêðåìåíòèðóåòñÿ âðåìåííîé øàã è âûïîëíÿåòñÿ ïåðåõîä íà Øàã 2.
Àëãîðèòì 2. Âû÷èñëåíèå ÷èñëà ïðîöåññîðîâ â ãðóïïå.
Ïðåäïîëîæèì, ÷òî êàæäàÿ ïîäîáëàñòü Sk ñîäåðæèò Nk ÷àñòèö, è îáùåå ÷èñëî ÷àñòèö
N = Nk . Ìû äîëæíû âû÷èñëèòü, ñêîëüêî ïðîöåññîðîâ äîëæíî áûòü íàçíà÷åíî îäíîé
P
ïîäîáëàñòè äëÿ îáðàáîòêè Nk ÷àñòèö è ïðè ýòîì îáåñïå÷èòü ïðèáëèçèòåëüíî îäèíàêîâóþ
çàãðóçêó âñåõ ïðîöåññîðîâ. Êàæäàÿ ïðîöåññîðíàÿ ãðóïïà ñîäåðæèò ïî êðàéíåé ìåðå îäèí
(ãëàâíûé) ïðîöåññîð gk0. Íà êàæäîì âðåìåííîì øàãå ìû äîëæíû âû÷èñëèòü Nmax ìàê-
ñèìàëüíîå ÷èñëî ÷àñòèö íà ïðîöåññîðå. Åñëè ïðîöåññîð ñîäåðæèò â òî÷íîñòè Nmax ÷àñòèö,
òî îáùèå âû÷èñëèòåëüíûå ðàñõîäû íà ýòîì âðåìåííîì øàãå áóäóò îïðåäåëÿòüñÿ äàííûì
ïðîöåññîðîì. Òàêèì îáðàçîì íàøåé çàäà÷åé ÿâëÿåòñÿ ìèíèìèçàöèÿ ïàðàìåòðà Nmax. Äëÿ
ýòîãî èñïîëüçóåòñÿ ìåòîä áèñåêöèè:
1. Âû÷èñëÿåì çíà÷åíèÿ Nlow = N/P è Nupp = 2 · N/P . Çíà÷åíèå Nlow ìåíüøå, ÷åì æå-
ëàåìîå Nmax, à çíà÷åíèå Nupp áîëüøå, ÷åì îïòèìàëüíîå Nmax. Ïðèñâàèâàåì Nmax :=
(Nlow + Nupp )/2.
2. Âû÷èñëÿåì çíà÷åíèÿ Pk = (Nk /Nmax) + 1. Âû÷èñëÿåì çíà÷åíèÿ P ∗ = P Pk . Ñðàâíè-
âàåì P ∗ ñ P :
• Åñëè P ∗ < P , òî Nupp := Nmax , âûïîëíÿåòñÿ ïåðåõîä íà Øàã 3.
• Åñëè P ∗ > P , òî Nlow := Nmax , âûïîëíÿåòñÿ ïåðåõîä íà Øàã 3.
• Åñëè P ∗ = P , òî Nupp := Nmax , è ïðîâåðÿåì: åñëè Nupp − Nlow < Neps (ãäå
Neps ≪ Nmax è îïðåäåëÿåòñÿ ïîëüçîâàòåëåì), òî ïåðåõîä íà çàâåðøåíèå, èíà÷å
âûïîëíÿåòñÿ ïåðåõîä íà 3.
575
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
3. Ïðèñâàèâàåì Nmax := (Nlow + Nupp)/2 è âûïîëíÿåì ïåðåõîä íà Øàã 2.
Âû÷èñëåíèå ïëîòíîñòè è èíòåãðèðîâàíèå òðàåêòîðèé ÷àñòèö âûïîëíÿåòñÿ ñ ïîìîùüþ
ñòàíäàðòíîãî âàðèàíòà ìåòîäà ÷àñòèö â ÿ÷åéêàõ [3℄. Âìåñòå ñ òåì, äëÿ ý åêòèâíîé ðåàëè-
çàöèè ïàðàëëåëüíîãî àëãîðèòìà íåîáõîäèìî èìåòü ïîäõîäÿùèå ñòðóêòóðû äàííûõ, êîìáè-
íèðóþùèõ ÷àñòèöû è ÿ÷åéêè. Àëãîðèòìû 3-4 îïðåäåëÿþò îñíîâíûå ñâîéñòâà òàêèõ ñòðóê-
òóð äàííûõ.
Àëãîðèòì 3. Âû÷èñëåíèå ïëîòíîñòè âíóòðè ïîäîáëàñòè.
• ×àñòèöû ñîðòèðóþòñÿ âíóòðè êàæäîé ïîäîáëàñòè. Êëþ÷îì ñîðòèðîâêè ÿâëÿåòñÿ ïî-
ðÿäêîâûé íîìåð ÷àñòèöû (ïîðÿäîê óñòàíàâëèâàåòñÿ ñíà÷àëà ïî êîîðäèíàòå X, çàòåì
ïî Y, è äàëåå ïî Z). Ýòà ðàçíîâèäíîñòü ñîðòèðîâî÷íîãî àëãîðèòìà èìååò ëèíåéíóþ
ñëîæíîñòü è ìîæåò áûòü ñäåëàíà ¾íà ëåòó¿ âî âðåìÿ èíòåãðèðîâàíèÿ òðàåêòîðèé
÷àñòèö (ñì. Àëãîðèòì 4).
• Äàëåå ÷àñòèöû ïåðåðàñïðåäåëÿþòñÿ ìåæäó ïðîöåññîðàìè ýòîé ãðóïïû â ñîîòâåòñòâèè
ñ èõ ïîðÿäêîâûìè íîìåðàìè â îòñîðòèðîâàííîì ìàññèâå.
• Ïîäîáíàÿ ïðîöåäóðà ñîðòèðîâêè ïðåäîñòàâëÿåò âîçìîæíîñòü ý åêòèâíîãî èñïîëü-
çîâàíèÿ êýø-ïàìÿòè ïðîöåññîðà ïðè âû÷èñëåíèè êîîðäèíàò PIC-÷àñòèö.
• Ñåòî÷íàÿ óíêöèÿ ïëîòíîñòè âû÷èñëÿåòñÿ ñ èñïîëüçîâàíèåì ÿäðà PIC (ìóëüòèëè-
íåéíîé èíòåðïîëÿöèè â óçëû ÿ÷åéêè). È ïîñëå ýòîãî óíêöèÿ ïëîòíîñòè ñîáèðàåòñÿ
â åäèíûé ìàññèâ íà ïðîöåññîðå gk0.
Àëãîðèòì 4. Âû÷èñëåíèå êîîðäèíàò ÷àñòèö (èíòåãðèðîâàíèå èõ òðàåêòîðèé).
• åàëèçîâàíà ñïåöèàëüíàÿ ñòðóêòóðà äàííûõ: êàæäàÿ ÿ÷åéêà èìååò ññûëêó íà ìàññèâ
÷àñòèö, êîòîðûå íà äàííîì øàãå íàõîäÿòñÿ â äàííîé ÿ÷åéêå.
• Äëÿ êàæäîé ÿ÷åéêè èíòåãðèðóþòñÿ òðàåêòîðèè ãðóïïû ÷àñòèö, ëîêàëèçîâàííûõ â
íåé.
• Ïðè ïåðåìåùåíèè ÷àñòèö èç îäíîé ÿ÷åéêè â äðóãóþ, âûïîëíÿåòñÿ ïåðåäà÷à ÷àñòèö
èç ìàññèâà ÷àñòèö ñâÿçàííûõ ñ îäíîé ÿ÷åéêîé, â ìàññèâ ÷àñòèö, ñâÿçàííûõ ñ äðóãîé
ÿ÷åéêîé.
• ×àñòèöû, êîòîðûå ïåðåìåñòèëèñü â ÿ÷åéêè, ðàñïîëîæåííûå çà ïðåäåëàìè äàííîé ïîä-
îáëàñòè (èëè çà ïðåäåëàìè ÿ÷ååê, íàçíà÷åííûõ äàííîìó ïðîöåññîðó), ïîìå÷àþòñÿ êàê
¾âíåøíèå¿ ÷àñòèöû è ïîçæå ïåðåìåùàþòñÿ â ñîîòâåòñòâóþùóþ ïîäîáëàñòü (ñì. Àë-
ãîðèòì 5).
Àëãîðèòì 5. Ïåðåðàñïðåäåëåíèå ÷àñòèö ìåæäó ïîäîáëàñòÿìè ïîñëå âû÷èñëåíèÿ íîâûõ
êîîðäèíàò ÷àñòèö.
1. Ïîñëå ïðèìåíåíèÿ Àëãîðèòìà 4 íà êàæäîì ïðîöåññîðå ìîãóò íàõîäèòüñÿ òðè òèïà
÷àñòèö: (à) ÷àñòèöû, êîòîðûå îñòàëèñü âíóòðè äàííîé ïîäîáëàñòè, (á) ÷àñòèöû, êî-
òîðûå äîëæíû ïåðåìåñòèòüñÿ â ëåâóþ ñìåæíóþ ïîäîáëàñòü, è (â) ÷àñòèöû, êîòîðûå
äîëæíû ïåðåìåñòèòüñÿ â ïðàâóþ ñìåæíóþ ïîäîáëàñòü. Îáùåå êîëè÷åñòâî ïåðåìåùà-
åìûõ ìåæäó ïîäîáëàñòÿìè ÷àñòèö íåâåëèêî èç-çà íåîáõîäèìîñòè âûïîëíåíèÿ óñëîâèÿ
Êóðàíòà: îíî íå ìîæåò áûòü áîëüøå, ÷åì ÷èñëî ÷àñòèö, êîòîðûå ñîäåðæàëèñü â ãðà-
íè÷íûõ ÿ÷åéêàõ ïîäîáëàñòè. Íà ïðàêòèêå ýòî ÷èñëî ñóùåñòâåííî ìåíüøå è ñîñòàâëÿåò
ìåíåå 0.1% îò îáùåãî êîëè÷åñòâà ÷àñòèö.
2. Âû÷èñëÿåì íîâîå ÷èñëî ÷àñòèö äëÿ êàæäîé èç ïîäîáëàñòåé (íà îñíîâå Àëãîðèòìà 4).
576
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
3. Âû÷èñëÿåì ÷èñëî ïðîöåññîðîâ äëÿ êàæäîé ïîäîáëàñòè (ñì. Àëãîðèòì 2).
4. Îïðåäåëÿåì òå ïðîöåññîðû â êàæäîé ãðóïïå, êîòîðûå äîëæíû áûòü ïåðåíàçíà÷åíû íà
ñîñåäíèå ïîäîáëàñòè (òî åñòü ïåðåäàíû äðóãèì ãðóïïàì). Ïåðåäàåì ñ íèõ òå ÷àñòèöû,
êîòîðûå äîëæíû îñòàòüñÿ â äàííîé ïîäîáëàñòè.
5. Ïåðåäàåì ÷àñòèöû, êîòîðûå ïåðåøëè èç äàííîé ïîäîáëàñòè â ñîñåäíèå ïîäîáëàñòè.
3. Ïàðàëëåëüíûé àëãîðèòì äëÿ âû÷èñëåíèÿ ïîòåíöèàëà ìåòî-
äîì ñâ¼ðòêè
Äëÿ âû÷èñëåíèÿ ãðàâèòàöèîííîãî ïîòåíöèàëà áûë ðåàëèçîâàí ìåòîä ñâ¼ðòêè, ïðåäëî-
æåííûé Õîêíè [2℄. Åãî ñóòü çàêëþ÷àåòñÿ â òîì, ÷òî âìåñòî çàäà÷è Äèðèõëå äëÿ óðàâíåíèÿ
Ïóàññîíà â áåñêîíå÷íîé îáëàñòè:
∆Φ(x) = ρ(x),
(1)
Φ(x)|x→∞ = 0,
âûïîëíÿåòñÿ ý åêòèâíîå âû÷èñëåíèå èíòåãðàëà, ïðåäñòàâëÿþùåãî óíäàìåíòàëüíîå ðå-
øåíèå óðàâíåíèÿ Ïóàññîíà:
ρ(x)dx
(2)
Z
Φ(x0 ) = − .
|x0 − x|
 äèñêðåòíîì ñëó÷àå â äåêàðòîâîé ñèñòåìå êîîðäèíàò íà ðàâíîìåðíîé ñåòêå ÷èñëîì óçëîâ
Nx ×Ny ×Nz è ñåòî÷íûìè øàãàìè hx , hy , hz ðåøåíèå áóäåò çàïèñûâàòüñÿ â ñëåäóþùåì âèäå:
y −1 Nz −1
x −1 NX
NX
qi,j,k
(3)
X
Φ(x0 , y0 , z0 ) = − p ,
i=1 j=1 k=1
(xi − x0 ) + (yi − y0 )2 + (zi − z0 )2
2
ãäå qi,j,k = ρi,j,k · (hxhy hz ) çíà÷åíèÿ çàðÿäîâ (ìàññ), íàõîäÿùèõñÿ â óçëàõ ñåòêè.
Íåòðóäíî âèäåòü, ÷òî ïðÿìîå âû÷èñëåíèå ýòîé ñóììû äëÿ âñåõ x0, y0, íåîáõîäèìîå äëÿ
âîññòàíîâëåíèÿ ñåòî÷íîé óíêöèè ãðàâèòàöèîííîãî ïîòåíöèàëà ïîòðåáóåò O(Nx2Ny2Nz2) îïå-
ðàöèé. Îäíàêî òðóäîåìêîñòü âû÷èñëåíèé ìîæíî ñóùåñòâåííî ñîêðàòèòü, âîñïîëüçîâàâøèñü
òåîðåìîé î ñâ¼ðòêå [14℄ è åå äèñêðåòíûì àíàëîãîì. Çàïèøåì (2) â âèäå:
(4)
Z
Φ(x0 ) = − ρ(x)K(x − x0 )dx = −ρ ∗ K,
ãäå
1
K(x − x0 ) =
|x − x0 |
è ρ ∗ K îáîçíà÷àåò ñâ¼ðòêó.
Åñëè èíòåãðàë â (4) ÿâëÿåòñÿ àáñîëþòíî èíòåãðèðóåìûì è ñóùåñòâóþò ñëåäóþùèå èí-
òåãðàëû (ò.å. ñóùåñòâóþò îãðàíè÷èâàþùèå êîíñòàíòû C1 è C2):
Z
ρ(x)dx < C1 < ∞,
(5)
Z
K(x)dx < C1 < ∞,
òî:
F T [Φ](k) = −F T [ρ](k) · F T [K](k),
(6)
Φ = −F T −1 [F T [ρ] · F T [K]]
ãäå F T [. . .] îáîçíà÷àåò ïðåîáðàçîâàíèå Ôóðüå.
577
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Ñ ïðàêòè÷åñêîé òî÷êè çðåíèÿ ýòî îçíà÷àåò, ÷òî, âîñïîëüçîâàâøèñü äèñêðåòíûì àíàëî-
ãîì òåîðåìû î ñâ¼ðòêè è àëãîðèòìîì áûñòðîãî ïðåîáðàçîâàíèÿ Ôóðüå, ìîæíî âû÷èñëèòü
ñóììó (3) çà O(NxNy Nz (log2Nx + log2Ny + log2Nz )) îïåðàöèé, ÷òî íàìíîãî áûñòðåå ïðÿìîãî
ñïîñîáà âû÷èñëåíèÿ óíäàìåíòàëüíîãî ðåøåíèÿ äëÿ óðàâíåíèÿ Ïóàññîíà è ñîîòâåòñòâó-
åò òðóäîåìêîñòè ðåøåíèÿ çàäà÷è Äèðèõëå äëÿ óðàâíåíèÿ Ïóàññîíà ìåòîäîì ðàçäåëåíèÿ
ïåðåìåííûõ [15℄.
Äëÿ òîãî, ÷òîáû ïðèìåíèòü äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå íåîáõîäèìî óñòðàíèòü
íåîïðåäåëåííîñòü èíòåãðàëà (5) â òî÷êå x = x0, ãäå îí ðàñõîäèòñÿ, è îïðåäåëèòü óíêöèè
K è ρ òàê, ÷òîáû îíè ñòàëè ïåðèîäè÷åñêèìè. Ïåðâàÿ èç ýòèõ ïðîáëåì ðåøàåòñÿ ñ ïîìî-
ùüþ îáðåçàíèÿ ïîòåíöèàëà íà áëèçêèõ ðàññòîÿíèÿõ. Ìû çàäàâàëè ñåòî÷íóþ óíêöèþ K
ñëåäóþùèì îáðàçîì:
1
p
0.5 min(hx,hy,hz) , x2 + y 2 + z 2 = 0,
K(x, y, z) =
1
p
√ , x2 + y 2 + z 2 > 0.
x2 +y 2 +z 2
Âòîðàÿ ïðîáëåìà ðåøàåòñÿ ñ ïîìîùüþ ââåäåíèÿ èêòèâíûõ äîïîëíèòåëüíûõ ïîäîáëà-
ñòåé, äóáëèðóþùèõ îáëàñòü ðåøåíèÿ ïî êàæäîìó íàïðàâëåíèþ â äâà ðàçà, è äîîïðåäåëåíèÿ
â íèõ óíêöèè K òàê, ÷òîáû îíà ñòàëà ïåðèîäè÷åñêîé âî âñåé íîâîé îáëàñòè, à óíêöèÿ ρ
ðàâíîé íóëþ. Àêêóðàòíîå äîêàçàòåëüñòâî êîððåêòíîñòè ìåòîäà è òîãî àêòà, ÷òî ïîëó÷åí-
íîå òàêèì ñïîñîáîì ðåøåíèå ñîâïàäàåò ñ ïðÿìûì âû÷èñëåíèåì (3), ïðèâåäåíî â ñòàòüå [16℄.
Ïðîèçâîäèòåëüíîñòü ïðåäñòàâëåííîãî àëãîðèòìà ñâ¼ðòêè àêòè÷åñêè îïðåäåëÿåòñÿ ïðî-
èçâîäèòåëüíîñòüþ áûñòðîãî ïðåîáðàçîâàíèÿ Ôóðüå (â íàøåé ðåàëèçàöèè ìåòîäà ñâ¼ðòêè ìû
èñïîëüçîâàëè FFTW [17℄).
Ïàðàëëåëüíàÿ ðåàëèçàöèÿ äàííîãî àëãîðèòìà çàêëþ÷àåòñÿ â ðàçáèåíèè íà ïîäîáëàñòè
è ïðèìåíåíè ìåòîäà òðàíñïîçèöèè äàííûõ (ñòàíäàðòíîãî ïîäõîäà äëÿ ìíîãîìåðíîãî ïðå-
îáðàçîâàíèÿ Ôóðüå [18℄).
Àëãîðèòì 6. Ïàðàëëåëüíûé àëãîðèòì äëÿ âû÷èñëåíèÿ ãðàâèòàöèîííîãî ïîòåíöèàëà.
1. Âû÷èñëèòåëüíàÿ îáëàñòü â 2D èëè 3D ïîäðàçäåëÿåòñÿ íà ïîäîáëàñòè â íàïðàâëåíèè
X.
2. Ïðèìåíÿåòñÿ ïðÿìîå áûñòðîå ïðåîáðàçîâàíèå Ôóðüå (ÁÏÔ) ê ñåòî÷íûì óíêöèÿì
ïëîòíîñòè ÿäðà ïîòåíöèàëà â íàïðàâëåíèè Y è â íàïðàâëåíèè Z.
3. Âûïîëíÿåòñÿ òðàíñïîçèöèÿ ¾ñëîåâ¿ èç íàïðàâëåíèÿ Y â íàïðàâëåíèå X.
4. Ïðèìåíÿåòñÿ ïðÿìîå ÁÏÔ â íàïðàâëåíèè X. Ïåðåìíîæàåòñÿ îáðàç ñåòî÷íîé óíêöèè
ÿäðà íà îáðàç óíêöèè ïëîòíîñòè. Ïðèìåíÿåòñÿ îáðàòíîå ÁÏÔ â íàïðàâëåíèè X ê
ïîëó÷åííîìó ðåçóëüòàòó.
5. Âûïîëíÿåòñÿ îáðàòíàÿ òðàíñïîçèöèÿ ¾ñëîåâ¿ èç íàïðàâëåíèÿ X â íàïðàâëåíèå Y.
6. Ïðèìåíÿåòñÿ îáðàòíîå ÁÏÔ â íàïðàâëåíèè Z è îáðàòíîå ÁÏÔ â íàïðàâëåíèè Y.
Äëÿ äàííîãî àëãîðèòìà åäèíñòâåííûìè ìåæïðîöåññîðíûìè êîììóíèêàöèÿìè ÿâëÿþòñÿ
ïðÿìàÿ è îáðàòíàÿ òðàíñïîçèöèÿ äàííûõ (ñîîòâåòñòâóþùàÿ ïðîöåäóðå MPI Alltoall). ×èñ-
ëåííûå ýêñïåðèìåíòû ïîêàçàëè, ÷òî äëÿ ñåòîê ñðåäíåãî ðàçìåðà (äî 10243 óçëîâ) è ÷èñëîì
ïðîöåññîðîâ äî 1024 êîììóíèêàöèîííîå âðåìÿ ñîñòàâëÿåò îêîëî 50% (íå áîëåå 1-3 ñåêóíä).
4. Ïðåäâàðèòåëüíûå òåñòîâûå ðåçóëüòàòû
×èñëåííûå òåñòîâûå ýêñïåðèìåíòû ïðîâîäèëèñü íà ñóïåðêîìïüþòåðàõ Ñèáèðñêîãî ñó-
ïåðêîìïüþòåðíîãî öåíòðà, Ìåæâåäîìñòâåííîãî ñóïåðêîìïüþòåðíîãî öåíòðà è ñóïåðêîì-
ïüþòåðà ¾Ëîìîíîñîâ¿ â Ì Ó.  êà÷åñòâå íà÷àëüíîãî ðàñïðåäåëåíèÿ f 0(r, u) çàäàâàëñÿ äèñê
578
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Ìàêëîðåíà ñ òâåðäîòåëüíûì âðàùåíèåì è ðàçíûìè äèñïåðñèÿìè ñêîðîñòåé ÷àñòèö.  êà÷å-
ñòâå ìàêñèìàëüíûõ òåõíè÷åñêèõ ïàðàìåòðîâ äëÿ êâàçèòðåõìåðíîé ìîäåëè (ñ îòñóòñòâèåì
âåðòèêàëüíîãî äâèæåíèÿ âåùåñòâà) çàäàâàëàñü ñåòêà 16384 × 16384 è 5 ìèëëèàðäîâ ÷àñòèö
(512 ïðîöåññîðîâ), à äëÿ ïîëíîñòüþ òðåõìåðíîé ìîäåëè 1024×1024×1024 è 10 ìèëëèàðäîâ
÷àñòèö (1024 ïðîöåññîðà). Äëÿ òåñòîâûõ çàäà÷ íà ðàçâèòèå ãðàâèòàöèîííîé íåóñòîé÷èâîñòè
îñåñèììåòðè÷íîãî òèïà (âàðüèðîâàíèå íà÷àëüíûõ äèñïåðñèé) îáùèé îáúåì êîììóíèêàöè-
îííûõ ðàñõîäîâ ñîñòàâëÿë íå áîëåå 30% ñ àáñîëþòíûì âðåìåíåì ñ÷åòà ïîðÿäêà 10 ñåêóíä
íà îäèí øàã ïî âðåìåíè.
Ïîäðîáíûå ðåçóëüòàòû ÷èñëåííûõ ýêñïåðèìåíòîâ íàõîäÿòñÿ â ñòàäèè ïîäãîòîâêè è áó-
äóò ïðåäñòàâëåíû â îòäåëüíîé ïóáëèêàöèè. Â äàëüíåéøåì ðàçðàáîòàííûé ïàðàëëåëüíûé
àëãîðèòì è åãî ïðîãðàììíàÿ ðåàëèçàöèÿ áóäåò èñïîëüçîâàòüñÿ äëÿ ñóïåðêîìïüþòåðíîãî
ìîäåëèðîâàíèÿ äèíàìèêè âðàùàþùèõñÿ ãàëàêòèê è ïûëåâîé êîìïîíåíòû â ïðîòîïëàíåò-
íûõ äèñêàõ.
Ëèòåðàòóðà
1. Ñíûòíèêîâ Â.Í., Âøèâêîâ Â.À., Êóêøåâà Ý.À., Íåóïîêîåâ Å.Â., Íèêèòèí Ñ.À.,
Ñíûòíèêîâ À.Â. Òðåõìåðíîå ÷èñëåííîå ìîäåëèðîâàíèå íåñòàöèîíàðíîé
ãðàâèòèðóþùåé ñèñòåìû ìíîãèõ òåë ñ ãàçîì // Ïèñüìà â àñòðîíîìè÷åñêèé æóðíàë.
2004. 30, N.2. 146-160.
2. Ho kney, R.W. and Eastwood, J.W. Computer Simulation Using Parti les. //
M Graw-Hill. New York. 1981.
3. Berezin Yu.A. Vshivkov V.A. Parti le-in- ell method in the plasma dynami s // Nauka.
1980.
4. J.E. Barnes and P. Hut. A Hierar hi al O(NlogN) For e-Cal ulation Algorithm // Nature
Vol. 324, pp.446-449, 1986.
5. R.A. Gingold and J.J. Monaghan. Smoothed parti le hydrodynami s - Theory and
appli ation to non-spheri al stars // Monthly Noti es of the Royal Astronomi al So iety,
vol. 181, p. 375-389. 1977.
6. P. Colella, P.R. Woodward. The Pie ewise Paraboli Method (PPM) for gas-dynami al
simulations // Journal of Computational Physi s. Volume 54, Issue 1, P. 174-201. 1984
7. A.Dubeya, K. Antypasb, M.K. Ganapathy , et al. Extensible omponent-based ar hite ture
for FLASH, a massively parallel, multiphysi s simulation ode // Parallel Computing.
Volume 35. 2009. P.512-522.
8. Springel V., Yoshida N., White S.D.M.: GADGET: a ode for ollisionless and
gasdynami al osmologi al simulation. New Astronomy. 6, pp. 79-117 (2001)
9. F.R. Pear e, H.M.P. Cou hman. Hydra: a parallel adaptive grid ode // New Astronomy.
Volume 2, Issue 5, P. 411-427. 1997.
10. V. Springel et al. Simulations of the formation, evolution and lustering of galaxies and
quasars // Nature, V. 435, p. 629. 2005,
11. A.A. Klypin et al. Dark Matter Halos in the Standard Cosmologi al Model: Results from
the Bolshoi Simulation // Astrophysi al Journal. V. 740 p. 102. 2011.
12. Y. Feng, T. Di Matteo, R.A.C. Croft, S. Bird, N. Battaglia, S. Wilkins // Monthly Noti e
of Royal Astronomi al So iety. 2015 (submitted)
579
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
13. N. Snytnikov. S alable Parallel Algorithm for Solving the Collisionless Boltzmann - Poisson
System of Equations // Astronomi al So iety of the Pa i Conferen e Series. - 2012. - V.
453. - P. 393.
14. Kolmogorov A.N., Fomin S.V. Elements of the Theory of Fun tions and Fun tional
Analysis // Graylo k Press, Ro hester, N.Y., 1961.
15. Ñàìàðñêèé À.À. Íèêîëàåâ Å.Ñ. Ìåòîäû ðåøåíèé ñåòî÷íûõ óðàâíåíèé. Ì.: Íàóêà.
1978. 592 ñ.
16. Eastwood J.W., Brownrigg D.R.K. Remarks on the Solution of Poisson's Equation for
Isolated Systems // Journal of Computational Physi s, Vol. 32, pp.24-38, 1979.
17. M.Frigo and S.G.Johnson. FFTW software // http://www.tw.org
18. O. Ayala, L.P. Wang. Parallel implementation and s alability analysis of 3D Fast Fourier
Transform using 2D domain de omposition // Parallel Computing. 2013. Vol.39. P. 58-77
580
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Domain decomposition method for supercomputer simulation of
gravitating systems
Nikolay Snytnikov and Vitaly Vshivkov
Keywords: particle in cell, Poisson solver, Vlasov equation, gravitational potential
We present a new parallel algorithm for supercomputer simulation of collisionless gravitating
systems. The algorithm combines particle-in-cell (PIC) method for solving Vlasov equation
with parallel convolution FFT-based method for calculating gravitational potential of an
isolated system. It uses a special domain decomposition technique for dynamical assignment
of processors to subdomains. It is designed to address the specifics of simulating non-
stationary rotating 2D/3D disks, in which PIC particles, representing collisionless matter, may
cross computational domain for many times during the numerical experiment. Therefore there
is a need to have an efficient load-balancing method. The parallel algorithm is suitable for
running on supercomputers with different types of architectures: traditional (CPU-based), and
hybrid (CPU with NVIDIA GPU and Intel Xeon Phi).