=Paper=
{{Paper
|id=Vol-1576/045
|storemode=property
|title=Parallel composition in element-by-element scheme of finite element method
|pdfUrl=https://ceur-ws.org/Vol-1576/045.pdf
|volume=Vol-1576
|authors=Sergey Kopysov,Aleksandr Novikov,Natalya Piminova
}}
==Parallel composition in element-by-element scheme of finite element method==
https://ceur-ws.org/Vol-1576/045.pdf
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
Ïàðàëëåëüíàÿ êîìïîçèöèÿ â ïîýëåìåíòíîé ñõåìå
ìåòîäà êîíå÷íûõ ýëåìåíòîâ∗
Ñ.Ï. Êîïûñîâ, À.Ê. Íîâèêîâ, Í.Ê. Ïèìèíîâà
Èíñòèòóò ìåõàíèêè ÓðÎ ÀÍ
Ïðåäëàãàåòñÿ ïîäõîä ê ïàðàëëåëüíîé êîìïîçèöèè â ïîýëåìåíòíîé ñõåìå ìåòîäà
êîíå÷íûõ ýëåìåíòîâ, ñîñòîÿùèé èç äâóõ ýòàïîâ: ðàçäåëåíèÿ ñåòêè ñ çàäàííûìè
ñâîéñòâàìè (ëîêàëèçàöèÿ íåñâÿçàííûõ ñåòî÷íûõ äàííûõ) è ñáîðêè (ñóììèðîâà-
íèÿ) ðàñïðåäåëåííûõ âåêòîðîâ. Òàêèì îáðàçîì, îáåñïå÷èâàåòñÿ áîëåå ðåãóëÿð-
íûé äîñòóï ê êîìïîíåíòàì êîíå÷íî-ýëåìåíòíûõ âåêòîðîâ è óìåíüøåíèå ÷èñëà
êîí ëèêòîâ ïðè îáðàùåíèè ê ïîäñèñòåìå ïàìÿòè. Èñïîëüçóÿ îòíîøåíèå ñîñåä-
ñòâà, îðìèðóþòñÿ ïîäìíîæåñòâà íåñâÿçàííûõ êîíå÷íûõ ýëåìåíòîâ, èñêëþ÷àþ-
ùèå ñîñòîÿíèå ãîíêè ïðè ïàðàëëåëüíîì ñóììèðîâàíèè ïîýëåìåíòíûõ âåêòîðîâ â
ïîóçëîâûå. àññìàòðèâàþòñÿ íåñêîëüêî âàðèàíòîâ êîìïîçèöèè.
Êëþ÷åâûå ñëîâà: ïàðàëëåëüíàÿ êîìïîçèöèÿ, óïîðÿäî÷åíèå íåèçâåñòíûõ, ðàçäå-
ëåíèå íåñòðóêòóðèðîâàííîé ñåòêè, ïîýëåìåíòíàÿ êîíå÷íî-ýëåìåíòíàÿ ñõåìà.
1. Ââåäåíèå
Âû÷èñëèòåëüíûå ñõåìû ðåøåíèÿ êîíå÷íî-ýëåìåíòíûõ ñèñòåì, èñêëþ÷àþùèå ÿâíîå îð-
ìèðîâàíèå ìàòðèöû êîý èöèåíòîâ (ãëîáàëüíîé ìàòðèöû æåñòêîñòè), çà ñ÷åò ïåðåíîñà
âû÷èñëåíèé íà óðîâåíü îòäåëüíûõ êîíå÷íûõ ýëåìåíòîâ ïðèíÿòî íàçûâàòü ïîýëåìåíòíû-
ìè (element-by-element) [1, 2℄. Òàêèå ñõåìû ïîçâîëÿþò íå òîëüêî îáõîäèòüñÿ áåç õðàíåíèÿ
ìàòðèöû êîý èöèåíòîâ ñèñòåìû, íî è áîëåå ý åêòèâíî èñïîëüçîâàòü êýø-ïàìÿòü çà
ñ÷åò ëîêàëèçàöèè äàííûõ [2℄. Îñíîâíûì îòëè÷èåì ïîýëåìåíòíîé ñõåìû ÿâëÿåòñÿ ñïîñîá
âû÷èñëåíèÿ ìàòðè÷íî-âåêòîðíîãî ïðîèçâåäåíèÿ, ïðè êîòîðîì èñïîëüçóþòñÿ äâà âàðèàíòà
îðãàíèçàöèè âû÷èñëåíèé: ñ èçâëå÷åíèåì äàííûõ â âåêòîð ìåíüøåãî ðàçìåðà è ðàçíåñåíèåì
äàííûõ â âåêòîð áîëüøåãî ðàçìåðà [3℄.
 áîëüøèíñòâå ñëó÷àåâ êîíå÷íî-ýëåìåíòíûå àïïðîêñèìàöèè ñòðîÿòñÿ íà íåñòðóêòóðè-
ðîâàííûõ ðàñ÷åòíûõ ñåòêàõ, ÷òî ïðèâîäèò ê íåðåãóëÿðíîìó äîñòóïó ê ñåòî÷íûì äàííûì
ñóùåñòâåííî óìåíüøàþùèì ý åêòèâíîñòü ïàðàëëåëüíûõ âû÷èñëåíèé. Óçêèì ìåñòîì ïî-
ýëåìåíòíûõ êîíå÷íî-ýëåìåíòíûõ ñõåì ÿâëÿåòñÿ ñóììèðîâàíèå êîìïîíåíò èç ïîýëåìåíòíûõ
âåêòîðîâ. Ïðè ïàðàëëåëüíîì ñóììèðîâàíèè êîìïîíåíò, ñîîòâåòñòâóþùèõ îáùèì óçëàì ñåò-
êè âîçíèêàåò, òàê íàçûâàåìîå ñîñòîÿíèå ãîíêè, êîãäà íåñêîëüêî ïàðàëëåëüíûõ âû÷èñëèòåëü-
íûõ ïðîöåññîâ îáðàùàþòñÿ ê îäíîé ÿ÷åéêå ïàìÿòè. Äàííàÿ îïåðàöèÿ ñóììèðîâàíèÿ âêëþ-
÷àåò â ñåáÿ: ÷òåíèå òåêóùåãî çíà÷åíèÿ êîìïîíåíòû, ÷òåíèå êîìïîíåíòû èç ïîýëåìåíòíîãî
âåêòîðà, ñëîæåíèå òåêóùåãî çíà÷åíèÿ ñ ïîýëåìåíòíîé êîìïîíåíòîé è çàïèñü ðåçóëüòàòà.
Ñîñòîÿíèå ãîíêè ïðèâîäèò ê âû÷èñëèòåëüíûì îøèáêàì, êîòîðûå ìîãóò áûòü ñâÿçàíû, êàê
ñ ÷òåíèåì òåêóùåãî çíà÷åíèÿ êîìïîíåíòû âåêòîðà, òàê è ñ çàïèñüþ ðåçóëüòàòà.
Äëÿ òîãî, ÷òîáû èñêëþ÷èòü òàêèå îøèáêè ïðåäëàãàåòñÿ óïîðÿäî÷åíèå êîíå÷íî-ýëåìåíò-
íûõ íåèçâåñòíûõ, ïðè êîòîðîì îäíîâðåìåííî â ñóììèðîâàíèè íå ó÷àñòâóþò êîíå÷íûå ýëå-
ìåíòû, ñîäåðæàùèå îáùèå âåðøèíû. Èñïîëüçóÿ îòíîøåíèÿ ñîñåäñòâà, âûäåëÿþòñÿ ñëîè
êîíå÷íûõ ýëåìåíòîâ, ïðè ïîìîùè êîòîðûõ ñåòêà ðàçäåëÿåòñÿ íà ïîäìíîæåñòâà êîíå÷íûõ
ýëåìåíòîâ äëÿ êàæäîãî ïàðàëëåëüíîãî âû÷èñëèòåëüíîãî ïðîöåññà. Ïîýëåìåíòíûå âåêòî-
ðû íàñëåäóþò ïîëó÷åííîå óïîðÿäî÷åíèå ñòåïåíåé ñâîáîäû. Òàêèì îáðàçîì ñóììèðîâàíèå
(ñáîðêà) âåêòîðîâ ðàññìàòðèâàåòñÿ âî âçàèìîñâÿçè ñ óïîðÿäî÷åíèåì, êàê ÷àñòü ïîýëåìåíò-
íîé îïåðàöèè êîìïîçèöèè.
∗
àáîòà âûïîëíåíà ïðè ïîääåðæêå ÔÔÈ (ïðîåêòû 16-01-00129-a, 14-01-00055-a).
555
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
2. Êîìïîçèöèÿ â ïîýëåìåíòíîé ñõåìå
ìåòîäà êîíå÷íûõ ýëåìåíòîâ
Êîíå÷íî-ýëåìåíòíûå âû÷èñëåíèÿ ïðåäïîëàãàþò ïðèìåíåíèå àëãîðèòìîâ, â êîòîðûõ êðî-
ìå ïàðàëëåëüíûõ è ïîñëåäîâàòåëüíûõ âû÷èñëåíèé ñóùåñòâóþò îïåðàöèè, îáúåäèíÿþùèå
(ñóììèðóþùèå) äàííûå èç ïàðàëëåëüíûõ âåòâåé àëãîðèòìà, íà îñíîâå íåêîòîðîãî ðàçäåëå-
íèÿ. Ýòè îïåðàöèè áóäåì íàçûâàòü êîìïîçèöèåé èëè îïåðàöèÿìè êîìïîçèöèè. Áóäåì ïîëà-
ãàòü, ÷òî êîìïîçèöèÿ ñîñòîèò èç äâóõ ýòàïîâ, âçàèìîñâÿçàííûõ, íî ðàçíåñåííûõ ïî âðåìåíè
âûïîëíåíèÿ: 1) ðàçäåëåíèå ñ çàäàííûìè ñâîéñòâàìè (ëîêàëèçàöèÿ äàííûõ è ñáàëàíñèðîâàí-
íîñòü âû÷èñëèòåëüíîé íàãðóçêè); 2) îáúåäèíåíèå / ñóììèðîâàíèå (ñáîðêà) ðàñïðåäåëåííûõ
äàííûõ. Ýòàï ðàçäåëåíèÿ ïðåäøåñòâóåò ñîîòâåòñòâóþùåìó øàãó âû÷èñëèòåëüíîé ñõåìû ìå-
òîäà êîíå÷íûõ ýëåìåíòîâ, à ýòàï ñáîðêè ÿâëÿåòñÿ ÷àñòüþ ýòîãî øàãà.
Êàê ïðàâèëî, â ìåòîäå êîíå÷íûõ ýëåìåíòîâ ïîä ñáîðêîé (àíñàìáëèðîâàíèåì) A ïîä-
ðàçóìåâàåòñÿ ñóììèðîâàíèå ëîêàëüíûõ ìàòðèö æåñòêîñòè êîíå÷íûõ ýëåìåíòîâ â ãëîáàëü-
íóþ ìàòðèöó æåñòêîñòè ñèñòåìû óðàâíåíèé K = AT K̃A [4, 5℄, ãäå K ∈ RN ×N ãëî-
áàëüíàÿ ìàòðèöà æåñòêîñòè; K̃ ∈ RÑ ×Ñ áëî÷íî-äèãîíàëüíàÿ ìàòðèöà, ñîñòàâëåííàÿ èç
Pm
ëîêàëüíûõ ìàòðèö æåñòêîñòè êîíå÷íûõ ýëåìåíòîâ; Ñ = e=1 Ne , çäåñü m ÷èñëî êî-
íå÷íûõ ýëåìåíòîâ, Ne ÷èñëî ñòåïåíåé ñâîáîäû â êîíå÷íîì ýëåìåíòå e. Äàííàÿ îïåðàöèÿ
îñóùåñòâëÿåòñÿ ïðè ïîìîùè îòîáðàæåíèÿ ëîêàëüíîãî ïðîñòðàíñòâà íîìåðîâ íåèçâåñòíûõ
(ñòåïåíåé ñâîáîäû) [1, 2, . . . , Ne ] â ãëîáàëüíîå [1, 2, . . . , N ]. Îïåðàöèÿ ðåàëèçóåòñÿ èëè â âèäå
êîñâåííîé èíäåêñàöèè íåèçâåñòíûõ, èëè â âèäå àðè ìåòè÷åñêèõ îïåðàöèé óìíîæåíèÿ
íà ìàòðèöó èíöèäåíòíîñòè, êîòîðîå â ïîýëåìåíòíûõ ñõåìàõ ý åêòèâíî âûïîëíÿåòñÿ íà
ãðà è÷åñêèõ óñêîðèòåëÿõ [6℄.  ïîýëåìåíòíûõ ñõåìàõ ñáîðêà ïåðåíîñèòñÿ íà ýòàï ðåøå-
íèÿ êîíå÷íîé ýëåìåíòíîé ñèñòåìû è ïðèìåíÿåòñÿ óæå íå ê ìàòðèöàì, à ê âåêòîðàì â âèäå
q = Kp = AT K̃Ap = AT q̃ . Ýòî ïîçâîëÿåò ðàçäåëèòü ïðîèçâåäåíèå q = Kp íà äâå îïåðà-
öèè: ïîýëåìåíòíîå ïðîèçâåäåíèå q̃ = K̃Ap è ñáîðêó q = AT q̃ , ñóùåñòâåííî îòëè÷àþùèåñÿ,
êàê ïî ñòåïåíè ïàðàëëåëèçìà, òàê è, â ñëó÷àå íåñòðóêòóðèðîâàííûõ ñåòîê, ïî ëîêàëèçàöèè
äàííûõ.
Äëÿ ïîýëåìåíòíûõ âû÷èñëèòåëüíûõ ñõåì, â êà÷åñòâå îñíîâíîãî âàðèàíòà ðàçäåëåíèÿ
áóäåì ðàññìàòðèâàòü óïîðÿäî÷åíèå ñ âûäåëåíèåì íåñâÿçàííûõ ïîäìíîæåñòâ êîíå÷íûõ ýëå-
ìåíòîâ. Êàæäîìó òàêîìó ïîäìíîæåñòâó ñòàâèòñÿ â ñîîòâåòñòâèå ïàðàëëåëüíûé ïðîöåññ
è/èëè ìíîæåñòâî íèòåé, à ýòàï ñáîðêè ïðèìåíÿåòñÿ ê íåñâÿçàííûì êîíå÷íûì ýëåìåíòàì.
3. àçäåëåíèå ñåòêè íà ïîäìíîæåñòâà ÿ÷ååê.
Áóäåì ñ÷èòàòü, ÷òî äâà ïîäìíîæåñòâà ÿ÷ååê ñåòêè íå ñâÿçàíû â äàííûé ìîìåíò âðåìå-
íè, åñëè îäíîâðåìåííî èçâëåêàåìûå èç ýòèõ ïîäìíîæåñòâ ÿ÷åéêè ñåòêè íå ñîäåðæàò îáùèõ
âåðøèí. Òàêèì îáðàçîì, îãðàíè÷åíèå íà ñâÿçàííîñòü ÿ÷ååê íàêëàäûâàåòñÿ òîëüêî íà ìî-
ìåíò îáðàùåíèÿ ê ïîäìíîæåñòâó. Ýòî îçíà÷àåò, ÷òî ÿ÷åéêè âíóòðè ïîäìíîæåñòâà è ñàìè
ïîäìíîæåñòâà ìîãóò áûòü òîïîëîãè÷åñêè ñâÿçàíû.
Ñîîòâåòñòâóþùèå ðàçäåëåíèÿ ñåòêè âû÷èñëÿþòñÿ ïðè ïîìîùè ðàçäåëåíèÿ ñåòêè íà
íåïåðåêðûâàþùèåñÿ ñëîè ÿ÷ååê è ïîñëåäóþùåãî îáúåäèíåíèÿ ñëîåâ (ÿ÷ååê) â ïîäìíîæåñòâà
ÿ÷ååê (áëîêè). àçäåëåíèå ñåòêè íà ñëîè îñóùåñòâëÿåòñÿ, èñõîäÿ èç îòíîøåíèÿ ñîñåäñòâà
ÿ÷ååê ïî ñëåäóþùåìó àëãîðèòìó: çàäàåòñÿ íà÷àëüíûé ñëîé s1 ; ïîñëåäóþùèå ñëîè îïðåäå-
(i)
ëÿþòñÿ èç âûðàæåíèÿ si = Adj(si−1 ) \ si−1 . Çäåñü si = {ej } ìíîæåñòâî ÿ÷ååê (êîíå÷íûõ
(i) S i (i)
ýëåìåíòîâ) ñåòêè â ñëîå i; ej ÿ÷åéêà íîìåðîì j â ñëîå i; Adj(si ) = m j=1 Adj(ej )
ìíîæåñòâî ÿ÷ååê ñåòêè ñîñåäíèõ (ñìåæíûõ) ñî ñëîåì i; mi ÷èñëî ÿ÷ååê â ñëîå. Ïðè îðìè-
ðîâàíèè ñëîè ÿ÷ååê ñåòêè íóìåðóþòñÿ è îïðåäåëÿåòñÿ èõ ÷èñëî ns . Îòíîøåíèå ñîñåäñòâà
äëÿ ÿ÷ååê ñ îðìóëèðóåì ñëåäóþùèì îáðàçîì: äâå ÿ÷åéêè ñåòêè áóäåì ñ÷èòàòü ñîñåäíèìè,
åñëè îíè ñîäåðæàò õîòÿ áû îäèí îáùèé óçåë.
Íà ðèñ. 1 ïðåäñòàâëåíû 64 ñëîÿ, ïîëó÷åííûå äëÿ íåñòðóêòóðèðîâàííîé ñåòêè, ñîñòîÿùåé
556
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
èç 31744 øåñòèãðàííèêîâ è 36873 óçëîâ. Öâåòàìè âûäåëåíû ñëîè ñ ÷åòíûìè è íå÷åòíûìè
íîìåðàìè. Ïî ïîñòðîåíèþ ÿ÷åéêè èç ðàçíûõ ñëîåâ îäíîãî öâåòà íå ÿâëÿþòñÿ ñîñåäíèìè.
èñ. 1. àçäåëåíèå ñåòêè íà ñëîè.
Íà îñíîâå ïîëó÷åííûõ ñëîåâ ñåòêè ðàññìàòðèâàëîñü íåñêîëüêî âàðèàíòîâ ïîñòðîåíèÿ
ïîäìíîæåñòâ ÿ÷ååê:
S s
1. Áëî÷íûé. Îáúåäèíåíèå ñëîåâ ñåòêè S = ni=1 si â ñîîòâåòñòâèè ñ ïîðÿäêîâûìè íîìå-
ðàìè ñëîåâ, äàëåå ðàçäåëåíèå ïîëó÷åííîãî îáúåäèíåíèÿ íà ïîäìíîæåñòâà Si , i = 1, np
ðàçìåðà m/np , ãäå np ÷èñëî ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ ïðîöåññîâ (ðèñ. 2);
2. Íå÷åòíî-÷åòíûé. Îáúåäèíåíèå â ïîäìíîæåñòâà Si , i = 1, np ñíà÷àëà âñåõ ñëîåâ ñ
íå÷åòíûìè íîìåðàìè, à çàòåì ñ ÷åòíûìè (ðèñ. 3à).  êà÷åñòâå ïðèìåðà íà ðèñ. 3á
ïîêàçàíî ïîäìíîæåñòâî S1 .
èñ. 2. Ïîäìíîæåñòâà ÿ÷ååê ñåòêè, ïîëó÷åííûå ïðè áëî÷íîì âàðèàíòå ïîñòðîåíèÿ.
à) á)
èñ. 3. Íå÷åòíî-÷åòíûé âàðèàíò ïîñòðîåíèÿ ïîäìíîæåñòâ ÿ÷ååê: à) ãðóïïû èç âîñüìè ñëîåâ,
ÿ÷åéêè èç êîòîðûõ ó÷àñòâóþò â ïàðàëëåëüíûõ âû÷èñëåíèÿõ, âûïîëíÿåìûõ np = 8 ïðîöåññàìè;
á)ïîñëåäîâàòåëüíîñòü ñëîåâ ñåòêè, îáðàçóþùèõ ïîäìíîæåñòâî S1 , íàä ÿ÷åéêàìè êîòîðîãî ïðîöåññ
ñ íîìåðîì íîëü âûïîëíÿåò ñáîðêó q = AT1 q̃ , çäåñü AT1 ⊂ AT .
557
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
Êàê âèäíî èç ðèñ. 2, â áëî÷íîì âàðèàíòå íåêîòîðûå ñëîè íåñòðóêòóðèðîâàííîé ñåòêè ðàç-
äåëåíû íà ÷àñòè, ïðèíàäëåæàùèå ñîñåäíèì ïîäìíîæåñòâàì. Áëàãîäàðÿ ðàçäåëåíèþ ñëîåâ
ïîëó÷àþòñÿ ðàâíûå ïî ÷èñëó ÿ÷ååê ïîäìíîæåñòâà è ñîîòâåòñòâåííî äîñòèãàþòñÿ ðàâíûå
âû÷èñëèòåëüíûå íàãðóçêè íà ïàðàëëåëüíûå ïðîöåññû â ïîýëåìåíòíîé ñõåìå.
Ñëåäóåò îòìåòèòü, ÷òî â íå÷åòíî-÷åòíîì âàðèàíòå òîïîëîãè÷åñêè ñâÿçàííûå íå÷åòíûå
è ÷åòíûå ñëîè ðàçíåñåíû â áëîêàõ ïî âðåìåíè âûïîëíåíèÿ âû÷èñëåíèé (ðèñ.3á). Îäíîâðå-
ìåííî â âû÷èñëåíèÿõ çàäåéñòâîâàíû ÿ÷åéêè (ðèñ.3à) èç âîñüìè íåñâÿçàííûõ ñëîåâ.
4. åçóëüòàòû âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ.
Îñòàíîâèìñÿ íà ïðåäâàðèòåëüíûõ ðåçóëüòàòàõ âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ. Ïðåä-
ëîæåííûå âàðèàíòû ðàñïàðàëëåëèâàíèÿ îïåðàöèè êîìïîçèöèè àïðîáèðîâàëèñü íà ñåòêàõ
øåñòèãðàííûõ êîíå÷íûõ ýëåìåíòîâ, ïðèìåíÿåìûõ ïðè ðåøåíèè äèíàìè÷åñêîé çàäà÷è òåî-
ðèè óïðóãîñòè â òðåõìåðíîé ïîñòàíîâêå, è ñîïðÿæåííûõ çàäà÷ äå îðìèðîâàíèÿ è ãàçîâîé
äèíàìèêè [3℄. Âû÷èñëèòåëüíûå ýêñïåðèìåíòû îñóùåñòâëÿëèñü íà âîñüìèÿäåðíîì óçëå êëà-
ñòåðà X4 (Èíñòèòóò ìåõàíèêè ÓðÎ ÀÍ), â êîòîðîì óñòàíîâëåíû: äâà ÑPU Intel Xeon
E5-2609 Quad Core 2.4GHz, 64 Á îïåðàòèâíîé ïàìÿòè. Ïðîãðàììíîå îáåñïå÷åíèå: îïåðà-
öèîííàÿ ñèñòåìà Linux 3.2.68, êîìïèëÿòîð g++ 4.7.2, ïðè êîìïèëÿöèè ïðèëîæåíèÿ
ïðèìåíÿëàñü îïòèìèçàöèÿ òðåòüåãî óðîâíÿ.
àñïàðàëëåëèâàíèå îïåðàöèè ñáîðêè q = AT q̃ âûïîëíÿëîñü â ðàìêàõ ìîäåëè îáùåé
ïàìÿòè ñðåäñòâàìè OpenMP: ðàññìàòðèâàëèñü âàðèàíòû ðàñïàðàëëåëèâàíèÿ öèêëà ïî êî-
íå÷íûì ýëåìåíòàì ïðè ïîìîùè äèðåêòèâû OpenMP for è ÿâíîå ðàñïàðàëëåëèâàíèå, èñõîäÿ
èç íîìåðà íèòè.
Ñëåäóåò îòìåòèòü, ÷òî íà íåñòðóêòóðèðîâàííîé ñåòêå ñ óïîðÿäî÷åíèåì ÿ÷ååê (ïî ïî-
ñòðîåíèþ, îïåðàöèÿ ñáîðêè âûçûâàëà ñîñòîÿíèå ãîíêè, ÷òî ïðèâîäèëî ê âû÷èñëèòåëüíîé
ïîãðåøíîñòè. Äî ïðèìåíåíèÿ óïîðÿäî÷åíèÿ, ñîñòîÿíèå ãîíêè óñòðàíÿëîñü ïðè ïîìîùè äè-
ðåêòèâû riti al.  òàêîì ñëó÷àå âðåìÿ ñáîðêè áûëî ñóùåñòâåííî áîëüøå, ÷åì â ïîñëå-
äîâàòåëüíîì âàðèàíòå. Ïðåäëîæåííîå óïîðÿäî÷åíèå ÿ÷ååê, îäíîâðåìåííî ó÷àñòâóþùèõ â
ñáîðêå, ïîçâîëèëî èñêëþ÷èòü ñèíõðîíèçàöèþ ïðè çàïèñè â âåêòîð q èç ïàðàëëåëüíûõ âû-
÷èñëèòåëüíûõ ïðîöåññîâ (íèòåé OpenMP).
Íà íåñòðóêòóðèðîâàííûõ ñåòêàõ äëÿ ÷åòâåðòîé ÷àñòè ìåìáðàíû (ïîäîáíûõ ñåòêå, ïî-
êàçàííîé íà ðèñ.1) ñ ÷èñëîì ÿ÷ååê m = 107136, 253952, 507904 ïîëó÷åíî óñêîðåíèå 4.2 5.1
ðàçà íà âîñüìè ÿäðàõ è 3.1 3.2 ðàçà íà ÷åòûðåõ ÿäðàõ öåíòðàëüíûõ ïðîöåññîðîâ îäíî-
ãî âû÷èñëèòåëüíîãî óçëà.  ðÿäå ñëó÷àåâ, çà ñ÷åò ââåäåííîãî óïîðÿäî÷åíèÿ, íàáëþäàëîñü
ïîëóòîðà-òðåõêðàòíîå óñêîðåíèå â ïîñëåäîâàòåëüíîì âàðèàíòå ñáîðêè. Äàííûå ðåçóëüòàòû
áûëè ïîëó÷åíû áåç ó÷åòà àðõèòåêòóðíûõ îñîáåííîñòåé âû÷èñëèòåëüíîãî óçëà, ñâÿçàííûõ ñ
íåîäíîðîäíûì äîñòóïîì ê ïàìÿòè (NUMA).
Ñî÷åòàíèå ïðåäëîæåííîãî óïîðÿäî÷åíèÿ ñ èçìåíåíèåì äîñòóïà ê ïàìÿòè ïðè ïîìîùè
óòèëèòû numa tl ñ îïöèåé interleave=all ïîçâîëèëî ïîëó÷èòü óñêîðåíèå â 6.3 ðàçà ïðè ñáîðêå
íà ñåòêå èç 507904 øåñòèãðàííèêîâ íà âîñüìè ÿäðàõ äâóõ ïðîöåññîðîâ, çà ñ÷åò óìåíüøåíèÿ
äîñòóïà â ïàìÿòü àññîöèèðîâàííóþ ñ äðóãèì ïðîöåññîðîì âû÷èñëèòåëüíîãî óçëà. Óñêîðå-
íèå íà ïîýëåìåíòíîì ïðîèçâåäåíèè q̃ = K̃Ap ñîñòàâèëî ïðèìåðíî 7.7 ðàçà ïðè îòñóòñòâèè
çàâèñèìîñòè ïî äàííûì (êàæäàÿ íèòü âû÷èñëÿëà ïðîèçâåäåíèå ëîêàëüíîé ìàòðèöû æåñò-
êîñòè íà ëîêàëüíûé âåêòîð). Êàê áûëî îòìå÷åíî ðàíåå, ïðîèçâåäåíèè q = Kp, âêëþ÷àåò
ïîýëåìåíòíîå ïðîèçâåäåíèå è ñáîðêó âåêòîðà q .  ýòîì ñëó÷àå ïîëó÷åíî óñêîðåíèå â 7.6
ðàçà.
5. Çàêëþ÷åíèå.
Áëàãîäàðÿ èñêëþ÷åíèþ ñèíõðîíèçàöèè, ïðè ïðèìåíåíèè ïîýëåìåíòíîé êîìïîçèöèè ïî-
ëó÷åíî ïðèìåðíî øåñòèêðàòíîå óñêîðåíèå â îïåðàöèè ñáîðêè âåêòîðîâ íà âîñüìèÿäåðíîì
558
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
óçëå êëàñòåðà îòíîñèòåëüíî íàèëó÷øåãî ïîñëåäîâàòåëüíîãî âàðèàíòà àëãîðèòìà ñáîðêè âåê-
òîðîâ äëÿ ïîýëåìåíòíîé ñõåìû ìåòîäà êîíå÷íûõ ýëåìåíòîâ.
Äàëüíåéøèå èññëåäîâàíèÿ ïîýëåìåíòîé êîìïîçèöèè áóäóò íàïðàâëåíû íà âûÿâëåíèå
àêòîðîâ íàèáîëåå âëèÿþùèõ íà óñêîðåíèå âû÷èñëåíèé, òàêèõ êàê íóìåðàöèÿ êîìïîíåíò
ðåçóëüòèðóþùåãî âåêòîðà, óïîðÿäî÷åíèå ÿ÷ååê â ñëîÿõ ñåòêè, ðàçìåùåíèå äàííûõ íà ðàç-
íûõ óðîâíÿõ ïîäñèñòåìû ïàìÿòè âû÷èñëèòåëüíîãî óçëà.
Ïðåäëîæåííûå âàðèàíòû ðàçäåëåíèÿ ñåòêè îáîáùàþòñÿ íà áîëüøåå ÷èñëî ïðîöåññîð-
íûõ ÿäåð (MIC-àðõèòåêòóðà, GPU) è âû÷èñëèòåëüíûõ óçëîâ. Îãðàíè÷åíèå íà àëãîðèòìû
ðàçäåëåíèÿ, ñâÿçàííîå ñ ÷èñëîì ñëîåâ ñåòêè, êîòîðîå çàâèñèò îò ãåîìåòðèè îáëàñòè è ÿ÷åé-
êè ñåòêè, à òàêæå îò îáùåãî ÷èñëà ÿ÷ååê ñåòêè, îñëàáëÿåòñÿ ââåäåíèåì íåñêîëüêèõ óðîâíåé
ðàçäåëåíèÿ.
Ëèòåðàòóðà
1. Carey G.F., Barragy E., M lay R. and Sharma M. Element-by-element ve tor and parallel
omputations // Communi ations in Appl. Numer. Meth. 1988. Vol. 4. pp. 299307.
2. Êîïûñîâ Ñ.Ï., Íîâèêîâ À.Ê. Ìåòîä äåêîìïîçèöèè äëÿ ïàðàëëåëüíîãî àäàïòèâíîãî
êîíå÷íî-ýëåìåíòíîãî ìåòîäà // Âåñòíèê Óäìóðòñêîãî óíèâåðñèòåòà. Ìàòåìàòèêà.
Ìåõàíèêà. Êîìïüþòåðíûå íàóêè. 2010. 3. Ñ. 141154.
3. Êîïûñîâ Ñ.Ï., Êóçüìèí È.Ì., Íåäîæîãèí Í.Ñ., Íîâèêîâ À.Ê., û÷êîâ Â.Í.,
Ñàãäååâà Þ.À., Òîíêîâ Ë.Å. Ïàðàëëåëüíàÿ ðåàëèçàöèÿ êîíå÷íî-ýëåìåíòíûõ
àëãîðèòìîâ íà ãðà è÷åñêèõ óñêîðèòåëÿõ â ïðîãðàììíîì êîìïëåêñå FEStudio //
Êîìïüþòåðíûå èññëåäîâàíèÿ è ìîäåëèðîâàíèå. 2014. Ò. 6. 1. Ñ. 7997.
4. Ce ka C., Lew A., Darve E. Assembly of Finite Element Methods on Graphi s Pro essors
// Int. J. Numer. Meth. Engng. 2011. Vol. 85. Issue 5. pp. 640669.
5. Markall G.R., Slemmer A., Ham D.A., Kelly P.H.J., Cantwell C.D. and Sherwin S.J. Finite
element assembly strategies on multi- ore and many- ore ar hite tures // Int. J. Numer.
Meth. Fluids. 2013. Vol. 71. Issue 1. pp. 8097.
6. Íîâèêîâ À.Ê., Êîïûñîâ Ñ.Ï., Êóçüìèí È.Ì., Íåäîæîãèí Í.Ñ. Êîíå÷íî-ýëåìåíòíûå
òåõíîëîãèè äëÿ êëàñòåðîâ ãèáðèäíîé àðõèòåêòóðû / Ïàðàëëåëüíûå âû÷èñëèòåëüíûå
òåõíîëîãèè (ÏàÂÒ'2015): òðóäû ìåæäóíàðîäíîé íàó÷íîé êîí åðåíöèè (31 ìàðòà 2
àïðåëÿ 2015 ã., ã. Åêàòåðèíáóðã). ×åëÿáèíñê: Èçäàòåëüñêèé öåíòð ÞÓð Ó, 2015.
Ñ. 442447.
559
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
Parallel omposition in element-by-element s heme
of nite element method
S.P. Kopysov, A.K. Novikov, N.K. Piminova
Institute of Me hani s UB RAS
The approa h to the parallel omposition in element-by-element s heme of nite
element method is oered. This approa h onsists of two phases: partition mesh
with desired properties (lo alization un oupled mesh data) and assembly (summation)
distributed ve tors. Thus, a regular a ess to the omponents of nite-element ve tors
is provided and the number of on i ts when a essing the memory subsystem is
redu ed. Subsets of un oupled nite elements ex luding a ra e ondition with parallel
summation of ve tors in a unit element by element are formed by using the ratio of
the adja en y. Several variants the ompositions are onsidered.
Keywords: parallel omposition, ordering unknowns, partitioning of unstru tured
mesh, element-by-element s heme, nite element method.
Referen es
1. Carey G.F., Barragy E., M lay R. and Sharma M. Element-by-element ve tor and parallel
omputations // Communi ations in Appl. Numer. Meth. 1988. Vol. 4. pp. 299307.
2. Kopysov S.P., Novikov A.K. Metod dekompozitsii dlya parallel'nogo adaptivnogo
kone hno-elementnogo metoda [Domain de omposition for parallel adaptive nite element
algorithm℄. Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Komp'yuternye
nauki [The Bulletin of Udmurt University. Mathemati s. Me hani s. Computer S ien e℄.
2010. No. 3. P. 141154.
3. Kopysov S.P., Kuzmin I.M., Nedozhogin N.S., Novikov A.K., Ry hkov V.N., Sagdeeva
Y.A., Tonkov L.E. Parallelnaya realiza iya kone hno-elementnyh algoritmov na gra heskih
uskoritelyah v programmnom komplekse FEStudio [Parallel implementation of a
nite-element algorithms on a graphi s a elerator in the software pa kage FEStudio℄.
Komp'yuternye issledovaniya i modelirovanie [Computer Resear h and Modeling℄. 2014.
Vol. 6. No. 1. P. 7997.
4. Ce ka C., Lew A., Darve E. Assembly of Finite Element Methods on Graphi s Pro essors
// Int. J. Numer. Meth. Engng. 2011. Vol. 85. Issue 5. P. 640669.
5. Markall G.R., Slemmer A., Ham D.A., Kelly P.H.J., Cantwell C.D. and Sherwin S.J. Finite
element assembly strategies on multi- ore and many- ore ar hite tures // Int. J. Numer.
Meth. Fluids. 2013. Vol. 71. Issue 1. P. 8097.
6. Novikov A.K., Kopysov S.P., Kuzmin I.M., Nedozhogin N.S. Kone hno-elementnye
teknologii dlya klasterov gibridnoj arhitektury [Finite element te hnologies for hybrid
arite ture lusters℄ Parallelnye vy hislitelnye tekhnologii (PaVT'2015): Trudy
mezhdunarodnoj nau hnoj konferentsii (Ekaterinburg, 31 marta 2 aprelya 2015) [Parallel
Computational Te hnologies (PCT'2015): Pro eedings of the International S ienti
Conferen e (Ekaterinburg, Russia, Mar h, 31 April, 2, 2015)℄. Chelyabinsk, Publishing of
the South Ural State University, 2015. P. 442447.
560