1673多處理機(jī)的并行和性能(編輯修改稿)
2024-11-04 19:09 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 * 1 2 6 = 5 Z ? 分配給 2個(gè)處理機(jī)，需 3級(jí)運(yùn)算 遞歸程序的并行性 ? 是研究并行算法的重要課題 ? 這里只討論線性遞歸 線性遞歸的例子 1 2 1 21 1 2 201( , , .. ., ) , ( , , .. ., )* .. .0,1nnnni i i iA a a a B b b bA B a b a b a bxx x a b i n???? ? ? ??? ? ? ?給定向量求歐幾里得內(nèi)積這可歸結(jié)為下列遞歸關(guān)系：線性遞歸的例子（續(xù)） 10 1 1001...,1nnn n ni i ip a x a x a x aH orn e rpap a x p i n???? ? ? ? ??? ? ? ?計(jì)算多項(xiàng)式寫成 法則形式，歸結(jié)為下列遞歸關(guān)系：線性遞歸的例子（續(xù)） 121211011,3... ...0( ) , 1i i inni i i i i iFi b o n a c c ifff f f i nn a a a b b bcc a b a b c i n?????? ? ? ????? ? ? ? ? ? ?計(jì)算 數(shù)列，計(jì)算 位二進(jìn)制數(shù) 和 相加時(shí)的進(jìn)位線性遞歸的例子（續(xù)） 111 1 12 2 21 23 3 31 32 31 2 30 , 0,10 0 0 . 00 0 . 00 . 0. . . . . . . ..0iii i ij jj i nn n n n n nxix c a x i nx c xx c a xx c a a xx c a a a x?? ? ???? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ???? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ??用矩陣形式：列掃算法 112 1 1 3 1 1 1 12 2 2 1 1 3 3 1 1 1 123 2 2 4 2 2 2 23 3 3 1 1 3 2 2 1 1 2 21. , ( 1 ), , ..., 。2. ( 1 ), , ...3. ( 2), , ..., 。4. ( 2), ... 。.nnnnn n nx c x na x a x a xnx c a x c a x c a xxna x a x a xnx c a x a x c a x a x???? ? ? ???? ? ? ? ?1先算 并將 播送到其余各式，用 個(gè)處理機(jī)計(jì)算用 個(gè)處理機(jī)計(jì)算把 播送到其余各式，用 個(gè)處理機(jī)計(jì)算用 個(gè)處理機(jī)計(jì)算......知道計(jì)算全部結(jié)果。需用（ n1）個(gè)處理機(jī)計(jì)算 2（ n1）步 例如：如 n=4，則需 3個(gè)處理機(jī)，用 6步 乘積形式遞歸算法 ? 當(dāng) n=4時(shí)，右邊只有 4種是不同，需用 4個(gè)處理機(jī)經(jīng) 2步算出，再用 2個(gè)處理機(jī)經(jīng) 3步算出 ? 比上一算法，少用 1步，多用 1個(gè)處理機(jī) ? N較大時(shí)，快速。 112 2 21 13 3 31 1 32 2 21 14 4 41 1 43 3 31 1 42 43 32 2 21 1( ) ( )( ) ( ) ( ) ( ). .. .. ..xcx c a cx c a c a c a cx c a c a c a c a a a c a c? ? ? ?? ? ? ??? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ?? ? ? ?程序舉例 DO 4 I=1,N 1 E(I)=3*F(I)+SIN(P(I)) 2 B(I)+D(I1)+Q(I) 3 D(I)=E(I)+B(I) 4 CONTINUE 語(yǔ)句 1提到循環(huán)前， 3構(gòu)成循環(huán) 1 3 2 3 F P D Q B D E 數(shù)據(jù)相關(guān)圖 程序的并行性分析 ? 假定一個(gè)程序包含 P1,P2,… ,Pi,… Pj,… Pn等 n個(gè)程序段，設(shè) Pi和 Pj程序段都是一條語(yǔ)句， Pi在 Pj之前執(zhí)行。 ? 數(shù)據(jù)相關(guān) ? 數(shù)據(jù)反相關(guān) ? 數(shù)據(jù)輸出相關(guān) 數(shù)據(jù)相關(guān) ? 如果 Pi的左部變量在 Pj的右部變量集內(nèi)，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1