并行算法的設計與分析(1)(參考版)
2025-01-10 10:53本頁面
【正文】 ⑤⑥ 同算法 1中的 ③④ ； Parallel Algorithms 36 / Ch5 Copyright USTC 2022/2/4 End of Chapter 5 。 ④ 求 M的中值 m－劃分元； ⑤ 同算法 1中 ③ ； ⑥ 同算法 1中 ④ ； Parallel Algorithms 35 / Ch5 2022/2/4 Copyright USTC 確定 k選擇算法 2. 分布式確定 k選擇算法 算法 4： ① 求 |B|, 當 |B|足夠小時，送入根結(jié)點，排序求 k元素 。 假定網(wǎng)絡中已有一個生成樹，場點 Si含有 B中的子集 Bi 算法 2： ① 通過對生成樹的掃描，根結(jié)點計算出樹中結(jié)點所含的元素數(shù) 若 |B|=1，根結(jié)點輸出，否則執(zhí)行 ② ～ ④ ； 各結(jié)點已知：其元素數(shù)和元素的編號，其第 j個子樹所含的元素數(shù) t(j)。 Parallel Algorithms 25 / Ch5 2022/2/4 Copyright USTC 分布式計算的概念 Several problems: The counting problem: Sequential Bottleneck!!! 1p 2p 3p4p5pShared variable 0, 1, 2, …… Parallel Algorithms 26 / Ch5 2022/2/4 Copyright USTC 分布式計算的概念 A better solution: Counting work 1p5p2p3pmany shared variables Parallel Algorithms 27 / Ch5 2022/2/4 Copyright USTC 分布式計算的概念 Routing Problems Parallel Algorithms 28 / Ch5 2022/2/4 Copyright USTC 分布式計算的概念 Finding the spanning tree problem Parallel Algorithms 29 / Ch5 2022/2/4 Copyright USTC 分布式計算的概念 Leader election problem Leader Parallel Algorithms 30 / Ch5 2022/2/4 Copyright USTC 隨機 k選擇算法 ?1. SISD上的隨機 k選擇算法 ?2. 分布式隨機 k選擇算法 Parallel Algorithms 31 / Ch5 2022/2/4 Copyright USTC 隨機 k選擇算法 1. SISD上的隨機 k選擇算法 從 B={b1,b2,… ,bn}中選出第 k個小的元素 算法 1： ① 若 |B|=1, 輸出；否則，執(zhí)行 ② ～ ④ ； ② 隨機選取劃分元 m。 算法在執(zhí)行過程中動態(tài)生成的進程數(shù)為 2i(i=0,1,…,k 1) 所以，在第 0層～第 l層上的進程可以由 p個處理器并行做，而第 l+1層～第 k1層上的進程需要一個處理器順序處理多個進程。 (Ai= Afi and ifi)為了排序穩(wěn)定 //Pi將 i并發(fā)寫入 SM變量 LCfi, 競爭為 fi的左孩子 //Pi將 i并發(fā)寫入 SM變量 RCfi, 競爭為 fi的右孩子 T(n)=O(logn), p(n)=n, c(n)=O(nlogn) Parallel Algorithms 13 / Ch5 2022/2/4 Copyright USTC MIMDTC模型上的異步快排序算法 算法的思想 Parallel Algorithms 14 / Ch5 2022/2/4 Copyright USTC MIMDTC模型上的異步快排序算法 算法的思想 ① 并行做：找中值； ② 并行做：依據(jù)中值，將序列劃分為 ,=,子序列； ③ 對子序列并行遞歸地執(zhí)行 ① 和 ② ，直至子序列長度 小于某個臨界值時，進行直接排序； SM的待排數(shù)組 X[1..n], Qi為 X的子數(shù)組， qi為 Qi中第 1個 元素的首地址， |Qi|=si, R是存放 (qi,si)的 SM
研究報告相關推薦
鄂ICP備17016276號-1