并行算法講稿

并行算法講稿第一頁(yè)，共五十三頁(yè)，2022年，8月28日把有唯一輸入向量和唯一輸出向量的一個(gè)程序段在某一環(huán)境下的一次執(zhí)行稱為一個(gè)進(jìn)程。設(shè)有一組程序段A1…An，若{Ai}在n個(gè)處理機(jī)上同時(shí)執(zhí)行的結(jié)果等同于{Ai}以任意順序執(zhí)行的結(jié)果，則稱{Ai}為可并行執(zhí)行的。設(shè)兩個(gè)程序段A、B，且A先于B，若A與B數(shù)據(jù)相關(guān)或控制相關(guān)，則稱A是B的父進(jìn)程。第二頁(yè)，共五十三頁(yè)，2022年，8月28日A1：x=1A2：y=2A3：s=2*x+yA4：t=x*x*yA5：u=3*s-tA6：v=cos(t)A7：z=u*v+1如下例所示：u,vzA7tvA6s,tuA5x,ytA4x,ysA3yA2xA1輸入輸出進(jìn)程輸入輸出表如下：BeginA1A2A3A4A5A6A7End進(jìn)程流程圖如下：第三頁(yè)，共五十三頁(yè)，2022年，8月28日下面簡(jiǎn)單例子讓我們能更深刻理解并行算法：倍增法求和倍增法是并行分治的一種簡(jiǎn)化形式。其基本思想是將原問(wèn)題反復(fù)分解為等規(guī)模的兩個(gè)子問(wèn)題，在逐步分解的過(guò)程中，子問(wèn)題個(gè)數(shù)成倍增加。將各個(gè)子問(wèn)題恰當(dāng)?shù)赜成涞礁髋_(tái)處理機(jī)上，即可實(shí)現(xiàn)計(jì)算過(guò)程的并行化。例如:倍增法求和計(jì)算序列L[0..n-1]的和，記為S(0,n-1)。intBSum(intL,ints,intt){if(s==t)returnL[s];intk=(s+t)/2;returnBSum(L,s,k)+BSum(L,k+1,t);}并行求和第四頁(yè)，共五十三頁(yè)，2022年，8月28日從以上一個(gè)簡(jiǎn)單的例子我們可以看到并行算法的真諦！所以這么說(shuō)基于普通的算法大家開(kāi)始加，串行從1到100加很累，而這個(gè)高斯思想的并行處理結(jié)果又快又準(zhǔn)確！體現(xiàn)出了這個(gè)思想，由此引申到計(jì)算機(jī)并行處理可以看出它潛力巨大，對(duì)解決現(xiàn)實(shí)問(wèn)題有很大的指導(dǎo)作用，希望大家認(rèn)真聽(tīng)講。那么什么叫并行算法？

科學(xué)家已經(jīng)定義為：利用并行計(jì)算機(jī)系統(tǒng)進(jìn)行數(shù)據(jù)與信息的并行處理稱為并行計(jì)算。第五頁(yè)，共五十三頁(yè)，2022年，8月28日并行計(jì)算研究的內(nèi)容包括并行計(jì)算方法、并行計(jì)算模型、并行算法、并行程序設(shè)計(jì)、并行測(cè)試程序設(shè)計(jì)、測(cè)試結(jié)果分析等。由于各種并行計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu)不同，系統(tǒng)內(nèi)各處理器和各功能部件之間在體現(xiàn)算法時(shí)的相互作用不同，使得并行算法不能通用。因此，當(dāng)前并行處理的研究重點(diǎn)，除了并行計(jì)算機(jī)體系結(jié)構(gòu)之外，就是研究基于各種并行與分布式計(jì)算機(jī)系統(tǒng)上的并行算法或分布式算法。

第六頁(yè)，共五十三頁(yè)，2022年，8月28日并行計(jì)算方法的研究，不僅對(duì)提高并行計(jì)算機(jī)的使用效率是必需的，而且往往能找到改進(jìn)現(xiàn)有串行算法的新途徑。并行計(jì)算方法的研究是研制高效并行數(shù)值計(jì)算軟件的基礎(chǔ)。并行計(jì)算中可供選擇的技術(shù)路線有兩條：一條是在現(xiàn)有的串行算法基礎(chǔ)上作并行化；另一條是直接從數(shù)學(xué)物理問(wèn)題出發(fā)，面向并行系統(tǒng)研制高效率的計(jì)算方法和設(shè)計(jì)算法。在并行算法設(shè)計(jì)中廣泛采用的是“DivideandConquer”（分而治之）和重新排序兩種基本方法。從以上基本方法引申具體以下幾種算法：

