高性能計(jì)算導(dǎo)論并行計(jì)算性能評(píng)價(jià)課件

并行計(jì)算性能評(píng)價(jià)并行計(jì)算性能評(píng)價(jià)上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院

計(jì)算的本質(zhì)串行計(jì)算模型—圖靈機(jī)并行計(jì)算模型

計(jì)算效能評(píng)價(jià)計(jì)算模型與效能評(píng)價(jià)高性能計(jì)算導(dǎo)論上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院計(jì)算的本質(zhì)計(jì)算模型與效能評(píng)價(jià)高“并行計(jì)算”研究的四大分支并行計(jì)算機(jī)體系結(jié)構(gòu)并行算法并行程序設(shè)計(jì)并行計(jì)算的性能評(píng)測(cè)而介于并行計(jì)算機(jī)體系結(jié)構(gòu)與并行算法之間的是并行計(jì)算模型。“并行計(jì)算”研究的四大分支并行計(jì)算機(jī)體系結(jié)構(gòu)PerformanceEvaluation并行計(jì)算效能評(píng)價(jià)PerformanceEvaluation并行計(jì)算效能評(píng)價(jià)程序性能評(píng)價(jià)與優(yōu)化給定并行算法，采用并行程序設(shè)計(jì)平臺(tái)，通過(guò)并行實(shí)現(xiàn)獲得實(shí)際可運(yùn)行的并行程序后，一個(gè)重要的工作就是，在并行機(jī)上運(yùn)行該程序，評(píng)價(jià)該程序的實(shí)際性能，揭示性能瓶頸，指導(dǎo)程序的性能優(yōu)化。性能評(píng)價(jià)和優(yōu)化是設(shè)計(jì)高效率并行程序必不可少的重要工作。程序性能評(píng)價(jià)與優(yōu)化給定并行算法，采用并行程序設(shè)計(jì)平臺(tái)，通過(guò)并并行程序執(zhí)行時(shí)間評(píng)價(jià)并行程序的性能之前，必須清楚并行程序的執(zhí)行時(shí)間是由哪些部分組成的。眾所周知，獨(dú)享處理器資源時(shí)，串行程序的執(zhí)行時(shí)間近似等于程序指令執(zhí)行花費(fèi)的CPU時(shí)間。但是，并行程序相對(duì)復(fù)雜，其執(zhí)行時(shí)間（executiontime）等于從并行程序開(kāi)始執(zhí)行，到所有進(jìn)程執(zhí)行完畢，墻上時(shí)鐘走過(guò)的時(shí)間，也稱之為墻上時(shí)間（walltime）。對(duì)各個(gè)進(jìn)程，墻上時(shí)間可進(jìn)一步分解為：計(jì)算CPU時(shí)間通信CPU時(shí)間同步開(kāi)銷(xiāo)時(shí)間進(jìn)程空閑時(shí)間（是由同步導(dǎo)致的）并行程序執(zhí)行時(shí)間評(píng)價(jià)并行程序的性能之前，必須清楚并行程序的執(zhí)并行程序執(zhí)行時(shí)間計(jì)算CPU時(shí)間進(jìn)程指令執(zhí)行所花費(fèi)的CPU時(shí)間，它可以分解為兩個(gè)部分，一個(gè)是程序本身指令執(zhí)行占用的CPU時(shí)間，即通常所說(shuō)的用戶時(shí)間（usertime），主要包含指令在CPU內(nèi)部的執(zhí)行時(shí)間和內(nèi)存訪問(wèn)時(shí)間，另一個(gè)是為了維護(hù)程序的執(zhí)行，操作系統(tǒng)花費(fèi)的CPU時(shí)間，即通常所說(shuō)的系統(tǒng)時(shí)間（systemtime），主要包含內(nèi)存調(diào)度和管理開(kāi)銷(xiāo)、I/O時(shí)間、以及維護(hù)程序執(zhí)行所必需要的操作系統(tǒng)開(kāi)銷(xiāo)等。通常地，系統(tǒng)時(shí)間可以忽略。并行程序執(zhí)行時(shí)間計(jì)算CPU時(shí)間并行程序執(zhí)行時(shí)間通信CPU時(shí)間

