多處理機(jī)的并行和性能課件

§3多處理機(jī)的并行和性能

并行算法

程序并行性分析

并行語言與并行編譯多處理性能§3多處理機(jī)的并行和性能并行算法1并行算法并行算法的定義和分類多處理機(jī)并行算法的研究思路并行算法并行算法的定義和分類2并行算法的定義算法規(guī)定了求解某一特定問題時的有窮的運(yùn)算處理步驟并行算法是指可同時執(zhí)行的多個進(jìn)程的集合，各進(jìn)程可相互作用、協(xié)調(diào)和并發(fā)操作并行算法的定義算法規(guī)定了求解某一特定問題時的有窮的運(yùn)算處理步3并行算法的分類按運(yùn)算基本對象：數(shù)值型（基于代數(shù)運(yùn)算），非數(shù)值型（基于關(guān)系運(yùn)算）按并行進(jìn)程間的操作順序不同：同步型，異步型，獨(dú)立型按計(jì)算任務(wù)的大?。杭?xì)粒度，中粒度，粗粒度并行算法的分類按運(yùn)算基本對象：數(shù)值型（基于代數(shù)運(yùn)算），非數(shù)值4并行計(jì)算的模型PRAM（ParallelRandomAccessMachine）APRAM(AsychromousPRAM)

BSP(Bulk

SynchronousParallel)logP(Latency,Overhead,Gap,Processor)并行計(jì)算的模型PRAM（ParallelRandomA5并行計(jì)算的功能降低單個問題求解的時間增加問題求解規(guī)模、提高問題求解精度(多機(jī)同時執(zhí)行多個串行程序)容錯、更高的可用性、提高吞吐率并行計(jì)算的功能降低單個問題求解的時間6如何實(shí)現(xiàn)并行計(jì)算?分而治之!如何實(shí)現(xiàn)并行計(jì)算?分而治之!7分而治之并行化的主要方法:分而治之根據(jù)問題的求解過程，把任務(wù)分成若干子任務(wù)(任務(wù)級并行或功能并行)根據(jù)處理數(shù)據(jù)的方式，形成多個相對獨(dú)立的數(shù)據(jù)區(qū)，由不同的處理器分別處理(數(shù)據(jù)并行)分而治之并行化的主要方法:分而治之8并行計(jì)算基本設(shè)計(jì)技術(shù)

劃分法(Partitioning)

首先，將原問題分成p個獨(dú)立的近乎大小相等的子問題；其次，用p臺處理器并行求解諸子問題。劃分的難點(diǎn)在于要留心分解子問題，使得子問題的解很容易被組合成原問題的解。例如(m,n)-selection網(wǎng)絡(luò)。分治法(Divide-and-Conquer)

將原問題規(guī)模從大到小逐漸分解成一些特性相同的子問題；直到子問題很容易求解為止。分治很自然地導(dǎo)致遞歸過程，其注意力集中在子問題地合并上。例如FFT的計(jì)算。并行計(jì)算基本設(shè)計(jì)技術(shù)劃分法(Partitioning)9并行計(jì)算基本設(shè)計(jì)技術(shù)（續(xù)）平衡樹法(BalancedTree)

