并行算法的設(shè)計(jì)基礎(chǔ)

1、2024/3/17,1,第四章 并行算法的設(shè)計(jì)基礎(chǔ),并行計(jì)算相關(guān)的研究分支1. 并行計(jì)算機(jī)體系結(jié)構(gòu)2. 并行計(jì)算的性能評(píng)價(jià)3. 并行算法4. 并行程序設(shè)計(jì),一、并行算法相關(guān)的基本概念及表示二、介紹幾種并行計(jì)算模型,3. 并行算法,1. 并行計(jì)算機(jī)體系結(jié)構(gòu),2. 并行計(jì)算的性能評(píng)價(jià),2024/3/17,2,一、并行算法相關(guān)的基本概念及表示,基本概念并行算法的表示并行算法的復(fù)雜性度量并行算法的同步與通信,2024/3/17

2、,3,1. 基本概念,定義1：算法：在有限步驟內(nèi)求解某一特定問題的一組無二義性的規(guī)則。定義2：并行算法是由一些獨(dú)立的、可以并行運(yùn)行的計(jì)算模塊（進(jìn)程）構(gòu)成，模塊（進(jìn)程）之間能相互作用和協(xié)調(diào)，以完成對(duì)一個(gè)給定問題的求解。,2024/3/17,4,根據(jù)算法的不同特征，可以對(duì)并行算法進(jìn)行不同的分類：SIMD算法和MIMD算法同步算法和異步算法數(shù)值計(jì)算算法和非數(shù)值計(jì)算算法共享存儲(chǔ)算法和分布存儲(chǔ)算法,2024/3/17,5,定義3：同步算

3、法(synchronized algorithm):是指算法的諸進(jìn)程的執(zhí)行必須相互等待的一類并行算法。SIMD算法是同步算法中的一種特例。定義4：異步算法(asynchronous algorithm):是指算法的諸進(jìn)程的執(zhí)行不必相互等待的一類并行算法。定義5：分布并行算法(distributed algorithm)：將同一任務(wù)分解為若干個(gè)子任務(wù)，使之分布在由通信鏈路連接的多個(gè)節(jié)點(diǎn)上協(xié)同完成運(yùn)算的算法。 分布式算法的執(zhí)行時(shí)間

4、，在很大程度上受通信開銷的影響。,2024/3/17,6,定義6：確定算法 (deterministic algorithm)：每個(gè)運(yùn)算步驟上均確定唯一操作的算法。如線性方程組求解的算法。 不確定算法 (non-deterministic algorithm)：在問題求解的搜索過程中，提出多種可供選擇的操作，它們中的任一種都有希望獲得問題的解答，但都不能肯定解出，有時(shí)甚至不能確定這些操作中哪一種求解的可能性更大些。對(duì)此，只能選擇

5、其中任意一種搜索下去。這種搜索方法稱為不確定算法。,2024/3/17,7,定義7：隨機(jī)算法( randomized algorithm, probabilistic algorithm )計(jì)算步驟具有隨機(jī)性的算法。在算法的某一步或某些步上，可以在指定范圍內(nèi)隨機(jī)地選擇下一個(gè)演算步的走向。 如果方法得當(dāng)，可比一般算法更快地得出結(jié)果，并且能以較高的概率提供正確的結(jié)果。,2024/3/17,8,表示算法的要求無二義性力圖直觀、易懂

6、不苛求嚴(yán)格的語法格式一般的串行算法常用類Pascal、類Algol表示,2. 并行算法的表示,2024/3/17,9,1. par-do語句 for i=1 to n par-do : :end for,,表示其間的 n (i=1 to n) 次語句序列的執(zhí)行可以并行完成,,表示 k 個(gè)處理器同時(shí)執(zhí)行其間的語句序列,2. for all 語句 for all Pi where 0

7、 ? i ? k-1 do : :end for,并行算法常引入以下兩條并行語句：,2024/3/17,10,3. 并行算法的復(fù)雜性度量,令 f(n) 和 g(n) 是定義在自然數(shù)集合N 上的兩個(gè)函數(shù)，定義8： 如果存在兩個(gè)正數(shù) c 和 n0 ，使得對(duì)于所有的 n ? n0 均有f(n) ? c g(n) ，則標(biāo)記為： f(n)=? ( g

8、(n) ) 我們稱 g(n) 為 f(n) 的上界。定義9： 如果存在兩個(gè)正數(shù) c 和 n0 ，使得對(duì)于所有的 n ? n0 均有f(n) ? c g(n) ，則標(biāo)記為： f(n)= ? ( g(n) ) 我們稱 g(n) 為 f(n) 的下界。,2024/3/17,11,定義10：如果存在正數(shù) c1、c2 和 n0 ，使得對(duì)于所有的 n ? n0 均有c1 g(n

9、) ? f(n) ? c2 g(n) ，則標(biāo)記為 f(n)= ? ( g(n) ) 我們稱 g(n) 為 f(n) 的緊致界。即：如果 f(n)=? ( g(n) )且 f(n)= ? ( g(n) ) 則 f(n)= ? ( g(n) ),2024/3/17,12,比較兩個(gè)算法的時(shí)間復(fù)雜性函數(shù)g(n)和f(n)的階的方法： 用定義判斷 用求極限的方法來加以判斷。

