并行算法的設(shè)計與分析(編輯修改稿)
2025-02-03 10:53 本頁面
【文章內(nèi)容簡介】 i+n} == MIN={b1,… ,bn}, ci=max{ai, ai+n} == MAX={c1,… ,}, 則 (1) bi≤ cj (1≤i, j≤n) (2) MIN和 MAX序列仍是雙調(diào)的 Parallel Algorithms 11 / Ch3 2022/2/4 Copyright USTC 雙調(diào)歸并網(wǎng)絡(luò) 2. 網(wǎng)絡(luò)構(gòu)造 (依據(jù) Batcher定理 ) ? 2n個輸入的雙調(diào)序列兩兩比較形成 2個大小為 n的 MIN和 MAX序列 ? MIN和 MAX序列是雙調(diào)的，可以遞歸重復(fù)進(jìn)行下去 MIN MIN MIN MIN MAX MAX MAX MAX MIN雙調(diào)序列 MAX雙調(diào)序列 Parallel Algorithms 12 / Ch3 2022/2/4 Copyright USTC 雙調(diào)歸并網(wǎng)絡(luò) 3. 例 :雙調(diào)序列 (8,6,4,2,0,1,3,5)的 (4,4)雙調(diào)歸并網(wǎng)絡(luò) 2個 (2,2)雙調(diào)歸并網(wǎng)絡(luò) 8 6 4 2 0 1 3 5 8 0 6 1 4 3 2 5 0 8 1 6 3 4 2 5 MIN歸并 MAX歸并 0 1 2 3 4 5 6 8 兩兩比較 Parallel Algorithms 13 / Ch3 2022/2/4 Copyright USTC 雙調(diào)歸并網(wǎng)絡(luò) 4. 復(fù)雜性分析 ? 比較器數(shù)目 MIN比較器數(shù) MAX比較器數(shù) 本級兩兩比較器數(shù) 當(dāng) n=2t時 ? 延遲級數(shù) 注：如何推導(dǎo)？ Parallel Algorithms 14 / Ch3 2022/2/4 Copyright USTC 雙調(diào)歸并網(wǎng)絡(luò) 4. 復(fù)雜性分析 ? 延遲級數(shù) 注：如何推導(dǎo)？ ? ? ? ?? ?? ? ? ?? ?? ?? ?nnDnDnDnnDnDnnDnMB I TniMB I TMB I TMB I TMB I TMB I Tl o g)2(1))2/(1(1)2/(11)2/(),2/(m a x110)(l o gl o g12???????????????????????Parallel Algorithms 15 / Ch3 2022/2/4 Copyright USTC Batcher排序網(wǎng)絡(luò) 1. 排序網(wǎng)絡(luò)原理 (1)對輸入數(shù)進(jìn)行兩兩比較，形成長度為 2的有序序列組； (2)對長度為 2的有序序列組進(jìn)行兩兩歸并，形成長度為 4的有序序列組； (3
公司管理相關(guān)推薦
鄂ICP備17016276號-1