適合于數(shù)字信號處理的并行處理算法與結(jié)構(gòu)

1、高性能計算機的體系結(jié)構(gòu)與程序優(yōu)化,唐志敏中國科學院計算技術(shù)研究所,提綱,應(yīng)用編程與體系結(jié)構(gòu)的關(guān)系高性能計算機體系結(jié)構(gòu)概述CPU內(nèi)的并行結(jié)構(gòu)（指令級并行）存儲器的層次結(jié)構(gòu)多體交叉的并行存儲系統(tǒng)分布存儲系統(tǒng)中的通信優(yōu)化,體系結(jié)構(gòu)的位置,體系結(jié)構(gòu)是硬件和系統(tǒng)軟件之間的界面Enable High PerformanceSupport Ease Programming編程模型是應(yīng)用和計算機系統(tǒng)間的界面理想的模型: 應(yīng)用不必了

2、解具體的結(jié)構(gòu)特征,體系結(jié)構(gòu)的主要研究內(nèi)容,如何提高性能?先進的工藝技術(shù)－－純粹屬于硬件的范圍？技術(shù)方面的缺點需要通過結(jié)構(gòu)來彌補DRAM慢，SRAM?。健反鎯ζ鲗哟谓Y(jié)構(gòu)體系結(jié)構(gòu)方面的革新各個級別上并行性的開發(fā)如何支持編程?共享內(nèi)存承擔一些軟件較難完成的優(yōu)化工作如動態(tài)執(zhí)行, 猜測執(zhí)行, COMA等,三種類型的體系結(jié)構(gòu)技術(shù),保守的結(jié)構(gòu)硬件僅提供必需的設(shè)施, 如大量的寄存器高性能能否最終達到, 完全依賴軟件折衷的結(jié)構(gòu)硬

3、件做一些動態(tài)的優(yōu)化, 如高速緩存軟件仍有優(yōu)化的余地包攬式的結(jié)構(gòu)硬件試圖做充分的動態(tài)優(yōu)化, 如COMA認為軟件在動態(tài)分析和優(yōu)化方面能力有限,結(jié)點內(nèi)并行：超長指令字結(jié)構(gòu),芯片面積主要用于功能部件和高速緩存完全依賴編譯程序開發(fā)指令級并行性分支預測, 循環(huán)展開, 軟件流水, 蹤跡調(diào)度指令系統(tǒng)結(jié)構(gòu)不兼容 顯式并行指令結(jié)構(gòu)（EPIC）Explicitly Parallel Instruction Computer 128位的Gr

4、oup包括3條指令設(shè)置專門的域指示指令間是否存在依賴關(guān)系可連接多個Group以支持更大范圍內(nèi)的并行,結(jié)點內(nèi)并行：同時多線程結(jié)構(gòu),由硬件提供快速的上下文切換機制引入了更多的指令級和線程級并行性容忍遠程訪問延遲和數(shù)據(jù)依賴的負面影響多個上下文之間的切換機制發(fā)生事件時切換(有點象進程的切換)每個時鐘周期都切換: 每次取不同線程的指令多個線程的指令在同一流水線中(無依賴)第一個多線程系統(tǒng)(Tera)已經(jīng)問世多線程同時工作對ca

5、che干擾很大,結(jié)點內(nèi)并行超標量、動態(tài)調(diào)度、猜測執(zhí)行,硬件動態(tài)地分析指令流，同時執(zhí)行多條指令在分析區(qū)間內(nèi)，指令以數(shù)據(jù)流的方式執(zhí)行彌補編譯器在靜態(tài)分析和調(diào)度方面的不足換代后目標碼不重新編譯也能獲得較好的性能需要發(fā)掘指令級并行性的新來源精確的動態(tài)分支預測，消除分支損耗設(shè)置大量換名寄存器，消除虛假的數(shù)據(jù)依賴不等分支完成，就開始執(zhí)行目標指令（猜測）同時執(zhí)行分支的多個目標（多標量）,結(jié)點間并行：消息傳遞系統(tǒng),Tcomm = Ts

