Параллельные вычислительные технологии (ПаВТ’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 oni 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