assignment

Ìåòîäè÷åñêîå ïîñîáèåïî âûïîëíåíèþ ïðàêòè÷åñêîãî çàäàíèÿ ïî êóðñóÑóïåðêîìïüþòåðíûå òåõíîëîãèèäëÿ ñòóäåíòîâ 5 êóðñà ÂÌÊîêòÿáðü-äåêàáðü 2011 ã.Àâòîðû: Â.Þ. Âîðîíîâ, Î.Â. Êîðæ, Í.Í. Ïîïîâà.Òåìà: Èññëåäîâàíèå ýôôåêòèâíîñòè ïàðàëëåëüíûõ àëãîðèòìîâ ðåøåíèÿ ñèñòåìëèíåéíûõ óðàâíåíèé íà ñóïåðêîìïüþòåðíûõ âû÷èñëèòåëüíûõ ñèñòåìàõ.Îáùàÿ ôîðìóëèðîâêà çàäàíèÿÈññëåäîâàíèå ýôôåêòèâíîñòè àëãîðèòìîâ ðåøåíèÿ ñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèéAx = b, ãäå An. âåùåñòâåííàÿ ìàòðèöà ðàçìåðíîñòèn × n, bâåùåñòâåííûé âåêòîððàçìåðíîñòèÏîñòàíîâêà çàäà÷è.Íà îñíîâå ïðåäëàãàåìîé ïàðàëëåëüíîé MPI-ïðîãðàììû, ðåàëè-çóþùåé ðåøåíèå ñèñòåìû ëèíåéíûõ óðàâíåíèé, âûïîëíèòü íàñòðîéêó åå ýôôåêòèâíîñòè,èñïîëüçóÿ âîçìîæíîñòè êîìïèëÿòîðà, è ïðîâåñòè èññëåäîâàíèå ýôôåêòèâíîñòè ïðîãðàììû.à) Íà îñíîâå ïðåäëàãàåìîé MPI-ïðîãðàììû ðåøåíèÿ ñèñòåìû ëèíåéíûõ óðàâíåíèéðåàëèçîâàòü ãèáðèäíóþ MPI/OpenMP ïðîãðàììó.b) Ïðîâåñòè èññëåäîâàíèå MPI-ïðîãðàììû äëÿ âû÷èñëèòåëüíûõ ñèñòåì Regatta p690,Blue Gene/P è ñóïåðêîìïüþòåðà "Ëîìîíîñîâ".c) Ïðîâåñòè èññëåäîâàíèå ýôôåêòèâíîñòè(óñêîðåíèÿ) ðàçðàáîòàííîé ãèáðèäíîé ïðîãðàììû íà Blue Gene/P, ñðàâíèòü ýôôåêòèâíîñòü MPI-ïðîãðàììû ñ ïîëó÷åííîé ãèáðèäíîé ðåàëèçàöèåé.Ìåòîä ðåøåíèÿ îïðåäåëÿåòñÿ âàðèàíòîì çàäàíèÿ.Äëÿ âûïîëíåíèÿ çàäàíèÿ ïðåäîñòàâëÿþòñÿ ïðîãðàììû ãåíåðàöèè ìàòðèöû ñèñòåìûëèíåéíûõ óðàâíåíèé (ñì.

ðàçäåë Óêàçàíèÿ ê âûïîëíåíèþ çàäàíèÿ). Ïîëíûå îïèñàíèÿðàññìàòðèâàåìûõ àëãîðèòìîâ ìîæíî íàéòè âÁàõâàëîâ et al. [1987], Golub and Van Loan[1996], Saad [2003].Ôîðìà ñäà÷è çàäàíèÿ îò÷åò î âû÷èñëèòåëüíûõ ýêñïåðèìåíòàõ â ñîîòâåòñòâèè ñ òðåáîâàíèÿìè è ðàçðàáîòàííàÿ ïðîãðàììíàÿ ðåàëèçàöèÿ.Èñõîäíûé êîä è íåîáõîäèìàÿ èíôîðìàöèÿ ïî çàäàíèþ äîñòóïíû ïî ññûëêåhttp://angel.cmc.msu.ru/~popova/SuperComp2011/assignment[1-5].tar.gzÂàðèàíò 1. Ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ ðåøåíèÿ ñèñòåì ëèíåéíûõ óðàâíåíèéÍà îñíîâå çàäàííîé MPI-ðåàëèçàöèè ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ ðåàëèçîâàòü ãèáðèäíóþ MPI-OpenMP ðåàëèçàöèþ ìåòîäà.