6、tartup + Tblock + Ncomm/Bcomm如何實現(xiàn)與處理能力匹配的通信帶寬通信帶寬、通信延遲對應(yīng)用性能的影響光互連技術(shù)如何減少通信開銷用戶級通信硬件支持重試、保證通信的可靠性和順序如何減少阻塞自適應(yīng)路由、優(yōu)化應(yīng)用的通信結(jié)構(gòu),結(jié)點間并行：共享存儲系統(tǒng),共享存儲的好處易于編程、通用性強與SMP及其應(yīng)用實現(xiàn)無縫銜接存儲一致性模型與實現(xiàn)效率松(弱)一致性模型允許多種優(yōu)化對系統(tǒng)軟件設(shè)計或應(yīng)用程序設(shè)計提出新

7、的要求?如何避免、隱藏或容忍遠程訪問的開銷Origin2000: 185周期; 未來可能達數(shù)百萬個周期緩存、預取、預送、多線程,結(jié)點間并行：COMA,CC-NUMA的主要問題數(shù)據(jù)靜態(tài)地分配在home結(jié)點上通過遠程訪問cache存取非本地的數(shù)據(jù)數(shù)據(jù)分配不當會造成大量的數(shù)據(jù)傳輸COMA中沒有物理地址, 數(shù)據(jù)可動態(tài)遷移經(jīng)過“預熱”, 數(shù)據(jù)將被“吸引”到處理結(jié)點附近主要問題: 不命中時如何快速找到所需數(shù)據(jù)全系統(tǒng)的查找需大量時

8、間ProbOwner目錄, Approximate Copyset,存儲器的供數(shù)率跟得上嗎？,CPU消耗數(shù)據(jù)的速率遠大于存儲器供數(shù)率時鐘頻率增長的速度大于訪存時間縮短的速度同時執(zhí)行多條指令要求供數(shù)率進一步提高多線程或芯片內(nèi)多處理器要求訪問多組數(shù)據(jù)已知的解決方案：存儲器層次結(jié)構(gòu)片內(nèi)cache的供數(shù)率能滿足指令級并行的要求?片內(nèi)cache的命中率足夠高?為多個線程或處理器提供各自的cache?如何通過程序或算法的改進增強訪

9、存局部性?,性能不僅依賴于結(jié)構(gòu),性能的提高依賴于體系結(jié)構(gòu)上的革新硬件技術(shù)的發(fā)展對體系結(jié)構(gòu)提出了新的要求各個層次并行性的開發(fā)是新體系結(jié)構(gòu)的主要特征實際性能的提高更依賴于體系結(jié)構(gòu)與編譯技 術(shù)、操作系統(tǒng)、應(yīng)用算法間的配合與協(xié)調(diào)Architectural Support for Programming Languages and Operating Systems, Since 1988未來系統(tǒng)中兩大問題的解決也是如此①極長的等待時

10、間；②極大的并行度,充分利用處理器內(nèi)的并行,提高單機性能是提高并行機性能的基礎(chǔ)目前CPU內(nèi)部常用的并行結(jié)構(gòu)包括：指令流水線與運算流水線多個功能部件并行執(zhí)行如：定點運算、存/取、浮點加、浮點乘、…充分流水、并行工作的條件指令間沒有相關(guān)，即相互獨立結(jié)構(gòu)相關(guān)：兩條指令要用同一個部件數(shù)據(jù)相關(guān)：一條指令要用另一條指令的結(jié)果控制相關(guān)：條件轉(zhuǎn)移指令影響其它指令,發(fā)揮CPU內(nèi)并行性的主要手段,編譯程序：靜態(tài)指令調(diào)度分析程序中的指令流

11、在不影響結(jié)果的前提下，對指令重新排序缺點：不能獲得運行時的動態(tài)信息改進：基于profile的指令調(diào)度或優(yōu)化硬件：超標量、動態(tài)指令調(diào)度由專用硬件檢查即將執(zhí)行的一段指令挑選出源操作數(shù)和功能部件都已齊備的指令缺點：硬件會變得很復雜、降低時鐘頻率,假設(shè)：取數(shù)時間較長，后續(xù)指令不能立即使用源程序語句：a = b + c; d = e - f;a, b, c, d ,e, f 都在存儲器中. Slow code:LW

12、Rb,bLW Rc,cADD Ra,Rb,RcSW a,Ra LW Re,e LW Rf,fSUB Rd,Re,RfSWd,Rd,指令調(diào)度的例子,Fast code:LW Rb,bLW Rc,cLW Re,e ADD Ra,Rb,RcLW Rf,fSW a,Ra SUB Rd,Re,RfSWd,Rd,,,應(yīng)用程序

