第六章并行算法的基本設(shè)計(jì)技術(shù)

第六章并行算法的基本設(shè)計(jì)技術(shù)第一頁，共四十五頁，2022年，8月28日第二篇并行算法的設(shè)計(jì)

第四章并行算法的設(shè)計(jì)基礎(chǔ)

第五章并行算法的一般設(shè)計(jì)方法

第六章并行算法的基本設(shè)計(jì)技術(shù)

第七章并行算法的一般設(shè)計(jì)過程

第二頁，共四十五頁，2022年，8月28日第六章并行算法的基本設(shè)計(jì)技術(shù)

6.1劃分設(shè)計(jì)技術(shù)

6.2分治設(shè)計(jì)技術(shù)

6.3平衡樹設(shè)計(jì)技術(shù)

6.4倍增設(shè)計(jì)技術(shù)

6.5流水線設(shè)計(jì)技術(shù)

第三頁，共四十五頁，2022年，8月28日6.1劃分設(shè)計(jì)技術(shù)

6.1.1均勻劃分技術(shù)

6.1.2方根劃分技術(shù)

6.1.3對(duì)數(shù)劃分技術(shù)

6.1.4功能劃分技術(shù)第四頁，共四十五頁，2022年，8月28日

均勻劃分技術(shù)劃分方法n個(gè)元素A[1..n]分成p組，每組A[(i-1)n/p+1..in/p]，i=1~p示例：MIMD-SM模型上的PSRS排序

begin(1)均勻劃分：將n個(gè)元素A[1..n]均勻劃分成p段，每個(gè)pi處理A[(i-1)n/p+1..in/p](2)局部排序：pi調(diào)用串行排序算法對(duì)A[(i-1)n/p+1..in/p]排序(3)選取樣本：pi從其有序子序列A[(i-1)n/p+1..in/p]中選取p個(gè)樣本元素(4)樣本排序：用一臺(tái)處理器對(duì)p2個(gè)樣本元素進(jìn)行串行排序(5)選擇主元：用一臺(tái)處理器從排好序的樣本序列中選取p-1個(gè)主元，并播送給其他pi(6)主元?jiǎng)澐郑簆i按主元將有序段A[(i-1)n/p+1..in/p]劃分成p段(7)全局交換：各處理器將其有序段按段號(hào)交換到對(duì)應(yīng)的處理器中(8)歸并排序：各處理器對(duì)接收到的元素進(jìn)行歸并排序end.第五頁，共四十五頁，2022年，8月28日

均勻劃分技術(shù)例6.1PSRS排序過程。N=27，p=3，PSRS排序如下：第六頁，共四十五頁，2022年，8月28日6.1劃分設(shè)計(jì)技術(shù)

6.1.1均勻劃分技術(shù)

6.1.2方根劃分技術(shù)

6.1.3對(duì)數(shù)劃分技術(shù)

6.1.4功能劃分技術(shù)第七頁，共四十五頁，2022年，8月28日

方根劃分技術(shù)劃分方法n個(gè)元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2)示例：SIMD-CREW模型上的Valiant歸并(1975年發(fā)表)//有序組A[1..p]、B[1..q],(假設(shè)p<=q),處理器數(shù)begin(1)方根劃分:A,B分別按；(2)段間比較:A劃分元與B劃分元比較(至多對(duì))，確定A劃分元應(yīng)插入B中的區(qū)段；(3)段內(nèi)比較:A劃分元與B相應(yīng)段內(nèi)元素進(jìn)行比較，并插入適當(dāng)?shù)奈恢茫?4)遞歸歸并:B按插入的A劃分元重新分段，與A相應(yīng)段(A除去原劃分元)構(gòu)成了成對(duì)的段組，對(duì)每對(duì)段組遞歸執(zhí)行(1)~(3)，直至A組為0時(shí)，遞歸結(jié)束;各組仍按分配處理器；end.第八頁，共四十五頁，2022年，8月28日

方根劃分技術(shù)第九頁，共四十五頁，2022年，8月28日

