多處理機的并行和性能課件

§3多處理機的并行和性能

并行算法

程序并行性分析

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

BSP(Bulk

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

劃分法(Partitioning)

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

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

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

串行算法的直接并行化

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

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

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

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

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

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

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

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

并行算法的一般設計過程劃分（Partitioning）：將14并行算法一般設計過程

并行算法一般設計過程15并行算法的性能分析

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

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

將大的程序分解成可由足夠的并行處理的過程（進程、任務、程序段）

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

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

用樹形流程圖

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

舉例3算術(shù)表達式28舉例3（需）利用并行編譯算法1*AB4+EF2/CD5+343*126=5Z分配給2個處理機，需3級運算舉例3（需）利用并行編譯算法29遞歸程序的并行性是研究并行算法的重要課題這里只討論線性遞歸遞歸程序的并行性是研究并行算法的重要課題30線性遞歸的例子線性遞歸的例子31線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）32線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）33線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）34列掃算法需用（n-1）個處理機計算2（n-1）步例如：如n=4，則需3個處理機，用6步列掃算法需用（n-1）個處理機計算2（n-1）步35乘積形式遞歸算法當n=4時，右邊只有4種是不同，需用4個處理機經(jīng)2步算出，再用2個處理機經(jīng)3步算出比上一算法，少用1步，多用1個處理機N較大時，快速。乘積形式遞歸算法當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ù)相關圖程序舉例DO4I=1,N1323FPDQBDE數(shù)37程序的并行性分析假定一個程序包含P1,P2,…,Pi,…Pj,…Pn等n個程序段，設Pi和Pj程序段都是一條語句，Pi在Pj之前執(zhí)行。數(shù)據(jù)相關數(shù)據(jù)反相關數(shù)據(jù)輸出相關程序的并行性分析假定一個程序包含P1,P2,…,Pi,…Pj38數(shù)據(jù)相關如果Pi的左部變量在Pj的右部變量集內(nèi)，且Pj必須取出Pi運算的結(jié)果來作為操作數(shù)，稱Pj”數(shù)據(jù)相關”于Pi，例：Pi:A=B+DPj:C=A*E相當于流水中的“先寫后讀”相關。順序執(zhí)行的正確結(jié)果是：PiA新=B原+D原

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

PjA新=B原+

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

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

FORK2030FORK4010G=A*B(進程S1)I+=G*H(進程S3)JOIN2JOIN2GOTO30GOTO5020H=C/D(進程S2)40J=E+F(進程S4)JOIN2JOIN250Z=I+J(進程S5)舉例1（續(xù)）FORK2048時間處理機S1S2S3S4S5FORK20FORK40JOIN2JOIN2JOIN2JOIN2GOTO50釋放釋放釋放時間處理機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處理機tJ=0J=1J=2J=3J=7J=4J=5J=6FORK7次JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8時間資源時間圖處理機tJ=0J=1J=2J=3J=7J=4J=5J=6FO51多處理機與并行處理機的區(qū)別并行處理機的每一條指令要求8個處理單元完全同步地對j=0,1,..7的不同數(shù)組進行運算。在多處理機中，不需要也不會完全同步。----操作級與任務級多處理機中可用處理機數(shù)目對程序編寫沒有影響。多處理機與并行處理機的區(qū)別并行處理機的每一條指令要求8個處理52塊結(jié)構(gòu)語言E.W.Dijkstra提出把可并行執(zhí)行的進程用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多處理機性能引起峰值性能下降的原因是：因處理機間通信而產(chǎn)生的延遲一臺處理機與其它處理機同步所需的開銷當沒有足夠多任務時，一臺或多臺處理機處于空閑狀態(tài)由于一臺或多臺處理機執(zhí)行無用的工作系統(tǒng)控制和操作調(diào)度所需開銷多處理機性能引起峰值性能下降的原因是：56多處理機性能（續(xù)）研究多處理機的目的：提前5年得到速度高10倍的機器?；蛴?/10的價格獲得一臺高性能的機器。如果設計得好，在某些適合進行并行處理得應用領域，可以達到：提前10年得到速度高100倍的機器或用1/100的價格獲得一臺高性能的機器。并行性在很大程度上依賴于E/C比值，其中：E代表程序執(zhí)行時間C代表通信開銷。多處理機性能（續(xù)）研究多處理機的目的：57多處理機性能（續(xù)）通常：E/C比值小，并行性低。E/C比值大，并行性高如果把作業(yè)分解成較大的塊，就能得到較大的E/C值，但是所得到的并行性比最大可能的并行性要小得多。E/C比值是衡量任務粒度(Granularity)大小的尺度在粗粒度（Coarsegrain）并行情況下，E/C比值比較大，通信開銷小多處理機性能（續(xù)）通常：E/C比值小，并行性低。E/C比值大58多處理機性能（續(xù)）在細粒度（Finegrain）并行情況下，E/C比值比較小，通信開銷大細粒度并行性需要的處理機多，粗粒度并行性需要的處理機少。細粒度并行性的基本原理是把一個程序盡可能地分解成能并行執(zhí)行的小任務。在極端情況下，一個小任務只完成一個操作。多處理機性能（續(xù)）在細粒度（Finegrain）并行情況下，59§4多處理機的操作系統(tǒng)

