課件多核并行計(jì)算

1、2022/8/3Parallel Computing Chapter 6 Supplement Fundamental Techniques of Designing Parallel Algorithms2022/8/3基本設(shè)計(jì)技術(shù)6.1 Partitioning Principle6.2 Divide-and-Conquer Strategy6.3 Balanced Trees Method6.4 Doubling Techniques 6.5 Pipelining Techniques2022/8/36.1 劃分設(shè)計(jì)技術(shù)設(shè)計(jì)思想將原問(wèn)題劃分成p個(gè)獨(dú)立的幾乎相等的子問(wèn)題；p臺(tái)處理器并行地求

2、解各子問(wèn)題。 Remark:劃分重點(diǎn)在于:子問(wèn)題易解,組合成原問(wèn)題的解方便;有別于分治法常見(jiàn)劃分方法均勻劃分 方根劃分 對(duì)數(shù)劃分 功能劃分(補(bǔ))2022/8/36.1.4 功能劃分方法: n個(gè)元素A1.n分成等長(zhǎng)的p組，每組滿足 某種特性。示例: (m, n)選擇問(wèn)題(求出n個(gè)元素中前m個(gè)最小者) - 功能劃分：要求每組元素個(gè)數(shù)必須大于m； - 算法是基于Batcher排序網(wǎng)絡(luò)，下面先介紹一些預(yù)備知識(shí)： 1.Batcher比較器 2.奇偶?xì)w并及排序網(wǎng)絡(luò): 網(wǎng)絡(luò)構(gòu)造、奇偶?xì)w并網(wǎng)絡(luò)、奇偶排序網(wǎng)絡(luò) 3.雙調(diào)歸并及排序網(wǎng)絡(luò): 定義與定理、網(wǎng)絡(luò)構(gòu)造、雙調(diào)歸并網(wǎng)絡(luò)、雙調(diào)排序網(wǎng)絡(luò)2022/8/36.1.4

3、功能劃分1. Batcher比較器比較和條件交換操作: CCI比較器網(wǎng)絡(luò)：用Batcher比較器連成完成某一功能的網(wǎng)絡(luò)假定：每次每個(gè)元素只能與另一個(gè)元素比較比較器網(wǎng)絡(luò)的參數(shù)：比較器數(shù)目、延遲級(jí)數(shù)2022/8/36.1.4 功能劃分2.1奇偶?xì)w并網(wǎng)絡(luò)構(gòu)造有序序列A:a1,a2,an B: b1,b2,bm歸并思想：A, B中奇數(shù)號(hào)元素進(jìn)入奇歸并器；A, B中偶數(shù)號(hào)元素進(jìn)入偶?xì)w并器；再將奇歸并器與偶?xì)w并器的輸出交叉比較注: (m,n)規(guī)模劃分為：2022/8/36.1.4 功能劃分2.2 奇偶?xì)w并示例：m=n=4 A=(2,4,6,8) B=(0,1,3,5)(4, 4)2(2, 2)4(1, 1

4、)(2,2)奇歸并2468013520634185023614580236145801234568(2,2)偶?xì)w并交叉比較2022/8/36.1.4 功能劃分2.3 奇偶排序網(wǎng)絡(luò)基于奇偶?xì)w并網(wǎng)絡(luò)示例： B(8)385172463815274613582467123456782022/8/36.1.4 功能劃分3.1 定義及定理定義: 一個(gè)序列a1,a2,an是雙調(diào)序列(Bitonic Sequence)，如果： (1)存在一個(gè)ak(1kn), 使得a1akan成立；或者 (2)序列能夠循環(huán)移位滿足條件(1)示例： 序列(1,3,5,7,8,6,4,2,0), (7,8,6,4,2,0,1,3,

5、5)和(1,2,3,4,5,6,7,8) 都是雙調(diào)序列。 ak定理(Batcher定理)： 設(shè)序列a1,an,an+1, a2n是一個(gè)雙調(diào)序列, 記 bi=minai, ai+n = MIN=b1,bn, ci=maxai, ai+n = MAX=c1,cn, 則 (1) bicj (1i, jn) (2) MIN和MAX序列仍是雙調(diào)的 2022/8/36.1.4 功能劃分3.2 雙調(diào)歸并網(wǎng)絡(luò)構(gòu)造(依據(jù)Batcher定理)2n個(gè)輸入的雙調(diào)序列兩兩比較形成2個(gè)大小為n的MIN和MAX序列MIN和MAX序列是雙調(diào)的，可以遞歸重復(fù)進(jìn)行下去MINMINMINMINMAXMAXMAXMAXMIN雙調(diào)序列