方根劃分技術(shù)第十頁，共四十五頁，2022年，8月28日6.1劃分設(shè)計(jì)技術(shù)

6.1.1均勻劃分技術(shù)

6.1.2方根劃分技術(shù)

6.1.3對(duì)數(shù)劃分技術(shù)

6.1.4功能劃分技術(shù)第十一頁，共四十五頁，2022年，8月28日

對(duì)數(shù)劃分技術(shù)劃分方法n個(gè)元素A[1..n]分成A[(i-1)logn+1..ilogn]，i=1~n/logn示例：PRAM-CREW上的對(duì)數(shù)劃分并行歸并排序(1)歸并過程:設(shè)有序組A[1..n]和B[1..m]

j[i]=rank(bilogm:A)為bilogm在A中的位序，即A中小于等于bilogm的元素個(gè)數(shù)(2)例：A=(4,6,7,10,12,15,18,20),B=(3,9,16,21)n=8,m=4=>logm=log4=2=>j[1]=rank(blogm:A)=rank(b2:A)=rank(9:A)=3,j[2]=…=8B0:3,9B1:16,21A0:4,6,7A1:10,12,15,18,20

A和B歸并化為(A0,B0)和(A1,B1)的歸并第十二頁，共四十五頁，2022年，8月28日6.1劃分設(shè)計(jì)技術(shù)

6.1.1均勻劃分技術(shù)

6.1.2方根劃分技術(shù)

6.1.3對(duì)數(shù)劃分技術(shù)

6.1.4功能劃分技術(shù)第十三頁，共四十五頁，2022年，8月28日

功能劃分技術(shù)劃分方法

n個(gè)元素A[1..n]分成等長(zhǎng)的p組，每組滿足某種特性。示例：(m,n)選擇問題(求出n個(gè)元素中前m個(gè)最小者)功能劃分：要求每組元素個(gè)數(shù)必須大于m；算法：p148算法6.4

輸入：A=(a1,…,an);輸出：前m個(gè)最小者；

Begin(1)功能劃分：將A劃分成g=n/m組，每組含m個(gè)元素；(2)局部排序：使用Batcher排序網(wǎng)絡(luò)將各組并行進(jìn)行排序；(3)兩兩比較：將所排序的各組兩兩進(jìn)行比較，從而形成MIN序列；(4)排序-比較：對(duì)各個(gè)MIN序列，重復(fù)執(zhí)行第(2)和第(3)步，直至選出m個(gè)最小者。End第十四頁，共四十五頁，2022年，8月28日

功能劃分技術(shù)第十五頁，共四十五頁，2022年，8月28日第六章并行算法的基本設(shè)計(jì)技術(shù)

6.1劃分設(shè)計(jì)技術(shù)

6.2分治設(shè)計(jì)技術(shù)

6.3平衡樹設(shè)計(jì)技術(shù)

6.4倍增設(shè)計(jì)技術(shù)

6.5流水線設(shè)計(jì)技術(shù)

第十六頁，共四十五頁，2022年，8月28日6.2分治設(shè)計(jì)技術(shù)

6.2.1并行分治設(shè)計(jì)步驟

6.2.2雙調(diào)歸并網(wǎng)絡(luò)

第十七頁，共四十五頁，2022年，8月28日

并行分治設(shè)計(jì)步驟將輸入劃分成若干個(gè)規(guī)模相等的子問題；同時(shí)(并行地)遞歸求解這些子問題；并行地歸并子問題的解，直至得到原問題的解。第十八頁，共四十五頁，2022年，8月28日6.2分治設(shè)計(jì)技術(shù)

6.2.1并行分治設(shè)計(jì)步驟

6.2.2雙調(diào)歸并網(wǎng)絡(luò)

第十九頁，共四十五頁，2022年，8月28日

雙調(diào)歸并網(wǎng)絡(luò)雙調(diào)序列(p149定義6.2)

(1,3,5,7,8,6,4,2,0)(8,7,6,4,2,0,1,3,5)(1,2,3,4,5,6,7,8)

