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

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

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

3、件做一些動(dòng)態(tài)的優(yōu)化, 如高速緩存軟件仍有優(yōu)化的余地包攬式的結(jié)構(gòu)硬件試圖做充分的動(dòng)態(tài)優(yōu)化, 如COMA認(rèn)為軟件在動(dòng)態(tài)分析和優(yōu)化方面能力有限,結(jié)點(diǎn)內(nèi)并行：超長指令字結(jié)構(gòu),芯片面積主要用于功能部件和高速緩存完全依賴編譯程序開發(fā)指令級(jí)并行性分支預(yù)測(cè), 循環(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)系可連接多個(gè)Group以支持更大范圍內(nèi)的并行,結(jié)點(diǎn)內(nèi)并行：同時(shí)多線程結(jié)構(gòu),由硬件提供快速的上下文切換機(jī)制引入了更多的指令級(jí)和線程級(jí)并行性容忍遠(yuǎn)程訪問延遲和數(shù)據(jù)依賴的負(fù)面影響多個(gè)上下文之間的切換機(jī)制發(fā)生事件時(shí)切換(有點(diǎn)象進(jìn)程的切換)每個(gè)時(shí)鐘周期都切換: 每次取不同線程的指令多個(gè)線程的指令在同一流水線中(無依賴)第一個(gè)多線程系統(tǒng)(Tera)已經(jīng)問世多線程同時(shí)工作對(duì)ca

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

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

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

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

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

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

11、在不影響結(jié)果的前提下，對(duì)指令重新排序缺點(diǎn)：不能獲得運(yùn)行時(shí)的動(dòng)態(tài)信息改進(jìn)：基于profile的指令調(diào)度或優(yōu)化硬件：超標(biāo)量、動(dòng)態(tài)指令調(diào)度由專用硬件檢查即將執(zhí)行的一段指令挑選出源操作數(shù)和功能部件都已齊備的指令缺點(diǎn)：硬件會(huì)變得很復(fù)雜、降低時(shí)鐘頻率,假設(shè)：取數(shù)時(shí)間較長，后續(xù)指令不能立即使用源程序語句：a = b + c; d = e - f;a, b, c, d ,e, f 都在存儲(chǔ)器中. 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、員可以做什么？,仔細(xì)地研究編譯器的優(yōu)化功能和選項(xiàng)-O2, -O3, -finline-functions, -funroll-loops充分利用已經(jīng)優(yōu)化過的庫函數(shù)如BLAS等如果可能，找或編適合自己需要的高效率庫做一些源程序級(jí)的優(yōu)化最典型的一種優(yōu)化：循環(huán)展開為編譯程序的優(yōu)化提供更多的機(jī)會(huì),循環(huán)展開的例子,展開前的代碼DO 10 I = 1, N10 Y(I) = A*X(I) + Y(I)這是一種常見的寫法循環(huán)體

14、里包含的運(yùn)算量較?。?加、1乘）循環(huán)控制意味著轉(zhuǎn)移如果CPU一拍能做4個(gè)浮點(diǎn)運(yùn)算，這個(gè)循環(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)暴露出了更多的可同時(shí)執(zhí)行的操作不好看，但實(shí)用,運(yùn)算順序的調(diào)整,通常的算法設(shè)計(jì)和程序?qū)崿F(xiàn)中，人

15、們習(xí)慣在需要某數(shù)據(jù)的地方才計(jì)算出該數(shù)據(jù)的值，緊接著使用該數(shù)據(jù)。這是很自然的思維習(xí)慣，但對(duì)于流水線則會(huì)造成麻煩。兩個(gè)運(yùn)算相繼進(jìn)行，但后一個(gè)運(yùn)算需要的操作數(shù)還沒有被計(jì)算出來，只有原地等待，造成了流水線的停滯。,運(yùn)算順序的調(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ù)的操作。雖然因?yàn)閏[0]緊接著b[0]計(jì)算，讓計(jì)算的內(nèi)在含義更明顯，也更符合通常的思維習(xí)慣，但對(duì)于流水線來說效率極差。,運(yùn)算順序的調(diào)整,現(xiàn)在變動(dòng)如下： 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)整以后，先是整個(gè)的把數(shù)組b[]計(jì)算出來，然后再計(jì)算數(shù)組c[]，此時(shí)，需要的b[]數(shù)組中的數(shù)據(jù)都

17、已經(jīng)計(jì)算出來了，就不會(huì)存在流水線停滯的問題。,更一般的形式,原始循環(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)拆分,進(jì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)整順序,存儲(chǔ)器的層次結(jié)構(gòu),彌補(bǔ)CPU與主存間的速度差異各個(gè)層次間的訪問速度和容量差別寄存器：32個(gè)；幾乎不需要時(shí)間一級(jí)cache：16KB-128KB；1個(gè)時(shí)鐘周期二級(jí)cache：128KB-

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

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

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

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

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

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

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

26、命中率,代碼（指令）重新安排程序中不同過程在內(nèi)存中的位置更適合編譯程序，在profile的幫助下做數(shù)據(jù)：程序設(shè)計(jì)者大有可為數(shù)組合并: 利用塊長，改善空間局部性循環(huán)交換: 改變嵌套循環(huán)中訪問內(nèi)存的次序循環(huán)合并: 增強(qiáng)數(shù)據(jù)的可重用性（時(shí)間局部性）分塊: 集中訪問可取入cache的塊狀矩陣，避免全行或全列的讀寫，以增強(qiáng)時(shí)間局部性,數(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問，增強(qiáng)了空間局部性,,循環(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;};兩個(gè)內(nèi)層循環(huán)中:讀了z[ ]的所有NxN個(gè)元素重復(fù)讀y[ ]的某一行

32、N次，寫x[ ]的某一行1次不命中次數(shù)是N及cache大小的函數(shù)當(dāng)3 NxNx4 小于cache容量時(shí)，沒有不命中分塊的思想：計(jì)算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但還存在因沖突導(dǎo)致的

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

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

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

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

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

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

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

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

42、成分，如數(shù)組運(yùn)算、并行循環(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、個(gè)并行進(jìn)程,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）一開始只有一個(gè)進(jìn)程在運(yùn)行,在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）一開始只有一個(gè)進(jìn)程在運(yùn)行,forall循環(huán)中的所有迭代均可并