包含進(jìn)程通信花費(fèi)的CPU時(shí)間。同步開(kāi)銷(xiāo)時(shí)間

包含進(jìn)程同步花費(fèi)的時(shí)間進(jìn)程空閑時(shí)間

當(dāng)一個(gè)進(jìn)程阻塞式等待其他進(jìn)程的消息時(shí)，CPU通常是空閑的，或者處于等待狀態(tài)。進(jìn)程空閑時(shí)間是指并行程序執(zhí)行過(guò)程中，進(jìn)程所有這些空閑時(shí)間的總和。顯然，進(jìn)程的計(jì)算CPU時(shí)間小于并行程序的墻上時(shí)間，而并行程序的墻上時(shí)間才是用戶真正關(guān)心的時(shí)間，是評(píng)價(jià)一個(gè)并行程序執(zhí)行速度的時(shí)間。并行程序執(zhí)行時(shí)間通信CPU時(shí)間8/10/20239/59并行算法設(shè)計(jì)及效能分析并行算法效能分析并行加速比并行效率可擴(kuò)展性（簡(jiǎn)單表述）處理機(jī)數(shù)p增加時(shí)，并行效率Ep不顯著下降。8/8/20239/59并行算法設(shè)計(jì)及效能分析并行算法效能分效能分析分析說(shuō)明需要說(shuō)明的是，T1指處理器個(gè)數(shù)為1時(shí)，并行程序的執(zhí)行時(shí)間。通常情形下，T1大于TS，因?yàn)椴⑿谐绦蛲胍恍┤哂嗟目刂坪凸芾黹_(kāi)銷(xiāo)。加速比和效率是衡量一個(gè)并行程序性能的最基本的評(píng)價(jià)方法。顯然，執(zhí)行最慢的進(jìn)程將決定并行程序的性能。在以上加速比和效率的定義中，有一個(gè)基本的假設(shè)，要求并行機(jī)的各個(gè)處理器是同構(gòu)(homogeneous)的，即并行機(jī)各個(gè)處理器的結(jié)構(gòu)完全一致（包含CPU類(lèi)型、內(nèi)存大小與性能、cache特征等等），或者說(shuō)，串行程序在各個(gè)處理器執(zhí)行的墻上時(shí)間相等。效能分析分析說(shuō)明需要說(shuō)明的是，T1指處理器個(gè)數(shù)為1時(shí)，并效能分析分析說(shuō)明如果并行機(jī)的各個(gè)處理器功能不一致，稱之為異構(gòu)并行機(jī)。對(duì)此，以上加速比和效率的定義不是很合適。其中，兩個(gè)突出的問(wèn)題就是，串行程序的執(zhí)行時(shí)間是選擇最快的處理器運(yùn)行，還是選擇最慢的處理器運(yùn)行？在效率定義中，處理器個(gè)數(shù)選擇為P是否合適？一個(gè)比較好的方法就是，將所有處理器以最快的處理器為基準(zhǔn)，進(jìn)行歸一化處理。效能分析分析說(shuō)明如果并行機(jī)的各個(gè)處理器功能不一致，稱之為異構(gòu)并行程序性能評(píng)價(jià)方法以上介紹的加速比和效率，只能反映并行程序的整體執(zhí)行性能，但是，無(wú)法反映并行程序的性能瓶頸。性能評(píng)價(jià)的主要目的在于，揭示并行程序的性能瓶頸，指導(dǎo)并行程序的性能優(yōu)化。因此，有必要進(jìn)一步分解加速比和效率，提出更細(xì)致的性能評(píng)價(jià)方法。并行程序性能評(píng)價(jià)方法以上介紹的加速比和效率，只能反映并行程序并行計(jì)算性能評(píng)測(cè)3.1并行機(jī)的一些基本性能指標(biāo)3.2加速比性能定律3.2.1Amdahl定律3.2.2Gustafson定律3.2.3Sun和Ni定律3.3可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)3.3.1并行計(jì)算的可擴(kuò)放性3.3.2等效率度量標(biāo)準(zhǔn)3.3.3等速度度量標(biāo)準(zhǔn)3.3.4平均延遲度量標(biāo)準(zhǔn) ﹡3.4基準(zhǔn)測(cè)試程序并行計(jì)算性能評(píng)測(cè)3.1并行機(jī)的一些基本性能指標(biāo)并行計(jì)算的性能評(píng)測(cè)機(jī)器級(jí)的性能評(píng)測(cè)CPU和存儲(chǔ)器的某些基本性能指標(biāo)并行通信開(kāi)銷(xiāo)機(jī)器的成本、價(jià)格、和性能/價(jià)格比等算法級(jí)的性能評(píng)測(cè)加速比效率可擴(kuò)展性程序級(jí)的性能評(píng)測(cè)基本測(cè)試程序數(shù)學(xué)庫(kù)測(cè)試并行測(cè)試程序等并行計(jì)算的性能評(píng)測(cè)機(jī)器級(jí)的性能評(píng)測(cè)并行機(jī)基本性能參數(shù)一覽表名稱符號(hào)含義單位機(jī)器規(guī)模n處理器的數(shù)目無(wú)量綱時(shí)鐘速率f時(shí)鐘周期長(zhǎng)度的倒數(shù)MHz工作負(fù)載W計(jì)算操作的數(shù)目Mflops順序執(zhí)行時(shí)間T1程序在單處理機(jī)上的運(yùn)行時(shí)間s并行執(zhí)行時(shí)間Tn程序在并行機(jī)上的運(yùn)行時(shí)間s速度Rn=W/Tn每秒百萬(wàn)次浮點(diǎn)運(yùn)算Mflops加速Sn=T1/Tn衡量并行機(jī)有多快無(wú)量綱效率En=Sn/n衡量處理器的利用率無(wú)量綱峰值速度Rpeak=nR’peak所有處理器峰值(R’peak)速度之積Mflops利用率U=Rn/Rpeak可達(dá)速度與峰值速度之比無(wú)量綱通信延遲t0傳送0個(gè)字節(jié)或單字的時(shí)間us漸近帶寬r∞傳送長(zhǎng)消息通信速率MB/s并行機(jī)基本性能參數(shù)一覽表名稱符號(hào)含義單位機(jī)器規(guī)模n處理器的數(shù)工作負(fù)載工作負(fù)載（荷）：計(jì)算操作數(shù)目執(zhí)行時(shí)間—掠過(guò)時(shí)間：墻上時(shí)間所執(zhí)行的指令數(shù)目所完成的浮點(diǎn)運(yùn)算數(shù)工作負(fù)載工作負(fù)載（荷）：計(jì)算操作數(shù)目CPU的某些基本性能指標(biāo)工作負(fù)載執(zhí)行時(shí)間:程序從開(kāi)始到結(jié)束的時(shí)間。浮點(diǎn)運(yùn)算數(shù)指令數(shù)目：通常用百萬(wàn)條指令并行執(zhí)行時(shí)間Tn：Tcomput為計(jì)算時(shí)間，Tparo為并行開(kāi)銷(xiāo)時(shí)間，Tcomm為相互通信時(shí)間