將輸入元素作為葉節(jié)點(diǎn)構(gòu)筑一棵平衡二叉樹；然后自葉向根往返遍歷。此法的優(yōu)點(diǎn)是在樹中能快速存取所需的信息。例如數(shù)據(jù)播送、求最大/最小值以及求和/前綴計(jì)算等。倍增法(Doubling)/指針跳躍法(PointerJumping)使用遞歸計(jì)算，將需要處理的數(shù)據(jù)間的距離逐步加倍，經(jīng)k步后就可以完成距離為2k的所有數(shù)據(jù)的計(jì)算。此法特別適合于處理以鏈表或有根樹之類為數(shù)據(jù)結(jié)構(gòu)的問題。例如表序問題的計(jì)算和求森林根等。并行計(jì)算基本設(shè)計(jì)技術(shù)（續(xù)）平衡樹法(BalancedTre10并行計(jì)算基本設(shè)計(jì)技術(shù)（續(xù)）流水線法(Piplining)將原任務(wù)t分成一系列子任務(wù)t1，t2，…，tm，使得一旦ti完成，后繼的子任務(wù)就立即開始，并以同樣的速率計(jì)算之。例如systolic計(jì)算。破對稱法(SymmetryBreaking)打破某些問題的對稱性，使原問題可并行計(jì)算。例如有向環(huán)圖的頂點(diǎn)著色。并行計(jì)算基本設(shè)計(jì)技術(shù)（續(xù)）流水線法(Piplining)11并行算法常用的設(shè)計(jì)策略

串行算法的直接并行化

檢測串行算法中固有并行性而直接將其并行化。直接并行化的關(guān)鍵是分析數(shù)據(jù)執(zhí)行時的相關(guān)性，為此有時需要調(diào)整原程序的執(zhí)行順序和復(fù)制共享變量等。直接并行化并非對所有問題均可行，但對很多應(yīng)用問題仍不失為一種有效的方法。并非任何優(yōu)秀的串行算法都可以產(chǎn)生最好的并行算法；相反一個不太好的串行算法則有可能產(chǎn)生很優(yōu)秀的并行算法。

并行算法常用的設(shè)計(jì)策略串行算法的直接并行化12并行算法常用的設(shè)計(jì)策略（續(xù)）設(shè)計(jì)全新的并行算法

從問題本身的描述出發(fā)，根據(jù)問題的固有屬性，從頭開始設(shè)計(jì)一個全新的并行算法，而不管其相關(guān)的串行算法。此方法有難度，但通?？僧a(chǎn)生高效的并行算法。

借用已有的算法求解新的一類問題

仔細(xì)研究兩類不同問題求解方法的內(nèi)在的、直接或間接的相似性，借用已有的求解某問題的并行算法來求解新的一類問題。此方法對初學(xué)者有一定難度，但一個好的借用法所設(shè)計(jì)的算法，往往給人帶來深刻的影響，廣為傳頌。

并行算法常用的設(shè)計(jì)策略（續(xù)）設(shè)計(jì)全新的并行算法13并行算法的一般設(shè)計(jì)過程

劃分（Partitioning）：將整個計(jì)算分解成一些小的任務(wù)，目的是盡量開拓并行性。

通信（Communication）：確定諸任務(wù)并行執(zhí)行中通信情況，以檢測上述劃分粒度的合理性。組合（Agglomeration）：根據(jù)性能和代價(jià)來考察上兩步的結(jié)果，必要時組合一些小任務(wù)以減小通信開銷。映射（Mapping）：將每個任務(wù)指派給個處理器，目的是最小化執(zhí)行時間和最大化處理器利用率。

并行算法的一般設(shè)計(jì)過程劃分（Partitioning）：將14并行算法一般設(shè)計(jì)過程

并行算法一般設(shè)計(jì)過程15并行算法的性能分析

并行算法的基本性能指標(biāo)執(zhí)行時間t(n)和所使用的處理器數(shù)p(n)計(jì)算成本c(n)=t(n)*p(n)加速比效率并行算法的性能分析并行算法的基本性能指標(biāo)16Amdahl定律計(jì)算負(fù)載固定，隨著處理器數(shù)的增加計(jì)算時間將減少。令W是計(jì)算負(fù)載，Ws是W中的串行分量，Wp是W中的并行分量，f=Ws/W是串行分量比率，則Amdahl加速定律所以即使使用無窮多的處理器，加速也只能是1/fAmdahl定律計(jì)算負(fù)載固定，隨著處理器數(shù)的增加計(jì)算時間將減17Gustafson定律計(jì)算時間不變，增加處理器的同時亦要增加計(jì)算負(fù)載以提高計(jì)算精度，則Gustafson加速定律

所以加速幾乎是線性的。Gustafson定律計(jì)算時間不變，增加處理器的同時亦要增加18性能損失的原因順序計(jì)算不需要的付出的開銷不可并行化的計(jì)算部分空閑的處理器對資源的競爭性能損失的原因順序計(jì)算不需要的付出的開銷19多處理機(jī)并行算法的研究思路

將大的程序分解成可由足夠的并行處理的過程（進(jìn)程、任務(wù)、程序段）

多處理機(jī)并行算法的研究思路將大的程序分解成可由足夠的并行處20舉例1E1=a+bx+cx2+dx3利用Horner法：E1=a+x(b+x(c+x(d)))

需3個乘加循環(huán)，6級運(yùn)算適合于單處理機(jī)

用樹形流程圖

+*+*+*axbxcdx舉例1E1=a+bx+cx2+dx3+*+*+*axbxcd21舉例1（續(xù)）E1=a+bx+cx2+dx3用3臺處理機(jī)，需4級運(yùn)算級數(shù)（高度）Tp=4處理機(jī)數(shù)P=3加速比Sp=順序運(yùn)算級數(shù)/高度=6/4=3/2效率Ep=Sp/P=1/2*+*++****abxxxxxxcd舉例1（續(xù)）E1=a+bx+cx2+dx3*+*++****22說明降低樹高，增加并行性用交換律、結(jié)合律、分配律來變換先利用交換律把相同的運(yùn)算集中起來，再用結(jié)合律把參加運(yùn)算的操作數(shù)配對，盡可能并行運(yùn)算，最后再把子樹結(jié)合起來。說明降低樹高，增加并行性23舉例2E2=a+b(c+def+g)+h需7級運(yùn)算++*++*habgcdf*e舉例2E2=a+b(c+def+g)+h++*++*habg24舉例2（續(xù)）利用交換律和結(jié)合律E2=(a+h)+b((c+g)+def)需5級運(yùn)算P=2Tp=5Sp=7/5Ep=Sp/p=0.7+++++++ahbcgdef舉例2（續(xù)）利用交換律和結(jié)合律+++++++ahbcgdef25舉例2（續(xù)）利用分配律降低樹高。E2=(a+h)+(bc+bg)+bdef需4級運(yùn)算P=3Tp=4Sp=7/4Ep=7/12**+***+++acbgahbdef舉例2（續(xù)）利用分配律降低樹高。**+***+++acbga26說明表達(dá)式運(yùn)算并行性的識別，除依靠算法可以依靠編譯程序可以經(jīng)過或不經(jīng)過逆波蘭后綴表達(dá)式產(chǎn)生并行指令說明表達(dá)式運(yùn)算并行性的識別，除依靠算法27舉例3算術(shù)表達(dá)式Z=E+A*B*C/D+F利用串行編譯算法，產(chǎn)生三元指令組1*AB4+3E2*1C5+4F3/2D6=5Z需5級運(yùn)算

舉例3算術(shù)表達(dá)式28舉例3（需）利用并行編譯算法1*AB4+EF2/CD5+343*126=5Z分配給2個處理機(jī)，需3級運(yùn)算舉例3（需）利用并行編譯算法29遞歸程序的并行性是研究并行算法的重要課題這里只討論線性遞歸遞歸程序的并行性是研究并行算法的重要課題30線性遞歸的例子線性遞歸的例子31線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）32線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）33線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）34列掃算法需用（n-1）個處理機(jī)計(jì)算2（n-1）步例如：如n=4，則需3個處理機(jī)，用6步列掃算法需用（n-1）個處理機(jī)計(jì)算2（n-1）步35乘積形式遞歸算法當(dāng)n=4時，右邊只有4種是不同，需用4個處理機(jī)經(jīng)2步算出，再用2個處理機(jī)經(jīng)3步算出比上一算法，少用1步，多用1個處理機(jī)N較大時，快速。乘積形式遞歸算法當(dāng)n=4時，右邊只有4種是不同，需用4個處理36程序舉例

DO4I=1,N1E(I)=3*F(I)+SIN(P(I))2B(I)+D(I-1)+Q(I)3D(I)=E(I)+B(I)4CONTINUE語句1提到循環(huán)前，2、3構(gòu)成循環(huán)1323FPDQBDE數(shù)據(jù)相關(guān)圖程序舉例DO4I=1,N1323FPDQBDE數(shù)37程序的并行性分析假定一個程序包含P1,P2,…,Pi,…Pj,…Pn等n個程序段，設(shè)Pi和Pj程序段都是一條語句，Pi在Pj之前執(zhí)行。數(shù)據(jù)相關(guān)數(shù)據(jù)反相關(guān)數(shù)據(jù)輸出相關(guān)程序的并行性分析假定一個程序包含P1,P2,…,Pi,…Pj38數(shù)據(jù)相關(guān)如果Pi的左部變量在Pj的右部變量集內(nèi)，且Pj必須取出Pi運(yùn)算的結(jié)果來作為操作數(shù)，稱Pj”數(shù)據(jù)相關(guān)”于Pi，例：Pi:A=B+DPj:C=A*E相當(dāng)于流水中的“先寫后讀”相關(guān)。順序執(zhí)行的正確結(jié)果是：PiA新=B原+D原

PjC新=A新*E原=(B原+D原)*E原數(shù)據(jù)相關(guān)如果Pi的左部變量在Pj的右部變量集內(nèi)，且Pj必須取39數(shù)據(jù)相關(guān)（續(xù)）Pi，Pj不能并行。特殊，當(dāng)Pi和Pj服從交換律時PiA=2*APjA=3*A雖不能并行，但能交換串行。得：6*A數(shù)據(jù)相關(guān)（續(xù)）Pi，Pj不能并行。40數(shù)據(jù)反相關(guān)如果Pj的左部變量在Pi的右部變量集內(nèi)，且當(dāng)Pi未取用其變量的值之前，是不允許被Pj所改變，稱Pi”數(shù)據(jù)反相關(guān)”于Pj，例：Pi:C=A+EPj:A=B+D相當(dāng)于流水中的“先讀后寫”相關(guān)。順序執(zhí)行的正確結(jié)果是：PiC新=A原+E原

PjA新=B原+

D原不能交換串行。數(shù)據(jù)反相關(guān)如果Pj的左部變量在Pi的右部變量集內(nèi)，且當(dāng)Pi未41數(shù)據(jù)輸出相關(guān)如果Pi的左部變量也是Pj的左部變量，且Pj存入其算得的值必須在P存入之后，則稱Pj”數(shù)據(jù)輸出相關(guān)”于Pi，例：Pi:A=B+DPj:A=C+E數(shù)據(jù)輸出相關(guān)如果Pi的左部變量也是Pj的左部變量，且Pj存入42總結(jié)兩個程序段之間如有先寫后讀的數(shù)據(jù)相關(guān)，不能并行，只在特殊情況下可以交換串行；如有先讀后寫的數(shù)據(jù)反相關(guān)，可以并行執(zhí)行，但必須保證其寫入共享主存時的先讀后寫次序，不能交換串行；如有寫-寫的數(shù)據(jù)輸出相關(guān)，可以并行執(zhí)行，但同樣需保證其寫入的先后次序，不能交換串行；如同時有先寫后讀和先讀后寫兩種相關(guān)，以交換數(shù)據(jù)為目的時，則必須讀寫完全同步，不許順序串行和交換串行；如沒有任何相關(guān)，或僅有源數(shù)據(jù)相同時，可以并行、順序串行和交換串行?？偨Y(jié)兩個程序段之間如有先寫后讀的數(shù)據(jù)相關(guān)，不能并行，只在特殊43并行語言和并行編譯是在普通順序型程序設(shè)計(jì)語言基礎(chǔ)上加以擴(kuò)充，增加能明確表示并行進(jìn)程的成分。并行程序設(shè)計(jì)語言要求能使程序員靈活方便地在其程序中表示出各類并行性，同時應(yīng)有高的效率，能在各種并行/向量計(jì)算機(jī)系統(tǒng)中有效地實(shí)現(xiàn)。并行進(jìn)程的特點(diǎn)：進(jìn)程在時間上重疊執(zhí)行。派生：FORK;匯合：JOIN在不同的機(jī)器上有不同的表現(xiàn)形式。并行語言和并行編譯是在普通順序型程序設(shè)計(jì)語言基礎(chǔ)上加以擴(kuò)充，44并行程序設(shè)計(jì)語言（續(xù)）M.E.Conway(康佳)形式：FORMm：派生出標(biāo)號為m開始的新進(jìn)程。如果是共享內(nèi)存，產(chǎn)生存儲器指針、映像函數(shù)和訪問權(quán)數(shù)據(jù)將空閑的處理機(jī)分配給被FORK語句派生的新進(jìn)程如果沒有可用的空閑處理機(jī)，排隊(duì)等待。并行程序設(shè)計(jì)語言（續(xù)）M.E.Conway(康佳)形式：45并行程序設(shè)計(jì)語言（續(xù)）JOINn：附有計(jì)數(shù)器，初值為0執(zhí)行語句時，計(jì)數(shù)器加1，與n比較如相等，表明執(zhí)行的第n格并發(fā)進(jìn)程經(jīng)過JOIN語句，允許通過語句，計(jì)數(shù)器清0，繼續(xù)執(zhí)行后續(xù)語句。如小于n，則進(jìn)程不是最后一個，先讓進(jìn)程結(jié)束，則把它占用的處理機(jī)釋放出來，分配給排隊(duì)的其他任務(wù)，如無任務(wù)，則空閑。并行程序設(shè)計(jì)語言（續(xù)）JOINn：46舉例1計(jì)算Z=E+A*B*C/D+F并行編譯：S1G=A*BS2H=C/DS3I=G*HS4J=E+F

S5Z=I+JS1S2S3S4S5ABCDEF舉例1計(jì)算S1S2S3S4S5ABCDEF47舉例1（續(xù)）

FORK2030FORK4010G=A*B(進(jìn)程S1)I+=G*H(進(jìn)程S3)JOIN2JOIN2GOTO30GOTO5020H=C/D(進(jìn)程S2)40J=E+F(進(jìn)程S4)JOIN2JOIN250Z=I+J(進(jìn)程S5)舉例1（續(xù)）FORK2048時間處理機(jī)S1S2S3S4S5FORK20FORK40JOIN2JOIN2JOIN2JOIN2GOTO50釋放釋放釋放時間處理機(jī)S1S2S3S4S5FORK20FORK40J49舉例2假定A，B兩個8*8矩陣相乘：

DO10J=0,6DO40K=0,710FORK2040C(I,J)=C(I,J)+A(I,K)*B(K,J)J=730CONTINUE20DO30I=0,7JOIN8C(I,J)=0舉例2假定A，B兩個8*8矩陣相乘：50處理機(jī)tJ=0J=1J=2J=3J=7J=4J=5J=6FORK7次JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8時間資源時間圖處理機(jī)tJ=0J=1J=2J=3J=7J=4J=5J=6FO51多處理機(jī)與并行處理機(jī)的區(qū)別并行處理機(jī)的每一條指令要求8個處理單元完全同步地對j=0,1,..7的不同數(shù)組進(jìn)行運(yùn)算。在多處理機(jī)中，不需要也不會完全同步。----操作級與任務(wù)級多處理機(jī)中可用處理機(jī)數(shù)目對程序編寫沒有影響。多處理機(jī)與并行處理機(jī)的區(qū)別并行處理機(jī)的每一條指令要求8個處理52塊結(jié)構(gòu)語言E.W.Dijkstra提出把可并行執(zhí)行的進(jìn)程用cobegin-coend括起來處理,最后一條語句執(zhí)行完成后，方可執(zhí)行后續(xù)語句。該語句可嵌套；可使用共享變量，但不允許修改。塊結(jié)構(gòu)語言E.W.Dijkstra提出53舉例1beginS0;CobeginS1;S2,…;Sn;coendSn+1;endS0S3S1SnSn+1舉例1S0S3S1SnSn+154舉例2BeginS0;cobeginS1;beginS2;cobeginS3;S4;S5;coendS6;endS7;coendS8;endS0S2S4S3S5S1S7S6S8舉例2BeginS0S2S4S3S5S1S7S6S855多處理機(jī)性能引起峰值性能下降的原因是：因處理機(jī)間通信而產(chǎn)生的延遲一臺處理機(jī)與其它處理機(jī)同步所需的開銷當(dāng)沒有足夠多任務(wù)時，一臺或多臺處理機(jī)處于空閑狀態(tài)由于一臺或多臺處理機(jī)執(zhí)行無用的工作系統(tǒng)控制和操作調(diào)度所需開銷多處理機(jī)性能引起峰值性能下降的原因是：56多處理機(jī)性能（續(xù)）研究多處理機(jī)的目的：提前5年得到速度高10倍的機(jī)器?；蛴?/10的價(jià)格獲得一臺高性能的機(jī)器。如果設(shè)計(jì)得好，在某些適合進(jìn)行并行處理得應(yīng)用領(lǐng)域，可以達(dá)到：提前10年得到速度高100倍的機(jī)器或用1/100的價(jià)格獲得一臺高性能的機(jī)器。并行性在很大程度上依賴于E/C比值，其中：E代表程序執(zhí)行時間C代表通信開銷。多處理機(jī)性能（續(xù)）研究多處理機(jī)的目的：57多處理機(jī)性能（續(xù)）通常：E/C比值小，并行性低。E/C比值大，并行性高如果把作業(yè)分解成較大的塊，就能得到較大的E/C值，但是所得到的并行性比最大可能的并行性要小得多。E/C比值是衡量任務(wù)粒度(Granularity)大小的尺度在粗粒度（Coarsegrain）并行情況下，E/C比值比較大，通信開銷小多處理機(jī)性能（續(xù)）通常：E/C比值小，并行性低。E/C比值大58多處理機(jī)性能（續(xù)）在細(xì)粒度（Finegrain）并行情況下，E/C比值比較小，通信開銷大細(xì)粒度并行性需要的處理機(jī)多，粗粒度并行性需要的處理機(jī)少。細(xì)粒度并行性的基本原理是把一個程序盡可能地分解成能并行執(zhí)行的小任務(wù)。在極端情況下，一個小任務(wù)只完成一個操作。多處理機(jī)性能（續(xù)）在細(xì)粒度（Finegrain）并行情況下，59§4多處理機(jī)的操作系統(tǒng)

多處理機(jī)操作系統(tǒng)的難度與特點(diǎn)

多處理機(jī)操作系統(tǒng)的類型

多處理機(jī)操作系統(tǒng)的的發(fā)展

§4多處理機(jī)的操作系統(tǒng)多處理機(jī)操作系統(tǒng)的難度與特點(diǎn)60多處理機(jī)操作系統(tǒng)的難度

處理機(jī)的分配和進(jìn)程調(diào)度

進(jìn)程間的同步進(jìn)程間的通信存儲系統(tǒng)的管理文件系統(tǒng)的管理系統(tǒng)重組

多處理機(jī)操作系統(tǒng)的難度處理機(jī)的分配和進(jìn)程調(diào)度61多處理機(jī)操作系統(tǒng)的特點(diǎn)

程序執(zhí)行的并行性

分布性機(jī)間通信與同步性系統(tǒng)容錯性

多處理機(jī)操作系統(tǒng)的特點(diǎn)程序執(zhí)行的并行性62多處理機(jī)操作系統(tǒng)的類型

主從型(Master-slaveConfiguration)管理程序只在主處理機(jī)上運(yùn)行。硬件結(jié)構(gòu)、管理、控制簡單，對主處理機(jī)要求高。用于工作負(fù)荷固定、從處理機(jī)能力明顯低的緊耦合、異構(gòu)型、非對稱多處理機(jī)系統(tǒng)。實(shí)現(xiàn)簡單，經(jīng)濟(jì)，方便多處理機(jī)操作系統(tǒng)的類型主從型(Master-slaveC63多處理機(jī)操作系統(tǒng)的類型（續(xù)）各自獨(dú)立型（SeparateSupervisor）每個處理機(jī)有獨(dú)立的管理程序在運(yùn)行。管理程序可再入，可靠性高，系統(tǒng)表格少，系統(tǒng)效率高；實(shí)現(xiàn)復(fù)雜、訪存沖突解決和負(fù)載平衡較困難。效率高；實(shí)現(xiàn)復(fù)雜，適合于松耦合多處理機(jī)多處理機(jī)操作系統(tǒng)的類型（續(xù)）各自獨(dú)立型（SeparateS64多處理機(jī)操作系統(tǒng)的類型（續(xù)）浮動型(FloatingSupervisor)管理程序在多個處理機(jī)間浮動。管理程序可再入，實(shí)現(xiàn)復(fù)雜，負(fù)載平衡較好。折衷方式；靈活性；適合于緊耦合型，同構(gòu)型；多處理機(jī)操作系統(tǒng)的類型（續(xù)）浮動型(FloatingSup65§3多處理機(jī)的并行和性能

并行算法

程序并行性分析

并行語言與并行編譯多處理性能§3多處理機(jī)的并行和性能并行算法66并行算法并行算法的定義和分類多處理機(jī)并行算法的研究思路并行算法并行算法的定義和分類67并行算法的定義算法規(guī)定了求解某一特定問題時的有窮的運(yùn)算處理步驟并行算法是指可同時執(zhí)行的多個進(jìn)程的集合，各進(jìn)程可相互作用、協(xié)調(diào)和并發(fā)操作并行算法的定義算法規(guī)定了求解某一特定問題時的有窮的運(yùn)算處理步68并行算法的分類按運(yùn)算基本對象：數(shù)值型（基于代數(shù)運(yùn)算），非數(shù)值型（基于關(guān)系運(yùn)算）按并行進(jìn)程間的操作順序不同：同步型，異步型，獨(dú)立型按計(jì)算任務(wù)的大?。杭?xì)粒度，中粒度，粗粒度并行算法的分類按運(yùn)算基本對象：數(shù)值型（基于代數(shù)運(yùn)算），非數(shù)值69并行計(jì)算的模型PRAM（ParallelRandomAccessMachine）APRAM(AsychromousPRAM)

BSP(Bulk

SynchronousParallel)logP(Latency,Overhead,Gap,Processor)并行計(jì)算的模型PRAM（ParallelRandomA70并行計(jì)算的功能降低單個問題求解的時間增加問題求解規(guī)模、提高問題求解精度(多機(jī)同時執(zhí)行多個串行程序)容錯、更高的可用性、提高吞吐率并行計(jì)算的功能降低單個問題求解的時間71如何實(shí)現(xiàn)并行計(jì)算?分而治之!如何實(shí)現(xiàn)并行計(jì)算?分而治之!72分而治之并行化的主要方法:分而治之根據(jù)問題的求解過程，把任務(wù)分成若干子任務(wù)(任務(wù)級并行或功能并行)根據(jù)處理數(shù)據(jù)的方式，形成多個相對獨(dú)立的數(shù)據(jù)區(qū)，由不同的處理器分別處理(數(shù)據(jù)并行)分而治之并行化的主要方法:分而治之73并行計(jì)算基本設(shè)計(jì)技術(shù)

劃分法(Partitioning)

首先，將原問題分成p個獨(dú)立的近乎大小相等的子問題；其次，用p臺處理器并行求解諸子問題。劃分的難點(diǎn)在于要留心分解子問題，使得子問題的解很容易被組合成原問題的解。例如(m,n)-selection網(wǎng)絡(luò)。分治法(Divide-and-Conquer)

將原問題規(guī)模從大到小逐漸分解成一些特性相同的子問題；直到子問題很容易求解為止。分治很自然地導(dǎo)致遞歸過程，其注意力集中在子問題地合并上。例如FFT的計(jì)算。并行計(jì)算基本設(shè)計(jì)技術(shù)劃分法(Partitioning)74并行計(jì)算基本設(shè)計(jì)技術(shù)（續(xù)）平衡樹法(BalancedTree)

將輸入元素作為葉節(jié)點(diǎn)構(gòu)筑一棵平衡二叉樹；然后自葉向根往返遍歷。此法的優(yōu)點(diǎn)是在樹中能快速存取所需的信息。例如數(shù)據(jù)播送、求最大/最小值以及求和/前綴計(jì)算等。倍增法(Doubling)/指針跳躍法(PointerJumping)使用遞歸計(jì)算，將需要處理的數(shù)據(jù)間的距離逐步加倍，經(jīng)k步后就可以完成距離為2k的所有數(shù)據(jù)的計(jì)算。此法特別適合于處理以鏈表或有根樹之類為數(shù)據(jù)結(jié)構(gòu)的問題。例如表序問題的計(jì)算和求森林根等。并行計(jì)算基本設(shè)計(jì)技術(shù)（續(xù)）平衡樹法(BalancedTre75并行計(jì)算基本設(shè)計(jì)技術(shù)（續(xù)）流水線法(Piplining)將原任務(wù)t分成一系列子任務(wù)t1，t2，…，tm，使得一旦ti完成，后繼的子任務(wù)就立即開始，并以同樣的速率計(jì)算之。例如systolic計(jì)算。破對稱法(SymmetryBreaking)打破某些問題的對稱性，使原問題可并行計(jì)算。例如有向環(huán)圖的頂點(diǎn)著色。并行計(jì)算基本設(shè)計(jì)技術(shù)（續(xù)）流水線法(Piplining)76并行算法常用的設(shè)計(jì)策略

串行算法的直接并行化

檢測串行算法中固有并行性而直接將其并行化。直接并行化的關(guān)鍵是分析數(shù)據(jù)執(zhí)行時的相關(guān)性，為此有時需要調(diào)整原程序的執(zhí)行順序和復(fù)制共享變量等。直接并行化并非對所有問題均可行，但對很多應(yīng)用問題仍不失為一種有效的方法。并非任何優(yōu)秀的串行算法都可以產(chǎn)生最好的并行算法；相反一個不太好的串行算法則有可能產(chǎn)生很優(yōu)秀的并行算法。

并行算法常用的設(shè)計(jì)策略串行算法的直接并行化77并行算法常用的設(shè)計(jì)策略（續(xù)）設(shè)計(jì)全新的并行算法

從問題本身的描述出發(fā)，根據(jù)問題的固有屬性，從頭開始設(shè)計(jì)一個全新的并行算法，而不管其相關(guān)的串行算法。此方法有難度，但通?？僧a(chǎn)生高效的并行算法。

借用已有的算法求解新的一類問題

仔細(xì)研究兩類不同問題求解方法的內(nèi)在的、直接或間接的相似性，借用已有的求解某問題的并行算法來求解新的一類問題。此方法對初學(xué)者有一定難度，但一個好的借用法所設(shè)計(jì)的算法，往往給人帶來深刻的影響，廣為傳頌。

并行算法常用的設(shè)計(jì)策略（續(xù)）設(shè)計(jì)全新的并行算法78并行算法的一般設(shè)計(jì)過程

劃分（Partitioning）：將整個計(jì)算分解成一些小的任務(wù)，目的是盡量開拓并行性。

通信（Communication）：確定諸任務(wù)并行執(zhí)行中通信情況，以檢測上述劃分粒度的合理性。組合（Agglomeration）：根據(jù)性能和代價(jià)來考察上兩步的結(jié)果，必要時組合一些小任務(wù)以減小通信開銷。映射（Mapping）：將每個任務(wù)指派給個處理器，目的是最小化執(zhí)行時間和最大化處理器利用率。

并行算法的一般設(shè)計(jì)過程劃分（Partitioning）：將79并行算法一般設(shè)計(jì)過程

并行算法一般設(shè)計(jì)過程80并行算法的性能分析

并行算法的基本性能指標(biāo)執(zhí)行時間t(n)和所使用的處理器數(shù)p(n)計(jì)算成本c(n)=t(n)*p(n)加速比效率并行算法的性能分析并行算法的基本性能指標(biāo)81Amdahl定律計(jì)算負(fù)載固定，隨著處理器數(shù)的增加計(jì)算時間將減少。令W是計(jì)算負(fù)載，Ws是W中的串行分量，Wp是W中的并行分量，f=Ws/W是串行分量比率，則Amdahl加速定律所以即使使用無窮多的處理器，加速也只能是1/fAmdahl定律計(jì)算負(fù)載固定，隨著處理器數(shù)的增加計(jì)算時間將減82Gustafson定律計(jì)算時間不變，增加處理器的同時亦要增加計(jì)算負(fù)載以提高計(jì)算精度，則Gustafson加速定律

所以加速幾乎是線性的。Gustafson定律計(jì)算時間不變，增加處理器的同時亦要增加83性能損失的原因順序計(jì)算不需要的付出的開銷不可并行化的計(jì)算部分空閑的處理器對資源的競爭性能損失的原因順序計(jì)算不需要的付出的開銷84多處理機(jī)并行算法的研究思路

將大的程序分解成可由足夠的并行處理的過程（進(jìn)程、任務(wù)、程序段）

多處理機(jī)并行算法的研究思路將大的程序分解成可由足夠的并行處85舉例1E1=a+bx+cx2+dx3利用Horner法：E1=a+x(b+x(c+x(d)))

需3個乘加循環(huán)，6級運(yùn)算適合于單處理機(jī)

用樹形流程圖

+*+*+*axbxcdx舉例1E1=a+bx+cx2+dx3+*+*+*axbxcd86舉例1（續(xù)）E1=a+bx+cx2+dx3用3臺處理機(jī)，需4級運(yùn)算級數(shù)（高度）Tp=4處理機(jī)數(shù)P=3加速比Sp=順序運(yùn)算級數(shù)/高度=6/4=3/2效率Ep=Sp/P=1/2*+*++****abxxxxxxcd舉例1（續(xù)）E1=a+bx+cx2+dx3*+*++****87說明降低樹高，增加并行性用交換律、結(jié)合律、分配律來變換先利用交換律把相同的運(yùn)算集中起來，再用結(jié)合律把參加運(yùn)算的操作數(shù)配對，盡可能并行運(yùn)算，最后再把子樹結(jié)合起來。說明降低樹高，增加并行性88舉例2E2=a+b(c+def+g)+h需7級運(yùn)算++*++*habgcdf*e舉例2E2=a+b(c+def+g)+h++*++*habg89舉例2（續(xù)）利用交換律和結(jié)合律E2=(a+h)+b((c+g)+def)需5級運(yùn)算P=2Tp=5Sp=7/5Ep=Sp/p=0.7+++++++ahbcgdef舉例2（續(xù)）利用交換律和結(jié)合律+++++++ahbcgdef90舉例2（續(xù)）利用分配律降低樹高。E2=(a+h)+(bc+bg)+bdef需4級運(yùn)算P=3Tp=4Sp=7/4Ep=7/12**+***+++acbgahbdef舉例2（續(xù)）利用分配律降低樹高。**+***+++acbga91說明表達(dá)式運(yùn)算并行性的識別，除依靠算法可以依靠編譯程序可以經(jīng)過或不經(jīng)過逆波蘭后綴表達(dá)式產(chǎn)生并行指令說明表達(dá)式運(yùn)算并行性的識別，除依靠算法92舉例3算術(shù)表達(dá)式Z=E+A*B*C/D+F利用串行編譯算法，產(chǎn)生三元指令組1*AB4+3E2*1C5+4F3/2D6=5Z需5級運(yùn)算

舉例3算術(shù)表達(dá)式93舉例3（需）利用并行編譯算法1*AB4+EF2/CD5+343*126=5Z分配給2個處理機(jī)，需3級運(yùn)算舉例3（需）利用并行編譯算法94遞歸程序的并行性是研究并行算法的重要課題這里只討論線性遞歸遞歸程序的并行性是研究并行算法的重要課題95線性遞歸的例子線性遞歸的例子96線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）97線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）98線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）99列掃算法需用（n-1）個處理機(jī)計(jì)算2（n-1）步例如：如n=4，則需3個處理機(jī)，用6步列掃算法需用（n-1）個處理機(jī)計(jì)算2（n-1）步100乘積形式遞歸算法當(dāng)n=4時，右邊只有4種是不同，需用4個處理機(jī)經(jīng)2步算出，再用2個處理機(jī)經(jīng)3步算出比上一算法，少用1步，多用1個處理機(jī)N較大時，快速。乘積形式遞歸算法當(dāng)n=4時，右邊只有4種是不同，需用4個處理101程序舉例

DO4I=1,N1E(I)=3*F(I)+SIN(P(I))2B(I)+D(I-1)+Q(I)3D(I)=E(I)+B(I)4CONTINUE語句1提到循環(huán)前，2、3構(gòu)成循環(huán)1323FPDQBDE數(shù)據(jù)相關(guān)圖程序舉例DO4I=1,N1323FPDQBDE數(shù)102程序的并行性分析假定一個程序包含P1,P2,…,Pi,…Pj,…Pn等n個程序段，設(shè)Pi和Pj程序段都是一條語句，Pi在Pj之前執(zhí)行。數(shù)據(jù)相關(guān)數(shù)據(jù)反相關(guān)數(shù)據(jù)輸出相關(guān)程序的并行性分析假定一個程序包含P1,P2,…,Pi,…Pj103數(shù)據(jù)相關(guān)如果Pi的左部變量在Pj的右部變量集內(nèi)，且Pj必須取出Pi運(yùn)算的結(jié)果來作為操作數(shù)，稱Pj”數(shù)據(jù)相關(guān)”于Pi，例：Pi:A=B+DPj:C=A*E相當(dāng)于流水中的“先寫后讀”相關(guān)。順序執(zhí)行的正確結(jié)果是：PiA新=B原+D原

PjC新=A新*E原=(B原+D原)*E原數(shù)據(jù)相關(guān)如果Pi的左部變量在Pj的右部變量集內(nèi)，且Pj必須取104數(shù)據(jù)相關(guān)（續(xù)）Pi，Pj不能并行。特殊，當(dāng)Pi和Pj服從交換律時PiA=2*APjA=3*A雖不能并行，但能交換串行。得：6*A數(shù)據(jù)相關(guān)（續(xù)）Pi，Pj不能并行。105數(shù)據(jù)反相關(guān)如果Pj的左部變量在Pi的右部變量集內(nèi)，且當(dāng)Pi未取用其變量的值之前，是不允許被Pj所改變，稱Pi”數(shù)據(jù)反相關(guān)”于Pj，例：Pi:C=A+EPj:A=B+D相當(dāng)于流水中的“先讀后寫”相關(guān)。順序執(zhí)行的正確結(jié)果是：PiC新=A原+E原

PjA新=B原+

D原不能交換串行。數(shù)據(jù)反相關(guān)如果Pj的左部變量在Pi的右部變量集內(nèi)，且當(dāng)Pi未106數(shù)據(jù)輸出相關(guān)如果Pi的左部變量也是Pj的左部變量，且Pj存入其算得的值必須在P存入之后，則稱Pj”數(shù)據(jù)輸出相關(guān)”于Pi，例：Pi:A=B+DPj:A=C+E數(shù)據(jù)輸出相關(guān)如果Pi的左部變量也是Pj的左部變量，且Pj存入107總結(jié)兩個程序段之間如有先寫后讀的數(shù)據(jù)相關(guān)，不能并行，只在特殊情況下可以交換串行；如有先讀后寫的數(shù)據(jù)反相關(guān)，可以并行執(zhí)行，但必須保證其寫入共享主存時的先讀后寫次序，不能交換串行；如有寫-寫的數(shù)據(jù)輸出相關(guān)，可以并行執(zhí)行，但同樣需保證其寫入的先后次序，不能交換串行；如同時有先寫后讀和先讀后寫兩種相關(guān)，以交換數(shù)據(jù)為目的時，則必須讀寫完全同步，不許順序串行和交換串行；如沒有任何相關(guān)，或僅有源數(shù)據(jù)相同時，可以并行、順序串行和交換串行?？偨Y(jié)兩個程序段之間如有先寫后讀的數(shù)據(jù)相關(guān)，不能并行，只在特殊108并行語言和并行編譯是在普通順序型程序設(shè)計(jì)語言基礎(chǔ)上加以擴(kuò)充，增加能明確表示并行進(jìn)程的成分。并行程序設(shè)計(jì)語言要求能使程序員靈活方便地在其程序中表示出各類并行性，同時應(yīng)有高的效率，能在各種并行/向量計(jì)算機(jī)系統(tǒng)中有效地實(shí)現(xiàn)。并行進(jìn)程的特點(diǎn)：進(jìn)程在時間上重疊執(zhí)行。派生：FORK;匯合：JOIN在不同的機(jī)器上有不同的表現(xiàn)形式。并行語言和并行編譯是在普通順序型程序設(shè)計(jì)語言基礎(chǔ)上加以擴(kuò)充，109并行程序設(shè)計(jì)語言（續(xù)）M.E.Conway(康佳)形式：FORMm：派生出標(biāo)號為m開始的新進(jìn)程。如果是共享內(nèi)存，產(chǎn)生存儲器指針、映像函數(shù)和訪問權(quán)數(shù)據(jù)將空閑的處理機(jī)分配給被FORK語句派生的新進(jìn)程如果沒有可用的空閑處理機(jī)，排隊(duì)等待。并行程序設(shè)計(jì)語言（續(xù)）M.E.Conway(康佳)形式：110并行程序設(shè)計(jì)語言（續(xù)）JOINn：附有計(jì)數(shù)器，初值為0執(zhí)行語句時，計(jì)數(shù)器加1，與n比較如相等，表明執(zhí)行的第n格并發(fā)進(jìn)程經(jīng)過JOIN語句，允許通過語句，計(jì)數(shù)器清0，繼續(xù)執(zhí)行后續(xù)語句。如小于n，則進(jìn)程不是最后一個，先讓進(jìn)程結(jié)束，則把它占用的處理機(jī)釋放出來，分配給排隊(duì)的其他任務(wù)，如無任務(wù)，則空閑。并行程序設(shè)計(jì)語言（續(xù)）JOINn：111舉例1計(jì)算Z=E+A*B*C/D+F并行編譯：S1G=A*BS2H=C/DS3I=G*HS4J=E+F

S5Z=I+JS1S2S3S4S5ABCDEF舉例1計(jì)算S1S2S3S4S5ABCDEF112舉例1（續(xù)）

FORK2030FORK4010G=A*B(進(jìn)程S1)I+=G*H(進(jìn)程S3)JOIN2JOIN2GOTO30GOTO5020H=C/D(進(jìn)程S2)40J=E+F(進(jìn)程S4)JOIN2JOIN250Z=I+J(進(jìn)程S5)舉例1（續(xù)）FORK20113時間處理機(jī)S1S2S3S4S5FORK20FORK40JOIN2JOIN2JOIN2JOIN2GOTO50釋放釋放釋放時間處理機(jī)S1S2S3S4S5FORK20FORK40J114舉例2假定A，B兩個8*8矩陣相乘：

DO10J=0,6DO40K=0,710FORK2040C(I,J)=C(I,J)+A(I,K)*B(K,J)J=730CONTINUE20DO30I=0,7JOIN8C(I,J)=0舉例2假定A，B兩個8*8矩陣相乘：115處理機(jī)tJ=0J=1J=2J=3J=7J=4J=5J=6FORK7次JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8時間資源時間圖處理機(jī)tJ=0J=1J=2J=3J=7J=4J=5J=6FO116多處理機(jī)與并行處理機(jī)的區(qū)別并行處理機(jī)的每一條指令要求8個處理單元完全同步地對j=0,1,..7的不同數(shù)組進(jìn)行運(yùn)算。在多處理機(jī)中，不需要也不會完全同步。----操作級與任務(wù)級多處理機(jī)中可用處理機(jī)數(shù)目對程序編寫