2010 Практикум. Пособие по выполнению (Практикум)

Ìåòîäè÷åñêîå ïîñîáèåïî âûïîëíåíèþ ïðàêòè÷åñêîãî çàäàíèÿ ïî êóðñóÑóïåðêîìïüþòåðíûå òåõíîëîãèèäëÿ ñòóäåíòîâ 5 êóðñà ÂÌÊìàðò-àïðåëü 2010 ã.Àâòîðû: Â.Þ. Âîðîíîâ, Î.Â. Äæîñàí, Í.Í. Ïîïîâà ïîä ðóêîâîäñòâîì Í.Í. Ïîïîâîé.Òåìà: Èññëåäîâàíèå ýåêòèâíîñòè ïàðàëëåëüíûõ àëãîðèòìîâ ðåøåíèÿ ñèñòåìëèíåéíûõ óðàâíåíèé íà ñóïåðêîìïüþòåðíûõ âû÷èñëèòåëüíûõ ñèñòåìàõ.Îáùàÿ îðìóëèðîâêà çàäàíèÿÈññëåäîâàíèå àëãîðèòìîâ ðåøåíèÿ ñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèéãäåA âåùåñòâåííàÿ ìàòðèöà ðàçìåðíîñòèìåðíîñòèn × n, bAx = b,âåêòîð âåøåñòâåííûõ çíà÷åíèé ðàç-n.Çàäàíèå ñîñòîèò èç 2 ÷àñòåé.