Èñõîäíûå êîäû è íåîáõîäèìàÿ èíôîðìàöèÿäîñòóïíû íà ïëàòôîðìå pSeries Regatta â ïàïêåÐàññìàòðèâàåòñÿ çàäà÷à ðåøåíèÿ ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé íàäâåùåñòâåííûìè ÷èñëàìèAx = b,ãäå ìàòðèöàAðàçìåðíîñòèn- ñèììåòðè÷íàÿ ïîëîæè-òåëüíî îïðåäåëåííàÿ. Ñõåìà ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ ïðåäñòàâëåíà íà Ðèñ.1 (1).cg.c.generator_spd.cpp.Ðåàëèçàöèÿ ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ íàõîäèòñÿ â ôàéëå àðõèâàòîð ìàòðèöû ñèñòåìû óðàâíåíèé íàõîäèòñÿ â ôàéëå àðõèâàÃåíåðà-Àëãîðèòì 1 Ñõåìà ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâRequire: ñèñòåìà óðàâíåíèé Ax = b, ïîðîã òî÷íîñòèðåøåíèÿτ,ìàêñèìàëüíîå ÷èñëîM , íà÷àëüíîå ïðèáëèæåíèå ðåøåíèÿ x0k = 0; r0 = 0;for all ïîêà ||rk || = ||b − Axk || > τ è k < M dok ←k+1if k = 1 thenp1 ← r0èòåðàöèéelserk−1βk ← rrk−1k−2 rk−2pk ← rk−1 + βk pk−1end ifsk = Apkrk−1αk = rk−1pk skxk ← xk−1 + αk pkrk ← rk−1 − αk skend forreturn xkÂàðèàíò 2. Ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ ñ ïðåäîáóñëîâëèâàòåëåì ßêîáèÄëÿ çàäàííîé MPI-ïðîãðàììû ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ áåç ïðåäîáóñëîâëèâàíèÿðåàëèçîâàòü ãèáðèäíóþ MPI/OpenMP ïðîãðàììó ñ äèàãîíàëüíûì ïðåäîáóñëîâëèâàíèåì.Èñõîäíûå êîäû è íåîáõîäèìàÿ èíôîðìàöèÿ äîñòóïíû íà ïëàòôîðìå pSeries Regatta âïàïêå/home/popova/SuperComp2011/assignment2.tar.gzÄèàãîíàëüíîå ïðåäîáóñëîâëèâàíèå çàêëþ÷àåòñÿ â ðåøåíèè ìåòîäîì ñîïðÿæåííûõ ãðà−1äèåíòîâ ìîäèôèöèðîâàííîé ñèñòåìû óðàâíåíèé PAx = P −1 b, ãäå P äèàãîíàëüíàÿ(ìàòðèöà ñî çíà÷åíèÿìèp−1ij=1aijåñëèi=j0ecëèi 6= j(1)Ðåàëèçàöèÿ ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ áåç ïðåäîáóñëîâëèâàíèÿ íàõîäèòñÿ â ôàéëåàðõèâàcg.c.

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

Èñõîäíûå êîäû è íåîáõîäèìàÿèíôîðìàöèÿ äîñòóïíû íà ïëàòôîðìå pSeries Regatta â ïàïêå/home/popova/SuperComp2011/assignment3.tar.gzÊðàòêàÿ ñõåìà ìåòîäà ßêîáè ïðåäñòàâëåíà íà Àëãîðèòìå (2).jacobi.c. Ãåíåðàòîðgenerator_relax.cpp.Ðåàëèçàöèÿ ìåòîäà ßêîáè íàõîäèòñÿ â ôàéëå àðõèâàñèñòåìû óðàâíåíèé íàõîäèòñÿ â ôàéëå àðõèâàìàòðèöûÀëãîðèòì 2 Ñõåìà ìåòîäà ßêîáèRequire: ñèñòåìà óðàâíåíèé Ax = b,èòåðàöèéM,Rýëåìåíòîâ, ñòîÿùèõ íà ãëàâíîé äèàãîíàëè;k = 0; r0 = 0;for allïîêà||rk || = ||b − Axk || > τèk ←k+1if k = 1 thenp1 ← r0τ,x0 , A = D + R ,ïîðîã òî÷íîñòè ðåøåíèÿíà÷àëüíîå ïðèáëèæåíèå ðåøåíèÿìàêñèìàëüíîå ÷èñëîãäåD ìàòðèöà èçìàòðèöà âíåäèàãîíàëüíûõ ýëåìåíòîâ.k < M doelsexk ← D−1 (b − Rxk−1 )end ifend forreturn xkÂàðèàíò 4.

Ìåòîä Ãàóññà-Çåéäåëÿ äëÿ ðåøåíèÿ ñèñòåìû ëèíåéíûõóðàâíåíèéÏî çàäàííîé MPI-ðåàëèçàöèè ìåòîäà ßêîáè ðåøåíèÿ ñèñòåìû ëèíåéíûõ óðàâíåíèé ðàçðàáîòàòü ãèáðèäíóþ MPI/OpenMP ðåàëèçàöèþ ìåòîäà Ãàóññà-Çåéäåëÿ. Èñõîäíûå êîäû èíåîáõîäèìàÿ èíôîðìàöèÿ äîñòóïíû íà ïëàòôîðìå pSeries Regatta â ïàïêå/home/popova/SuperComp2011/assignment4.tar.gzÑõåìà ìåòîäà Ãàóññà-Çåéäåëÿ ïðåä-ñòàâëåíà íà Àëãîðèòìå (3).Àëãîðèòì 3 Ñõåìà ìåòîäà Ãàóññà-ÇåéäåëÿRequire: ñèñòåìà óðàâíåíèé Ax = b, ïîðîãèòåðàöèéM,ýëåìåíòîâ, ñòîÿùèõ íà ãëàâíîé äèàãîíàëè;äèàãîíàëüþ,Uτ , ìàêñèìàëüíîå ÷èñëîx0 , A = L + D + U , ãäå D ìàòðèöà èçòî÷íîñòè ðåøåíèÿíà÷àëüíîå ïðèáëèæåíèå ðåøåíèÿL ìàòðèöà ýëåìåíòîâ, ñòîÿùèõ ïîä ãëàâíîé ìàòðèöà ýëåìåíòîâ, ñòîÿùàÿ íàä ãëàâíîé äèàãîíàëüþ.k = 0; r0 = 0;ïîêà ||rk || = ||b − Axk || > τk ←k+1if k = 1 thenp1 ← r0for allèk < M doelsexk ← (L + D)−1 (b − U xk−1 )end ifend forreturn xkjacobi.c. Ãåíåðàòîðgenerator_relax.cpp.Ðåàëèçàöèÿ ìåòîäà ßêîáè íàõîäèòñÿ â ôàéëå àðõèâàñèñòåìû óðàâíåíèé íàõîäèòñÿ â ôàéëå àðõèâàìàòðèöûÂàðèàíò 5.

Ìåòîä Ãàóññà äëÿ ðåøåíèÿ ñèñòåìû ëèíåéíûõ óðàâíåíèéÏî çàäàííîé MPI-ðåàëèçàöèè ìåòîäà Ãàóññà ðåøåíèÿ ñèñòåìû ëèíåéíûõ óðàâíåíèé ðàçðàáîòàòü ãèáðèäíóþ MPI/OpenMP ðåàëèçàöèþ ìåòîäà Ãàóññà. Èñõîäíûå êîäû è íåîáõîäèìàÿèíôîðìàöèÿ äîñòóïíû íà ïëàòôîðìå pSeries Regatta â ïàïêå/home/popova/SuperComp2011/assignment5.tar.gzgauss_elimination.c. Ãåíåðàòîðìàòðèöû ñèñòåìû óðàâíåíèé íàõîäèòñÿ â ôàéëå àðõèâà generator_relax.cpp. ÏîñêîëüêóÐåàëèçàöèÿ ìåòîäà Ãàóññà íàõîäèòñÿ â ôàéëå àðõèâàìåòîä Ãàóññà ÿâëÿåòñÿ ïðÿìûì, òðåáîâàíèÿ ê îò÷åòó ïî çàäàíèþ âàðèàíòà îòëè÷àþòñÿ îòäðóãèõ âàðèàíòîâ.Òðåáîâàíèÿ ê ñîäåðæàíèþ îò÷åòàÎò÷åò î âûïîëíåíèè çàäàíèÿ äîëæåí ñîäåðæàòü êðàòêîå îïèñàíèå ïðîäåëàííîé ðàáîòûïî ñîçäàíèþ ãèáðèäíîãî êîäà, êðàòêîå îïèñàíèå òîãî, êàê ôîðìóëèðóåòñÿ çàäà÷à (êàêîåâûáðàíî ðåøåíèå, íà÷àëüíîå ïðèáëèæåíèå, ïîðîã òî÷íîñòè ðåøåíèÿ, ìàêñèìàëüíîå ÷èñëîèòåðàöèé) è âêëþ÷àòü ñëåäóþùèå ðåçóëüòàòû ðàñ÷åòîâ:0) Íà ïëàòôîðìå Regatta: íåîáõîäèìî ïîñòðîèòü ãðàôèê óñêîðåíèÿ MPI-ïðîãðàììûäëÿ ÷èñëà ïðîöåññîðîânp = 1, 2, 4, 8è ÑËÀÓ ðàçìåðíîñòèN = 1024, 2048, 4096.à) Ïî ïåðâîé ÷àñòè çàäàíèÿ (ãèáðèäíàÿ ðåàëèçàöèÿ):1.

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

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

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