多處理機操作系統(tǒng)的難度與特點

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

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

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

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

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

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

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

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

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

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

并行算法

程序并行性分析

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

BSP(Bulk

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

劃分法(Partitioning)

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

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

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

串行算法的直接并行化

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

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

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

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

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

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

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

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

并行算法的一般設計過程劃分（Partitioning）：將79并行算法一般設計過程

并行算法一般設計過程80并行算法的性能分析

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

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

將大的程序分解成可由足夠的并行處理的過程（進程、任務、程序段）

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

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

用樹形流程圖

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

舉例3算術(shù)表達式93舉例3（需）利用并行編譯算法1*AB4+EF2/CD5+343*126=5Z分配給2個處理機，需3級運算舉例3（需）利用并行編譯算法94遞歸程序的并行性是研究并行算法的重要課題這里只討論線性遞歸遞歸程序的并行性是研究并行算法的重要課題95線性遞歸的例子線性遞歸的例子96線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）97線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）98線性遞歸的例子（續(xù)）線性遞歸的例子（續(xù)）99列掃算法需用（n-1）個處理機計算2（n-1）步例如：如n=4，則需3個處理機，用6步列掃算法需用（n-1）個處理機計算2（n-1）步100乘積形式遞歸算法當n=4時，右邊只有4種是不同，需用4個處理機經(jīng)2步算出，再用2個處理機經(jīng)3步算出比上一算法，少用1步，多用1個處理機N較大時，快速。乘積形式遞歸算法當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ù)相關圖程序舉例DO4I=1,N1323FPDQBDE數(shù)102程序的并行性分析假定一個程序包含P1,P2,…,Pi,…Pj,…Pn等n個程序段，設Pi和Pj程序段都是一條語句，Pi在Pj之前執(zhí)行。數(shù)據(jù)相關數(shù)據(jù)反相關數(shù)據(jù)輸出相關程序的并行性分析假定一個程序包含P1,P2,…,Pi,…Pj103數(shù)據(jù)相關如果Pi的左部變量在Pj的右部變量集內(nèi)，且Pj必須取出Pi運算的結(jié)果來作為操作數(shù)，稱Pj”數(shù)據(jù)相關”于Pi，例：Pi:A=B+DPj:C=A*E相當于流水中的“先寫后讀”相關。順序執(zhí)行的正確結(jié)果是：PiA新=B原+D原

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

PjA新=B原+

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

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

FORK2030FORK4010G=A*B(進程S1)I+=G*H(進程S3)JOIN2JOIN2GOTO30GOTO5020H=C/D(進程S2)40J=E+F(進程S4)JOIN2JOIN250Z=I+J(進程S5)舉例1（續(xù)）FORK20113時間處理機S1S2S3S4S5FORK20FORK40JOIN2JOIN2JOIN2JOIN2GOTO50釋放釋放釋放時間處理機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處理機tJ=0J=1J=2J=3J=7J=4J=5J=6FORK7次JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8時間資源時間圖處理機tJ=0J=1J=2J=3J=7J=4J=5J=6FO116多處理機與并行處理機的區(qū)別并行處理機的每一條指令要求8個處理單元完全同步地對j=0,1,..7的不同數(shù)組進行運算。在多處理機中，不需要也不會完全同步。----操作級與任務級多處理機中可用處理機數(shù)目對程序編寫