Ïåðâàÿ ÷àñòü âàðèàíòíàÿ, âòîðàÿ ÷àñòü çàäàíèÿ îäèíàêîâàÿ äëÿ âñåõ.×àñòü 1.à) Íà îñíîâå ïðåäëàãàåìîé MPI-ïðîãðàììû ðåøåíèÿ ñèñòåìû ëèíåéíûõ óðàâ-íåíèé ðåàëèçîâàòü ãèáðèäíóþ MPI/OpenMP ïðîãðàììó.b) Ïðîâåñòè èññëåäîâàíèå MPI-ïðîãðàììû äëÿ ñèñòåì Regatta p690 è Blue Gene/P.) Ïðîâåñòè èññëåäîâàíèå ýåêòèâíîñòè(óñêîðåíèÿ) ðàçðàáîòàííîé ãèáðèäíîé ïðîãðàììû íà Blue Gene/P, ñðàâíèòü ýåêòèâíîñòü MPI-ïðîãðàììû ñ ïîëó÷åííîé ãèáðèäíîé ðåàëèçàöèåé.Ìåòîä ðåøåíèÿ îïðåäåëÿåòñÿ âàðèàíòîì çàäàíèÿ.×àñòü 2.Ïðîâåñòè èññëåäîâàíèå ýåêòèâíîñòè ïàðàëëåëüíîé ïðîãðàììû ðåøåíèÿ ñè-ñòåìû ëèíåéíûõ óðàâíåíèé, èñïîëüçóþùåé ïàðàëëåëüíóþ ìàòåìàòè÷åñêóþ áèáëèîòåêóPETS.Äëÿ âûïîëíåíèÿ çàäàíèÿ ïðåäîñòàâëÿþòñÿ ïðîãðàììû ãåíåðàöèè ìàòðèöû ñèñòåìûëèíåéíûõ óðàâíåíèé (ñì.

ðàçäåë Óêàçàíèÿ ê âûïîëíåíèþ çàäàíèÿ). Ïîëíûå îïèñàíèÿðàññìàòðèâàåìûõ àëãîðèòìîâ ìîæíî íàéòè â [3, 1, 2℄. Ìàòåðèàëû ëåêöèè ïî òåõíîëîãèÿìïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ MPI è OpenMP Âëàäèìèðà Àëåêñàíäðîâè÷à Áàõòèíàäîñòóïíû â [4℄.Ôîðìà ñäà÷è çàäàíèÿ îò÷åò î âû÷èñëèòåëüíûõ ýêñïåðèìåíòàõ â ñîîòâåòñòâèè ñ òðåáîâàíèÿìè è ðàçðàáîòàííàÿ ïðîãðàììíàÿ ðåàëèçàöèÿ. Ñðîê ñäà÷è çàäàíèÿ 5 àïðåëÿ 2010ã.Âàðèàíò 1. Ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ ðåøåíèÿ ñèñòåì ëèíåéíûõ óðàâíåíèéÍà îñíîâå çàäàííîé MPI-ðåàëèçàöèè ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ ðåàëèçîâàòü ãèáðèäíóþ MPI-OpenMP ðåàëèçàöèþ ìåòîäà.

Èñõîäíûå êîäû è íåîáõîäèìàÿ èíîðìàöèÿäîñòóïíû íà ïëàòîðìå pSeries Regatta â ïàïêå/home/basrav/superomp2010/assignment_1.tar.gzàññìàòðèâàåòñÿ çàäà÷à ðåøåíèÿ ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé íàä âåùåñòâåííûìè ÷èñëàìèAx = b, ãäå ìàòðèöà A ðàçìåðíîñòè n - ñèììåòðè÷íàÿïîëîæèòåëü-íî îïðåäåëåííàÿ. Ñõåìà ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ ïðåäñòàâëåíà íà Àëãîðèòìå (1).g..generator_spd.pp.åàëèçàöèÿ ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ íàõîäèòñÿ â àéëå àðõèâàòîð ìàòðèöû ñèñòåìû óðàâíåíèé íàõîäèòñÿ â àéëå àðõèâàåíåðà-Àëãîðèòì 1 Ñõåìà ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâRequire: ñèñòåìà óðàâíåíèé Ax = b, ïîðîã òî÷íîñòèðåøåíèÿτ,ìàêñèìàëüíîå ÷èñëîM , íà÷àëüíîå ïðèáëèæåíèå ðåøåíèÿ x0k = 0 ; r0 = 0 ;for all ïîêà ||rk || = ||b − Axk || > τ è k < M dok ←k+1if k = 1 thenp1 ← r0èòåðàöèéelserrk−1 k−1βk ← rk−2rk−2pk ← rk−1 + βk pk−1end ifsk = Apkrrk−1αk = k−1pk skxk ← xk−1 + αk pkrk ← rk−1 − αk skend forreturn xkÂàðèàíò 2.

Ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ ñ ïðåäîáóñëîâëèâàòåëåì ßêîáèÄëÿ çàäàííîé MPI-ïðîãðàììû ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ áåç ïðåäîáóñëîâëèâàíèÿðåàëèçîâàòü ãèáðèäíóþ MPI/OpenMP ïðîãðàììó ñ äèàãîíàëüíûì ïðåäîáóñëîâëèâàíèåì.Èñõîäíûå êîäû è íåîáõîäèìàÿ èíîðìàöèÿ äîñòóïíû íà ïëàòîðìå pSeries Regatta âïàïêå/home/basrav/superomp2010/assignment_2.tar.gzÄèàãîíàëüíîå ïðåäîáóñëîâëèâàíèå çàêëþ÷àåòñÿ â ðåøåíèè ìåòîäîì ñîïðÿæåííûõ ãðàP −1 Ax = P −1b, ãäå P äèàãîíàëüíàÿäèåíòîâ ìîäèèöèðîâàííîé ñèñòåìû óðàâíåíèéìàòðèöà ñî çíà÷åíèÿìèp−1ij =(1aijåñëèi=j0eëèi 6= j(1)åàëèçàöèÿ ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ áåç ïðåäîáóñëîâëèâàíèÿ íàõîäèòñÿ â àéëåàðõèâàg..

åíåðàòîð ìàòðèöû ñèñòåìû óðàâíåíèé íàõîäèòñÿ â àéëå àðõèâà generator_spd.pp. êà÷åñòâå ïðîñòåéøåé ðåàëèçàöèè âûïîëíèòü ïðåîáðàçîâàíèå èñõîäíîé ñèñòåìû óðàâíåíèé äî ðàññûëêè äàííûõ ïî ïðîöåññîðàì, ò.å. â ïîñëåäîâàòåëüíîì âàðèàíòå. Ïàðàëëåëüíàÿðåàëèçàöèÿ ïðåäîáóñëîâëèâàòåëÿ ïðèâåòñòâóåòñÿ.Âàðèàíò 3. Ìåòîä ßêîáè äëÿ ðåøåíèÿ ñèñòåìû ëèíåéíûõ óðàâíåíèéÏî çàäàííîé MPI-ðåàëèçàöèè ìåòîäà ßêîáè ðåøåíèÿ ñèñòåìû ëèíåéíûõ óðàâíåíèé ðàçðàáîòàòü ãèáðèäíóþ MPI/OpenMP ðåàëèçàöèþ ìåòîäà.

Èñõîäíûå êîäû è íåîáõîäèìàÿèíîðìàöèÿ äîñòóïíû íà ïëàòîðìå pSeries Regatta â ïàïêå/home/basrav/superomp2010/assignment_3.tar.gzÊðàòêàÿ ñõåìà ìåòîäà ßêîáè ïðåäñòàâëåíà íà Àëãîðèòìå (2).jaobi.. åíåðàòîðgenerator_relax.pp.åàëèçàöèÿ ìåòîäà ßêîáè íàõîäèòñÿ â àéëå àðõèâàñèñòåìû óðàâíåíèé íàõîäèòñÿ â àéëå àðõèâàìàòðèöûÀëãîðèòì 2 Ñõåìà ìåòîäà ßêîáèRequire: ñèñòåìà óðàâíåíèé Ax = b,èòåðàöèéM,τ,A = D + R,ïîðîã òî÷íîñòè ðåøåíèÿíà÷àëüíîå ïðèáëèæåíèå ðåøåíèÿRýëåìåíòîâ, ñòîÿùèõ íà ãëàâíîé äèàãîíàëè;x0 ,ìàêñèìàëüíîå ÷èñëîãäåD ìàòðèöà èçìàòðèöà âíåäèàãîíàëüíûõ ýëåìåíòîâ.k = 0 ; r0 = 0 ;for allïîêà ||rk || = ||b − Axk || > τk ←k+1if k = 1 thenp1 ← r0èk < M doelsexk ← D −1 (b − Rxk−1 )end ifend forreturn xkÂàðèàíò 4. Ìåòîä àóññà-Çåéäåëÿ äëÿ ðåøåíèÿ ñèñòåìû ëèíåéíûõóðàâíåíèéÏî çàäàííîé MPI-ðåàëèçàöèè ìåòîäà ßêîáè ðåøåíèÿ ñèñòåìû ëèíåéíûõ óðàâíåíèé ðàçðàáîòàòü ãèáðèäíóþ MPI/OpenMP ðåàëèçàöèþ ìåòîäà àóññà-Çåéäåëÿ.

Èñõîäíûå êîäû èíåîáõîäèìàÿ èíîðìàöèÿ äîñòóïíû íà ïëàòîðìå pSeries Regatta â ïàïêå/home/basrav/superomp2010/assignment_4.tar.gzÑõåìà ìåòîäà àóññà-Çåéäåëÿ ïðåä-ñòàâëåíà íà Àëãîðèòìå (3).Àëãîðèòì 3 Ñõåìà ìåòîäà àóññà-ÇåéäåëÿRequire: ñèñòåìà óðàâíåíèé Ax = b, ïîðîãèòåðàöèéM,äèàãîíàëüþ,x0 ,L ìàòðèöà ýëåìåíòîâ, ñòîÿùèõíà÷àëüíîå ïðèáëèæåíèå ðåøåíèÿýëåìåíòîâ, ñòîÿùèõ íà ãëàâíîé äèàãîíàëè;Uτ , ìàêñèìàëüíîå ÷èñëîA = L + D + U , ãäå D ìàòðèöà èçòî÷íîñòè ðåøåíèÿïîä ãëàâíîé ìàòðèöà ýëåìåíòîâ, ñòîÿùàÿ íàä ãëàâíîé äèàãîíàëüþ.k = 0 ; r0 = 0 ;for allïîêà||rk || = ||b − Axk || > τèk < M dok ←k+1if k = 1 thenp1 ← r0elsexk ← (L + D)−1 (b − Uxk−1 )end ifend forreturn xkjaobi..

åíåðàòîðgenerator_relax.pp.åàëèçàöèÿ ìåòîäà ßêîáè íàõîäèòñÿ â àéëå àðõèâàñèñòåìû óðàâíåíèé íàõîäèòñÿ â àéëå àðõèâàìàòðèöûÂàðèàíò 5. Ìåòîä àóññà äëÿ ðåøåíèÿ ñèñòåìû ëèíåéíûõ óðàâíåíèéÏî çàäàííîé MPI-ðåàëèçàöèè ìåòîäà àóññà ðåøåíèÿ ñèñòåìû ëèíåéíûõ óðàâíåíèé ðàçðàáîòàòü ãèáðèäíóþ MPI/OpenMP ðåàëèçàöèþ ìåòîäà àóññà.

Èñõîäíûå êîäû è íåîáõîäèìàÿèíîðìàöèÿ äîñòóïíû íà ïëàòîðìå pSeries Regatta â ïàïêå/home/basrav/superomp2010/assignment_5.tar.gzåàëèçàöèÿ ìåòîäà àóññà íàõîäèòñÿ â àéëå àðõèâàìàòðèöû ñèñòåìû óðàâíåíèé íàõîäèòñÿ â àéëå àðõèâàgauss_elimination.. åíåðàòîðgenerator_relax.pp.

Ïîñêîëüêóìåòîä àóññà ÿâëÿåòñÿ ïðÿìûì, òðåáîâàíèÿ ê îò÷åòó ïî çàäàíèþ âàðèàíòà îòëè÷àþòñÿ îòäðóãèõ âàðèàíòîâ.Òðåáîâàíèÿ ê ñîäåðæàíèþ îò÷åòàÎò÷åò î âûïîëíåíèè çàäàíèÿ äîëæåí ñîäåðæàòü êðàòêîå îïèñàíèå ïðîäåëàííîé ðàáîòûïî ñîçäàíèþ ãèáðèäíîãî êîäà, êðàòêîå îïèñàíèå òîãî, êàê îðìóëèðóåòñÿ çàäà÷à (êàêîåâûáðàíî ðåøåíèå, íà÷àëüíîå ïðèáëèæåíèå, ïîðîã òî÷íîñòè ðåøåíèÿ, ìàêñèìàëüíîå ÷èñëîèòåðàöèé) è âêëþ÷àòü ñëåäóþùèå ðåçóëüòàòû ðàñ÷åòîâ:0) Íà ïëàòîðìå Regatta: íåîáõîäèìî ïîñòðîèòü ãðàèê óñêîðåíèÿ MPI-ïðîãðàììûäëÿ ÷èñëà ïðîöåññîðîânp = 1, 2, 4, 8è ÑËÀÓ ðàçìåðíîñòèN = 1024, 2048, 4096.à) Ïî ïåðâîé ÷àñòè çàäàíèÿ (ãèáðèäíàÿ ðåàëèçàöèÿ):1.

Ïîñòðîèòü òàáëèöó, ñîäåðæàùóþ âðåìÿ ðåøåíèÿ, ÷èñëî èòåðàöèé ïðè ðåøåíèè ñè-N = 1024, 2048, 4096 äëÿ ÷èñëà óçëîâ npðåæèìå mode = SMP ñ 3 íèòÿìè. Äëÿ ïðÿìîãîñòåìû ëèíåéíûõ óðàâíåíèé ðàçìåðíîñòè= 1, 2, 4, 8, 16, 32, 64, 128âÒàáëèöà 1: Ïðèìåð òàáëèöû èç çàäàíèÿ à).1×èñëî óçëîâ nàçìåðíîñòü ÑËÀÓ Âðåìÿ ðåøåíèÿÓñêîðåíèåÊîë-âî èòåðàöèéNSI110242102441024810241610243210246410241281024120482204842048820481620483220486420481282048140962409644096840961640963240966440961284096ìåòîäà àóññàíîñòè ðåøåíèÿ.Tâ òàáëèöå óêàçàòü âìåñòî ÷èñëà èòåðàöèé ïîëó÷àåìóþ ñòåïåíü òî÷-np = 1, 2, 4, 8, 16, 32, 64,128 äëÿ ðåæèìà âûïîëíåíèÿ çàäà÷ mode = SMP ñ òðåìÿ OpenMP-íèòÿìè äëÿ ðàçìåðíîñòè ñèñòåìû óðàâíåíèé N = 1024, 2048, 4096. Óñêîðåíèå âû÷èñëÿåòñÿ ïî îðìó-2.