第七頁(yè)，共五十三頁(yè)，2022年，8月28日三、并行編程的基本方法這里主要介紹網(wǎng)絡(luò)并行編程的基本模式和負(fù)載平衡的基本方法。(1)網(wǎng)絡(luò)并行編程的基本模式

應(yīng)用標(biāo)準(zhǔn)化環(huán)境進(jìn)行網(wǎng)絡(luò)并行編程與MPP并行機(jī)（如IBMSPZ，IntelParagon等）在算法設(shè)計(jì)和編程邏輯的基本方法上是相同的，它們存在的不同點(diǎn)是：

★任務(wù)管理方式不同，網(wǎng)絡(luò)并行標(biāo)準(zhǔn)化環(huán)境編程要涉及到進(jìn)程的動(dòng)態(tài)創(chuàng)建與命名。

★標(biāo)準(zhǔn)環(huán)境不同，網(wǎng)絡(luò)并行編程要求在正式計(jì)算前完成語(yǔ)句的初始化。

★粒度選取不同，分布式網(wǎng)絡(luò)并行計(jì)算的并行粒度較大。

★計(jì)算環(huán)境不同，分布式網(wǎng)絡(luò)并行計(jì)算要考慮到異構(gòu)環(huán)境。

從不同計(jì)算任務(wù)組織的角度看，分布式編程主要有星形計(jì)算模式和樹(shù)形計(jì)算模式兩種：

第八頁(yè)，共五十三頁(yè)，2022年，8月28日三、并行編程的基本方法

▲星形計(jì)算模式。由一組相互緊密關(guān)聯(lián)的進(jìn)程組成，它們可以是執(zhí)行相同的程序，只是數(shù)據(jù)不同，共同執(zhí)行同一計(jì)算問(wèn)題的不同部位。這種計(jì)算模式又可以分為兩類：一種是主從式（masterslave），這種計(jì)算模式有一個(gè)控制程序作為主進(jìn)程，負(fù)責(zé)進(jìn)程的生成、初始化、收集并顯示結(jié)果，其余的進(jìn)程（slave）執(zhí)行實(shí)際計(jì)算，從進(jìn)程的負(fù)載或由主進(jìn)程分配，或由自身分配；另外一種是純結(jié)點(diǎn)模式，這時(shí)所有進(jìn)程都在執(zhí)行單個(gè)程序，只是少數(shù)進(jìn)程（初始時(shí)由人工指定）同時(shí)負(fù)責(zé)非計(jì)算的功能（如I/O等）。

第九頁(yè)，共五十三頁(yè)，2022年，8月28日三、并行編程的基本方法

▲樹(shù)形（tree）計(jì)算模式。在這種計(jì)算模式中，進(jìn)程通常是在計(jì)算過(guò)程中以樹(shù)形方式動(dòng)態(tài)生成。在求解組合優(yōu)化問(wèn)題時(shí)常用的一種算法是構(gòu)造性的探索算法，主要思想是對(duì)解集合反復(fù)進(jìn)行分支，對(duì)每個(gè)分支計(jì)算最優(yōu)解的界。如果該解符合要求，則繼續(xù)分支以探索更好的解，直到所有的子集合中僅有一個(gè)最優(yōu)的解為止。這種方法在人工智能的搜索策略中以及遞歸的“分而治之”算法中也常使用。第十頁(yè)，共五十三頁(yè)，2022年，8月28日三、并行編程的基本方法(2)負(fù)載平衡的基本方法

各處理器之間的負(fù)載是否能做到基本平衡，是并行計(jì)算效率能否提高的一個(gè)關(guān)鍵。對(duì)于網(wǎng)絡(luò)分布式并行計(jì)算而言，負(fù)載平衡的基本方法有兩個(gè)：數(shù)據(jù)分解與功能分解。