Ôàéëû ñ èñõîäíûìè òåêñòàìè ãåíåðàòîðîâgenerator_spd.cègenerator_relax.cñîîòâåñòâåííî íàõîäèòñÿâ àðõèâå ñ çàäàíèåì. Ðàñïàêîâàòü àðõèâ ìîæíî ñëåäóþùèìè êîìàíäàìè:>gunzip assignment_N.tar.gz>tar -xvf assignment_N.tarÈñïîëüçîâàíèå ãåíåðàòîðà:>xlC generator_spd.cpp -o generator_spd # äëÿ ïåðâîãî ãåíåðàòîðà>xlC generator_relax.cpp -o generator_relax # äëÿ âòîðîãî ãåíåðàòîðà>./generator_spd N output_file>./generator_relax N output_fileãäåN ðàçìåðíîñòü ãåíåðèðóåìîé ìàòðèöû,ñîõðàíåíà ìàòðèöà.Îáðàòèòå âíèìàíèå,output_file ôàéë, â êîòîðûé áóäåò÷òî â MPI-ðåàëèçàöèÿõ çàäàíèÿ ïðåäïî-ëàãàåòñÿ, ÷òî ðàçìåðíîñòü ìàòðèöû äîëæíà íàöåëî äåëèòüñÿ íà ÷èñëî ïðîöåññîðîâïðè çàïóñêå ïðîãðàììû.2.