Tn=Tcomput+Tparo+Tcomm 例：估計(jì)APRAM模型下執(zhí)行時(shí)間其中T1為串行時(shí)間，n為處理器數(shù)，T∞為使用無(wú)限多處理器且不考慮

Tparo與Tcomm的并行執(zhí)行時(shí)間CPU的某些基本性能指標(biāo)工作負(fù)載存儲(chǔ)器性能存儲(chǔ)器的層次結(jié)構(gòu)(C,L,B)-----容量C，延遲L，帶寬B估計(jì)存儲(chǔ)器的帶寬RISC指令addr1,r2,r3，寄存器8bytes，主頻100MHzB=3*8*100*106B/s=2.4GB/s存儲(chǔ)器性能存儲(chǔ)器的層次結(jié)構(gòu)(C,L,B)并行與通信開(kāi)銷(xiāo)并行和通信開(kāi)銷(xiāo)：相對(duì)于計(jì)算很大。PowerPC(每個(gè)周期15ns執(zhí)行4flops;

創(chuàng)建一個(gè)進(jìn)程1.4ms可執(zhí)行372000flops)開(kāi)銷(xiāo)的測(cè)量：乒--乓方法（Ping-PongScheme）節(jié)點(diǎn)0發(fā)送m個(gè)字節(jié)給節(jié)點(diǎn)1；節(jié)點(diǎn)1從節(jié)點(diǎn)0接收m個(gè)字節(jié)后，立即將消息發(fā)回節(jié)點(diǎn)0?？偟臅r(shí)間除以2，即可得到點(diǎn)到點(diǎn)通信時(shí)間，也就是執(zhí)行單一發(fā)送或接收操作的時(shí)間?？梢话慊癁闊嵬炼狗ǎ℉ot-Potato），也稱為救火隊(duì)法（Fire-Brigade)0——1——2——…——n-1——0即從節(jié)點(diǎn)0發(fā)送m字節(jié)給1，節(jié)點(diǎn)1給節(jié)點(diǎn)2，依次類(lèi)推，最后節(jié)點(diǎn)n-1再將其返回給0，最后時(shí)間再除以n即可。并行與通信開(kāi)銷(xiāo)并行和通信開(kāi)銷(xiāo)：相對(duì)于計(jì)算很大。Ping-PongSchemeif（my_node_id=0）then/*發(fā)送者*/ start_time=second（） sendanm-bytemessagetonode1//發(fā)送 receiveanm-bytemessagefromnode1//接收 end_time=second（） total_time=end_time–start_timecommunication_time[i]=total_time/2 elseif（my_node_id=1）then/*接收者*/ receiveanm-bytemessagefromnode0 sendanm-bytemessagetonode0 endifPing-PongSchemeif（my_node_并行開(kāi)銷(xiāo)的表達(dá)式：點(diǎn)到點(diǎn)通信通信開(kāi)銷(xiāo)