數(shù)據(jù)分解方法，有時(shí)也稱數(shù)據(jù)分割法，這種方法適應(yīng)于各處理器執(zhí)行相同的任務(wù)、只是數(shù)據(jù)不同的情況。數(shù)據(jù)的分解有靜態(tài)方式和動(dòng)態(tài)方式的區(qū)別。靜態(tài)方式中每個(gè)進(jìn)程的負(fù)載是固定的，而在動(dòng)態(tài)方式中各進(jìn)程的負(fù)載分配是隨計(jì)算過(guò)程而改變的。第十一頁(yè)，共五十三頁(yè)，2022年，8月28日三、并行編程的基本方法功能分解方法。網(wǎng)絡(luò)計(jì)算的并行化也可通過(guò)把總負(fù)載按功能進(jìn)行分解，分配給各個(gè)處理器承擔(dān)。最簡(jiǎn)單的是把整個(gè)計(jì)算過(guò)程分為輸入數(shù)據(jù)、計(jì)算進(jìn)程和輸出結(jié)果三個(gè)部分。當(dāng)然根據(jù)實(shí)際情況這三個(gè)部分又可以再進(jìn)行細(xì)分。第十二頁(yè)，共五十三頁(yè)，2022年，8月28日三.并行計(jì)算基本概念

(1)并行算法的目標(biāo)

并行算法的目標(biāo)就是以增加空間的復(fù)雜性來(lái)減少時(shí)間的復(fù)雜性，即增加空間的維數(shù)，增加處理器的臺(tái)數(shù)，來(lái)減少算法實(shí)現(xiàn)所需的時(shí)間。從算法的結(jié)構(gòu)觀察，通常的串行算法樹(shù)“深而窄”，而并行算法樹(shù)結(jié)構(gòu)截然不同。為達(dá)到把時(shí)間的復(fù)雜性轉(zhuǎn)化為空間復(fù)雜性的目的，并行算法樹(shù)采用了“淺而寬”的結(jié)構(gòu)。(2)并行加速比

并行加速比表示采用多個(gè)處理器計(jì)算速度所能達(dá)到的加速的倍數(shù)。(3)粒度（granularity）

第十三頁(yè)，共五十三頁(yè)，2022年，8月28日三.并行計(jì)算基本概念粒度是各個(gè)多處理機(jī)可獨(dú)立并行執(zhí)行的任務(wù)大小的度量。大粒度反映可并行執(zhí)行的運(yùn)算量與程序量大，有時(shí)稱粗粒度。任務(wù)級(jí)并行的粒度大于語(yǔ)句級(jí)的并行。向量機(jī)主要是對(duì)內(nèi)層Do循環(huán)語(yǔ)句作向量化，所以向量化是一種小粒度（細(xì)粒度）并行；在網(wǎng)絡(luò)并行計(jì)算中，由于通信開(kāi)銷比較大，應(yīng)盡量采用粗粒度方式。(4)可擴(kuò)展性（Scalability）可擴(kuò)展性是指并行機(jī)和并行算法有效利用多處理機(jī)臺(tái)數(shù)增加的能力的一個(gè)度量。隨著處理機(jī)的增加，如果效率曲線基本保持不變，或略有下降，則認(rèn)為該算法在所用的并行機(jī)上擴(kuò)展性好；否則，其可擴(kuò)展性差。影響一個(gè)并行算法的擴(kuò)展性因素較多，評(píng)判的準(zhǔn)則也不盡相同。第十四頁(yè)，共五十三頁(yè)，2022年，8月28日四.并行算法分類依據(jù)處理對(duì)象劃分，并行算法可分為兩類：

●數(shù)值并行算法主要為數(shù)值計(jì)算而設(shè)計(jì)的并行算法；●非數(shù)值并行算法如神經(jīng)網(wǎng)絡(luò)算法、演化算法、遺傳算法、格子氣算法、格子依據(jù)算法中進(jìn)程的控制方式劃分，可分為以下兩種：ltzmann算法以及為符號(hào)計(jì)算而設(shè)計(jì)的并行算法。

●同步并行算法（synchronizedalgorithm）。是指某些進(jìn)程必須等待其他進(jìn)程的一種并行算法，要求所有進(jìn)程必須在一個(gè)給定時(shí)刻同步。SIMD以及共享存儲(chǔ)型MIMD并行機(jī)上通常運(yùn)行同步并行算法。