10、 若 則（1）當(dāng)c≠0時(shí)，說明f(n)和g(n)同階，記為f(n)=Θ(g(n))（2）當(dāng)c=0時(shí)，說明f(n)比g(n)低階，記為f(n) =O(g(n))（3）當(dāng)c=∞時(shí)，說明f(n)比g(n)高階，記為f(n)=Ω(g(n)),,2024/3/17,13,并行算法的運(yùn)行時(shí)間 t(n) ：對(duì)于輸入規(guī)模為 n 的問題，在給定的并行計(jì)算模型之下求解問題所需的時(shí)間，也稱為時(shí)間復(fù)雜性 ( time

11、 complexity )。運(yùn)行時(shí)間 = 計(jì)算時(shí)間 + 通信時(shí)間處理器數(shù)p(n)：表示對(duì)給定的問題規(guī)模 n，并行算法所用的處理器的個(gè)數(shù)。并行算法的成本c(n)：并行算法的運(yùn)行時(shí)間 t(n)與所需的處理器數(shù) p(n) 之積，即c(n) = t(n) * p(n),2024/3/17,14,例:(1)設(shè)f(n)=n2/2, g(n)=307n2，則因此，f(n)=n2/2與g(n)=307n2是同階的。

12、 (2)設(shè)f(n)=lg n，g(n)=n，則所以，f(n)=lg n比g(n)=n低階。,,,2024/3/17,15,定義11：一個(gè)并行算法最壞情況下的時(shí)間復(fù)雜性( worst-case time-complexity ) ：對(duì)于所有輸入規(guī)模為 n 的問題，在給定的并行計(jì)算模型之下求解問題所需的時(shí)間的最大值。定義12：一個(gè)并行算法的期望時(shí)間復(fù)雜性( expected time-complexity )

13、：對(duì)于所有輸入規(guī)模為 n 的問題，在給定的計(jì)算模型之下求解問題所需的時(shí)間的平均值。,2024/3/17,16,定義13：一個(gè)并行算法最壞情況下的空間復(fù)雜性(worst-case space-complexity) ：對(duì)于所有輸入規(guī)模為 n 的問題，在給定的并行計(jì)算模型之下求解問題所需的內(nèi)存空間的最大值。定義14：一個(gè)并行算法的期望空間復(fù)雜性(expected space-complexity) ：對(duì)于所有輸入規(guī)模為 n 的問題，在給定

14、的計(jì)算模型之下求解問題所需的內(nèi)存空間的平均值。,2024/3/17,17,定義15：如果一個(gè)并行算法的成本與其對(duì)應(yīng)的最佳串行算法的最壞情況下時(shí)間復(fù)雜性在同一個(gè)數(shù)量級(jí)上，則稱該并行算法為成本最佳的( cost-optimal ) 或最佳并行算法 (optimal parallel algorithm )。總運(yùn)算量W (n): (并行)算法中所要完成的總的操作數(shù)量( the number of computational operatio

15、ns ),2024/3/17,18,4. 并行算法中的同步與通信,同步(synchronization)：使多個(gè)相關(guān)事件的發(fā)生保持相同的節(jié)奏，彼此之間能良好地配合。在并行算法的各進(jìn)程異步執(zhí)行過程中，為了確保各處理器的正確工作順序和對(duì)共享存儲(chǔ)器的訪問，程序員需要在算法的適當(dāng)位置設(shè)置同步點(diǎn)。下面給出一個(gè)利用 lock 和 unlock 構(gòu)造的臨界區(qū)完成數(shù)組求和的算法,2024/3/17,19,begin S = 0 for