t(m)=t0+m/r∞通信啟動(dòng)時(shí)間t0漸近帶寬r∞

：傳送無(wú)限長(zhǎng)的消息時(shí)的通信速率m為傳輸?shù)淖止?jié)數(shù)半峰值長(zhǎng)度m1/2：達(dá)到一半漸近帶寬所要的消息長(zhǎng)度特定性能π0：表示短消息帶寬

t0=m1/2/

r∞=1/π0并行開(kāi)銷(xiāo)的表達(dá)式：點(diǎn)到點(diǎn)通信通信開(kāi)銷(xiāo)t(m)=t0并行開(kāi)銷(xiāo)的表達(dá)式：組通信典型的組通信有：播送（Broadcasting）：處理器0發(fā)送m個(gè)字節(jié)給所有的n個(gè)處理器----廣播收集（Gather）：處理0接收所有n個(gè)處理器發(fā)來(lái)在消息，所以處理器0最終接收了mxn個(gè)字節(jié)；散射（Scatter）：處理器0發(fā)送了m個(gè)字節(jié)的不同消息給所有n個(gè)處理器，因此處理器0最終發(fā)送了mxn個(gè)字節(jié)；全交換（TotalExchange）：每個(gè)處理器均彼此相互發(fā)送m個(gè)字節(jié)的不同消息給對(duì)方，所以總通信量為mxn2個(gè)字節(jié)；循環(huán)移位（Circular-shift）：處理器i發(fā)送m個(gè)字節(jié)給處理器i+1，處理器n-1發(fā)送m個(gè)字節(jié)給處理器0，所以通信量為mxn個(gè)字節(jié)。并行開(kāi)銷(xiāo)的表達(dá)式：組通信典型的組通信有：機(jī)器的成本、價(jià)格與性/價(jià)比機(jī)器的成本與價(jià)格機(jī)器的性能/價(jià)格比Performance/CostRatio：系指用單位代價(jià)（通常以百萬(wàn)美元表示）所獲取的性能（通常以MIPS或MFLOPS表示）利用率（Utilization）：可達(dá)到的速度與峰值速度之比機(jī)器的成本、價(jià)格與性/價(jià)比機(jī)器的成本與價(jià)格并行計(jì)算性能評(píng)測(cè)3.1并行機(jī)的一些基本性能指標(biāo)3.2加速比性能定律3.2.1Amdahl定律3.2.2Gustafson定律3.2.3Sun和Ni定律3.3可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)3.3.1并行計(jì)算的可擴(kuò)放性3.3.2等效率度量標(biāo)準(zhǔn)3.3.3等速度度量標(biāo)準(zhǔn)3.3.4平均延遲度量標(biāo)準(zhǔn) ﹡3.4基準(zhǔn)測(cè)試程序并行計(jì)算性能評(píng)測(cè)3.1并行機(jī)的一些基本性能指標(biāo)算法級(jí)性能評(píng)測(cè)加速比性能定律并行系統(tǒng)的加速比是指對(duì)于一個(gè)給定的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對(duì)于串行算法（或串行程序）的執(zhí)行速度加快了多少倍。Amdahl定律Gustafson定律SunNi定律可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)等效率度量標(biāo)準(zhǔn)等速度度量標(biāo)準(zhǔn)平均延遲度量標(biāo)準(zhǔn)算法級(jí)性能評(píng)測(cè)加速比性能定律Amdahl定律（1967）參數(shù)約定P：處理器數(shù)；W：?jiǎn)栴}規(guī)模（計(jì)算負(fù)載、工作負(fù)載，給定問(wèn)題的總計(jì)算量）；Ws：應(yīng)用程序中的串行分量，f是串行分量比例