第十五頁(yè)，共五十三頁(yè)，2022年，8月28日四.并行算法分類異步并行算法（asynchronizedalgorithm），是指諸進(jìn)程執(zhí)行相對(duì)獨(dú)立、不要互相等待的一類算法。其主要特征是在計(jì)算的整個(gè)過(guò)程中都不需要等待，而是根據(jù)當(dāng)前的最新信息決定進(jìn)程的繼續(xù)或終止。這種算法通常是針對(duì)分布式存儲(chǔ)的MIMD并行機(jī)設(shè)計(jì)的。另外，還有分布式算法（distributedalgorithm），是指由包括網(wǎng)絡(luò)在內(nèi)的通信鏈路連接的多結(jié)點(diǎn)機(jī)或計(jì)算機(jī)群協(xié)同完成某個(gè)計(jì)算任務(wù)的算法。第十六頁(yè)，共五十三頁(yè)，2022年，8月28日五.并行計(jì)算模型所謂計(jì)算模型，是算法設(shè)計(jì)者進(jìn)行理論分析時(shí)所依據(jù)的計(jì)算機(jī)模型。馮·諾依曼機(jī)是理想的串行計(jì)算模型。由于并行機(jī)在飛速發(fā)展之中，尚未定型，故目前尚沒(méi)有所謂的通用并行計(jì)算模型。當(dāng)前，人們將并行計(jì)算機(jī)的某一些特征抽象出來(lái)，形成了各種特定的并行計(jì)算理論模型，以便于并行算法的設(shè)計(jì)與理論分析。并行機(jī)的特征有：消息包的長(zhǎng)度或延遲時(shí)間、消息包傳遞的開(kāi)銷、處理器連續(xù)傳遞消息的最小間隔（或通信的帶寬）、處理器個(gè)數(shù)等。由諸如此類的參數(shù)構(gòu)成各種特定的并行計(jì)算模型。常用的并行計(jì)算模型有PRAM、VLSI、BSP、LogP和C3模型。下面我講述幾點(diǎn)經(jīng)典算法。第十七頁(yè)，共五十三頁(yè)，2022年，8月28日5.1平衡樹(shù)法

平衡樹(shù)法的評(píng)估：以平衡樹(shù)法求解最大值是一個(gè)EREW算法，計(jì)算時(shí)間tp(n)=O(logn)，運(yùn)用處理器最多為p(n)=n/2，工作量為O(nlogn)，不是工作量有效的算法。平衡樹(shù)方法的優(yōu)點(diǎn)是在樹(shù)中能快速存取信息，對(duì)數(shù)據(jù)的傳遞、壓縮、抽取和前綴計(jì)算均十分有用。第十八頁(yè)，共五十三頁(yè)，2022年，8月28日5.2向量法向量法的基本思想★以向量方式描述計(jì)算過(guò)程；★以并行方式執(zhí)行向量計(jì)算。以矩陣計(jì)算為例

對(duì)n階矩陣，串行加法的計(jì)算量為n2，若動(dòng)用n個(gè)（或n2個(gè)）處理器，分別處理每行（或列）的相加運(yùn)算，則可以得到計(jì)算量亦為n2，工作量有效。第十九頁(yè)，共五十三頁(yè)，2022年，8月28日5.2

向量法以矩陣計(jì)算為例矩陣相乘：C=A*B第二十頁(yè)，共五十三頁(yè)，2022年，8月28日5.2向量法串行算法：{fori=1tondo forj=1tondo ci,j=0 fork=1tondo ci,j+=ai,k*bj,k

}并行算法：fori=1tondo forallPjj=1tondo ci,j=0 //Ci.=0 fork=1tond //Ci.=∑ai,k*Bk. forallPjj=1tondo ci,j+=ai,k*bk,j第二十一頁(yè)，共五十三頁(yè)，2022年，8月28日5.3線性代數(shù)方程組法高斯消去法

第二十二頁(yè)，共五十三頁(yè)，2022年，8月28日串行求解算法：for(k=1;i<N;i++){forallPjj=k…NdoA[k][j+1]=A[k][k]; for(i=1;i<=N;i++) if(i!=k) forallPjj=k…Ndo A[i][j+1]=A[i][k]*A[k][j+1];}第二十三頁(yè)，共五十三頁(yè)，2022年，8月28日并行求解算法：for(k=1;i<N;i++){ forallPjj=k…NdoA[k][j+1]=A[k][k]; for(i=1;i<=N;i++) if(i!=k) forallPjj=k…Ndo A[i][j+1]=A[i][k]*A[k][j+1];}第二十四頁(yè)，共五十三頁(yè)，2022年，8月28日5.4