16、all Pi where 0 ? i ? p-1 do L = 0 for j = i to n-1 step p do L = L + aj end for lock (u) S = S + L unlock (u) end forend,[算法4.1.3] 共享存儲(chǔ)多處理機(jī)上求和算法輸入：A = (a0 , a1 ,…, a

17、n-1) , 處理器數(shù) p； 輸出： a 0 + a 1 +…+ a n-1 存放在全局變量S 中。,2024/3/17,20,通信(communication)：把信息用一定手段通過某種介質(zhì)或傳輸線路從一個(gè)點(diǎn)傳送至另一點(diǎn)的過程。通信是在空間上對(duì)并發(fā)執(zhí)行的進(jìn)程實(shí)現(xiàn)數(shù)據(jù)交換。原語 (primitive)：它由若干條機(jī)器指令構(gòu)成的，用來完成特定功能的一段程序。原語有以下特點(diǎn)：不可中斷性：一旦原語被開始執(zhí)行，就應(yīng)不間斷地執(zhí)行到結(jié)束；

18、不可侵犯性：原語一旦被執(zhí)行，中間不許插入任何其他操作。,2024/3/17,21,通信可使用通信原語來表示：1. 在共享存儲(chǔ)的多處理機(jī)中，可使用1) global read (X, Y)將全局存儲(chǔ)器中數(shù)據(jù) X 讀入局部變量 Y；2) global write (U, V)將局部數(shù)據(jù) U 寫入共享存儲(chǔ)變量 V 中。2. 在分布存儲(chǔ)的多計(jì)算機(jī)中，可使用1) send (X, i ) 或 send (X, Pi ) 當(dāng)前處理

19、器發(fā)送數(shù)據(jù) X 到 Pi ；2) receive (Y, j ) 或 receive (Y, Pj )當(dāng)前處理器從Pj 接收數(shù)據(jù) Y。,2024/3/17,22,[算法4.1.4] 分布存儲(chǔ)多計(jì)算機(jī)上矩陣向量相乘算法給定: 一個(gè) n*n 的矩陣 A 和一個(gè)向量 X,計(jì)算: A*X，得到一個(gè)向量。假設(shè) r = n/p 為一整數(shù)因?yàn)槲覀兇蛩阍诜植即鎯?chǔ)的多計(jì)算機(jī)系統(tǒng)上運(yùn)行該算法，被計(jì)算的數(shù)據(jù)只能分布在各個(gè)處理器的局部存儲(chǔ)器上。,2

20、024/3/17,23,我們把 A 按列分為 p 個(gè) n*r 的小矩陣A1 , A2 ,… , Ap 把 X 按行分為 p 個(gè) r*1 的小向量X1 , X2 ,… , Xp,計(jì)算 A*X就轉(zhuǎn)化為計(jì)算： A1 X1 + A2 X2 +… Ap Xp所以處理器Pi（其中1 ? i ? p）將Ai 和 Xi 存放在自己的局部存儲(chǔ)器中，各處理器首先計(jì)算 Ai Xi ，然后利用通信實(shí)現(xiàn)數(shù)據(jù)求

21、和。,2024/3/17,24,我們假設(shè)處理器是以環(huán)結(jié)構(gòu)組織的,Pi,P2,Pp,P1,2024/3/17,25,[算法4.1.4] 分布存儲(chǔ)多計(jì)算機(jī)上矩陣向量相乘算法輸入：處理器數(shù) p， 第 i 個(gè) A 矩陣分量 Ai 于 B 中， 第 i 個(gè) X 向量分量 Xi于 w 中;輸出：A*X 于 P1 變量 y 中。begin compute z = Bw if i =

22、 1 then y = 0 else receive (y , left) endif y = y + z send (y , right) if i = 1 then receive (y , left)end,2024/3/17,26,2024/3/17,27,第四章 并行算法的設(shè)計(jì)基礎(chǔ),一、并行算法相關(guān)的基本概念及表示二、介紹幾種并行計(jì)算模型,二、介紹幾種

23、并行計(jì)算模型,2024/3/17,28,二、并行計(jì)算模型,并行計(jì)算模型：從并行算法的設(shè)計(jì)和分析出發(fā)，將各種并行計(jì)算機(jī)（至少是某一類并行計(jì)算機(jī)）的基本特征抽象出來，形成一個(gè)抽象的計(jì)算模型。并行計(jì)算模型為并行計(jì)算提供了硬件和軟件的界面，使硬件設(shè)計(jì)者和軟件設(shè)計(jì)者可以開發(fā)并行性的支持機(jī)制，從而提高系統(tǒng)的性能。對(duì)并行算法的研制者，不會(huì)局限于某種具體的并行計(jì)算機(jī)來研究并行算法，而需借助于抽象的計(jì)算模型，它是設(shè)計(jì)和分析并行算法的基礎(chǔ)。,2024/