（f=Ws/W，Ws=W1）；WP：應(yīng)用程序中可并行化部分，1-f為并行分量比例；Ws+Wp=W；Ts=T1：串行執(zhí)行時(shí)間，Tp：并行執(zhí)行時(shí)間；S：加速比，E：效率；出發(fā)點(diǎn)：固定不變的計(jì)算負(fù)載；固定的計(jì)算負(fù)載分布在多個(gè)處理器上；增加處理器加快執(zhí)行速度，從而達(dá)到了加速的目的。Amdahl定律（1967）參數(shù)約定Amdahl定律（cont‘d)固定負(fù)載的加速公式：

歸一化：Ws+Wp可相應(yīng)地表示為f+（1-f）

近似公式：p→∞時(shí)，上式極限為S=1/f考慮額外開(kāi)銷(xiāo)Wo： Amdahl定律（cont‘d)固定負(fù)載的加速公式：Amdahl’slaw(cont’d)Amdahl’slaw(cont’d)Gustafson定律（1988）出發(fā)點(diǎn)：對(duì)于很多大型計(jì)算，精度要求很高，即在此類(lèi)應(yīng)用中精度是個(gè)關(guān)鍵因素，而計(jì)算時(shí)間是固定不變的。此時(shí)為提高精度，必須加大計(jì)算量，相應(yīng)地亦必須增多處理器數(shù)才能維持時(shí)間不變；除非學(xué)術(shù)研究，在實(shí)際應(yīng)用中沒(méi)有必要固定工作負(fù)載而計(jì)算程序運(yùn)行在不同數(shù)目的處理器上，增多處理器必須相應(yīng)地增大問(wèn)題規(guī)模才有實(shí)際意義。Gustafson定律（1988）出發(fā)點(diǎn)：Gustafson定律（1988）Gustafson加速定律:近似公式：p→∞時(shí)，S’=p-fp=(1-f)P,1-f為斜率并行開(kāi)銷(xiāo)Wo：Gustafson定律（1988）Gustafson定律（cont‘d)Gustafson定律（cont‘d)Sun和Ni定律基本思想：只要存儲(chǔ)空間許可，應(yīng)盡量增大問(wèn)題規(guī)模以產(chǎn)生更好和更精確的解（此時(shí)可能使執(zhí)行時(shí)間略有增加）。假定在單節(jié)點(diǎn)上使用了全部存儲(chǔ)容量M并在相應(yīng)于W的時(shí)間內(nèi)求解之，此時(shí)工作負(fù)載W=fW+（1-f）W。在p個(gè)節(jié)點(diǎn)的并行系統(tǒng)上，能夠求解較大規(guī)模的問(wèn)題是因?yàn)榇鎯?chǔ)容量可增加到pM。令因子G（p）反應(yīng)存儲(chǔ)容量增加到p倍時(shí)并行工作負(fù)載的增加量，所以擴(kuò)大后的工作負(fù)載W=fW+（1-f）G（p）W。Sun和Ni定律基本思想：Sun和Ni定律存儲(chǔ)受限的加速公式：并行開(kāi)銷(xiāo)Wo:Sun和Ni定律存儲(chǔ)受限的加速公式：Sun和Ni定律(cont’d)Sun和Ni定律(cont’d)Sun和Ni定律(cont’d)討論：G（p）=1時(shí)，就是Amdahl加速定律；G（p）=p時(shí),s’’變?yōu)閒+p（1-f），就是Gustafson加速定律G（p）>p時(shí)，相應(yīng)于計(jì)算機(jī)負(fù)載比存儲(chǔ)要求增加得快，此時(shí)Sun和Ni加速均比Amdahl加速和Gustafson加速為高。Sun和Ni定律(cont’d)討論：加速比討論參考的加速經(jīng)驗(yàn)公式：p/logp≤S≤P線性加速比：很少通信開(kāi)銷(xiāo)的矩陣相加、內(nèi)積運(yùn)算等p/logp的加速比：分治類(lèi)的應(yīng)用問(wèn)題通信密集類(lèi)的應(yīng)用問(wèn)題：S=1/C（p）,C（p）為與p有關(guān)的通信函數(shù)超線性加速：并行搜索，Cache效應(yīng)絕對(duì)加速：最佳并行算法與串行算法相對(duì)加速：同一算法在單機(jī)和并行機(jī)的運(yùn)行時(shí)間加速比討論參考的加速經(jīng)驗(yàn)公式：p/logp≤S≤P可擴(kuò)展分析給定并行算法（程序）和并行機(jī)，如何調(diào)整參與并行計(jì)算的處理器個(gè)數(shù)P和求解問(wèn)題的計(jì)算規(guī)模W，使得隨著處理器個(gè)數(shù)的增長(zhǎng)，并行計(jì)算的效率可以保持不變，稱之為并行程序和并行機(jī)相結(jié)合的可擴(kuò)展分析?？蓴U(kuò)展分析是并行計(jì)算一個(gè)重要研究課題，被廣泛應(yīng)用于描述并行算法（程序）能否有效利用可擴(kuò)展的處理器個(gè)數(shù)的能力?？蓴U(kuò)展分析給定并行算法（程序）和并行機(jī)，如何調(diào)整參與并行計(jì)算可擴(kuò)展分析目的通常地，可擴(kuò)展分析具有四個(gè)目的：選擇合理的算法與結(jié)構(gòu)組合

