并行算法的設(shè)計基礎(chǔ)課件

第四章并行算法的設(shè)計基礎(chǔ)并行計算相關(guān)的研究分支1.并行計算機(jī)體系結(jié)構(gòu)2.并行計算的性能評價3.并行算法4.并行程序設(shè)計一、并行算法相關(guān)的基本概念及表示二、介紹幾種并行計算模型3.并行算法1.并行計算機(jī)體系結(jié)構(gòu)2.并行計算的性能評價11/30/20221第四章并行算法的設(shè)計基礎(chǔ)并行計算相關(guān)的研究分支一、并行算一、并行算法相關(guān)的基本概念及表示基本概念并行算法的表示并行算法的復(fù)雜性度量并行算法的同步與通信11/30/20222一、并行算法相關(guān)的基本概念及表示基本概念11/30/20221.基本概念定義1：算法：在有限步驟內(nèi)求解某一特定問題的一組無二義性的規(guī)則。定義2：并行算法是由一些獨(dú)立的、可以并行運(yùn)行的計算模塊（進(jìn)程）構(gòu)成，模塊（進(jìn)程）之間能相互作用和協(xié)調(diào)，以完成對一個給定問題的求解。11/30/202231.基本概念定義1：算法：在有限步驟內(nèi)求解某一特定問題的一根據(jù)算法的不同特征，可以對并行算法進(jìn)行不同的分類：SIMD算法和MIMD算法同步算法和異步算法數(shù)值計算算法和非數(shù)值計算算法共享存儲算法和分布存儲算法11/30/20224根據(jù)算法的不同特征，可以對并行算法進(jìn)行不同的分類：11/30定義3：同步算法(synchronizedalgorithm):是指算法的諸進(jìn)程的執(zhí)行必須相互等待的一類并行算法。SIMD算法是同步算法中的一種特例。定義4：異步算法(asynchronousalgorithm):是指算法的諸進(jìn)程的執(zhí)行不必相互等待的一類并行算法。定義5：分布并行算法(distributedalgorithm)：將同一任務(wù)分解為若干個子任務(wù)，使之分布在由通信鏈路連接的多個節(jié)點上協(xié)同完成運(yùn)算的算法。分布式算法的執(zhí)行時間，在很大程度上受通信開銷的影響。11/30/20225定義3：同步算法(synchronizedalgorith定義6：確定算法(deterministicalgorithm)：每個運(yùn)算步驟上均確定唯一操作的算法。如線性方程組求解的算法。

不確定算法(non-deterministicalgorithm)：在問題求解的搜索過程中，提出多種可供選擇的操作，它們中的任一種都有希望獲得問題的解答，但都不能肯定解出，有時甚至不能確定這些操作中哪一種求解的可能性更大些。對此，只能選擇其中任意一種搜索下去。這種搜索方法稱為不確定算法。11/30/20226定義6：確定算法(deterministicalgori定義7：隨機(jī)算法(randomizedalgorithm,probabilisticalgorithm)計算步驟具有隨機(jī)性的算法。在算法的某一步或某些步上，可以在指定范圍內(nèi)隨機(jī)地選擇下一個演算步的走向。如果方法得當(dāng)，可比一般算法更快地得出結(jié)果，并且能以較高的概率提供正確的結(jié)果。11/30/20227定義7：隨機(jī)算法(randomizedalgorithm表示算法的要求無二義性力圖直觀、易懂不苛求嚴(yán)格的語法格式一般的串行算法常用類Pascal、類Algol表示2.并行算法的表示11/30/20228表示算法的要求2.并行算法的表示11/30/202281.par-do語句fori=1tonpar-do::endfor表示其間的n(i=1ton)次語句序列的執(zhí)行可以并行完成表示k個處理器同時執(zhí)行其間的語句序列2.forall語句forallPiwhere0i

k-1do::endfor并行算法常引入以下兩條并行語句：11/30/202291.par-do語句表示其間的n(i=1ton)3.并行算法的復(fù)雜性度量令f(n)和g(n)是定義在自然數(shù)集合N上的兩個函數(shù)，定義8：如果存在兩個正數(shù)c和n0，使得對于所有的nn0均有f(n)

cg(n)，則標(biāo)記為：

f(n)=(g(n))

我們稱g(n)為f(n)的上界。定義9：如果存在兩個正數(shù)c和n0，使得對于所有的nn0均有f(n)cg(n)，則標(biāo)記為：

f(n)=(g(n))我們稱g(n)為f(n)的下界。11/30/2022103.并行算法的復(fù)雜性度量令f(n)和g(n)是定義定義10：如果存在正數(shù)c1、c2

和n0，使得對于所有的nn0均有c1g(n)f(n)

c2g(n)，則標(biāo)記為

f(n)=(g(n))我們稱g(n)為f(n)的緊致界。即：如果f(n)=(g(n))且f(n)=(g(n))

則f(n)=(g(n))11/30/202211定義10：如果存在正數(shù)c1、c2和n0，使得對于所有

比較兩個算法的時間復(fù)雜性函數(shù)g(n)和f(n)的階的方法：用定義判斷用求極限的方法來加以判斷。若

則（1）當(dāng)c≠0時，說明f(n)和g(n)同階，記為f(n)=Θ(g(n))（2）當(dāng)c=0時，說明f(n)比g(n)低階，記為f(n)=O(g(n))（3）當(dāng)c=∞時，說明f(n)比g(n)高階，記為f(n)=Ω(g(n))11/30/20221211/30/202212并行算法的運(yùn)行時間t(n)：對于輸入規(guī)模為n的問題，在給定的并行計算模型之下求解問題所需的時間，也稱為時間復(fù)雜性(timecomplexity)。運(yùn)行時間=計算時間+通信時間處理器數(shù)p(n)：表示對給定的問題規(guī)模n，并行算法所用的處理器的個數(shù)。并行算法的成本c(n)：并行算法的運(yùn)行時間t(n)與所需的處理器數(shù)p(n)之積，即c(n)=t(n)*p(n)11/30/202213并行算法的運(yùn)行時間t(n)：對于輸入規(guī)模為n的問題，例:(1)設(shè)f(n)=n2/2,g(n)=307n2，則因此，f(n)=n2/2與g(n)=307n2是同階的。

(2)設(shè)f(n)=lgn，g(n)=n，則所以，f(n)=lgn比g(n)=n低階。11/30/202214例:(1)設(shè)f(n)=n2/2,g(n)=307n2，則1定義11：一個并行算法最壞情況下的時間復(fù)雜性(worst-casetime-complexity)：對于所有輸入規(guī)模為n的問題，在給定的并行計算模型之下求解問題所需的時間的最大值。定義12：一個并行算法的期望時間復(fù)雜性(expectedtime-complexity)：對于所有輸入規(guī)模為n的問題，在給定的計算模型之下求解問題所需的時間的平均值。11/30/202215定義11：一個并行算法最壞情況下的時間復(fù)雜性(worst-定義13：一個并行算法最壞情況下的空間復(fù)雜性(worst-casespace-complexity)：對于所有輸入規(guī)模為n的問題，在給定的并行計算模型之下求解問題所需的內(nèi)存空間的最大值。定義14：一個并行算法的期望空間復(fù)雜性(expectedspace-complexity)：對于所有輸入規(guī)模為n的問題，在給定的計算模型之下求解問題所需的內(nèi)存空間的平均值。11/30/202216定義13：一個并行算法最壞情況下的空間復(fù)雜性(worst-c定義15：如果一個并行算法的成本與其對應(yīng)的最佳串行算法的最壞情況下時間復(fù)雜性在同一個數(shù)量級上，則稱該并行算法為成本最佳的(cost-optimal)或最佳并行算法(optimalparallelalgorithm)?？傔\(yùn)算量W(n):(并行)算法中所要完成的總的操作數(shù)量(thenumberofcomputationaloperations)11/30/202217定義15：如果一個并行算法的成本與其對應(yīng)的最佳串行算法的最壞4.并行算法中的同步與通信同步(synchronization)：使多個相關(guān)事件的發(fā)生保持相同的節(jié)奏，彼此之間能良好地配合。在并行算法的各進(jìn)程異步執(zhí)行過程中，為了確保各處理器的正確工作順序和對共享存儲器的訪問，程序員需要在算法的適當(dāng)位置設(shè)置同步點。下面給出一個利用lock和unlock構(gòu)造的臨界區(qū)完成數(shù)組求和的算法11/30/2022184.并行算法中的同步與通信同步(synchronizatibeginS=0forallPiwhere0ip-1doL=0forj=iton-1steppdoL=L

+ajendforlock(u)S=S+Lunlock(u)endforend[算法4.1.3]共享存儲多處理機(jī)上求和算法輸入：A=(a0,a1,…,an-1),處理器數(shù)p；輸出：a0+a1+…+an-1存放在全局變量S

中。11/30/202219begin[算法4.1.3]共享存儲多處理機(jī)上求和算法通信(communication)：把信息用一定手段通過某種介質(zhì)或傳輸線路從一個點傳送至另一點的過程。通信是在空間上對并發(fā)執(zhí)行的進(jìn)程實現(xiàn)數(shù)據(jù)交換。原語(primitive)：它由若干條機(jī)器指令構(gòu)成的，用來完成特定功能的一段程序。原語有以下特點：不可中斷性：一旦原語被開始執(zhí)行，就應(yīng)不間斷地執(zhí)行到結(jié)束；不可侵犯性：原語一旦被執(zhí)行，中間不許插入任何其他操作。11/30/202220通信(communication)：把信息用一定手段通過某種通信可使用通信原語來表示：1.在共享存儲的多處理機(jī)中，可使用1)globalread(X,Y)將全局存儲器中數(shù)據(jù)X讀入局部變量Y；2)globalwrite(U,V)將局部數(shù)據(jù)U寫入共享存儲變量V中。2.在分布存儲的多計算機(jī)中，可使用1)send(X,i)或send(X,Pi)當(dāng)前處理器發(fā)送數(shù)據(jù)X到Pi；2)receive(Y,j)或receive(Y,Pj)當(dāng)前處理器從Pj接收數(shù)據(jù)Y。11/30/202221通信可使用通信原語來表示：11/30/202221[算法4.1.4]分布存儲多計算機(jī)上矩陣向量相乘算法給定:一個n*n的矩陣A和一個向量X

a11a12a13……a1n-1a1na21a22a23……a2n-1a2n

A=a31a32a33……a3n-1a3n……..an1an2an3……ann-1annx1x2X=x3…xn計算:A*X，得到一個向量。假設(shè)r=n/p為一整數(shù)因為我們打算在分布存儲的多計算機(jī)系統(tǒng)上運(yùn)行該算法，被計算的數(shù)據(jù)只能分布在各個處理器的局部存儲器上。11/30/202222[算法4.1.4]分布存儲多計算機(jī)上矩陣向量相乘算法我們把A按列分為p個n*r的小矩陣A1,A2,…,Ap

把X按行分為p個r*1的小向量X1,X2,…,Xp計算A*X就轉(zhuǎn)化為計算：A1X1+A2X2+…ApXp所以處理器Pi（其中1ip）將Ai和Xi存放在自己的局部存儲器中，各處理器首先計算AiXi，然后利用通信實現(xiàn)數(shù)據(jù)求和。X1(r*1)X2(r*1)…Xp(r*1)A=A1A2

…ApX=

(n*r)(n*r)(n*r)11/30/202223我們把A按列分為p個n*r的小矩陣A1,A2我們假設(shè)處理器是以環(huán)結(jié)構(gòu)組織的PiP2PpP111/30/202224我們假設(shè)處理器是以環(huán)結(jié)構(gòu)組織的PiP2PpP111/30/2[算法4.1.4]分布存儲多計算機(jī)上矩陣向量相乘算法輸入：處理器數(shù)p，第i個A矩陣分量Ai于B中，第i個X向量分量Xi于w中;輸出：A*X于P1變量y中。begincomputez=Bwifi=1theny=0elsereceive(y,left)endify=y+zsend(y,right)ifi=1thenreceive(y,left)end11/30/202225[算法4.1.4]分布存儲多計算機(jī)上矩陣向量相乘算法11/p1p3p2p4計算z=Bw計算z=Bw計算z=Bw計算z=Bwy=0rec(y,p1)rec(y,p2)rec(y,p3)y=y+zsend(y,p2)send(y,p3)send(y,p4)rec(y,p4)send(y,p1)y=y+zy(1)y=y+zy(2)y=y+zy(3)y(4)結(jié)束11/30/202226p1p3p2p4計算z=Bw計算z=Bw計算z=Bw計算z=第四章并行算法的設(shè)計基礎(chǔ)一、并行算法相關(guān)的基本概念及表示二、介紹幾種并行計算模型二、介紹幾種并行計算模型11/30/202227第四章并行算法的設(shè)計基礎(chǔ)一、并行算法相關(guān)的基本概念及表示二、并行計算模型并行計算模型：從并行算法的設(shè)計和分析出發(fā)，將各種并行計算機(jī)（至少是某一類并行計算機(jī)）的基本特征抽象出來，形成一個抽象的計算模型。并行計算模型為并行計算提供了硬件和軟件的界面，使硬件設(shè)計者和軟件設(shè)計者可以開發(fā)并行性的支持機(jī)制，從而提高系統(tǒng)的性能。對并行算法的研制者，不會局限于某種具體的并行計算機(jī)來研究并行算法，而需借助于抽象的計算模型，它是設(shè)計和分析并行算法的基礎(chǔ)。11/30/202228二、并行計算模型并行計算模型：從并行算法的設(shè)計和分析出發(fā)，將為了能對計算機(jī)系統(tǒng)進(jìn)行簡單、明確的描述，發(fā)現(xiàn)一般規(guī)律，通常在不同層次上進(jìn)行抽象來定義模型。不同層次模型的關(guān)系圖：編程模型計算模型體系結(jié)構(gòu)模型機(jī)器模型用戶系統(tǒng)硬件和操作系統(tǒng)互連網(wǎng)絡(luò)的作用和執(zhí)行通信的形式等計算機(jī)的費(fèi)用和資源編程語言的語義11/30/202229為了能對計算機(jī)系統(tǒng)進(jìn)行簡單、明確的描述，發(fā)現(xiàn)一般規(guī)律，通常在并行計算模型的主要作用：它是并行算法實現(xiàn)的基礎(chǔ)對同一問題在不同的模型上的不同解決辦法，來比較該問題究竟更合理在哪一種模型上實現(xiàn)它給并行算法設(shè)計和分析提供了一個簡單、方便的框架撇開了硬件的繁雜的細(xì)節(jié)它使并行算法設(shè)計具有一定的生命力集中精力開發(fā)應(yīng)用問題自身的并行性和算法的性能，并使算法具有一定的通用性11/30/202230并行計算模型的主要作用：11/30/202230串行算法的研究已經(jīng)相當(dāng)成熟，它們基本上都是基于馮.諾依曼(vonNeumann)體系結(jié)構(gòu)控制器運(yùn)算器主存儲器輸出設(shè)備輸入設(shè)備CPU高速緩存11/30/202231串行算法的研究已經(jīng)相當(dāng)成熟，它們基本上都是基于馮.諾依曼(v程序指令計數(shù)器r0r1r2r3:存儲器累加器xn……x2x1只讀輸入磁帶……y2y1只寫輸出磁帶串行計算模型RAM(RandomAccessMachine)11/30/202232指令r0存儲器累加器xn……x2x1只讀輸入磁帶……y2y1RAM機(jī)器模型的指令系統(tǒng)與實際計算機(jī)的指令系統(tǒng)類似，有四類指令：1.控制流向指令，如jump;2.輸入/輸出指令，如read,write；3.累加器與存儲器之間的傳送數(shù)據(jù)指令，如load；4.算術(shù)運(yùn)算指令，如add。11/30/202233RAM機(jī)器模型的指令系統(tǒng)與實際計算機(jī)的指令系統(tǒng)類似，有四類指PRAM模型

(ParallelRandomAccessMachineModel)1978年S.Fortune和J.Wyllie總結(jié)了陣列式結(jié)構(gòu)的并行機(jī)和流水線結(jié)構(gòu)的向量機(jī)的特點，將其抽象為具有如下特征的PRAM模型：1）有一個控制器2）有p（可有限或無限）臺功能相同的處理器3）有一個容量無限的共享存儲器4）每臺處理器有自己的局部存儲器5）處于激活狀態(tài)的處理器必須執(zhí)行相同的指令6）允許任何時刻各處理器均可通過共享存儲器與其它處理器交換數(shù)據(jù)。11/30/202234PRAM模型

(ParallelRandomAccesPRAM模型----SIMD計算模型控制器互聯(lián)網(wǎng)絡(luò)全局共享存儲器P1LM1P2LM2PpLMp……11/30/202235PRAM模型----SIMD計算模型控制器互聯(lián)PRAM模型允許任何時刻各處理器均可通過共享存儲器的共享單元與其它處理器交換數(shù)據(jù)。根據(jù)處理器對共享單元的存、取訪問的不同約束條件進(jìn)一步對PRAM模型分類：PRAM-EREW(ExclusiveRead,ExclusiveWrite)：不允許有讀沖突和寫沖突PRAM-CREW(ConcurrentRead,ExclusiveWrite)：每次允許多臺處理器同時讀同一共享單元內(nèi)容，但不允許同時寫。PRAM-CRCW(ConcurrentRead,ConcurrentWrite)：允許多臺處理器同時讀、寫同一共享單元內(nèi)容。11/30/202236PRAM模型允許任何時刻各處理器均可通過共享存儲器的共享單PRAM-CRCW模型中允許同時寫同一共享單元顯然是不現(xiàn)實的，所以對PRAM-CRCW模型作了更進(jìn)一步的約定：共用的

(Common)PRAM-CRCW：同時寫同一共享單元的所有處理器必須寫相同的值；優(yōu)先的

(Priority)PRAM-CRCW：從同時要寫同一共享單元的所有處理器中找出標(biāo)號最小的處理器，將它的值寫入共享地址中；任意的

(Arbitrary)PRAM-CRCW：從同時要寫同一共享單元的所有處理器中任選一個處理器的值寫入共享地址中。11/30/202237PRAM-CRCW模型中允許同時寫同一共享單元顯然是不現(xiàn)實PRAM模型上的算法的執(zhí)行：1）輸入數(shù)據(jù)存放在全局共享存儲器中，并只有一個處理器處于激活狀態(tài)；2）在每個計算步中，一個激活的處理器可做：從局部或全局存儲器中讀一個值完成一個RAM操作寫值到局部或全局存儲器中激活另一個處理器11/30/202238PRAM模型上的算法的執(zhí)行：11/30/202238[算法4.2.1]在PRAM-EREW模型上求和算法輸入：n個待求和的數(shù)A[0..(n-1)]輸出：最終的n個數(shù)的和在A[0]中全局變量：n,A[0..(n-1)],jbegin*spawn(P0,P1,…,Pn/2-1)forallPiwhere0in/2-1doforj=0tologn-1doifimod2j=0and2i+2j<nthenA[2i]=A[2i]+A[2i+2j]endifendforendforend11/30/202239[算法4.2.1]在PRAM-EREW模型上求和算法spawn()：激活n個處理機(jī)例：n=12spawn()：激活n個處理機(jī)的時間為logn。時間11/30/202240spawn()：激活n個處理機(jī)例：n=12spa2.APRAM模型(AsynchronousPRAM)80年代初，人們總結(jié)了共享存儲型多處理機(jī)結(jié)構(gòu)的向量機(jī)的特點，將其抽象為具有如下特征的APRAM模型：1）有p（可有限或無限）個處理器；2）每個處理器有自己的控制器（局部時鐘）；3）有一個容量無限的共享存儲器；4）每臺處理器有自己的局部存儲器和局部程序；5）各處理器異步地、獨(dú)立地執(zhí)行各自的指令，處理器間的同步需明確地在各處理器的程序中加入障礙（路障）同步(barriersynchronization)指令；6）利用共享存儲器實現(xiàn)處理器間的通信。11/30/2022412.APRAM模型(AsynchronousPRAAPRAM模型----MIMD計算模型控制器1互聯(lián)網(wǎng)絡(luò)全局共享存儲器P1LM1P2LM2PpLMp……控制器2控制器p……11/30/202242APRAM模型----MIMD計算模型控制器1互聯(lián)PRAM模型----SIMD計算模型（對比）控制器互聯(lián)網(wǎng)絡(luò)全局共享存儲器P1LM1P2LM2PpLMp……11/30/202243PRAM模型----SIMD計算模型（對比）控制器互APRAM模型同樣利用共享存儲器實現(xiàn)處理器間的通信障礙(路障)同步

(barriersynchronization)：它在程序中設(shè)置一些障礙點，當(dāng)處理器執(zhí)行到障礙點時暫停，等待所有進(jìn)程都執(zhí)行到這個障礙點上，以此方法取得同步。11/30/202244APRAM模型同樣利用共享存儲器實現(xiàn)處理器間的通信11/3APRAM模型中的計算:計算是由一系列用同步障礙點分開的全局相（globalphase）組成的。在各全局相內(nèi)每個處理器異步地運(yùn)行其局部程序每個局部程序中的最后一條指令是一條障礙同步指令各處理器均可異步地讀取和寫入全局存儲器，但在同一相（phase）內(nèi)不允許兩個處理器訪問同一共享單元11/30/202245APRAM模型中的計算:11/30/202245處理器1處理器2處理器3

Phase1同步障礙readx1readx3readxnreadx2:::writetoB:writetoAwritetoCwritetoDreadBreadAreadC:::writetoBwritetoD:writetoCwritetoBreadD:readA::writetoBPhase2同步障礙Phase3同步障礙11/30/202246處理器1處理器2處理器3在APRAM模型上設(shè)計的算法的時間復(fù)雜性包括以下幾個方面：假設(shè)一個局部操作取為1個單位時間全局讀/寫時間為d，它表示全局讀/寫的平均時間。該值應(yīng)隨著處理器的個數(shù)增加而增加。同步障礙的時間為B，B是處理器個數(shù)p的非遞減函數(shù)B(p)。在APRAM中常假設(shè)：2dBp設(shè)tph為全局相內(nèi)各處理器指令執(zhí)行時間中最長者，則整個程序運(yùn)行時間T應(yīng)為：T=tph+B*同步障礙次數(shù)11/30/202247在APRAM模型上設(shè)計的算法的時間復(fù)雜性包括以下幾個方面：13.LogP模型

(Latency,overhead,gap,Processor)1993年D.Culler等人在分析了分布式存儲計算機(jī)特點的基礎(chǔ)上，提出了基于點到點通信的多計算機(jī)模型----LogP模型。該模型雖未涉及到網(wǎng)絡(luò)的具體結(jié)構(gòu)，但充分說明了互聯(lián)網(wǎng)絡(luò)的性能特性：互連網(wǎng)絡(luò)帶寬的限制通信中可觀的延遲它是MPP系統(tǒng)的模型11/30/2022483.LogP模型

(Latency,overLogP模型主要由以下4個參數(shù)來描述：1）L(Latency)最大延遲：在通信時包含一個或幾個字的一個消息從源節(jié)點傳到目標(biāo)節(jié)點的時間的上限值。2）o(overhead)開銷：處理器準(zhǔn)備發(fā)送或接收一個消息的時間開銷，在這段時間里處理器不能執(zhí)行其它操作。3）g(gap)間隔：一臺處理器發(fā)送或接收一組消息時，兩個消息之間的最小時間間隔，其倒數(shù)即為處理器的通信帶寬。4）P(Processor)節(jié)點數(shù)：處理器/存儲器個數(shù)，假定每個局部操作需要1個單位時間（即一個處理器周期）。11/30/202249LogP模型主要由以下4個參數(shù)來描述：11/30/202LogP的參數(shù)示意圖PiPkPj處理器ogLo消息下一個消息時間發(fā)送并接收一個消息共需2o+L個單位時間;處理器Pi在向處理器Pj發(fā)送消息后,在發(fā)送下一個消息之前必須等待g個時間單位。11/30/202250LogP的參數(shù)示意圖PiPkPj處理器oLogP模型的特點處理機(jī)之間異步地工作，通過消息傳遞實現(xiàn)同步；消息延遲不確定，但延遲不會大于L，即任何消息經(jīng)歷的等待時間是不可預(yù)測的，但不會超過L；LogP模型支持了計算和通信的重疊；能夠預(yù)測算法的實際運(yùn)行時間。LogP模型抓住了網(wǎng)絡(luò)與處理機(jī)之間的性能瓶頸。消息間隔參數(shù)g反映了通信帶寬，當(dāng)一臺處理機(jī)發(fā)送的消息已到達(dá)這個容量限度時，再發(fā)送的消息將被阻塞。11/30/202251LogP模型的特點11/30/202251例2：在通信模式是一棵樹的情況下求和算法假設(shè)P=8、L=5、g=4、o=2，我們考慮在時間為28個單位時間內(nèi)最多可能求和的個數(shù)。P0P4P6P7P2P3P5P111/30/202252例2：在通信模式是一棵樹的情況下求和算法假設(shè)P=84.BSP模型(BulkSynchronousParallel)BSP模型是一個分布存儲的MIMD計算模型BSP模型的組成主要包括如下部分：1）若干個能進(jìn)行處理和內(nèi)存操作的處理器，2）一個用于在處理器之間傳遞消息的路由器，3）在定義的時間間隔內(nèi)，對所有處理器進(jìn)行同步的機(jī)制。一般情況下，假設(shè)這個全局同步機(jī)制是用特殊的硬件支持的。一個BSP程序是由一系列超步(superstep)組成的。11/30/2022534.BSP模型(BulkSynchronousPaBSP模型有以下三個重要參數(shù)：1）處理器數(shù)p2）路由器吞吐量g，（也稱為帶寬因子）3）全局同步之間的時間間隔L在一個超步中，一個處理機(jī)最多發(fā)送h個消息或接收h個消息。若有h個消息，則稱此通信有一個h關(guān)系(h-relation)。g值的定義方式：每秒處理機(jī)所能完成的局部計算數(shù)與每秒路由器所能傳輸?shù)臄?shù)據(jù)量之比；或在一個h關(guān)系中,傳遞h個消息所需的時間為g.h。11/30/202254BSP模型有以下三個重要參數(shù)：11/30/202254BSP模型與APRAM模型類似，使用障礙同步使整個計算任務(wù)以緊同步方式進(jìn)行各處理器局部計算全局通信障礙同步一個超步的執(zhí)行時間：計算時間max+ghmax+l11/30/202255BSP模型與APRAM模型類似，使用障礙同步使整個計算BSP模型的主要特點：將處理器和路由器分開，即把計算任務(wù)和通信任務(wù)分開。路由器僅進(jìn)行點到點的消息傳遞，不考慮互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)；利用硬件實現(xiàn)全局障礙同步使并行粒度增大(相對APRAM而言)，并能夠?qū)崿F(xiàn)緊耦合同步并行算法；兼顧了計算和通信的平衡問題；硬件可將L設(shè)置盡量小----這表示通信帶寬會更寬些，在設(shè)計并行算法時應(yīng)使L盡量大從而提高并行粒度。11/30/202256BSP模型的主要特點：11/30/2022565.C3模型(Computing,Communication,Congestion)1994年S.E.Hambrush等人在分析高性能可擴(kuò)展的網(wǎng)絡(luò)計算機(jī)系統(tǒng)特點的基礎(chǔ)上提出了C3模型，它適用于粗粒度的并行系統(tǒng)。和BPS與LogP模型相似，C3計算模型也將計算劃分為一系列超級步，同步出現(xiàn)在兩個超級步之間，這個同步也是利用障礙同步機(jī)制來實現(xiàn)。擁塞(Congestion)：在通信網(wǎng)絡(luò)中，當(dāng)各輸入站的呼叫數(shù)量超過網(wǎng)絡(luò)的容量，或超過了網(wǎng)絡(luò)處理的能力時，則稱網(wǎng)絡(luò)中發(fā)生了擁塞。11/30/2022575.C3模型(Computing,CommunicatC3模型主要由以下幾個參數(shù)來描述：1）處理器的個數(shù)p；2）網(wǎng)絡(luò)延遲h：網(wǎng)絡(luò)中任意兩節(jié)點間的距離的平均值；3）網(wǎng)絡(luò)的對分寬度b：表示網(wǎng)絡(luò)的帶寬；4）啟動時間s，即建立一個消息時的開銷；5）消息包的長度l，即消息包所含字節(jié)數(shù)。消息包是處理機(jī)間通信的基本單位。11/30/202258C3模型主要由以下幾個參數(shù)來描述：11/30/202258C3模型中用到的一些概念C3模型中考慮了兩種路由方式：存儲轉(zhuǎn)發(fā)路由方式(store-and-forwardmode)：它是網(wǎng)絡(luò)中信息交換的一種方式。轉(zhuǎn)發(fā)中心不是將終端發(fā)出的信息立即傳送到接收終端，而是先存儲起來，等待適當(dāng)?shù)臅r機(jī)，選擇空閑的信道，并按信息的優(yōu)先級別轉(zhuǎn)發(fā)到下一個轉(zhuǎn)發(fā)中心或接收終端。蟲孔(蟲蝕)路由方式(wormholeroutingmode)：在平面網(wǎng)絡(luò)結(jié)構(gòu)的多處理機(jī)系統(tǒng)中進(jìn)行路徑選擇的一種方法。它把消息分成若干個包，包又分成若干個稱為遷移塊(flit)的基本信息單元。每個包中的遷移塊以流水線方式向前依次傳送。只有包的頭幾個遷移塊含有路徑信息，因而一個包的所有遷移塊必須一個跟著一個，而不能被別的消息包打斷。11/30/202259C3模型中用到的一些概念C3模型中考慮了兩種路由方式：11C3模型中用到的一些概念C3模型中考慮了兩種發(fā)送/接收原語：1）阻塞發(fā)送和接收原語2）非阻塞發(fā)送和接收原語阻塞發(fā)送(blockingsend)：指一個源處理器從開始發(fā)送一條消息，直到它被目標(biāo)處理器收到消息，源處理器的發(fā)送操作才結(jié)束。非阻塞的發(fā)送(non-blockingsend)：源處理器只需將要發(fā)送的消息放在發(fā)送緩沖器。非阻塞的發(fā)送不需考慮目標(biāo)處理器什么時候接收到信息。11/30/202260C3模型中用到的一些概念C3模型中考慮了兩種發(fā)送/接收各種并行計算模型的比較

模型屬性PRAMAPRAMLogPBSPC3體系結(jié)構(gòu)SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM計算模式同步計算異步計算異步計算異步計算異步計算同步方式自動同步障礙同步隱式同步障礙同步障礙同步計算粒度細(xì)/中粒度中/大粒度中/大粒度中/大粒度粗粒度通信方式共享變量共享變量發(fā)/收消息發(fā)/收消息發(fā)/收消息模型參數(shù)1(單位時間步)d:全局讀/寫時間B:同步時間L:通信延遲o:通信開銷g:消息間隔P:處理器數(shù)p:處理器數(shù)g:帶寬因子L:同步間隔l:消息包長度s:發(fā)送開銷h:通信延遲11/30/202261各種并行計算模型的比較模型PRAMAPRAMLogPBS由于并行計算機(jī)正在處于飛速發(fā)展中，但尚未定型，因此到現(xiàn)在為止，還沒有一個通用的并行計算模型。人們只能將某一類并行機(jī)的基本特征抽象出來，形成各種特定的并行計算模型，以便并行算法的設(shè)計與理論分析。11/30/202262由于并行計算機(jī)正在處于飛速發(fā)展中，但尚未定型，因此到現(xiàn)在為止PRAM模型是對一類共享的并行機(jī)特征抽取，它拋開了通信的干擾，可用于開發(fā)細(xì)粒度并行算法；LogP模型是對一類分布式并行計算機(jī)特征抽取，基于點對點通信的計算模型，集中分析處理機(jī)與網(wǎng)絡(luò)之間的瓶頸問題；C3模型是對一類基于消息傳遞的分布式粗粒度系統(tǒng)特征抽取，集中反映的是網(wǎng)絡(luò)擁擠和路由影響。11/30/202263PRAM模型是對一類共享的并行機(jī)特征抽取，它拋開了通信的干例1_1：在PRAM-EREW計算機(jī)上對兩個N維向量A和B求內(nèi)積s。假設(shè)用p個處理機(jī)完成該任務(wù)，并設(shè)N/p是整數(shù)，內(nèi)積的值在LocalVal[0]中。VECTORMUL(PRAM-EREW):GlobalN,i,A[0..N-1],B[0..N-1],LocalVal[0..p-1]Localjbeginspawn(P0,P1,P2,…,Pp-1)forallPi,其中0ip-1dobeginLocalVal[i]=0;forj=i;j<NsteppdoLocalVal[i]=LocalVal[i]+A[j]*B[j];forj=0tologp-1doifimod2j+1==0andi+2j<pthenLocalVal[i]=LocalVal[i]+LocalVal[i+2j]end;end11/30/202264例1_1：在PRAM-EREW計算機(jī)上對兩個N維向量A該算法的執(zhí)行時間：假設(shè)一次乘法和加法各用一個單位時間激活p個處理機(jī)的時間：logp---spawn(P0,P1,P2,…,Pp-1)

各處理機(jī)計算局部和的時間：2N/p-------forj=i;j<NsteppdoLocalVal[i]=LocalVal[i]+A[j]*B[j];求全局和的時間：logpforj=0tologp-1doifimod2j+1==0andi+2j<pthenLocalVal[i]=LocalVal[i]+LocalVal[i+2j]整個算法的執(zhí)行時間為：2logp+2N/p=(logp+N/p)相應(yīng)的串行算法的執(zhí)行時間為：2N當(dāng)N>>p時，該P(yáng)RAM算法的加速比為：2N/(2logp+2N/p)→p11/30/202265該算法的執(zhí)行時間：11/30/202265例1_2：在APRAM計算模型上對兩個N維向量A和B求內(nèi)積。算法思想：整個算法僅需一個全局相。將數(shù)據(jù)分散在各個處理機(jī)的局部存儲器中；在全局相中：局部計算：每個處理機(jī)在2N/p個單位時間內(nèi)計算出局部和。全局計算：將各個處理機(jī)的局部和放到全局存儲器中，并求總和。執(zhí)行時間=(pd+p)

障礙同步。時間為B。11/30/202266例1_2：在APRAM計算模型上對兩個N維向量A例1_3：在BSP計算機(jī)上對兩個N維向量A和B求內(nèi)積。假設(shè)用p=8個處理機(jī)完成該任務(wù)，用4個超步完成問題的求解。超步1：計算：每個處理機(jī)在2N/8個單位時間內(nèi)計算出局部和。通信：處理機(jī)0，2，4，6將其局部和送給處理機(jī)1，3，5，7。完成1-relation通信。障礙同步。超步2：計算：處理機(jī)1，3，5，7各自完成一次加法。通信：處理機(jī)1，5將其局部和送給處理機(jī)3，7。完成1-relation通信。障礙同步。超步3：計算：處理機(jī)3，7各自完成一次加法。通信：處理機(jī)3將其局部和送給處理機(jī)7。完成1-relation通信。障礙同步。超步4：計算：處理機(jī)7完成一次加法，產(chǎn)生最終結(jié)果。不再需要通信和同步。11/30/202267例1_3：在BSP計算機(jī)上對兩個N維向量A和B求該算法各個超步的執(zhí)行時間：超步1：2N/8+g+l超步2：1+g+l超步3：1+g+l超步4：1該算法總的執(zhí)行時間：2N/8+3g+3l+3若處理機(jī)的個數(shù)為p，則算法總的執(zhí)行時間：2N/p+logp(g+l+1)相對PRAM算法，算法時間增加了g*logp和l*logp，顯然BSP模型考慮了通信和同步開銷。11/30/202268該算法各個超步的執(zhí)行時間：11/30/202268第四章并行算法的設(shè)計基礎(chǔ)并行計算相關(guān)的研究分支1.并行計算機(jī)體系結(jié)構(gòu)2.并行計算的性能評價3.并行算法4.并行程序設(shè)計一、并行算法相關(guān)的基本概念及表示二、介紹幾種并行計算模型3.并行算法1.并行計算機(jī)體系結(jié)構(gòu)2.并行計算的性能評價11/30/202269第四章并行算法的設(shè)計基礎(chǔ)并行計算相關(guān)的研究分支一、并行算一、并行算法相關(guān)的基本概念及表示基本概念并行算法的表示并行算法的復(fù)雜性度量并行算法的同步與通信11/30/202270一、并行算法相關(guān)的基本概念及表示基本概念11/30/20221.基本概念定義1：算法：在有限步驟內(nèi)求解某一特定問題的一組無二義性的規(guī)則。定義2：并行算法是由一些獨(dú)立的、可以并行運(yùn)行的計算模塊（進(jìn)程）構(gòu)成，模塊（進(jìn)程）之間能相互作用和協(xié)調(diào)，以完成對一個給定問題的求解。11/30/2022711.基本概念定義1：算法：在有限步驟內(nèi)求解某一特定問題的一根據(jù)算法的不同特征，可以對并行算法進(jìn)行不同的分類：SIMD算法和MIMD算法同步算法和異步算法數(shù)值計算算法和非數(shù)值計算算法共享存儲算法和分布存儲算法11/30/202272根據(jù)算法的不同特征，可以對并行算法進(jìn)行不同的分類：11/30定義3：同步算法(synchronizedalgorithm):是指算法的諸進(jìn)程的執(zhí)行必須相互等待的一類并行算法。SIMD算法是同步算法中的一種特例。定義4：異步算法(asynchronousalgorithm):是指算法的諸進(jìn)程的執(zhí)行不必相互等待的一類并行算法。定義5：分布并行算法(distributedalgorithm)：將同一任務(wù)分解為若干個子任務(wù)，使之分布在由通信鏈路連接的多個節(jié)點上協(xié)同完成運(yùn)算的算法。分布式算法的執(zhí)行時間，在很大程度上受通信開銷的影響。11/30/202273定義3：同步算法(synchronizedalgorith定義6：確定算法(deterministicalgorithm)：每個運(yùn)算步驟上均確定唯一操作的算法。如線性方程組求解的算法。

不確定算法(non-deterministicalgorithm)：在問題求解的搜索過程中，提出多種可供選擇的操作，它們中的任一種都有希望獲得問題的解答，但都不能肯定解出，有時甚至不能確定這些操作中哪一種求解的可能性更大些。對此，只能選擇其中任意一種搜索下去。這種搜索方法稱為不確定算法。11/30/202274定義6：確定算法(deterministicalgori定義7：隨機(jī)算法(randomizedalgorithm,probabilisticalgorithm)計算步驟具有隨機(jī)性的算法。在算法的某一步或某些步上，可以在指定范圍內(nèi)隨機(jī)地選擇下一個演算步的走向。如果方法得當(dāng)，可比一般算法更快地得出結(jié)果，并且能以較高的概率提供正確的結(jié)果。11/30/202275定義7：隨機(jī)算法(randomizedalgorithm表示算法的要求無二義性力圖直觀、易懂不苛求嚴(yán)格的語法格式一般的串行算法常用類Pascal、類Algol表示2.并行算法的表示11/30/202276表示算法的要求2.并行算法的表示11/30/202281.par-do語句fori=1tonpar-do::endfor表示其間的n(i=1ton)次語句序列的執(zhí)行可以并行完成表示k個處理器同時執(zhí)行其間的語句序列2.forall語句forallPiwhere0i

k-1do::endfor并行算法常引入以下兩條并行語句：11/30/2022771.par-do語句表示其間的n(i=1ton)3.并行算法的復(fù)雜性度量令f(n)和g(n)是定義在自然數(shù)集合N上的兩個函數(shù)，定義8：如果存在兩個正數(shù)c和n0，使得對于所有的nn0均有f(n)

cg(n)，則標(biāo)記為：

f(n)=(g(n))

我們稱g(n)為f(n)的上界。定義9：如果存在兩個正數(shù)c和n0，使得對于所有的nn0均有f(n)cg(n)，則標(biāo)記為：

f(n)=(g(n))我們稱g(n)為f(n)的下界。11/30/2022783.并行算法的復(fù)雜性度量令f(n)和g(n)是定義定義10：如果存在正數(shù)c1、c2

和n0，使得對于所有的nn0均有c1g(n)f(n)

c2g(n)，則標(biāo)記為

f(n)=(g(n))我們稱g(n)為f(n)的緊致界。即：如果f(n)=(g(n))且f(n)=(g(n))

則f(n)=(g(n))11/30/202279定義10：如果存在正數(shù)c1、c2和n0，使得對于所有

比較兩個算法的時間復(fù)雜性函數(shù)g(n)和f(n)的階的方法：用定義判斷用求極限的方法來加以判斷。若

則（1）當(dāng)c≠0時，說明f(n)和g(n)同階，記為f(n)=Θ(g(n))（2）當(dāng)c=0時，說明f(n)比g(n)低階，記為f(n)=O(g(n))（3）當(dāng)c=∞時，說明f(n)比g(n)高階，記為f(n)=Ω(g(n))11/30/20228011/30/202212并行算法的運(yùn)行時間t(n)：對于輸入規(guī)模為n的問題，在給定的并行計算模型之下求解問題所需的時間，也稱為時間復(fù)雜性(timecomplexity)。運(yùn)行時間=計算時間+通信時間處理器數(shù)p(n)：表示對給定的問題規(guī)模n，并行算法所用的處理器的個數(shù)。并行算法的成本c(n)：并行算法的運(yùn)行時間t(n)與所需的處理器數(shù)p(n)之積，即c(n)=t(n)*p(n)11/30/202281并行算法的運(yùn)行時間t(n)：對于輸入規(guī)模為n的問題，例:(1)設(shè)f(n)=n2/2,g(n)=307n2，則因此，f(n)=n2/2與g(n)=307n2是同階的。

(2)設(shè)f(n)=lgn，g(n)=n，則所以，f(n)=lgn比g(n)=n低階。11/30/202282例:(1)設(shè)f(n)=n2/2,g(n)=307n2，則1定義11：一個并行算法最壞情況下的時間復(fù)雜性(worst-casetime-complexity)：對于所有輸入規(guī)模為n的問題，在給定的并行計算模型之下求解問題所需的時間的最大值。定義12：一個并行算法的期望時間復(fù)雜性(expectedtime-complexity)：對于所有輸入規(guī)模為n的問題，在給定的計算模型之下求解問題所需的時間的平均值。11/30/202283定義11：一個并行算法最壞情況下的時間復(fù)雜性(worst-定義13：一個并行算法最壞情況下的空間復(fù)雜性(worst-casespace-complexity)：對于所有輸入規(guī)模為n的問題，在給定的并行計算模型之下求解問題所需的內(nèi)存空間的最大值。定義14：一個并行算法的期望空間復(fù)雜性(expectedspace-complexity)：對于所有輸入規(guī)模為n的問題，在給定的計算模型之下求解問題所需的內(nèi)存空間的平均值。11/30/202284定義13：一個并行算法最壞情況下的空間復(fù)雜性(worst-c定義15：如果一個并行算法的成本與其對應(yīng)的最佳串行算法的最壞情況下時間復(fù)雜性在同一個數(shù)量級上，則稱該并行算法為成本最佳的(cost-optimal)或最佳并行算法(optimalparallelalgorithm)?？傔\(yùn)算量W(n):(并行)算法中所要完成的總的操作數(shù)量(thenumberofcomputationaloperations)11/30/202285定義15：如果一個并行算法的成本與其對應(yīng)的最佳串行算法的最壞4.并行算法中的同步與通信同步(synchronization)：使多個相關(guān)事件的發(fā)生保持相同的節(jié)奏，彼此之間能良好地配合。在并行算法的各進(jìn)程異步執(zhí)行過程中，為了確保各處理器的正確工作順序和對共享存儲器的訪問，程序員需要在算法的適當(dāng)位置設(shè)置同步點。下面給出一個利用lock和unlock構(gòu)造的臨界區(qū)完成數(shù)組求和的算法11/30/2022864.并行算法中的同步與通信同步(synchronizatibeginS=0forallPiwhere0ip-1doL=0forj=iton-1steppdoL=L

+ajendforlock(u)S=S+Lunlock(u)endforend[算法4.1.3]共享存儲多處理機(jī)上求和算法輸入：A=(a0,a1,…,an-1),處理器數(shù)p；輸出：a0+a1+…+an-1存放在全局變量S

中。11/30/202287begin[算法4.1.3]共享存儲多處理機(jī)上求和算法通信(communication)：把信息用一定手段通過某種介質(zhì)或傳輸線路從一個點傳送至另一點的過程。通信是在空間上對并發(fā)執(zhí)行的進(jìn)程實現(xiàn)數(shù)據(jù)交換。原語(primitive)：它由若干條機(jī)器指令構(gòu)成的，用來完成特定功能的一段程序。原語有以下特點：不可中斷性：一旦原語被開始執(zhí)行，就應(yīng)不間斷地執(zhí)行到結(jié)束；不可侵犯性：原語一旦被執(zhí)行，中間不許插入任何其他操作。11/30/202288通信(communication)：把信息用一定手段通過某種通信可使用通信原語來表示：1.在共享存儲的多處理機(jī)中，可使用1)globalread(X,Y)將全局存儲器中數(shù)據(jù)X讀入局部變量Y；2)globalwrite(U,V)將局部數(shù)據(jù)U寫入共享存儲變量V中。2.在分布存儲的多計算機(jī)中，可使用1)send(X,i)或send(X,Pi)當(dāng)前處理器發(fā)送數(shù)據(jù)X到Pi；2)receive(Y,j)或receive(Y,Pj)當(dāng)前處理器從Pj接收數(shù)據(jù)Y。11/30/202289通信可使用通信原語來表示：11/30/202221[算法4.1.4]分布存儲多計算機(jī)上矩陣向量相乘算法給定:一個n*n的矩陣A和一個向量X

a11a12a13……a1n-1a1na21a22a23……a2n-1a2n

A=a31a32a33……a3n-1a3n……..an1an2an3……ann-1annx1x2X=x3…xn計算:A*X，得到一個向量。假設(shè)r=n/p為一整數(shù)因為我們打算在分布存儲的多計算機(jī)系統(tǒng)上運(yùn)行該算法，被計算的數(shù)據(jù)只能分布在各個處理器的局部存儲器上。11/30/202290[算法4.1.4]分布存儲多計算機(jī)上矩陣向量相乘算法我們把A按列分為p個n*r的小矩陣A1,A2,…,Ap

把X按行分為p個r*1的小向量X1,X2,…,Xp計算A*X就轉(zhuǎn)化為計算：A1X1+A2X2+…ApXp所以處理器Pi（其中1ip）將Ai和Xi存放在自己的局部存儲器中，各處理器首先計算AiXi，然后利用通信實現(xiàn)數(shù)據(jù)求和。X1(r*1)X2(r*1)…Xp(r*1)A=A1A2

…ApX=

(n*r)(n*r)(n*r)11/30/202291我們把A按列分為p個n*r的小矩陣A1,A2我們假設(shè)處理器是以環(huán)結(jié)構(gòu)組織的PiP2PpP111/30/202292我們假設(shè)處理器是以環(huán)結(jié)構(gòu)組織的PiP2PpP111/30/2[算法4.1.4]分布存儲多計算機(jī)上矩陣向量相乘算法輸入：處理器數(shù)p，第i個A矩陣分量Ai于B中，第i個X向量分量Xi于w中;輸出：A*X于P1變量y中。begincomputez=Bwifi=1theny=0elsereceive(y,left)endify=y+zsend(y,right)ifi=1thenreceive(y,left)end11/30/202293[算法4.1.4]分布存儲多計算機(jī)上矩陣向量相乘算法11/p1p3p2p4計算z=Bw計算z=Bw計算z=Bw計算z=Bwy=0rec(y,p1)rec(y,p2)rec(y,p3)y=y+zsend(y,p2)send(y,p3)send(y,p4)rec(y,p4)send(y,p1)y=y+zy(1)y=y+zy(2)y=y+zy(3)y(4)結(jié)束11/30/202294p1p3p2p4計算z=Bw計算z=Bw計算z=Bw計算z=第四章并行算法的設(shè)計基礎(chǔ)一、并行算法相關(guān)的基本概念及表示二、介紹幾種并行計算模型二、介紹幾種并行計算模型11/30/202295第四章并行算法的設(shè)計基礎(chǔ)一、并行算法相關(guān)的基本概念及表示二、并行計算模型并行計算模型：從并行算法的設(shè)計和分析出發(fā)，將各種并行計算機(jī)（至少是某一類并行計算機(jī)）的基本特征抽象出來，形成一個抽象的計算模型。并行計算模型為并行計算提供了硬件和軟件的界面，使硬件設(shè)計者和軟件設(shè)計者可以開發(fā)并行性的支持機(jī)制，從而提高系統(tǒng)的性能。對并行算法的研制者，不會局限于某種具體的并行計算機(jī)來研究并行算法，而需借助于抽象的計算模型，它是設(shè)計和分析并行算法的基礎(chǔ)。11/30/202296二、并行計算模型并行計算模型：從并行算法的設(shè)計和分析出發(fā)，將為了能對計算機(jī)系統(tǒng)進(jìn)行簡單、明確的描述，發(fā)現(xiàn)一般規(guī)律，通常在不同層次上進(jìn)行抽象來定義模型。不同層次模型的關(guān)系圖：編程模型計算模型體系結(jié)構(gòu)模型機(jī)器模型用戶系統(tǒng)硬件和操作系統(tǒng)互連網(wǎng)絡(luò)的作用和執(zhí)行通信的形式等計算機(jī)的費(fèi)用和資源編程語言的語義11/30/202297為了能對計算機(jī)系統(tǒng)進(jìn)行簡單、明確的描述，發(fā)現(xiàn)一般規(guī)律，通常在并行計算模型的主要作用：它是并行算法實現(xiàn)的基礎(chǔ)對同一問題在不同的模型上的不同解決辦法，來比較該問題究竟更合理在哪一種模型上實現(xiàn)它給并行算法設(shè)計和分析提供了一個簡單、方便的框架撇開了硬件的繁雜的細(xì)節(jié)它使并行算法設(shè)計具有一定的生命力集中精力開發(fā)應(yīng)用問題自身的并行性和算法的性能，并使算法具有一定的通用性11/30/202298并行計算模型的主要作用：11/30/202230串行算法的研究已經(jīng)相當(dāng)成熟，它們基本上都是基于馮.諾依曼(vonNeumann)體系結(jié)構(gòu)控制器運(yùn)算器主存儲器輸出設(shè)備輸入設(shè)備CPU高速緩存11/30/202299串行算法的研究已經(jīng)相當(dāng)成熟，它們基本上都是基于馮.諾依曼(v程序指令計數(shù)器r0r1r2r3:存儲器累加器xn……x2x1只讀輸入磁帶……y2y1只寫輸出磁帶串行計算模型RAM(RandomAccessMachine)11/30/2022100指令r0存儲器累加器xn……x2x1只讀輸入磁帶……y2y1RAM機(jī)器模型的指令系統(tǒng)與實際計算機(jī)的指令系統(tǒng)類似，有四類指令：1.控制流向指令，如jump;2.輸入/輸出指令，如read,write；3.累加器與存儲器之間的傳送數(shù)據(jù)指令，如load；4.算術(shù)運(yùn)算指令，如add。11/30/2022101RAM機(jī)器模型的指令系統(tǒng)與實際計算機(jī)的指令系統(tǒng)類似，有四類指PRAM模型

(ParallelRandomAccessMachineModel)1978年S.Fortune和J.Wyllie總結(jié)了陣列式結(jié)構(gòu)的并行機(jī)和流水線結(jié)構(gòu)的向量機(jī)的特點，將其抽象為具有如下特征的PRAM模型：1）有一個控制器2）有p（可有限或無限）臺功能相同的處理器3）有一個容量無限的共享存儲器4）每臺處理器有自己的局部存儲器5）處于激活狀態(tài)的處理器必須執(zhí)行相同的指令6）允許任何時刻各處理器均可通過共享存儲器與其它處理器交換數(shù)據(jù)。11/30/2022102PRAM模型

(ParallelRandomAccesPRAM模型----SIMD計算模型控制器互聯(lián)網(wǎng)絡(luò)全局共享存儲器P1LM1P2LM2PpLMp……11/30/2022103PRAM模型----SIMD計算模型控制器互聯(lián)PRAM模型允許任何時刻各處理器均可通過共享存儲器的共享單元與其它處理器交換數(shù)據(jù)。根據(jù)處理器對共享單元的存、取訪問的不同約束條件進(jìn)一步對PRAM模型分類：PRAM-EREW(ExclusiveRead,ExclusiveWrite)：不允許有讀沖突和寫沖突PRAM-CREW(ConcurrentRead,ExclusiveWrite)：每次允許多臺處理器同時讀同一共享單元內(nèi)容，但不允許同時寫。PRAM-CRCW(ConcurrentRead,ConcurrentWrite)：允許多臺處理器同時讀、寫同一共享單元內(nèi)容。11/30/2022104PRAM模型允許任何時刻各處理器均可通過共享存儲器的共享單PRAM-CRCW模型中允許同時寫同一共享單元顯然是不現(xiàn)實的，所以對PRAM-CRCW模型作了更進(jìn)一步的約定：共用的

(Common)PRAM-CRCW：同時寫同一共享單元的所有處理器必須寫相同的值；優(yōu)先的

(Priority)PRAM-CRCW：從同時要寫同一共享單元的所有處理器中找出標(biāo)號最小的處理器，將它的值寫入共享地址中；任意的

(Arbitrary)PRAM-CRCW：從同時要寫同一共享單元的所有處理器中任選一個處理器的值寫入共享地址中。11/30/2022105PRAM-CRCW模型中允許同時寫同一共享單元顯然是不現(xiàn)實PRAM模型上的算法的執(zhí)行：1）輸入數(shù)據(jù)存放在全局共享存儲器中，并只有一個處理器處于激活狀態(tài)；2）在每個計算步中，一個激活的處理器可做：從局部或全局存儲器中讀一個值完成一個RAM操作寫值到局部或全局存儲器中激活另一個處理器11/30/2022106PRAM模型上的算法的執(zhí)行：11/30/202238[算法4.2.1]在PRAM-EREW模型上求和算法輸入：n個待求和的數(shù)A[0..(n-1)]輸出：最終的n個數(shù)的和在A[0]中全局變量：n,A[0..(n-1)],jbegin*spawn(P0,P1,…,Pn/2-1)forallPiwhere0in/2-1doforj=0tologn-1doifimod2j=0and2i+2j<nthenA[2i]=A[2i]+A[2i+2j]endifendforendforend11/30/2022107[算法4.2.1]在PRAM-EREW模型上求和算法spawn()：激活n個處理機(jī)例：n=12spawn()：激活n個處理機(jī)的時間為logn。時間11/30/2022108spawn()：激活n個處理機(jī)例：n=12spa2.APRAM模型(AsynchronousPRAM)80年代初，人們總結(jié)了共享存儲型多處理機(jī)結(jié)構(gòu)的向量機(jī)的特點，將其抽象為具有如下特征的APRAM模型：1）有p（可有限或無限）個處理器；2）每個處理器有自己的控制器（局部時鐘）；3）有一個容量無限的共享存儲器；4）每臺處理器有自己的局部存儲器和局部程序；5）各處理器異步地、獨(dú)立地執(zhí)行各自的指令，處理器間的同步需明確地在各處理器的程序中加入障礙（路障）同步(barriersynchronization)指令；6）利用共享存儲器實現(xiàn)處理器間的通信。11/30/20221092.APRAM模型(AsynchronousPRAAPRAM模型----MIMD計算模型控制器1互聯(lián)網(wǎng)絡(luò)全局共享存儲器P1LM1P2LM2PpLMp……控制器2控制器p……11/