24、3/17,29,為了能對(duì)計(jì)算機(jī)系統(tǒng)進(jìn)行簡(jiǎn)單、明確的描述，發(fā)現(xiàn)一般規(guī)律，通常在不同層次上進(jìn)行抽象來定義模型。不同層次模型的關(guān)系圖：,2024/3/17,30,并行計(jì)算模型的主要作用：它是并行算法實(shí)現(xiàn)的基礎(chǔ)對(duì)同一問題在不同的模型上的不同解決辦法，來比較該問題究竟更合理在哪一種模型上實(shí)現(xiàn)它給并行算法設(shè)計(jì)和分析提供了一個(gè)簡(jiǎn)單、方便的框架撇開了硬件的繁雜的細(xì)節(jié)它使并行算法設(shè)計(jì)具有一定的生命力集中精力開發(fā)應(yīng)用問題自身的并行性和算法的性

25、能，并使算法具有一定的通用性,2024/3/17,31,串行算法的研究已經(jīng)相當(dāng)成熟，它們基本上都是基于馮.諾依曼(von Neumann)體系結(jié)構(gòu),高速緩存,2024/3/17,32,,,,,程序,指令計(jì)數(shù)器,,,,串行計(jì)算模型RAM (Random Access Machine),2024/3/17,33,RAM機(jī)器模型的指令系統(tǒng)與實(shí)際計(jì)算機(jī)的指令系統(tǒng)類似，有四類指令： 1. 控制流向指令， 如 jump; 2. 輸入/

26、輸出指令， 如 read , write； 3. 累加器與存儲(chǔ)器之間的傳送數(shù)據(jù)指令，如 load； 4. 算術(shù)運(yùn)算指令， 如 add。,2024/3/17,34,PRAM 模型(Parallel Random Access Machine Model),1978年S. Fortune 和 J. Wyllie總結(jié)了陣列式結(jié)構(gòu)的并行機(jī)和流水線結(jié)構(gòu)的向量機(jī)的特點(diǎn)，將其抽象為具有如下特征的 PRAM 模型：1）有一個(gè)控制器2

27、）有 p（可有限或無限）臺(tái)功能相同的處理器3）有一個(gè)容量無限的共享存儲(chǔ)器4）每臺(tái)處理器有自己的局部存儲(chǔ)器5）處于激活狀態(tài)的處理器必須執(zhí)行相同的指令6）允許任何時(shí)刻各處理器均可通過共享存儲(chǔ)器與其它處理器交換數(shù)據(jù)。,2024/3/17,35,PRAM模型----SIMD計(jì)算模型,2024/3/17,36,PRAM 模型允許任何時(shí)刻各處理器均可通過共享存儲(chǔ)器的共享單元與其它處理器交換數(shù)據(jù)。根據(jù)處理器對(duì)共享單元的存、取訪問的不同約束條

28、件進(jìn)一步對(duì) PRAM 模型分類：PRAM-EREW (Exclusive Read, Exclusive Write)：不允許有讀沖突和寫沖突PRAM-CREW (Concurrent Read, Exclusive Write)：每次允許多臺(tái)處理器同時(shí)讀同一共享單元內(nèi)容，但不允許同時(shí)寫。PRAM-CRCW (Concurrent Read, Concurrent Write)：允許多臺(tái)處理器同時(shí)讀、寫同一共享單元內(nèi)容。,2024

29、/3/17,37,PRAM-CRCW 模型中允許同時(shí)寫同一共享單元顯然是不現(xiàn)實(shí)的，所以對(duì)PRAM-CRCW 模型作了更進(jìn)一步的約定：共用的 (Common) PRAM-CRCW：同時(shí)寫同一共享單元的所有處理器必須寫相同的值；優(yōu)先的 (Priority) PRAM-CRCW：從同時(shí)要寫同一共享單元的所有處理器中找出標(biāo)號(hào)最小的處理器，將它的值寫入共享地址中；任意的 (Arbitrary) PRAM-CRCW：從同時(shí)要寫同一共享單元的所