ðàèêè óñêîðåíèÿ ïðîãðàììû äëÿ ÷èñëà óçëîâëå:S(n) =ãäåT (n)T (ïîñëåäîâàòåëüíàÿT (n)ïðîãðàììà), âðåìÿ ñ÷åòà ïðîãðàììû íà çàäàííîì ÷èñëå ïðîöåññîðîâ.èñ. 1: Ïðèìåð ãðàèêà äëÿ çàäàíèÿ à).23. ðàèê çíà÷åíèé íîðìû íåâÿçêèóçëîânp = 128||rn ||â çàâèñèìîñòè îò íîìåðà èòåðàöèè äëÿ ÷èñëàè ðàçìåðà ñèñòåìû óðàâíåíèéâûïîëíåíèÿ çàäà÷èmode = SMPñ 3 íèòÿìè.N = 1024, 2048, 4096äëÿ ðåæèìàÄëÿ ïðÿìîãî ìåòîäà àóññàäàííûéãðàèê â îò÷åòå íå òðåáóåòñÿ.á) Ïî âòîðîé ÷àñòè çàäàíèÿ (èçó÷åíèå ýåêòèâíîñòè àëãîðèòìîâ èç ïàêåòàPETS):1. Ïîñòðîèòü ãðàèêè óñêîðåíèÿ ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ (áåç ïðåäîáóñëîâëèâàíèÿ, ñ äèàãîíàëüíûì ïðåäîáóñëîâëèâàòåëåì ßêîáè, èòîãî 2 ãðàèêà) äëÿ àíàëî-N = 1024, 2048, 4096 è òðåáîâàíèé ê òî÷íîñòè ðåøåíèÿ τäëÿ ÷èñëà óçëîâ np = 1, 2, 4, 8, 16, 32, 64, 128 â ðåæèìå mode = VN.