MIMD算法算術(shù)表達(dá)式的同步MIMD算法例：(A+B(C+D*E*F))+G變形為：A+G+B*C+B*D*E*F第二十五頁(yè)，共五十三頁(yè)，2022年，8月28日P1P2P3P4a1=A+GP(r1)a1+=a2P(v3)a1+=a3a2=B*CV(r1)a3=B*DP(r2)a3*=a4V(r3)a4=E*FV(r2)第二十六頁(yè)，共五十三頁(yè)，2022年，8月28日5.5

MIMD算法區(qū)間分割法解代數(shù)方程的根求單調(diào)連續(xù)函數(shù)f(x)=0的根。設(shè)已知兩端l~u，對(duì)區(qū)間進(jìn)行n+1等分，令y[0]=f(l)，y[n+1]=f(u)。第二十七頁(yè)，共五十三頁(yè)，2022年，8月28日5.5

MIMD算法同步牛頓迭代法解代數(shù)方程的根迭代公式：第二十八頁(yè)，共五十三頁(yè)，2022年，8月28日P0P1while未達(dá)到精度{ y=f(x); wait(y’) x=x–y/y’;}while未達(dá)到精度{ wait(x) y’=f’(x);}并行進(jìn)程如下：P0P1y0=f(x0)y0’=f’(x0)x1=x0–y0/y0’y1=f(x1)y1’=f’(x1)x2=x1-y1/y1’…………并行計(jì)算過(guò)程如下：第二十九頁(yè)，共五十三頁(yè)，2022年，8月28日5.5

MIMD算法異步牛頓迭代法解代數(shù)方程的根P1P2While未達(dá)到精度{ y=f(x); x=x–y/y’;}While未達(dá)到精度{ y’=f’(x);}第三十頁(yè)，共五十三頁(yè)，2022年，8月28日5.6

流水線技術(shù)

歸并排序：設(shè)輸入長(zhǎng)度為n=2r，用p(n)=r+1個(gè)處理器并行完全合并排序的任務(wù)。設(shè)處理器編號(hào)從1到r+1，其中首處理器有一個(gè)輸入，尾處理器有一個(gè)輸出，其他處理器各有兩個(gè)輸入和兩個(gè)輸出。各處理器同步運(yùn)行，在一個(gè)時(shí)間步內(nèi)，P1從原始輸入序列中讀取一個(gè)數(shù)并將其作為結(jié)果輸出，Pi(i=2…r+1)接收從Pi-1輸出的兩個(gè)長(zhǎng)度為2i-2的子序列，并將其合并為一個(gè)長(zhǎng)度為2i-1的子序列。從P1到Pr，每一個(gè)處理器交替地在上面和下面兩條輸出線上產(chǎn)生合并子序列。除P1外，每個(gè)處理器Pi當(dāng)其前一個(gè)處理器的一條輸出線上已經(jīng)產(chǎn)生了長(zhǎng)為2i-2的子序列，另一條輸出線上出現(xiàn)了第一個(gè)元素時(shí)，就可以開(kāi)始?xì)w并了。第三十一頁(yè)，共五十三頁(yè)，2022年，8月28日設(shè)Pi和Pi+1之間通過(guò)的隊(duì)列為q2i和q2i+1，即q2i和q2i+1是Pi的輸出序列，Pi+1的輸入序列。如下圖所示：第三十二頁(yè)，共五十三頁(yè)，2022年，8月28日設(shè)n=2r，p(n)=r+1，算法描述如下：P1:j2;fork=1tondo{ xkq1; qjxk; j=5-j;}Pi:i=2…rj0;k1;whilek<=ndo{ ifq2(i-1)+j已裝滿2i-2個(gè)元素and q2(i-1)+(1-j)已出現(xiàn)1個(gè)元素then { form=1to2i-1do q2i+jmin(q2(i-1)+j,q2(i-1)+(1-j)); j1-j; kk+2i-1; }}Pr+1:ifq2r已裝滿2r-1個(gè)元素，且q2r+1已出現(xiàn)1個(gè)元素then{ form=1to2rdo q2(r+1)min(q2r,q2r+1);}第三十三頁(yè)，共五十三頁(yè)，2022年，8月28日十五、接力技術(shù)基本思想F:讓兩種算法接力，產(chǎn)生一個(gè)求解該問(wèn)題的新算法，使得既有耗時(shí)少的特性又有工作量有效性較高的特性。S:先用需要較少時(shí)間（速度較快）的算法求解給定的問(wèn)題，直到問(wèn)題的規(guī)模減到某一個(gè)閾值為止；L:再用工作量有效性較高的算法，繼續(xù)求解，直到獲得最終的解答。第三十四頁(yè)，共五十三頁(yè)，2022年，8月28日5.8接力技術(shù)求解最大值的常數(shù)時(shí)間算法對(duì)n個(gè)元素的數(shù)組，可以動(dòng)用n2個(gè)處理器，在O(1)的時(shí)間內(nèi)求解出最大值。A1A2A3mA1?F?FA2TTTTA3?F?FforallPii=1…ndo m[i]true;forallPi,ji=1…n,j=1…ndo if(A[i]<A[j])m[i]false;forallPii=1…ndo if(m[i]==true)maxA[i];第三十五頁(yè)，共五十三頁(yè)，2022年，8月28日216個(gè)葉子根28個(gè)結(jié)點(diǎn)，每個(gè)分28個(gè)葉結(jié)點(diǎn)28*24個(gè)結(jié)點(diǎn)，每個(gè)分24個(gè)葉結(jié)點(diǎn)28*24*22個(gè)結(jié)點(diǎn)，每個(gè)分22個(gè)葉結(jié)點(diǎn)28*24*22*2個(gè)結(jié)點(diǎn)，每個(gè)分2個(gè)葉結(jié)點(diǎn)第三十六頁(yè)，共五十三頁(yè)，2022年，8月28日十五、接力技術(shù)求解最大值的重對(duì)數(shù)時(shí)間算法設(shè)n個(gè)元素的序列，定義一棵以n個(gè)元素為葉結(jié)點(diǎn)的重對(duì)數(shù)深度平衡樹(shù)如下：

