并行算法的設計與分析(1)-資料下載頁
2025-01-07 10:53本頁面
【正文】 llel 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。 ③ 將 B分成 BL,BE,BG，分別包含 B中 ,=,m的元素 若 |BL|≥k, 令 B’=BL, k’=k 若 |BL|+|BE|≥k＞ |BL|, 則輸出 m 若 |BL|+|BE|＜ k, 令 B’=BG, k’=k|BL||BE| ④ 用 B’, k’遞歸調用算法； Parallel Algorithms 32 / Ch5 2022/2/4 Copyright USTC 分布式隨機 k選擇算法 2. 分布式隨機 k選擇算法 輸入 B={b1,b2,… ,bn}, 場點 S={S1,S2,… ,Sp}, 通訊鏈 L=S S。 假定網(wǎng)絡中已有一個生成樹，場點 Si含有 B中的子集 Bi 算法 2： ① 通過對生成樹的掃描，根結點計算出樹中結點所含的元素數(shù) 若 |B|=1，根結點輸出，否則執(zhí)行 ② ～ ④ ； 各結點已知：其元素數(shù)和元素的編號，其第 j個子樹所含的元素數(shù) t(j)。 ② 隨機地選取一個劃分元素 m: 先隨機產(chǎn)生整數(shù) i， 如果 i≤ t， t為 根結點中的元素數(shù)，則在根中選第 i個元素 ； 否則取使 j=itt(1)t(2)… t(f1)0的最大整數(shù) f，在根的第 f個子樹中找第 j個元素 , 遞歸地找下去； 將劃分元素 m － 根結點－ 所有結點 ③ 每個進程 i將 Bi分成 BLi, BEi, BGi, 計算 依據(jù) m, |BL|, |BE|, |BG|之間的關系 (同算法 1)，確定下一步的調用 需加上：將信息播送到所有結點 ④ 根據(jù) B’, k’做遞歸調用 ??? pi iBB 1 ||||??? ??? ??? pi ipi ipi i BGBGBEBEBLBL 111 ||||||||,||||Parallel Algorithms 33 / Ch5 2022/2/4 Copyright USTC 確定 k選擇算法 ?1. SISD上的確定 k選擇算法 ?2. 分布式確定 k選擇算法 Parallel Algorithms 34 / Ch5 2022/2/4 Copyright USTC 確定 k選擇算法 1. SISD上的確定 k選擇算法 算法 3: ① |B|較小，用排序求； ② 將 B分成每 5個一組； ③ 求每組的中值 :中值集 M。 ④ 求 M的中值 m－劃分元； ⑤ 同算法 1中 ③ ； ⑥ 同算法 1中 ④ ； Parallel Algorithms 35 / Ch5 2022/2/4 Copyright USTC 確定 k選擇算法 2. 分布式確定 k選擇算法 算法 4： ① 求 |B|, 當 |B|足夠小時，送入根結點，排序求 k元素 。 ② 每個進程按 5個元素一組分組，每個結點從其子結點 接收零頭，每 5個一組分組，再把零頭送往父結點； ③ 局部求 5個元素的中值； ④ 以 M為輸入，遞歸調用求 M的中值 m。 ⑤⑥ 同算法 1中的 ③④ ； Parallel Algorithms 36 / Ch5 Copyright USTC 2022/2/4 End of Chapter 5
研究報告相關推薦
鄂ICP備17016276號-1