30、有處理器中任選一個(gè)處理器的值寫入共享地址中。,2024/3/17,38,PRAM 模型上的算法的執(zhí)行：1）輸入數(shù)據(jù)存放在全局共享存儲(chǔ)器中，并只有一個(gè)處理器處于激活狀態(tài)；2）在每個(gè)計(jì)算步中，一個(gè)激活的處理器可做：從局部或全局存儲(chǔ)器中讀一個(gè)值完成一個(gè) RAM 操作寫值到局部或全局存儲(chǔ)器中激活另一個(gè)處理器,2024/3/17,39,[算法4.2.1] 在 PRAM-EREW 模型上求和算法輸入：n個(gè)待求和的數(shù) A [0..(

31、n-1)]輸出：最終的n個(gè)數(shù)的和在 A [0] 中全局變量：n , A [ 0..(n-1)] , jbegin* spawn(P0 , P1, … , P?n/2? - 1) for all Pi where 0 ? i ? ?n/2? - 1 do for j = 0 to ?log n? - 1 do if i mod 2j = 0 and 2i +2j < n th

32、en A [ 2i ] = A [ 2i ] + A [ 2i + 2j ] endif endfor endforend,2024/3/17,40,spawn( )：激活 n 個(gè)處理機(jī) 例：n=12,spawn( )：激活 n 個(gè)處理機(jī)的時(shí)間為?log n? 。,,,時(shí)間,2024/3/17,41,2. APRAM 模型 ( Asynchronous PR

33、AM ),80年代初，人們總結(jié)了共享存儲(chǔ)型多處理機(jī)結(jié)構(gòu)的向量機(jī)的特點(diǎn)，將其抽象為具有如下特征的 APRAM 模型：1）有 p（可有限或無限）個(gè)處理器；2）每個(gè)處理器有自己的控制器（局部時(shí)鐘）；3）有一個(gè)容量無限的共享存儲(chǔ)器；4）每臺(tái)處理器有自己的局部存儲(chǔ)器和局部程序；5）各處理器異步地、獨(dú)立地執(zhí)行各自的指令，處理器間的同步需明確地在各處理器的程序中加入障礙（路障）同步 (barrier synchronization) 指令；

34、6）利用共享存儲(chǔ)器實(shí)現(xiàn)處理器間的通信。,2024/3/17,42,APRAM 模型----MIMD計(jì)算模型,2024/3/17,43,PRAM模型----SIMD計(jì)算模型（對(duì)比）,2024/3/17,44,APRAM 模型同樣利用共享存儲(chǔ)器實(shí)現(xiàn)處理器間的通信障礙(路障)同步 (barrier synchronization)：它在程序中設(shè)置一些障礙點(diǎn)，當(dāng)處理器執(zhí)行到障礙點(diǎn)時(shí)暫停，等待所有進(jìn)程都執(zhí)行到這個(gè)障礙點(diǎn)上，以此方法取得同步。,

35、2024/3/17,45,APRAM 模型中的計(jì)算 :計(jì)算是由一系列用同步障礙點(diǎn)分開的全局相（global phase）組成的。在各全局相內(nèi)每個(gè)處理器異步地運(yùn)行其局部程序每個(gè)局部程序中的最后一條指令是一條障礙同步指令各處理器均可異步地讀取和寫入全局存儲(chǔ)器，但在同一相（phase）內(nèi)不允許兩個(gè)處理器訪問同一共享單元,2024/3/17,46,處理器 1 處理器 2 處理器 3,read x1

36、read x3 read xnread x2 : : : write to B :write to A write to C write to D,read B read A read C :

37、 : :write to B write to D,: write to C write to Bread D : read A :

38、 : write to B,2024/3/17,47,在APRAM模型上設(shè)計(jì)的算法的時(shí)間復(fù)雜性包括以下幾個(gè)方面：假設(shè)一個(gè)局部操作取為 1 個(gè)單位時(shí)間全局讀/寫時(shí)間為 d，它表示全局讀/寫的平均時(shí)間。該值應(yīng)隨著處理器的個(gè)數(shù)增加而增加。同步障礙的時(shí)間為 B，B 是處理器個(gè)數(shù) p 的非遞減函數(shù) B (p) 。在 APRAM 中常

39、假設(shè)：2 ? d ? B ? p設(shè) tph 為全局相內(nèi)各處理器指令執(zhí)行時(shí)間中最長(zhǎng)者，則整個(gè)程序運(yùn)行時(shí)間 T 應(yīng)為：T = ? tph + B * 同步障礙次數(shù),2024/3/17,48,3. Log P 模型 (Latency , overhead , gap , Processor),1993年D. Culler 等人在分析了分布式存儲(chǔ)計(jì)算機(jī)特點(diǎn)的基礎(chǔ)上，提出了基于點(diǎn)到點(diǎn)通信的多計(jì)算機(jī)模型----Log P模型。該模型雖未