以上都是雙調(diào)序列Batcher定理給定雙調(diào)序列(x0,x1,…,xn-1),對(duì)于si=min{xi,xi+n/2}和li=max{xi,xi+n/2}，則小序列(s0,s1,…,sn-1)和大序列(l0,l1,…,ln-1)

仍是雙調(diào)序列第二十頁，共四十五頁，2022年，8月28日

雙調(diào)歸并網(wǎng)絡(luò)(4,4)雙調(diào)歸并網(wǎng)絡(luò)第二十一頁，共四十五頁，2022年，8月28日

雙調(diào)歸并網(wǎng)絡(luò)Batcher雙調(diào)歸并算法輸入：雙調(diào)序列X=(x0,x1,…,xn-1)輸出：非降有序序列Y=(y0,y1,…,yn-1)ProcedureBITONIC_MERG(x)Begin(1)fori=0ton/2-1par-do(1.1)si=min{xi,xi+n/2}(1.2)li=max{xi,xi+n/2}endfor(2)RecursiveCall:(2.1)BITONIC_MERG(MIN=(s0,…,sn/2-1))(2.2)BITONIC_MERG(MIN=(l0,…,ln/2-1))(3)outputsequenceMINfollowedbysequenceMAXEnd第二十二頁，共四十五頁，2022年，8月28日第六章并行算法的基本設(shè)計(jì)技術(shù)

6.1劃分設(shè)計(jì)技術(shù)

6.2分治設(shè)計(jì)技術(shù)

6.3平衡樹設(shè)計(jì)技術(shù)

6.4倍增設(shè)計(jì)技術(shù)

6.5流水線設(shè)計(jì)技術(shù)

第二十三頁，共四十五頁，2022年，8月28日6.3平衡樹設(shè)計(jì)技術(shù)

6.3.1設(shè)計(jì)思想

6.3.2求最大值

6.3.3計(jì)算前綴和

第二十四頁，共四十五頁，2022年，8月28日

平衡樹設(shè)計(jì)技術(shù)設(shè)計(jì)思想以樹的葉結(jié)點(diǎn)為輸入，中間結(jié)點(diǎn)為處理結(jié)點(diǎn)，由葉向根或由根向葉逐層進(jìn)行并行處理。示例求最大值計(jì)算前綴和

第二十五頁，共四十五頁，2022年，8月28日6.3平衡樹設(shè)計(jì)技術(shù)

6.3.1設(shè)計(jì)思想

6.3.2求最大值

6.3.3計(jì)算前綴和

第二十六頁，共四十五頁，2022年，8月28日

求最大值算法6.8:SIMD-TC(SM)上求最大值算法

Beginfork=m-1to0doforj=2kto2k+1-1par-doA[j]=max{A[2j],A[2j+1]}endforendforend圖示時(shí)間分析t(n)=m×O(1)=O(logn)p(n)=n/2A1An/4An/2-1An/2An/2+1An-2An-1AnAn+1An+2An+3A2n-4A2n-3A2n-2A2n-1K=m-1K=m-2K=0P1P1P2Pn/2-1Pn/2P1Pn/2-1第二十七頁，共四十五頁，2022年，8月28日6.3平衡樹設(shè)計(jì)技術(shù)

6.3.1設(shè)計(jì)思想

6.3.2求最大值

6.3.3計(jì)算前綴和

第二十八頁，共四十五頁，2022年，8月28日

計(jì)算前綴和問題定義n個(gè)元素{x1,x2,…,xn}，前綴和是n個(gè)部分和：Si=x1*x2*…*xi,1≤i≤n這里*可以是＋或×串行算法：Si=Si－1*xi計(jì)算時(shí)間為O(n)

并行算法：p154算法6.9SIMD-TC上非遞歸算法

令A(yù)[i]=xi,i=1~n,B[h,j]和C[h,j]為輔助數(shù)組(h=0~logn,j=1~n/2h)數(shù)組B記錄由葉到根正向遍歷樹中各結(jié)點(diǎn)的信息(求和)數(shù)組C記錄由根到葉反向遍歷樹中各結(jié)點(diǎn)的信息(播送前綴和)第二十九頁，共四十五頁，2022年，8月28日