13、員可以做什么？,仔細地研究編譯器的優(yōu)化功能和選項-O2, -O3, -finline-functions, -funroll-loops充分利用已經(jīng)優(yōu)化過的庫函數(shù)如BLAS等如果可能，找或編適合自己需要的高效率庫做一些源程序級的優(yōu)化最典型的一種優(yōu)化：循環(huán)展開為編譯程序的優(yōu)化提供更多的機會,循環(huán)展開的例子,展開前的代碼DO 10 I = 1, N10 Y(I) = A*X(I) + Y(I)這是一種常見的寫法循環(huán)體

14、里包含的運算量較?。?加、1乘）循環(huán)控制意味著轉(zhuǎn)移如果CPU一拍能做4個浮點運算，這個循環(huán)的性能就不高了,展開4次后的代碼DO 10 I = 1，N，4Y(I)=A*X(I)+Y(I)Y(I+1)=A*X(I+1)+Y(I+1)Y(I+2)=A*X(I+2)+Y(I+2)10 Y(I+3)=A*X(I+3)+Y(I+3)暴露出了更多的可同時執(zhí)行的操作不好看，但實用,運算順序的調(diào)整,通常的算法設(shè)計和程序?qū)崿F(xiàn)中，人

15、們習慣在需要某數(shù)據(jù)的地方才計算出該數(shù)據(jù)的值，緊接著使用該數(shù)據(jù)。這是很自然的思維習慣，但對于流水線則會造成麻煩。兩個運算相繼進行，但后一個運算需要的操作數(shù)還沒有被計算出來，只有原地等待，造成了流水線的停滯。,運算順序的調(diào)整,如下例所示：b[0]=a[0]*a[0];c[0]=1/b[0];b[1]=a[1]*a[1];c[1]=1/b[1];b[2]=a[2]*a[2];c[2]=1/b[2];……是求一系列數(shù)的平方的

16、倒數(shù)的操作。雖然因為c[0]緊接著b[0]計算，讓計算的內(nèi)在含義更明顯，也更符合通常的思維習慣，但對于流水線來說效率極差。,運算順序的調(diào)整,現(xiàn)在變動如下： b[0]=a[0]*a[0];b[1]=a[1]*a[1];b[2]=a[2]*a[2];……c[0]=1/b[0];c[1]=1/b[1];c[2]=1/b[2];……,調(diào)整以后，先是整個的把數(shù)組b[]計算出來，然后再計算數(shù)組c[]，此時，需要的b[]數(shù)組中的數(shù)據(jù)都

17、已經(jīng)計算出來了，就不會存在流水線停滯的問題。,更一般的形式,原始循環(huán)DO 10 I = 1, NB(I) = A(I) * A(I)10 C(I) = 1 / B(I)優(yōu)化后的循環(huán)DO 10 I = 1, N10 B(I) = A(I) * A(I)DO 20 I = 1, N20 C(I) = 1 / B(I)又稱為循環(huán)拆分,進一步優(yōu)化DO 10 I = 1, N, 3B(I) = A(I

18、) * A(I)B(I+1)=A(I+1)*A(I+1)B(I+2)=A(I+2)*A(I+2)C(I) = 1 / B(I)C(I+1) = 1 / B(I+1)10C(I+2) = 1 / B(I+2)先展開，再調(diào)整順序,存儲器的層次結(jié)構(gòu),彌補CPU與主存間的速度差異各個層次間的訪問速度和容量差別寄存器：32個；幾乎不需要時間一級cache：16KB-128KB；1個時鐘周期二級cache：128KB-

19、4MB；幾個時鐘周期本地主存：64MB-1GB；幾十個時期周期遠程主存：512MB以上；成百上千個周期硬盤對換區(qū)（虛存）：成千上萬個周期,存儲層次發(fā)揮作用的基本原理,程序的訪存局部性（locality）時間局部性：最近訪問的，將來還要訪問空間局部性：訪問了A，則要訪問A的近鄰局部性使快速存儲區(qū)的內(nèi)容多次被訪問比喻：80%的時間花在20%的代碼上工作集：最近程序集中訪問的地址空間調(diào)整程序結(jié)構(gòu)，使工作集小于cache容量,