40、涉及到網(wǎng)絡(luò)的具體結(jié)構(gòu)，但充分說明了互聯(lián)網(wǎng)絡(luò)的性能特性：互連網(wǎng)絡(luò)帶寬的限制通信中可觀的延遲它是 MPP 系統(tǒng)的模型,2024/3/17,49,Log P 模型主要由以下4個(gè)參數(shù)來描述：1）L(Latency)最大延遲：在通信時(shí)包含一個(gè)或幾個(gè)字的一個(gè)消息從源節(jié)點(diǎn)傳到目標(biāo)節(jié)點(diǎn)的時(shí)間的上限值。2）o(overhead)開銷：處理器準(zhǔn)備發(fā)送或接收一個(gè)消息的時(shí)間開銷，在這段時(shí)間里處理器不能執(zhí)行其它操作。3）g(gap)間隔：一臺(tái)處理器發(fā)

41、送或接收一組消息時(shí)，兩個(gè)消息之間的最小時(shí)間間隔，其倒數(shù)即為處理器的通信帶寬。4）P(Processor)節(jié)點(diǎn)數(shù)：處理器/存儲(chǔ)器個(gè)數(shù)，假定每個(gè)局部操作需要 1 個(gè)單位時(shí)間（即一個(gè)處理器周期）。,2024/3/17,50,Log P 的參數(shù)示意圖,,Pi,Pk,Pj,處理器,,,,,,,,,,,,,,,o g,L o,,消息,下一個(gè)消息,時(shí)間,發(fā)送并接收一個(gè)消息共需2o+L個(gè)單位時(shí)間; 處理

42、器 Pi 在向處理器 Pj 發(fā)送消息后, 在發(fā)送下一個(gè)消息之前必須等待 g 個(gè)時(shí)間單位。,2024/3/17,51,LogP模型的特點(diǎn)處理機(jī)之間異步地工作，通過消息傳遞實(shí)現(xiàn)同步；消息延遲不確定，但延遲不會(huì)大于L，即任何消息經(jīng)歷的等待時(shí)間是不可預(yù)測(cè)的，但不會(huì)超過L；Log P模型支持了計(jì)算和通信的重疊；能夠預(yù)測(cè)算法的實(shí)際運(yùn)行時(shí)間。Log P模型抓住了網(wǎng)絡(luò)與處理機(jī)之間的性能瓶頸。消息間隔參數(shù) g 反映了通信帶寬，當(dāng)一臺(tái)處理機(jī)發(fā)送的

43、消息已到達(dá)這個(gè)容量限度時(shí)，再發(fā)送的消息將被阻塞。,2024/3/17,52,例2：在通信模式是一棵樹的情況下求和算法,假設(shè)P = 8、L = 5、g = 4、o = 2，我們考慮在時(shí)間為 28 個(gè)單位時(shí)間內(nèi)最多可能求和的個(gè)數(shù)。,2024/3/17,53,4. BSP 模型 (Bulk Synchronous Parallel),BSP 模型是一個(gè)分布存儲(chǔ)的 MIMD 計(jì)算模型BSP 模型的組成主要包括如下部分：1）若干個(gè)能進(jìn)行處理和

44、內(nèi)存操作的處理器，2）一個(gè)用于在處理器之間傳遞消息的路由器，3）在定義的時(shí)間間隔內(nèi)，對(duì)所有處理器進(jìn)行同步的機(jī)制。一般情況下，假設(shè)這個(gè)全局同步機(jī)制是用特殊的硬件支持的。一個(gè) BSP 程序是由一系列超步 (superstep) 組成的。,2024/3/17,54,BSP 模型有以下三個(gè)重要參數(shù)：1）處理器數(shù) p2）路由器吞吐量 g，（也稱為帶寬因子）3）全局同步之間的時(shí)間間隔 L在一個(gè)超步中，一個(gè)處理機(jī)最多發(fā)送 h 個(gè)消息或接

45、收 h 個(gè)消息。若有 h 個(gè)消息，則稱此通信有一個(gè) h 關(guān)系(h-relation)。g 值的定義方式：每秒處理機(jī)所能完成的局部計(jì)算數(shù)與每秒路由器所能傳輸?shù)臄?shù)據(jù)量之比；或在一個(gè) h 關(guān)系中,傳遞h個(gè)消息所需的時(shí)間為 g.h。,2024/3/17,55,BSP 模型與 APRAM 模型類似，使用障礙同步使整個(gè)計(jì)算任務(wù)以緊同步方式進(jìn)行,一個(gè)超步的執(zhí)行時(shí)間：計(jì)算時(shí)間max + gh max + l,2024/3/17,56,BSP 模型