確定求解某類(lèi)問(wèn)題的何種并行算法與何種并行機(jī)的組合，它可以有效地利用所期望的處理器規(guī)模。性能預(yù)測(cè)

對(duì)于運(yùn)行在某臺(tái)并行機(jī)上的某種算法（程序），根據(jù)算法（程序）在小處理器規(guī)模上的運(yùn)行性能，預(yù)測(cè)該算法（程序）移植到大處理器規(guī)模上后運(yùn)行的性能。最優(yōu)性能選擇

對(duì)某類(lèi)算法，假設(shè)問(wèn)題規(guī)模固定，確定在某類(lèi)并行機(jī)上最優(yōu)的處理器個(gè)數(shù)和可獲得的最優(yōu)的加速比。指導(dǎo)性能優(yōu)化指導(dǎo)改進(jìn)并行算法（程序），使得并行算法充分利用可擴(kuò)展的處理器規(guī)模。指導(dǎo)性能優(yōu)化

指導(dǎo)改進(jìn)并行算法（程序），使得并行算法充分利用可擴(kuò)展的處理器規(guī)模?？蓴U(kuò)展分析目的通常地，可擴(kuò)展分析具有四個(gè)目的：可擴(kuò)展分析方法（1）等效率度量對(duì)于某類(lèi)算法和并行機(jī)，如何保持問(wèn)題規(guī)模W與處理器個(gè)數(shù)P之間的關(guān)系WpPq，使得隨著處理器個(gè)數(shù)P的增長(zhǎng)，保持并行計(jì)算的效率不變。也就是求出等效率函數(shù)：W=

