并行算法的設(shè)計(jì)與分析(1)(編輯修改稿)
2025-02-03 10:53 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 小于某個(gè)臨界值時(shí)，進(jìn)行直接排序； SM的待排數(shù)組 X[1..n], Qi為 X的子數(shù)組， qi為 Qi中第 1個(gè) 元素的首地址， |Qi|=si, R是存放 (qi,si)的 SM數(shù)組 算法輸入數(shù)組 X[1..n]，輸出為排好序的數(shù)組 X[1..n] Parallel Algorithms 15 / Ch5 2022/2/4 Copyright USTC MIMDTC模型上的異步快排序算法 3. MIMDTC上的異步快排序算法 begin (1)Q1=X (2)R[1]=(q1, n) (3)生成進(jìn)程 1 (4)進(jìn)程 i: //對(duì) Qi進(jìn)行快排序 ()(qi, si)=R[i] //取出 Qi的首地址和子序列的大小 ()if si≤2 then 直接排序 Qi else (i)求 Qi的中值 m //調(diào)用串行 k選擇算法 (ii)將 m定位在 X的最終排序位置上 (iii)將 Qi劃分成小于和大于 m的 Q2i和 Q2i+1兩子序列 (iv)R[2i]=(q2i, s2i), (v) R[2i+1]=(q2i+1, s2i+1) (vi)生成進(jìn)程 2i和進(jìn)程 2i+1 end if end Parallel Algorithms 16 / Ch5 2022/2/4 Copyright USTC MIMDTC模型上的異步快排序算法 ： X={10, 3, 7, 15, 2, 4, 11, 1, 12, 6, 8, 13, 9, 16, 14, 5}, n=16, p(n)=4的執(zhí)行過程 Remark:第 0層～第 2層可以由 4個(gè)處理器并行求解，而第 3層以上 需要一個(gè)處理器順序處理多個(gè)進(jìn)程。 1 687432361113151781 231 041 41911 111 321 5 ， 1 6S im結(jié) 點(diǎn) 說 明 ：進(jìn) 程 P r iP i 處 理 器P r 1Q 1 = XP r 2Q 2 = { 3 , 7 , 2 , 4 , 1 , 6 , 5 }P r 3Q 3 = { 1 0 , 1 5 , 1 1 , 1 2 , 1 3 , 9 , 1 6 , 1 4 }P r 4P 1Q 4 = { 3 , 2 , 1 }P r 5P 3Q 5 = { 7 , 6 , 5 }P 2Q 5 = { 1 0 , 1 1 , 9 }P 4Q 6 = { 1 5 , 1 3 , 1 6 , 1 4 }P r 6P r 7P 2P 1P 1P r 8 P r 9 P r 1 0 P r 1 1P r 1 2 P r1 3P r 1 4P r 1 5P 1 P1P 3 P 3 P 2P2P 4 P 4Q i 子 序 列Parallel Algorithms 17 / Ch5 2022/2/4 Copyright USTC MIMDTC模型上的異步快排序算法 假設(shè) n=2k (k=logn), p=2l。 算法在執(zhí)行過程中動(dòng)態(tài)生成的進(jìn)程數(shù)為 2i(i=0,1,…,k 1) 所以，在第 0層～第 l層上的進(jìn)程可以由 p個(gè)處理器并行做，而第 l+1層～第 k1層上的進(jìn)程需要一個(gè)處理器順序處理多個(gè)進(jìn)程。 分情況如下： (1)對(duì)于第 0～ l層上各進(jìn)程可以并行處理，每個(gè)進(jìn)程執(zhí)行時(shí)間為 O(si)=O(n/2i) i=0~l=logp (2)對(duì)于第 (l +1)～ (k1)層上各進(jìn)程 , 順序執(zhí)行的進(jìn)程數(shù)為 2ilogp, 執(zhí)行的時(shí)間為 2ilogpO(n/2i) i=logp+1~logn1 綜上，算法的時(shí)間 當(dāng) p≤logn時(shí)，算法是成本最優(yōu)的 )l o g()()))2l o g (12(()2
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1