46、的主要特點(diǎn)：將處理器和路由器分開，即把計(jì)算任務(wù)和通信任務(wù)分開。路由器僅進(jìn)行點(diǎn)到點(diǎn)的消息傳遞，不考慮互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)；利用硬件實(shí)現(xiàn)全局障礙同步使并行粒度增大(相對(duì)APRAM而言)，并能夠?qū)崿F(xiàn)緊耦合同步并行算法；兼顧了計(jì)算和通信的平衡問題；硬件可將 L 設(shè)置盡量小----這表示通信帶寬會(huì)更寬些，在設(shè)計(jì)并行算法時(shí)應(yīng)使 L 盡量大從而提高并行粒度。,2024/3/17,57,5. C3 模型(Computing, Communicat

47、ion, Congestion),1994 年S. E. Hambrush 等人在分析高性能可擴(kuò)展的網(wǎng)絡(luò)計(jì)算機(jī)系統(tǒng)特點(diǎn)的基礎(chǔ)上提出了 C3 模型，它適用于粗粒度的并行系統(tǒng)。和 BPS 與 Log P 模型相似， C3 計(jì)算模型也將計(jì)算劃分為一系列超級(jí)步，同步出現(xiàn)在兩個(gè)超級(jí)步之間，這個(gè)同步也是利用障礙同步機(jī)制來實(shí)現(xiàn)。擁塞 (Congestion)：在通信網(wǎng)絡(luò)中，當(dāng)各輸入站的呼叫數(shù)量超過網(wǎng)絡(luò)的容量，或超過了網(wǎng)絡(luò)處理的能力時(shí)，則稱網(wǎng)絡(luò)中發(fā)

48、生了擁塞。,2024/3/17,58,C3 模型主要由以下幾個(gè)參數(shù)來描述：1）處理器的個(gè)數(shù) p；2）網(wǎng)絡(luò)延遲 h：網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)間的距離的平均值；3）網(wǎng)絡(luò)的對(duì)分寬度 b：表示網(wǎng)絡(luò)的帶寬；4）啟動(dòng)時(shí)間 s，即建立一個(gè)消息時(shí)的開銷；5）消息包的長(zhǎng)度 l，即消息包所含字節(jié)數(shù)。消息包是處理機(jī)間通信的基本單位。,2024/3/17,59,C3模型中用到的一些概念,C3 模型中考慮了兩種路由方式：存儲(chǔ)轉(zhuǎn)發(fā)路由方式(store-and-

49、forward mode)：它是網(wǎng)絡(luò)中信息交換的一種方式。轉(zhuǎn)發(fā)中心不是將終端發(fā)出的信息立即傳送到接收終端，而是先存儲(chǔ)起來，等待適當(dāng)?shù)臅r(shí)機(jī)，選擇空閑的信道，并按信息的優(yōu)先級(jí)別轉(zhuǎn)發(fā)到下一個(gè)轉(zhuǎn)發(fā)中心或接收終端。蟲孔(蟲蝕)路由方式(wormhole routing mode)：在平面網(wǎng)絡(luò)結(jié)構(gòu)的多處理機(jī)系統(tǒng)中進(jìn)行路徑選擇的一種方法。它把消息分成若干個(gè)包，包又分成若干個(gè)稱為遷移塊(flit)的基本信息單元。每個(gè)包中的遷移塊以流水線方式向前依次傳

50、送。只有包的頭幾個(gè)遷移塊含有路徑信息，因而一個(gè)包的所有遷移塊必須一個(gè)跟著一個(gè)，而不能被別的消息包打斷。,2024/3/17,60,C3 模型中用到的一些概念,C3 模型中考慮了兩種發(fā)送/接收原語：1）阻塞發(fā)送和接收原語2）非阻塞發(fā)送和接收原語阻塞發(fā)送 (blocking send) ：指一個(gè)源處理器從開始發(fā)送一條消息，直到它被目標(biāo)處理器收到消息，源處理器的發(fā)送操作才結(jié)束。非阻塞的發(fā)送 (non-blocking send) ：

51、源處理器只需將要發(fā)送的消息放在發(fā)送緩沖器。非阻塞的發(fā)送不需考慮目標(biāo)處理器什么時(shí)候接收到信息。,2024/3/17,61,各種并行計(jì)算模型的比較,2024/3/17,62,由于并行計(jì)算機(jī)正在處于飛速發(fā)展中，但尚未定型，因此到現(xiàn)在為止，還沒有一個(gè)通用的并行計(jì)算模型。人們只能將某一類并行機(jī)的基本特征抽象出來，形成各種特定的并行計(jì)算模型，以便并行算法的設(shè)計(jì)與理論分析。,2024/3/17,63,PRAM 模型是對(duì)一類共享的并行機(jī)特征抽取，它拋