fE(P)

E固定等效率值越小，則當(dāng)處理器個(gè)數(shù)增多時(shí)為保持相同效率所需增加的問(wèn)題規(guī)模就越小，因此就有更好的可擴(kuò)展性。可擴(kuò)展分析方法（1）等效率度量可擴(kuò)展分析方法（2）等速度度量對(duì)于運(yùn)行在并行機(jī)上的某個(gè)算法，當(dāng)處理器個(gè)數(shù)增加時(shí)，需要增加多大的計(jì)算量，才能保持并行程序的平均速度不變。定義平均速度:V為并行程序的執(zhí)行速度，問(wèn)題規(guī)模從(W,P)變化到(W’,P’)，則等速度可擴(kuò)展度量公式可寫(xiě)為：越接近1，說(shuō)明可擴(kuò)展性越好。可擴(kuò)展分析方法（2）等速度度量并行程序性能優(yōu)化并行程序的性能優(yōu)化相對(duì)于串行程序而言更加復(fù)雜，其中最主要的是選擇好的并行算法及通信模式。在并行算法確定之后，影響并行程序效率的主要因素是通信開(kāi)銷(xiāo)、由于數(shù)據(jù)相關(guān)性或負(fù)載不平衡引起的進(jìn)程空閑等待、以及并行算法引入的冗余計(jì)算。在設(shè)計(jì)并行程序時(shí)，可以采用多種技術(shù)來(lái)減少或消除這些因素對(duì)并行效率的影響。并行程序性能優(yōu)化并行程序的性能優(yōu)化相對(duì)于串行程序而言更加復(fù)雜并行程序優(yōu)化技術(shù)1.減少通信量、提高通信粒度2.全局通信盡量利用高效聚合通信算法3.挖掘算法的并行度，減少CPU空閑等待4.負(fù)載平衡5.通信、計(jì)算的重疊6.通過(guò)引入重復(fù)計(jì)算來(lái)減少通信并行程序優(yōu)化技術(shù)1.減少通信量、提高通信粒度1.減少通信量、提高通信粒度在消息傳遞并行程序中，花費(fèi)在通信上的時(shí)間是純開(kāi)銷(xiāo)，因此如何減少通信時(shí)間是并行程序設(shè)計(jì)中首先要考慮的問(wèn)題。減少通信時(shí)間的途徑主要有三個(gè)：減少通信量、提高通信粒度和提高通信中的并發(fā)度(即不同結(jié)點(diǎn)對(duì)間同時(shí)進(jìn)行通信，要注意的是，這些手段都是相對(duì)于特定條件而言的，例如，在網(wǎng)絡(luò)重負(fù)載的情況下，提高通信并行度并不能改善程序的性能)。提高通信粒度的有效方法是減少通信次數(shù)，即盡可能將可以一起傳遞的數(shù)據(jù)合并起來(lái)一次傳遞。在收發(fā)不同類(lèi)型的數(shù)據(jù)時(shí)，定義適當(dāng)?shù)腗PI數(shù)據(jù)類(lèi)型來(lái)避免內(nèi)存中的數(shù)據(jù)拷貝。1.減少通信量、提高通信粒度在消息傳遞并行程序中，花費(fèi)在通2.全局通信盡量利用高效聚合通信算法當(dāng)組織多個(gè)進(jìn)程之間的聚合通信時(shí)，使用高效的通信算法可以大大提高通信效率、降低通信開(kāi)銷(xiāo)。對(duì)于標(biāo)準(zhǔn)的聚合通信，如廣播、歸約、數(shù)據(jù)散發(fā)與收集等，盡量調(diào)用MPI標(biāo)準(zhǔn)庫(kù)中的函數(shù)，因?yàn)檫@些函數(shù)往往經(jīng)過(guò)專(zhuān)門(mén)優(yōu)化。但使用標(biāo)準(zhǔn)庫(kù)函數(shù)的一個(gè)缺點(diǎn)是整個(gè)通信過(guò)程被封裝起來(lái)，無(wú)法在通信的同時(shí)進(jìn)行計(jì)算工作，此時(shí)，可以自行編制相應(yīng)通信代碼，