并行算法的設(shè)計與分析(1)(編輯修改稿)
2025-02-03 10:53 本頁面
【文章內(nèi)容簡介】 小于某個臨界值時，進行直接排序； SM的待排數(shù)組 X[1..n], Qi為 X的子數(shù)組， qi為 Qi中第 1個 元素的首地址， |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)生成進程 1 (4)進程 i: //對 Qi進行快排序 ()(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)生成進程 2i和進程 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個處理器并行求解，而第 3層以上 需要一個處理器順序處理多個進程。 1 687432361113151781 231 041 41911 111 321 5 ， 1 6S im結(jié) 點 說 明 ：進 程 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í)行過程中動態(tài)生成的進程數(shù)為 2i(i=0,1,…,k 1) 所以，在第 0層～第 l層上的進程可以由 p個處理器并行做，而第 l+1層～第 k1層上的進程需要一個處理器順序處理多個進程。 分情況如下： (1)對于第 0～ l層上各進程可以并行處理，每個進程執(zhí)行時間為 O(si)=O(n/2i) i=0~l=logp (2)對于第 (l +1)～ (k1)層上各進程 , 順序執(zhí)行的進程數(shù)為 2ilogp, 執(zhí)行的時間為 2ilogpO(n/2i) i=logp+1~logn1 綜上，算法的時間 當 p≤logn時，算法是成本最優(yōu)的 )l o g()()))2l o g (12(()2
研究報告相關(guān)推薦
鄂ICP備17016276號-1