52、開了通信的干擾，可用于開發(fā)細(xì)粒度并行算法；Log P 模型是對(duì)一類分布式并行計(jì)算機(jī)特征抽取，基于點(diǎn)對(duì)點(diǎn)通信的計(jì)算模型，集中分析處理機(jī)與網(wǎng)絡(luò)之間的瓶頸問題；C3 模型是對(duì)一類基于消息傳遞的分布式粗粒度系統(tǒng)特征抽取，集中反映的是網(wǎng)絡(luò)擁擠和路由影響。,2024/3/17,64,例1_1：在PRAM-EREW計(jì)算機(jī)上對(duì)兩個(gè) N 維向量 A 和 B 求內(nèi)積 s。假設(shè)用 p 個(gè)處理機(jī)完成該任務(wù)，并設(shè) N/p 是整數(shù)，內(nèi)積的值在 LocalVal

53、 [0] 中。,VECTORMUL(PRAM-EREW): Global N, i, A[0..N-1], B[0..N-1], LocalVal[0..p-1] Local jbegin spawn(P0, P1, P2, …, Pp-1) for all Pi, 其中 0 ? i ? p-1 do begin LocalVal[i] = 0; for j =

54、 i; j < N step p do LocalVal[i] = LocalVal[i] + A[j] * B[j]; for j = 0 to ?log p? -1 do if i mod 2j+1 == 0 and i+ 2j <p then LocalVal[i] = LocalVal[i] + LocalVal[i

55、+ 2j] end;end,2024/3/17,65,該算法的執(zhí)行時(shí)間：假設(shè)一次乘法和加法各用一個(gè)單位時(shí)間激活p個(gè)處理機(jī)的時(shí)間： ?log p? ---spawn(P0, P1, P2, …, Pp-1) 各處理機(jī)計(jì)算局部和的時(shí)間：2N / p-------for j = i; j >p時(shí)，該P(yáng)RAM算法的加速比為：2N/ (2 ?log p? + 2N / p ) → p,2024/3/17,66,例1_2：

56、在 APRAM 計(jì)算模型上對(duì)兩個(gè) N 維向量 A 和 B 求內(nèi)積。算法思想：整個(gè)算法僅需一個(gè)全局相。將數(shù)據(jù)分散在各個(gè)處理機(jī)的局部存儲(chǔ)器中；在全局相中：局部計(jì)算：每個(gè)處理機(jī)在 2N / p 個(gè)單位時(shí)間內(nèi)計(jì)算出局部和。全局計(jì)算：將各個(gè)處理機(jī)的局部和放到全局存儲(chǔ)器中，并求總和。 執(zhí)行時(shí)間= ? ( pd + p ) 障礙同步。時(shí)間為B。,2024/3/17,67,例1_3：在BSP計(jì)算機(jī)上對(duì)兩個(gè) N 維向量 A 和 B 求內(nèi)

57、積。假設(shè)用 p =8個(gè)處理機(jī)完成該任務(wù)，用4個(gè)超步完成問題的求解。超步1：計(jì)算：每個(gè)處理機(jī)在 2N / 8 個(gè)單位時(shí)間內(nèi)計(jì)算出局部和。通信：處理機(jī) 0，2，4，6 將其局部和送給處理機(jī) 1，3，5，7。完成1-relation 通信。障礙同步。超步2：計(jì)算：處理機(jī)1，3，5，7各自完成一次加法。通信：處理機(jī) 1，5 將其局部和送給處理機(jī) 3，7。完成1-relation通信。障礙同步。超步3：計(jì)算：處理機(jī)3，7各自完

58、成一次加法。通信：處理機(jī) 3 將其局部和送給處理機(jī)7。完成1-relation通信。障礙同步。超步4：計(jì)算：處理機(jī)7完成一次加法，產(chǎn)生最終結(jié)果。不再需要通信和同步。,2024/3/17,68,該算法各個(gè)超步的執(zhí)行時(shí)間：超步1：2N / 8 + g + l 超步2：1 + g + l超步3：1 + g + l超步4：1該算法總的執(zhí)行時(shí)間：2N / 8 + 3g + 3l + 3若處理機(jī)的個(gè)數(shù)為 p，則算法總的執(zhí)行時(shí)