20、寄存器的使用,寄存器的使用基本上是可以控制的在匯編子程序里完全可以控制在C語言里用register說明用得最多的變量需要考慮CPU內(nèi)通用寄存器和浮點寄存器的數(shù)量編譯程序在生成代碼前，會進行寄存器分配程序設(shè)計與優(yōu)化時，可考慮寄存器利用最內(nèi)層循環(huán)體不宜過長，寄存器會不夠用循環(huán)展開的次數(shù)不能太多,寄存器的使用,for ( k=0;k<10;k++){ for (j=0;j<1000;j++) 執(zhí)行運算過

21、程B；}運算過程B的大小也是我們必須考慮的。如果B過大，CPU內(nèi)部寄存器的壓力就會很大，如果寄存器的數(shù)量不足以保存B中出現(xiàn)的所有數(shù)據(jù)，可能會出現(xiàn)顛簸的現(xiàn)象，剛剛從寄存器中換出的數(shù)據(jù)也許就是下一個需要的數(shù)據(jù)，還得重新讀入寄存器，這對效率顯然是有影響的。解決的辦法是將循環(huán)體過大的循環(huán)拆分成若干循環(huán)體較小的循環(huán)，這種方法叫做循環(huán)分布，循環(huán)體拆分的粒度是以寄存器數(shù)量的多少為參考的。,寄存器的使用,根據(jù)運算過程B的實際情況和并行環(huán)境的特點，可

22、以拆分為以下兩種形式中的一種。 形式A：for(k=0;k<10;k++) { for(j=0;j<1000;j++) 執(zhí)行運算過程B1； for(j=0;j<1000;j++) 執(zhí)行運算過程B2；},寄存器的使用,形式B：for(k=0;k<10;k++){ for(j=0;j<1000;j++) 執(zhí)行運算過程B1；}for(k=0;k<10;k

23、++){ for(j=0;j<1000;j++) 執(zhí)行運算過程B2；}形式A比較符合人們的習慣思維方式，形式B對循環(huán)的拆分更徹底，更加有利于并行執(zhí)行。,高速緩沖存儲器(cache),自然地利用局部性，對程序員“透明”存放最近最常用的數(shù)據(jù)和指令Cache的工作規(guī)則基本單位：塊(block)、行(line)放置策略：直接映射、組相聯(lián)、全相聯(lián)衡量cache效果的主要指標：命中率若命中率為90%, 不命中時需要

24、另花10個周期則平均訪存時間為：1+10%*10 = 2 周期即存儲系統(tǒng)的速度是cache速度的1/2,Cache中塊的放置策略,Block 12 placed in 8 block cache:全相聯(lián)、直接映射、2路組相聯(lián)組號 = 塊號 % 組數(shù),Memory,Cache,8路組相聯(lián),1路組相聯(lián),2路組相聯(lián),只有1個組,共有8個組,共有4個組,Cache不命中的三個原因(3C),首次訪問Compulsory Cache中沒有這

25、個塊，必須從內(nèi)存取入 Misses in even an Infinite Cache容量不足Capacity 換出后又被取入cacheMisses in Fully Associative Size X Cache沖突Conflict 組相聯(lián)或直接映射cache中，映射到同一組的內(nèi)存塊數(shù)過多，導致某些塊換出后又被取入 Misses in N-way Associative, Size X Cache,調(diào)整程序以提高cache

26、命中率,代碼（指令）重新安排程序中不同過程在內(nèi)存中的位置更適合編譯程序，在profile的幫助下做數(shù)據(jù)：程序設(shè)計者大有可為數(shù)組合并: 利用塊長，改善空間局部性循環(huán)交換: 改變嵌套循環(huán)中訪問內(nèi)存的次序循環(huán)合并: 增強數(shù)據(jù)的可重用性（時間局部性）分塊: 集中訪問可取入cache的塊狀矩陣，避免全行或全列的讀寫，以增強時間局部性,數(shù)組合并的例子,/* Before: 2 sequential arrays */int val[

27、SIZE]; int key[SIZE];/* After: 1 array of stuctures */struct merge {int val;int key;};struct merge merged_array[SIZE];Reducing conflicts between val & key; improve spatial locality,循環(huán)交換的例子,/* Before */for

