assignment (811098)
Текст из файла
Ìåòîäè÷åñêîå ïîñîáèåïî âûïîëíåíèþ ïðàêòè÷åñêîãî çàäàíèÿ ïî êóðñóÑóïåðêîìïüþòåðíûå òåõíîëîãèèäëÿ ñòóäåíòîâ 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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
