第23講 并行算法設(shè)計(jì)方法

并行算法的一般設(shè)計(jì)過(guò)程

PCAM設(shè)計(jì)方法

1

PCAM設(shè)計(jì)方法學(xué)設(shè)計(jì)并行算法的四個(gè)階段劃分(Partitioning)通訊(Communication)組合(Agglomeration)映射(Mapping)劃分：分解成小的任務(wù)，開拓并發(fā)性；通訊：確定諸任務(wù)間的數(shù)據(jù)交換，監(jiān)測(cè)劃分的合理性；組合：依據(jù)任務(wù)的局部性，組合成更大的任務(wù)；映射：將每個(gè)任務(wù)分配到處理器上，提高算法的性能。2

PCAM設(shè)計(jì)過(guò)程3劃分

1方法描述

2域分解

3功能分解

4劃分判據(jù)4劃分方法描述充分開拓算法的并發(fā)性和可擴(kuò)放性；先進(jìn)行數(shù)據(jù)分解(稱域分解)，再進(jìn)行計(jì)算功能的分解(稱功能分解)；使數(shù)據(jù)集和計(jì)算集互不相交；劃分階段忽略處理器數(shù)目和目標(biāo)機(jī)器的體系結(jié)構(gòu)；能分為兩類劃分：域分解(domaindecomposition)功能分解(functionaldecomposition)5域分解劃分的對(duì)象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)；將數(shù)據(jù)分解成大致相等的小數(shù)據(jù)片；劃分時(shí)考慮數(shù)據(jù)上的相應(yīng)操作；如果一個(gè)任務(wù)需要?jiǎng)e的任務(wù)中的數(shù)據(jù)，則會(huì)產(chǎn)生任務(wù)間的通訊；6域分解示例：三維網(wǎng)格的域分解，各格點(diǎn)上計(jì)算都是重復(fù)的。下圖是三種分解方法：實(shí)際上，分解沿X、Y、Z維及它們的任意組合都可以進(jìn)行。開始時(shí)，應(yīng)進(jìn)行三維劃分，因?yàn)樵摲椒芴峁┳畲箪`活性。

7域分解不規(guī)則區(qū)域的分解示例：8功能分解劃分的對(duì)象是計(jì)算，將計(jì)算劃分為不同的任務(wù)，其出發(fā)點(diǎn)不同于域分解；劃分后，研究不同任務(wù)所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的，則劃分是成功的；如果數(shù)據(jù)有相當(dāng)?shù)闹丿B，意味著要重新進(jìn)行域分解和功能分解；功能分解是一種更深層次的分解。9功能分解示例1：搜索樹搜索樹沒(méi)有明顯的可分解的數(shù)據(jù)結(jié)構(gòu)，但易于進(jìn)行細(xì)粒度的功能分解：開始時(shí)根生成一個(gè)任務(wù)，對(duì)其評(píng)價(jià)后，如果它不是一個(gè)解，就生成若干葉結(jié)點(diǎn)，這些葉結(jié)點(diǎn)可以分到各個(gè)處理器上并行地繼續(xù)搜索。

示例2：氣候模型10劃分判據(jù)劃分是否具有靈活性？(所劃分的任務(wù)數(shù)是否高于目標(biāo)機(jī)上處理器數(shù)目一個(gè)量級(jí)

?)劃分是否避免了冗余計(jì)算和存儲(chǔ)？(若不是，則產(chǎn)生的算法對(duì)大型問(wèn)題可能不是可擴(kuò)展的。

)劃分任務(wù)尺寸是否大致相當(dāng)？(若不是，則分配處理器時(shí)很難做到負(fù)載平衡。

)11劃分判據(jù)任務(wù)數(shù)與問(wèn)題尺寸是否成比例？(理想情況下，問(wèn)題尺寸的增加應(yīng)引起任務(wù)數(shù)的增加而不是任務(wù)尺寸的增加。若不是這樣，算法可能不能求解更大的問(wèn)題，盡管有更多的處理器。)功能分解是一種更深層次的分解，是否合理？(多考慮幾種選擇可以提高靈活性。同時(shí)既要考慮域分解又要考慮功能分解。)12通訊

方法描述

四種通訊模式

通訊判據(jù)

13通訊方法描述通訊是PCAM設(shè)計(jì)過(guò)程的重要階段；劃分產(chǎn)生的諸任務(wù)，一般不能完全獨(dú)立執(zhí)行，需要在任務(wù)間進(jìn)行數(shù)據(jù)交流；從而產(chǎn)生了通訊；功能分解確定了諸任務(wù)之間的數(shù)據(jù)流；諸任務(wù)是并發(fā)執(zhí)行的，通訊則限制了這種并發(fā)性；14四種通訊模式局部/全局通訊結(jié)構(gòu)化/非結(jié)構(gòu)化通訊靜態(tài)/動(dòng)態(tài)通訊同步/異步通訊15局部通訊通訊限制在一個(gè)鄰域內(nèi)16局部通訊當(dāng)一個(gè)任務(wù)僅要求與鄰近的其它任務(wù)通信時(shí)，就呈現(xiàn)局部通信模式。例如在數(shù)值計(jì)算中的雅可比有限差分法。如果采用5點(diǎn)格式，迭代公式為:

17全局通訊通訊非局部的例如：AlltoAllMaster-Worker5372118全局通訊在全局通信中，有很多任務(wù)參與交換數(shù)據(jù)。這可能造成過(guò)多的通信，從而限制了并行執(zhí)行的機(jī)會(huì)。例如我們希望計(jì)算

。為此，我們使用一個(gè)根進(jìn)程S負(fù)責(zé)從各進(jìn)程一次接收一個(gè)值（xi）并進(jìn)行累加。這時(shí)就會(huì)出現(xiàn)全局通信的局面。

19全局通訊采用分治策略可以開拓求和的并行性：

上式右邊的兩個(gè)求和可以同時(shí)執(zhí)行，并且每一個(gè)仍可按同樣的方式進(jìn)一步分解。求和的過(guò)程如下圖所示，同一級(jí)上的求和可以并行執(zhí)行。這樣就可以避免全局通信，并提高算法的并行度。圖中

表示處理器X至處理器Y上所有數(shù)據(jù)的和。

20全局通訊21結(jié)構(gòu)化通訊每個(gè)任務(wù)的通訊模式是相同的；下面是否存在一個(gè)相同通訊模式？22非結(jié)構(gòu)化通訊沒(méi)有一個(gè)統(tǒng)一的通訊模式例如：無(wú)結(jié)構(gòu)化網(wǎng)格23通訊判據(jù)所有任務(wù)是否執(zhí)行大致相當(dāng)?shù)耐ㄓ?(若不是，所設(shè)計(jì)的算法的可擴(kuò)展性可能會(huì)不好。)是否盡可能的局部通訊？(若不是，則可能導(dǎo)致全局通信。此時(shí)應(yīng)設(shè)法將全局通信換成局部通信。)24通訊判據(jù)通訊操作是否能并行執(zhí)行?(若不能，所設(shè)計(jì)的算法可能是低效的和不具可擴(kuò)展性的。此時(shí)可試用分治策略來(lái)開發(fā)并行性。)同步任務(wù)的計(jì)算能否并行執(zhí)行？(是否會(huì)因?yàn)榈却龜?shù)據(jù)而降低并行度？若不能并行執(zhí)行，所設(shè)計(jì)的算法可能是低效的和不具可擴(kuò)展性的。此時(shí)可考慮重新安排通信和計(jì)算的順序以改善這種情況。

)25

方法描述

表面-容積效應(yīng)

重復(fù)計(jì)算

組合判據(jù)

組合26方法描述組合是由抽象到具體的過(guò)程，是將組合的任務(wù)能在一類并行機(jī)上有效的執(zhí)行；合并小尺寸任務(wù)，減少任務(wù)數(shù)。如果任務(wù)數(shù)恰好等于處理器數(shù)，則也完成了映射過(guò)程；通過(guò)增加任務(wù)的粒度和重復(fù)計(jì)算，可以減少通訊成本；保持映射和擴(kuò)展的靈活性，降低軟件工程成本；27增加粒度在劃分階段，為了盡可能地開發(fā)問(wèn)題的并行性，可能產(chǎn)生了大量的細(xì)粒度任務(wù)。但是大量的任務(wù)可能會(huì)增加通信開銷和任務(wù)創(chuàng)建開銷。28表面-容積效應(yīng)通訊量與任務(wù)子集的表面成正比，計(jì)算量與任務(wù)子集的體積成正比；增加重復(fù)計(jì)算有可能減少通訊量；29表面-容積效應(yīng)因此一個(gè)計(jì)算單元的通信與計(jì)算之比隨任務(wù)尺寸的增加而減小。例如在二維問(wèn)題中，“表面積”即是數(shù)據(jù)域的周長(zhǎng)，它正比于問(wèn)題的尺寸，而“容積”指數(shù)據(jù)域的面積，它正比于問(wèn)題尺寸的平方。

30表面-容積效應(yīng)以二維平面上的雅可比有限差分法5點(diǎn)格式為例。假設(shè)需要計(jì)算的數(shù)據(jù)是4×4矩陣。如果把計(jì)算每個(gè)元素算作一個(gè)任務(wù)，則有16個(gè)任務(wù)。每輪迭代中，每個(gè)任務(wù)都需要與其上下左右的任務(wù)通信，共需48次通信（當(dāng)然這些通信中許多可以并行進(jìn)行）。如下圖（a）所示，每個(gè)箭頭表示一次通信。

31表面-容積效應(yīng)如果將相鄰的四個(gè)元素的計(jì)算作為一個(gè)任務(wù)則只需8次通信，如上圖（b）所示。雖然每次通信要傳遞兩個(gè)數(shù)據(jù)，但是相對(duì)于圖（a），通信的次數(shù)和通信量都大大減少了?？梢?，當(dāng)小任務(wù)組合為大任務(wù)后，原來(lái)的某些數(shù)據(jù)傳遞被“包含”在大任務(wù)里面了，它們不再表現(xiàn)為通信，實(shí)際計(jì)算時(shí)，這些數(shù)據(jù)交換可以通過(guò)直接讀取內(nèi)存完成。這正是增加粒度可以減少通信的原因。

32重復(fù)計(jì)算重復(fù)計(jì)算減少通訊量，但增加了計(jì)算量，應(yīng)保持恰當(dāng)?shù)钠胶?；重?fù)計(jì)算的目標(biāo)應(yīng)減少算法的總運(yùn)算時(shí)間；33重復(fù)計(jì)算假定在二叉樹上求N個(gè)數(shù)的和，且要求最終在每個(gè)處理器上都有該結(jié)果。一種方法是先自葉向根求和，得到結(jié)果后再自根向葉播送，共需2

步。如下圖所示。

34重復(fù)計(jì)算以上述方式求和，處理器的利用率是逐級(jí)減半的。如果在每一級(jí)每個(gè)處理器均接收兩個(gè)數(shù)據(jù)，求和后再發(fā)送給上一級(jí)的兩個(gè)處理器，那么經(jīng)過(guò)

步后，每個(gè)處理器中就都得到了N個(gè)數(shù)的全和。計(jì)算過(guò)程如下圖所示。

35組合判據(jù)增加粒度是否減少了通訊成本？（若不是，能否換用別的組合策略以減少通信開銷？）重復(fù)計(jì)算是否已權(quán)衡了其得益？是否保持了靈活性和可擴(kuò)放性？36組合判據(jù)組合的任務(wù)數(shù)是否與問(wèn)題尺寸成比例?（若不是，算法是不可擴(kuò)展的。）是否保持了類似的計(jì)算和通訊？有沒(méi)有減少并行執(zhí)行的機(jī)會(huì)？（是否已證實(shí)現(xiàn)在的并發(fā)性仍能適應(yīng)目前和將來(lái)的并行機(jī)？）37

方法描述

負(fù)載平衡算法

任務(wù)調(diào)度算法

映射判據(jù)映射38方法描述每個(gè)任務(wù)要映射到具體的處理器，定位到運(yùn)行機(jī)器上；任務(wù)數(shù)大于處理器數(shù)時(shí)，存在負(fù)載平衡和任務(wù)調(diào)度問(wèn)題；映射的目標(biāo)：減少算法的執(zhí)行時(shí)間并發(fā)的任務(wù)

不同的處理器任務(wù)之間存在高通訊的

同一處理器映射實(shí)際是一種權(quán)衡，屬于NP完全問(wèn)題；39負(fù)載平衡算法靜態(tài)的：事先確定；概率的：隨機(jī)確定；動(dòng)態(tài)的：執(zhí)行期間動(dòng)態(tài)負(fù)載；基于域分解的：遞歸對(duì)剖局部算法概率方法循環(huán)映射40負(fù)載平衡算法

局部算法局部負(fù)載平衡算法的思想是通過(guò)從近鄰遷入任務(wù)和向近鄰遷出任務(wù)來(lái)達(dá)到負(fù)載平衡。比如，每個(gè)處理器周期性地與鄰居比較負(fù)載的輕重。如果差異超過(guò)了某個(gè)閾值，就進(jìn)行負(fù)載遷移。如果自己的負(fù)載輕且有鄰居負(fù)載重，則從該鄰居遷入一些任務(wù)。反之，如果自己的負(fù)載重，而別的鄰居較空閑，則把自己的一部分負(fù)載遷給它。局部算法的優(yōu)點(diǎn)是這個(gè)方案只利用局部的負(fù)載信息。同時(shí)，遷移任務(wù)時(shí)往往通信量很大，而此方案只在局部遷移，有利于提高效率。

41負(fù)載平衡算法

概率方法（ProbabilisticMethod）此法的思想是將任務(wù)隨機(jī)地分配給處理器，如果任務(wù)足夠多，則每個(gè)處理器預(yù)計(jì)能分到大致等量的任務(wù)。此法的優(yōu)點(diǎn)是低價(jià)和可擴(kuò)展性好；缺點(diǎn)是要求跨處理器進(jìn)行通信，并且只有當(dāng)任務(wù)數(shù)遠(yuǎn)遠(yuǎn)多于處理器數(shù)時(shí)才能達(dá)到預(yù)期的效果。

循環(huán)映射（CyclicMapping）此法又稱為循環(huán)指派法，即輪流地給處理器分配計(jì)算任務(wù)。它實(shí)際上是概率方法的一種形式。此法適用于各計(jì)算任務(wù)呈明顯的空間局部性的情況。

總之，局部算法代價(jià)小，但當(dāng)負(fù)載變化大時(shí)調(diào)整很慢；概率方法代價(jià)小，可擴(kuò)展性好，但通信代價(jià)可能較大，且只適用于任務(wù)數(shù)遠(yuǎn)多于處理器數(shù)的情況；循環(huán)映射技術(shù)是概率映射的一種形式，而概率方法比其它技術(shù)易于導(dǎo)致可觀的通信。

42負(fù)載平衡算法43任務(wù)調(diào)度算法任務(wù)放在集中的或分散的任務(wù)池中，使用任務(wù)調(diào)度算法將池中的任務(wù)分配給特定的處理器。下面是兩種常用調(diào)度模式：經(jīng)理/雇員模式

經(jīng)理/雇員模式：

在此模式中，有一個(gè)進(jìn)程（經(jīng)理）負(fù)責(zé)分配任務(wù)，每個(gè)雇員向經(jīng)理請(qǐng)求任務(wù)，得到任務(wù)后執(zhí)行任務(wù)。使用預(yù)取方法（以使計(jì)算和通信重疊）可以提高效率。

層次經(jīng)理/雇員模式：在此模式中，雇員被分成不相交的集合，每個(gè)集合有一個(gè)小經(jīng)理。雇員們從小經(jīng)理那里領(lǐng)取任務(wù)，小經(jīng)理從經(jīng)理處領(lǐng)取任務(wù)。經(jīng)理/雇員模式的缺點(diǎn)是經(jīng)理進(jìn)程容易成為系統(tǒng)的瓶頸。44任務(wù)調(diào)度算法非集中模式它就是無(wú)中心管理者的分布式調(diào)度法。

45映射判據(jù)如果采用集中式負(fù)載平衡方案，是否檢查了中央管理者不會(huì)成為瓶頸？如果采用動(dòng)態(tài)負(fù)載平衡方案，是否衡量過(guò)不同策略的成本？

如果采用概率或循環(huán)指派法，是否有足夠多的任務(wù)？一般地，任務(wù)數(shù)應(yīng)不少于處理器數(shù)的10倍。46并行算法的復(fù)雜性度量串行算法的復(fù)雜性度量最壞情況下的復(fù)雜度(Worst-CASEComplexity)期望復(fù)雜度(ExpectedComplexity)并行算法的幾個(gè)復(fù)雜性度量指標(biāo)運(yùn)行時(shí)間t(n):包含計(jì)算時(shí)間和通訊時(shí)間，分別用計(jì)算時(shí)間步和選路時(shí)間步作單位。n為問(wèn)題實(shí)例的輸入規(guī)模。處理器數(shù)p(n)并行算法成本c(n):c(n)=t(n)p(n)總運(yùn)算量W(n):并行算法求解問(wèn)題時(shí)所完成的總的操作步數(shù)。

47Brent定理令W(n)是某并行算法A在運(yùn)行時(shí)間T(n)內(nèi)所執(zhí)行的運(yùn)算量，則A使用p臺(tái)處理器可在t(n)=O(W(n)/p+T(n))時(shí)間內(nèi)執(zhí)行完畢。W(n)和c(n)密切相關(guān)P=O(W(n)/T(n))時(shí)，W(n)和c(n)兩者是漸進(jìn)一致的對(duì)于任意的p，c(n)?W(n)并行算法的復(fù)雜性度量48算法級(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)49Amdahl定律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：串行執(zhí)行時(shí)間，Tp：并行執(zhí)行時(shí)間；S：加速比，E：效率；出發(fā)點(diǎn)：固定不變的計(jì)算負(fù)載；固定的計(jì)算負(fù)載分布在多個(gè)處理器上的，增加處理器加快執(zhí)行速度，從而達(dá)到了加速的目的。50固定負(fù)載的加速公式：

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

p→∞時(shí)，上式極限為：S=1/fWo為額外開銷

Amdahl定律51Amdahl定律52Gustafson定律出發(fā)點(diǎn)：對(duì)于很多大型計(jì)算，精度要求很高，即在此類應(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加速定律:并行開銷Wo：53Gustafson定律54Sun和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。存儲(chǔ)受限的加速公式：并行開銷Wo:55Sun和Ni定律G（p）=1時(shí)就是Amdahl加速定律；

G（p）=p變?yōu)閒+p（1-f），就是Gustafson加速定律G（p）>p時(shí)，相應(yīng)于計(jì)算機(jī)負(fù)載比存儲(chǔ)要求增加得快，此時(shí)Sun和Ni加速均比Amdahl加速和Gustafson加速為高。

56加速比討論參考的加速經(jīng)驗(yàn)公式：p/logp≤S≤P線性加速比：很少通信開銷的矩陣相加、內(nèi)積運(yùn)算等p/logp的加速比：分治類的應(yīng)用問(wèn)題通信密集類的應(yīng)用問(wèn)題：S=1/C（p）超線性加速絕對(duì)加速：最佳并行算法與串行算法相對(duì)加速：同一算法在單機(jī)和并行機(jī)的運(yùn)行時(shí)間57可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)并行計(jì)算的可擴(kuò)放性（Scalability）也是主要性能指標(biāo)可擴(kuò)放性最簡(jiǎn)樸的含意是在確定的應(yīng)用背景下，計(jì)算機(jī)系統(tǒng)（或算法或程序等）性能隨處理器數(shù)的增加而按比例提高的能力影響加速比的因素：處理器數(shù)與問(wèn)題規(guī)模求解問(wèn)題中的串行分量并行處理所引起的額外開銷（通信、等待、競(jìng)爭(zhēng)、冗余操作和同步等）加大的處理器數(shù)超過(guò)了算法中的并發(fā)程度增加問(wèn)題的規(guī)模有利于提高加速的因素：較大的問(wèn)題規(guī)?？商峁┹^高的并發(fā)度；額外開銷的增加可能慢于有效計(jì)算的增加；算法中的串行分量比例不是固定不變的（串行部分所占的比例隨著問(wèn)題規(guī)模的增大而縮?。?。增加處理器數(shù)會(huì)增大額外開銷和降低處理器利用率，所以對(duì)于一個(gè)特定的并行系統(tǒng)（算法或程序），它們能否有效利用不斷增加的處理器的能力應(yīng)是受限的，而度量這種能力就是可擴(kuò)放性這一指標(biāo)。

58可擴(kuò)放性:調(diào)整什么和按什么比例調(diào)整并行計(jì)算要調(diào)整的是處理數(shù)p和問(wèn)題規(guī)模W，兩者可按不同比例進(jìn)行調(diào)整，此比例關(guān)系（可能是線性的，多項(xiàng)式的或指數(shù)的等）就反映了可擴(kuò)放的程度。并行算法和體系結(jié)構(gòu)可擴(kuò)放性研究的主要目的：確定解決某類問(wèn)題用何種并行算法與何種并行體系結(jié)構(gòu)的組合，可以有效地利用大量的處理器；對(duì)于運(yùn)行于某種體系結(jié)構(gòu)的并行機(jī)上的某種算法當(dāng)移植到大規(guī)模處理機(jī)上后運(yùn)行的性能；對(duì)固定的問(wèn)題規(guī)模，確定在某類并行機(jī)上最優(yōu)的處理器數(shù)與可獲得的最大的加速比；用于指導(dǎo)改進(jìn)并行算法和并行機(jī)體系結(jié)構(gòu)，以使并行算法盡可能地充分利用可擴(kuò)充的大量處理器目前無(wú)一個(gè)公認(rèn)的、標(biāo)準(zhǔn)的和被普遍接受的嚴(yán)格定義和評(píng)判它的標(biāo)準(zhǔn)可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)59等速度度量標(biāo)準(zhǔn)p表示處理器個(gè)數(shù)，W表示要求解問(wèn)題的工作量或稱問(wèn)題規(guī)模（在此可指浮點(diǎn)操作個(gè)數(shù)），T為并行執(zhí)行時(shí)間，定義并行計(jì)算的速度V為工作量W除以并行時(shí)間Tp個(gè)處理器的并行系統(tǒng)的平均速度定義為并行速度V除以處理器個(gè)數(shù)p：W是使用p個(gè)處理器時(shí)算法的工作量，令W’表示當(dāng)處理數(shù)從p增大到p’時(shí)，為了保持整個(gè)系統(tǒng)的平均速度不變所需執(zhí)行的工作量，則可得到處理器數(shù)從p到p’時(shí)平均速度可擴(kuò)放度量標(biāo)準(zhǔn)公式60等速度度量標(biāo)準(zhǔn)優(yōu)點(diǎn)：直觀地使用易測(cè)量的機(jī)器性能速度指標(biāo)來(lái)度量缺點(diǎn)：某些非浮點(diǎn)運(yùn)算可能造成性能的變化61并行數(shù)值算法

三角形方程組的求解

62基本術(shù)語(yǔ)線性方程組的定義和符號(hào)

a1,1x1+a1,2x2+…+a1,nxn=b1a2,1x1+a2,1x2+…+a2