樹(shù)中每一個(gè)非葉子結(jié)點(diǎn)u的子結(jié)點(diǎn)的個(gè)數(shù)為以u(píng)為根的子樹(shù)上的葉結(jié)點(diǎn)的個(gè)數(shù)的平方根。則第0層為樹(shù)根，有一個(gè)結(jié)點(diǎn)，第1層為n1/2個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)為根的子樹(shù)上有n/n1/2=n1/2個(gè)葉子，所以每個(gè)結(jié)點(diǎn)有n1/4個(gè)子結(jié)點(diǎn)，可以證明，以第i層上每一個(gè)結(jié)點(diǎn)為根的子樹(shù)上有個(gè)葉子結(jié)點(diǎn)，第i層上共有個(gè)結(jié)點(diǎn)，可知這樣一棵樹(shù)的高度為loglogn+1，因此稱為重對(duì)數(shù)深度平衡樹(shù)。在重對(duì)數(shù)深度平衡樹(shù)上，除第0層外，對(duì)每一層按父結(jié)點(diǎn)分組，對(duì)每一組用常數(shù)時(shí)間算法求解最大值，結(jié)果放在其父結(jié)點(diǎn)中?？勺C明，共須n個(gè)處理器，經(jīng)過(guò)loglogn+1個(gè)并行步完成計(jì)算，時(shí)間復(fù)雜度為O(loglogn)。第三十七頁(yè)，共五十三頁(yè)，2022年，8月28日5.5、流水線技術(shù)排序問(wèn)題每個(gè)進(jìn)程一次從前一個(gè)進(jìn)程接收待排序序列中的一個(gè)數(shù)，保存當(dāng)前接受到的最大的數(shù)字，把比這個(gè)數(shù)小的其他數(shù)傳給下一個(gè)進(jìn)程。第一個(gè)進(jìn)程P0直接從待排序序列接收數(shù)據(jù)。P0P1P2P3P44|3|1|2|512345第三十八頁(yè)，共五十三頁(yè)，2022年，8月28日P0P1P2P3P4-----4|3|1|2|55----4|3|1|25----4|3|1252---4|3152---431531--42542--315431-254321第三十九頁(yè)，共五十三頁(yè)，2022年，8月28日十四、流水線技術(shù)質(zhì)數(shù)生成問(wèn)題順序解法for(i=2;i<=n;i++) prime[i]=1;for(i=0;i<=sqrt_n;i++) if(prime[i]==1) for(j=i*i;j<=n;j+=i) prime[j]=0;第四十頁(yè)，共五十三頁(yè)，2022年，8月28日質(zhì)數(shù)生成問(wèn)題流水線解法：第一個(gè)流水線級(jí)輸入一系列連續(xù)的數(shù)，然后剔出所有2的倍數(shù)，并把余下的數(shù)傳遞給第二級(jí)流水線；第二級(jí)剔出所有3的倍數(shù)并把余下的數(shù)傳遞給第三級(jí)流水線；以此類推；流水線的個(gè)數(shù)與質(zhì)數(shù)的個(gè)數(shù)的方根相同；十四、流水線技術(shù)第四十一頁(yè)，共五十三頁(yè)，2022年，8月28日十五、接力技術(shù)對(duì)數(shù)深度樹(shù)和重對(duì)數(shù)深度樹(shù)算法接力第一步，利用對(duì)數(shù)深度平衡樹(shù)方法向上逐層進(jìn)行計(jì)算，經(jīng)過(guò)logloglogn層的選拔后停下來(lái)。第二步，以第一步選拔出的最大值候選結(jié)點(diǎn)為葉結(jié)點(diǎn)，按重對(duì)數(shù)時(shí)間算法進(jìn)行繼續(xù)計(jì)算，直到所求的解。第一步所需時(shí)間為O(logloglogn)，工作量為O(nlogloglogn)，在第一步結(jié)束時(shí)，剩下的結(jié)點(diǎn)數(shù)為：n’=n/2logloglogn=n/loglogn。則第二步需要的時(shí)間為O(loglogn’)=O(loglogn)，工作量為O(n’loglogn)=O(n)。從而進(jìn)一步提高了工作量的有效性。第四十二頁(yè)，共五十三頁(yè)，2022年，8月28日十二、并行分治分治通過(guò)將一個(gè)問(wèn)題分解成若干個(gè)性質(zhì)相同的子問(wèn)題，并遞歸地對(duì)子問(wèn)題進(jìn)行求解，然后將各子問(wèn)題的解加以合并構(gòu)造出原問(wèn)題的解。分治步驟將問(wèn)題的輸入進(jìn)行均勻劃分，構(gòu)成規(guī)模大致相等的若干個(gè)同類的子問(wèn)題；遞歸求解各子問(wèn)題；將各子問(wèn)題的解歸并成為原問(wèn)題的解；第四十三頁(yè)，共五十三頁(yè)，2022年，8月28日十二、并行分治并行分治:F(I){ if輸入足夠小then OAnswer(I); else {

分解輸入：I1,…Ik；

forallPii=1…kdo Oi

F(Ii,Oi); OCombine(O1,…Ok); }}第四十四頁(yè)，共五十三頁(yè)，2022年，8月28日十二、并行分治最近點(diǎn)對(duì)問(wèn)題d1d2d2d第四十五頁(yè)，共五十三頁(yè)，2022年，8月28日十三、劃分法劃分法與分治法相似，劃分原理也是將原問(wèn)題進(jìn)行分解，分別求解，再歸并子問(wèn)題的解。所不同的是，分治法采用簡(jiǎn)單的分解方法，因此設(shè)計(jì)的難點(diǎn)在于如何歸并子問(wèn)題的解，而劃分方法則講究分解的方法，以獲得簡(jiǎn)單的歸并策略。有序序列歸并:設(shè)A=(a1,a2,…,an)，