28、 (k = 0; k < 100; k = k+1)for (j = 0; j < 100; j = j+1)for (i = 0; i < 5000; i = i+1)x[i][j] = 2 * x[i][j];/* After */for (k = 0; k < 100; k = k+1)for (i = 0; i < 5000; i = i+1)for (j = 0;

29、j < 100; j = j+1)x[i][j] = 2 * x[i][j];將步長為100字的跳躍式訪問變?yōu)轫樞蛟L問，增強了空間局部性,,循環(huán)合并的例子,/* Before */for (i = 0; i < N; i = i+1)for (j = 0; j < N; j = j+1)a[i][j] = 1/b[i][j] * c[i][j];for (i = 0; i < N; i =

30、 i+1)for (j = 0; j < N; j = j+1)d[i][j] = a[i][j] + c[i][j];/* After */for (i = 0; i < N; i = i+1)for (j = 0; j < N; j = j+1){a[i][j] = 1/b[i][j] * c[i][j];d[i][j] = a[i][j] + c[i][j];}訪問a和c的2次不命

31、中降為1次,分塊的例子,/* Before */for (i = 0; i < N; i = i+1)for (j = 0; j < N; j = j+1){r = 0; for (k = 0; k < N; k = k+1){r = r + y[i][k]*z[k][j];}; x[i][j] = r;};兩個內(nèi)層循環(huán)中:讀了z[ ]的所有NxN個元素重復讀y[ ]的某一行

32、N次，寫x[ ]的某一行1次不命中次數(shù)是N及cache大小的函數(shù)當3 NxNx4 小于cache容量時，沒有不命中分塊的思想：計算cache中放得下的 BxB子矩陣,,,,,,,,,分塊的例子,/* After */for (jj = 0; jj < N; jj = jj+B)for (kk = 0; kk < N; kk = kk+B)for (i = 0; i < N; i = i+1) for (

33、j = jj; j < min(jj+B-1,N); j = j+1){r = 0; for (k = kk; k < min(kk+B-1,N); k = k+1) {r = r + y[i][k]*z[k][j];}; x[i][j] = x[i][j] + r;};B稱為分塊因子Blocking Factor不命中數(shù)從 2N3 + N2 降到 2N3/B +N2但還存在因沖突導致的

34、不命中,減少因分塊導致的沖突不命中,需要對分塊后形成的子矩陣進行重新布置,分塊的性能提高,矩陣乘法：N=500在i860上分塊前，運行時間為77.00秒分塊后，運行時間為22.41秒，加速比3.44在Pentium 166MMX上分塊前，運行時間為28.52秒分塊后，運行時間為6.67秒，加速比4.22,多體交叉并行存儲系統(tǒng),提高主存帶寬的重要途徑多個獨立的存儲體，統(tǒng)一編址，同時工作訪問均勻地分布在所有體內(nèi)時，帶寬線性提

35、高地址分配方式：word interleave,并行存儲器中的訪問沖突,基本條件：體數(shù)不小于訪存所需要的時鐘周期數(shù)，以保證順序訪問時不會有體沖突體數(shù)增大時，沖突的機會會少一些，但成本增加了體數(shù)正好等于訪存周期數(shù)時，有下面的結(jié)論考慮固定步長的訪問序列A, A+S, A+2S, A+3S, ...若一共有N個存儲模塊，則該訪問序列集中在若GCD(N, S) = 1, 則沖突訪問的概率最小因為N一般是2的冪次，所以S最好不是

36、2的冪次,對數(shù)組元素的沖突訪問,在C語言中，數(shù)組元素按行存放，按列訪問時會產(chǎn)生沖突在FORTRAN中，按列存放，按行訪問時會產(chǎn)生沖突其它導致沖突的情形矩陣中的一個長方形塊FFT算法中存取步長依次為2i, i = 0, 1, 2, …減少沖突的方法（與cache優(yōu)化類似）循環(huán)交換、數(shù)組加邊,并行處理概述,利用多個部件完成同一個任務(wù)并行處理的好處提高性能：縮短解題時間，擴大解題規(guī)模降低成本：與同樣性能的單機相比容錯：更高

37、的可用性并行處理的層次處理機內(nèi)：指令級并行，多功能部件處理機間：多處理機，多計算機,多機并行的基本形式,按指令流與數(shù)據(jù)流的數(shù)量來劃分單指令流多數(shù)據(jù)流（SIMD）多指令流多數(shù)據(jù)流（MIMD）按機間的互連方式來劃分總線結(jié)構(gòu)、交叉開關(guān)、網(wǎng)格結(jié)構(gòu)、超立方體樹型結(jié)構(gòu)、星型結(jié)構(gòu)按存儲器的組織方式來劃分集中式存儲，通常是為多個處理機共享分布式存儲，通常是各個處理機私有的,兩種基本的結(jié)構(gòu),互連網(wǎng)絡(luò)（總線、開關(guān)等）,,,,,,,,,