Ïîñêîëü-ãè÷íûõ ðàçìåðîâ çàäà÷èêó ðàññìàòðèâàåìûå ñèñòåìû óðàâíåíèé ãåíåðèðóþòñÿ ïñåâäî-ñëó÷àéíî, ñõîäèìîñòüìåòîäîâ äëÿ çàäàííîé òî÷íîñòè ðåøåíèÿ íå âñåãäà äîñòèãàåòñÿ.  ñëó÷àå îòñóòñòâèÿñõîäèìîñòè ïîñòðîèòü ãðàèêè óñêîðåíèÿ äëÿ îäèíàêîâîãî çíà÷åíèÿ ìàêñèìàëüíîãî÷èñëà èòåðàöèé (íàïðèìåð, 50 èòåðàöèé).Óêàçàíèÿ ê âûïîëíåíèþ çàäàíèÿ1. Äëÿ èññëåäîâàíèÿ ýåêòèâíîñòè ïðîãðàììû ïðåäîñòàâëåí ãåíåðàòîð ïñåâäî-ñëó÷àéíûõñèììåòðè÷íûõ ïîëîæèòåëüíî îïðåäåëåííûõ ìàòðèö (äëÿ ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ) è ìàòðèö îñîáîãî âèäà äëÿ îñòàëüíûõ ìåòîäîâ.