B=(b1,b2,…,bm)，

是U上的單調(diào)增序列，且A∩B=Ф。

將A和B歸并到：

C=(c1,c2,…,cm+n)。第四十六頁(yè)，共五十三頁(yè)，2022年，8月28日十三、劃分法有序序列歸并定義：對(duì)U上的有序序列列X=(x1,x2,…,xt)，x∈U，x在X上的位序rank(x:X)為X中小于等于x的元素個(gè)數(shù)。歸并問(wèn)題即求rank(x:A∪B)，x∈A∪B。分別求出rank(ai:B)和rank(bj:A)，即可得到rank(x:A∪B)=rank(x:A)+rank(x:B)。這樣就可以在O(logn)時(shí)間內(nèi)用O(nlogn)工作量完成合并的任務(wù)。但這樣的解法不是一個(gè)工作量有效的算法。通過(guò)進(jìn)一步劃分，可以得到工作量有效的解法。第四十七頁(yè)，共五十三頁(yè)，2022年，8月28日十三、劃分法有序序列歸并定義：對(duì)U上的有序序列列X=(x1,x2,…,xt)，x∈U，x在X上的位序rank(x:X)為X中小于等于x的元素個(gè)數(shù)。歸并問(wèn)題即求rank(x:A∪B)，x∈A∪B。分別求出rank(ai:B)和rank(bj:A)，即可得到rank(x:A∪B)=rank(x:A)+rank(