38、P1,Pn,M1,Mn,分布存儲的結(jié)構(gòu)適合任務(wù)間并行,互連網(wǎng)絡(luò)（總線、開關(guān)等）,,,,,,,,,P1,Pn,M1,Mn,共享存儲的結(jié)構(gòu)適合任務(wù)間、任務(wù)內(nèi)并行,并行處理的過程：矩陣乘法,A ? B = C的過程可分為四個獨立的部分：Ai ? B = Ci，i = 1, 2, 3, 4每部分包含的運算可由一臺處理機單獨完成在集中存儲的系統(tǒng)中，同時訪問B會導致沖突在分布存儲的系統(tǒng)中，B的分散存儲會導致通信,,,,,,,,,,A

39、,B,C,X,=,A1,A2,A3,A4,C1,C2,C3,C4,并行處理的性能,加速比：串行計算時間除以并行計算時間加速比小于處理單元數(shù)目的原因：存在不可并行成分：Speedup < 1/s負載不均衡：有些處理機沒事做通信開銷：包括傳遞消息、訪存沖突等同步開銷：為了步調(diào)一致，必須相互等待極端的情況：并行后的性能比單機還差也可能出現(xiàn)超線性的加速比,并行粒度：在哪個級別上并行？,子任務(wù)級的并行（粗粒度）例如：方位FF

40、T、距離FFT、距離IFFT、方位IFFT各由一個處理機完成，形成宏觀流水子任務(wù)的運算量差別較大時，不易實現(xiàn)負載的平衡數(shù)據(jù)級的并行（中等粒度或細粒度）對問題相關(guān)的數(shù)據(jù)場進行劃分，每個處理器負責整個數(shù)據(jù)場的一小部分各部分間耦合較多時，對存儲器及互連網(wǎng)絡(luò)的性能要求較高,并行算法設(shè)計,并行算法設(shè)計的目標開發(fā)問題求解過程中的并行性尋求并行算法與并行結(jié)構(gòu)的最佳匹配合理地組織并行任務(wù)，減少額外的開銷并行化的主要方法：分而治之根據(jù)問

41、題的求解過程，把任務(wù)分成若干子任務(wù)根據(jù)處理數(shù)據(jù)的方式，形成多個相對獨立的數(shù)據(jù)區(qū)，由不同的處理器分別處理將一個循環(huán)分成多個循環(huán)并行地執(zhí)行,并行計算機設(shè)計程序的三種方式,串行程序的自動并行化用戶提供常規(guī)的串行程序，編譯器完成并行化由于編譯器能力有限，只對部分應(yīng)用有效使用全新的并行語言：函數(shù)型、數(shù)據(jù)流等已有應(yīng)用程序需要全部改寫新語言的實現(xiàn)效率有待進一步提高串行語言+并行化擴充增加支持并行性開發(fā)與通信同步的庫調(diào)用增加新的語言

42、成分，如數(shù)組運算、并行循環(huán)等SPMD (Single Program Multiple Data)編程模式,例子：矩陣乘法（串行）,double a[N][N],b[N][N],c[N][N];for (i=0; i<N; i++)for (j=0; j<N; j++)for (k=0; k<N; k++)c[i][j]+=a[i][k]*b[k][j];,例子：矩陣乘法（并行1）一開始就有P

43、個并行進程,myid的值為0,1,...,P-1begin=N*myid/P;end=N*(myid+1)/P;for (i=begin; i<end; i++)for (j=0; j<N; j++)for (k=0; k<N; k++) c[i][j]+=a[i][k]*b[k][j];,例子：矩陣乘法（并行2）一開始只有一個進程在運行,在main函數(shù)內(nèi)：for (i=0; i<P

44、; i++)fork(subp,N*i/P,N*(i+1)/P)在subp(int begin, int end)函數(shù)內(nèi)：for (i=begin; i<end; i++)for (j=0; j<N; j++)for (k=0; k<N; k++) c[i][j]+=a[i][k]*b[k][j];,例子：矩陣乘法（并行3）一開始只有一個進程在運行,forall循環(huán)中的所有迭代均可并