6、MAX雙調(diào)序列2022/8/36.1.4 功能劃分3.3 雙調(diào)歸并示例:雙調(diào)序列(8,6,4,2,0,1,3,5)的(4,4)雙調(diào)歸并網(wǎng)絡(luò)2個(gè)(2,2)雙調(diào)歸并網(wǎng)絡(luò)864201358061432508163425MIN歸并MAX歸并01234568兩兩比較2022/8/36.1.4 功能劃分3.4 雙調(diào)排序網(wǎng)絡(luò)基于雙調(diào)歸并網(wǎng)絡(luò)示例：B(8)831572463851724613587642123456782022/8/36.1.4 功能劃分基于劃分原理的(m,n)-選擇過(guò)程 將n個(gè)輸入數(shù)據(jù)劃分成若干個(gè)大小相等的子序列(m)； 使用Batcher排序網(wǎng)絡(luò)對(duì)各子序列排序； 將有序子序列形成雙調(diào)序列，

7、進(jìn)行 兩兩對(duì)接； 使用Batcher定理形成MAX,MIN序 列，棄去MAX序列； 再使用Batcher排序網(wǎng)絡(luò)將MIN序列 排成有序序列； 重復(fù)直至MIN序列恰好包含所需 的m個(gè)最小元素為止。2022/8/36.1.4 功能劃分(m,n)-選擇示例：B(4)奇偶排序137110241185153961216141710132481135915612141617423596124735691243分組雙調(diào)對(duì)接比較取MIN雙調(diào)對(duì)接比較取MIN分組Batcher奇偶排序分組Batcher奇偶排序2022/8/312341234Prefix Sums on a Tree: More6.3 平衡樹(shù)設(shè)計(jì)

8、技術(shù)2022/8/312341,33,76.3 平衡樹(shù)設(shè)計(jì)技術(shù)Prefix Sums on a Tree: More2022/8/312341,33,713376.3 平衡樹(shù)設(shè)計(jì)技術(shù)Prefix Sums on a Tree: More2022/8/3133736.3 平衡樹(shù)設(shè)計(jì)技術(shù)Prefix Sums on a Tree: More2022/8/31337336.3 平衡樹(shù)設(shè)計(jì)技術(shù)Prefix Sums on a Tree: More2022/8/313373336.3 平衡樹(shù)設(shè)計(jì)技術(shù)Prefix Sums on a Tree: More2022/8/3136106.3 平衡樹(shù)設(shè)計(jì)技術(shù)Pr

9、efix Sums on a Tree: More2022/8/3Properties:time:2 log nprocessors:2n 1costO(n log n)Comparison with PRAM algorithmasymptotically equivalentin practice, less efficientweaker model6.3 平衡樹(shù)設(shè)計(jì)技術(shù)Prefix Sums on a Tree: More2022/8/3Specialized Circuit123456781357911131513610141822261361015212836depth (time

10、) = 3complexity (cost)= 3 8 = 246.3 平衡樹(shù)設(shè)計(jì)技術(shù)2022/8/3Recursive Circuit12345678Circuit for4 inputsCircuit for4 inputs136105111826+123415212836101010106.3 平衡樹(shù)設(shè)計(jì)技術(shù)2022/8/36.5 流水線設(shè)計(jì)技術(shù)Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 13,4,5,1,7,262022/8/36.5 流水線設(shè)計(jì)技術(shù)Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2,

11、6 Step 263,4,5,1,722022/8/36.5 流水線設(shè)計(jì)技術(shù)Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 3263,4,5,172022/8/36.5 流水線設(shè)計(jì)技術(shù)Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 4263,4,5172022/8/36.5 流水線設(shè)計(jì)技術(shù)Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 51673,4522022/8/36.5 流水線設(shè)計(jì)技術(shù)Systolic排序算法示例: Sorting 3, 4

12、, 5, 1, 7, 2, 6 Step 612734562022/8/36.5 流水線設(shè)計(jì)技術(shù)Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 712673452022/8/36.5 流水線設(shè)計(jì)技術(shù)Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 812576432022/8/36.5 流水線設(shè)計(jì)技術(shù)Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 912467532022/8/36.5 流水線設(shè)計(jì)技術(shù)Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 1012357642022/8/36.5 流水線設(shè)計(jì)技術(shù)Systolic排序算法示例: Sor