Ôàéëû ñ èñõîäíûìè òåêñòàìè ãåíåðàòîðîâgenerator_spd.ègenerator_relax.ñîîòâåñòâåííî íàõîäèòñÿâ àðõèâå ñ çàäàíèåì. àñïàêîâàòü àðõèâ ìîæíî ñëåäóþùèìè êîìàíäàìè:>gunzip assignment_N.tar.gz>tar -xvf assignment_N.tarÈñïîëüçîâàíèå ãåíåðàòîðà:>xlC generator_spd.pp -o generator_spd # äëÿ ïåðâîãî ãåíåðàòîðà>xlC generator_relax.pp -o generator_relax # äëÿ âòîðîãî ãåíåðàòîðà>./generator_spd N output_file>./generator_relax N output_fileãäåN ðàçìåðíîñòü ãåíåðèðóåìîé ìàòðèöû,ñîõðàíåíà ìàòðèöà.Îáðàòèòå âíèìàíèå,output_file àéë, â êîòîðûé áóäåò÷òî â MPI-ðåàëèçàöèÿõ çàäàíèÿ ïðåäïî-ëàãàåòñÿ, ÷òî ðàçìåðíîñòü ìàòðèöû äîëæíà íàöåëî äåëèòüñÿ íà ÷èñëî ïðîöåññîðîâïðè çàïóñêå ïðîãðàììû.2. Ñîçäàíèå âåêòîðà ïðàâîé ÷àñòèbïðåäëàãàåòñÿ âûïîëíÿòü èç èçâåñòíîãî ðåøåíèÿx ïóòåì óìíîæåíèÿ b = Ax.  ïðåäëàãàåìûõ MPI-ðåàëèçàöèÿõ óíêöèÿ double*GenerateSolution(int size) ñîçäàåò ðåøåíèå x, ïî êîòîðîìó âû÷èñëÿåòñÿ âåêòîðïðàâîé ÷àñòè.