計(jì)算前綴和例：n=8,p=8,C01~C08為前綴和第三十頁，共四十五頁，2022年，8月28日第六章并行算法的基本設(shè)計(jì)技術(shù)

6.1劃分設(shè)計(jì)技術(shù)

6.2分治設(shè)計(jì)技術(shù)

6.3平衡樹設(shè)計(jì)技術(shù)

6.4倍增設(shè)計(jì)技術(shù)

6.5流水線設(shè)計(jì)技術(shù)

第三十一頁，共四十五頁，2022年，8月28日6.4倍增設(shè)計(jì)技術(shù)

6.4.1設(shè)計(jì)思想

6.4.2表序問題

6.4.3求森林的根

第三十二頁，共四十五頁，2022年，8月28日

倍增設(shè)計(jì)技術(shù)設(shè)計(jì)思想又稱指針跳躍(pointerjumping)技術(shù)，特別適合于處理鏈表或有向樹之類的數(shù)據(jù)結(jié)構(gòu)；當(dāng)遞歸調(diào)用時(shí)，所要處理數(shù)據(jù)之間的距離逐步加倍，經(jīng)過k步后即可完成距離為2k的所有數(shù)據(jù)的計(jì)算。示例表序問題求森林的根第三十三頁，共四十五頁，2022年，8月28日6.4倍增設(shè)計(jì)技術(shù)

6.4.1設(shè)計(jì)思想

6.4.2表序問題

6.4.3求森林的根

第三十四頁，共四十五頁，2022年，8月28日

表序問題問題描述n個(gè)元素的列表L，求出每個(gè)元素在L中的次第號(hào)(秩或位序或rank(k))，rank(k)可視為元素k至表尾的距離；示例：n=7(1)p[a]=b,p[b]=c,p[c]=d,p[d]=e,p[e]=f,p[f]=g,p[g]=g

r[a]=r[b]=r[c]=r[d]=r[e]=r[f]=1,r[g]=0(2)p[a]=c,p[b]=d,p[c]=e,p[d]=f,p[e]=p[f]=p[g]=g

r[a]=r[b]=r[c]=r[d]=r[e]=2,r[f]=1,r[g]=0(3)p[a]=e,p[b]=f,p[c]=p[d]=p[e]=p[f]=p[g]=g

r[a]=4,r[b]=4,r[c]=4,r[d]=3,r[e]=2,r[f]=1,r[g]=0(4)p[a]=p[b]=p[c]=p[d]=p[e]=p[f]=p[g]=g

r[a]=6,r[b]=5,r[c]=4,r[d]=3,r[e]=2,r[f]=1,r[g]=0第三十五頁，共四十五頁，2022年，8月28日

表序問題算法：P155算法6.10(1)并行做：初始化p[k]和distance[k]//O(1)(2)執(zhí)行次//O(logn)(2.1)對(duì)k并行地做//O(1)如果k的后繼不等于k的后繼之后繼，則(i)distance[k]=distance[k]+distance[p[k]](ii)p[k]=p[p[k]](2.2)對(duì)k并行地做rank[k]=distance[k]//O(1)運(yùn)行時(shí)間：t(n)=O(logn)p(n)=n第三十六頁，共四十五頁，2022年，8月28日6.4倍增設(shè)計(jì)技術(shù)

6.4.1設(shè)計(jì)思想

6.4.2表序問題

6.4.3求森林的根

第三十七頁，共四十五頁，2022年，8月28日

求森林的根問題描述一組有向樹F中,如果<i,j>是F中的一條弧，則p[i]=j(即j是i的雙親)；若i為根，則p[i]=i。求每個(gè)結(jié)點(diǎn)j(j=1~n)的樹根s[j].示例初始時(shí)P[1]=p[2]=5p[3]=p[4]=p[5]=6P[6]=p[7]=8p[8]=8P[9]=10p[10]=11p[11]=12p[12]=13