本科系統(tǒng)結(jié)構(gòu)課件 chapter7-3

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

并行算法

程序并行性分析

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

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

舉例1E1=a+bx+cx2+dx3利用Horner法：E1=a+x(b+x(c+x(d)))

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

用樹形流程圖

+*+*+*axbxcdx舉例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說明降低樹高，增加并行性用交換律、結(jié)合律、分配律來變換先利用交換律把相同的運算集中起來，再用結(jié)合律把參加運算的操作數(shù)配對，盡可能并行運算，最后再把子樹結(jié)合起來。舉例2E2=a+b(c+def+g)+h需7級運算++*++*habgcdf*e舉例2（續(xù)）利用交換律和結(jié)合律E2=(a+h)+b((c+g)+def)需5級運算P=2Tp=5Sp=7/5Ep=Sp/p=0.7+++++++ahbcgdef舉例2（續(xù)）利用分配律降低樹高。E2=(a+h)+(bc+bg)+bdef需4級運算P=3Tp=4Sp=7/4Ep=7/12**+***+++acbgahbdef說明表達式運算并行性的識別，除依靠算法可以依靠編譯程序可以經(jīng)過或不經(jīng)過逆波蘭后綴表達式產(chǎn)生并行指令舉例3算術(shù)表達式

Z=E+A*B*C/D+F利用串行編譯算法，產(chǎn)生三元指令組

1*AB4+3E2*1C5+4F3/2D6=5Z需5級運算

舉例3（需）利用并行編譯算法

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

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)圖程序的并行性分析假定一個程序包含P1,P2,…,Pi,…Pj,…Pn等n個程序段，設(shè)Pi和Pj程序段都是一條語句，Pi在Pj之前執(zhí)行。數(shù)據(jù)相關(guān)數(shù)據(jù)反相關(guān)數(shù)據(jù)輸出相關(guān)數(shù)據(jù)相關(guān)如果Pi的左部變量在Pj的右部變量集內(nèi)，且Pj必須取出Pi運算的結(jié)果來作為操作數(shù)，稱Pj”數(shù)據(jù)相關(guān)”于Pi，例：

Pi:A=B+D

Pj:C=A*E相當于流水中的“先寫后讀”相關(guān)。順序執(zhí)行的正確結(jié)果是：

PiA新=B原+D原

PjC新=A新*E原=(B原+D原)*E原數(shù)據(jù)相關(guān)（續(xù)）Pi，Pj不能并行。特殊，當Pi和Pj服從交換律時

PiA=2*A

PjA=3*A雖不能并行，但能交換串行。得：6*A數(shù)據(jù)反相關(guān)如果Pj的左部變量在Pi的右部變量集內(nèi)，且當Pi未取用其變量的值之前，是不允許被Pj所改變，稱Pi”數(shù)據(jù)反相關(guān)”于Pj，例：

Pi:C=A+E

Pj:A=B+D相當于流水中的“先讀后寫”相關(guān)。順序執(zhí)行的正確結(jié)果是：

PiC新=A原+E原

PjA新=B原+

D原不能交換串行。數(shù)據(jù)輸出相關(guān)如果Pi的左部變量也是Pj的左部變量，且Pj存入其算得的值必須在P存入之后，則稱Pj”數(shù)據(jù)輸出相關(guān)”于Pi，例：

Pi:A=B+D

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

Z=E+A*B*C/D+F并行編譯：

S1G=A*BS2H=C/DS3I=G*HS4J=E+F

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

FORK2030FORK4010G=A*B(進程S1)I+=G*H(進程S3)JOIN2JOIN2GOTO30GOTO5020H=C/D(進程S2)40J=E+F(進程S4)JOIN2JOIN250Z=I+J(進程S5)時間處理機S1S2S3S4S5FORK20FORK40JOIN2JOIN2JOIN2JOIN2GOTO50釋放釋放釋放舉例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處理機tJ=0J=1J=2J=3J=7J=4J=5J=6FORK7次JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8JOIN8時間資源時間圖多處理機與并行處理機的區(qū)別并行處理機的每一條指令要求8個處理單元完全同步地對j=0,1,..7的不同數(shù)組進行運算。在多處理機中，不需要也不會完全同步。----操作級與任務級多處理機中可用處理機數(shù)目對程序編寫沒有影響。塊結(jié)構(gòu)語言E.W.Dijkstra提出把可并行執(zhí)行的進程用cobegin-coend括起來處理,最后一條語句執(zhí)行完成后，方可執(zhí)行后續(xù)語句。該語句可嵌套；可使用共享變量，但不允許修改。舉例1beginS0;CobeginS1;S2,…;Sn;coendSn+1;endS0S3S1SnSn+1舉例2BeginS0;

cobeginS1;beginS2;

cobeginS3;S4;S5;coendS6;endS7;

coendS8;endS0S2S4S3S5S1S7S6S8多處理機性能引起峰值性能下降的原因是：因處理機間通信而產(chǎn)生的延遲一臺處理機與其它處理機同步所需的開銷當沒有足夠多任務時，一臺或多臺處理機處于空閑狀態(tài)由于一臺或多臺處理機執(zhí)行無用的工作系統(tǒng)控制和操作調(diào)度所需開銷多處理機性能（續(xù)）研究多處理機的目的：提前5年得到速度高10倍的機器。或用1/10的價格獲得一臺高性能的機器。如果設(shè)計得好，在某些適合進行并行處理得應用領(lǐng)域，可以達到：提前10年得到速度高100倍的機器或用1/100的價格獲得一臺高性能的機器。并行性在很大程度上依賴于E/C比值，其中：E代表程序執(zhí)行時間C代表通信開銷。多處理機性能（續(xù)）通常：E/C比值小，并行性低。E/C比值大，并行性高如果把作業(yè)分解成較大的塊，就能得到較大的E/C值，但是所得到的并行性比最大可能的并行性要小得多。E/C比值是衡量任務粒度(Granularity)大小的尺度在粗粒度（Coarsegrain）并行情況下，E/C比值比較大，通信開銷小多處理機性能（續(xù)）在細粒度（Finegrain）并行情況下，E/C比值比較小，通信開銷大細粒度并行性需要的處理機多，粗粒度并行性需要的處理機少。細粒度并行性的基本原理是把一個程序盡可能地分解成能并行執(zhí)行的小任務。在極端情況下，一個小任務只完成一個操作?！?多處理機的操作系統(tǒng)

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

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

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

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

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

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

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

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

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

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

主從型(Master-slaveConfiguration)管理程序只在主處理機上運行。硬件結(jié)構(gòu)、管理、控制簡單，對主處理機要求高。用于工作負荷固定、從處理機能力明顯低的緊耦合、異構(gòu)型、非對稱多處理機系統(tǒng)。實現(xiàn)簡單，經(jīng)濟，方便多處理機操作系統(tǒng)的類型（續(xù)）各自獨立型（SeparateSup