并行計(jì)算.3性能

1、并行計(jì)算1 并行系統(tǒng)的性能分析 并行系統(tǒng)的性能分析 一個(gè)串行程序的性能通常用它的運(yùn)行時(shí)間來(lái)衡量，表達(dá)為它的輸入規(guī)模（問(wèn)題規(guī)模）的函數(shù)。而并行算法的執(zhí)行時(shí)間不僅與問(wèn)題的規(guī)模有關(guān)，還與并行計(jì)算機(jī)的體系結(jié)構(gòu)和處理器的數(shù)目直接相關(guān)，因此，對(duì)并行算法性能的評(píng)價(jià)不能脫離具體的并行體系結(jié)構(gòu)。一個(gè)并行系統(tǒng)是并行算法以及實(shí)現(xiàn)這個(gè)算法的并行體系結(jié)構(gòu)的組合體。 運(yùn)行時(shí)間 一個(gè)程序的串行運(yùn)行時(shí)間是程序在一個(gè)串行計(jì)算機(jī)上開(kāi)始執(zhí)行到執(zhí)行完成之間所經(jīng)過(guò)的時(shí)間段的長(zhǎng)度。 并行運(yùn)行時(shí)間則定義為并行計(jì)算開(kāi)始到最后一個(gè)處理器完成它的計(jì)算任務(wù)之間的時(shí)間段的長(zhǎng)度。 定義Ts為串行部分的執(zhí)行時(shí)間，Tp為并行部分的執(zhí)行時(shí)間 加速比 在評(píng)價(jià)

2、一個(gè)并行系統(tǒng)時(shí)，人們通常關(guān)心的是對(duì)一個(gè)給定的應(yīng)用，它的并行化版本比串行實(shí)現(xiàn)有多大的性能提高。加速比就是一個(gè)衡量并行解題過(guò)程中的相對(duì)收益的指 標(biāo)。簡(jiǎn)單的講，并行系統(tǒng)的加速比是指對(duì)于一個(gè)給定的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對(duì)于串行算法（或者串行程序）的執(zhí)行速度加快了多少倍。加速比通常由三種加速比性能定律：適用于固定計(jì)算負(fù)載的Amdahl定律，適用于可擴(kuò)展性問(wèn)題的Gustafson定律和受限于存儲(chǔ)器的Sun和Ni定律。 為討論方便，定義以下的參數(shù)： p是并行系統(tǒng)中處理器的數(shù)目； W是問(wèn)題規(guī)模（也常常叫做計(jì)算負(fù)載、工作負(fù)載，它定義為給定問(wèn)題的總計(jì)算量），Ws是應(yīng)用程序中的串行分量，W中可并行

3、化部分為Wp ； f是串行分量的比例，即f = Ws / W ，則1 - f 為并行分量的比例； Ts 為串行部分的執(zhí)行時(shí)間，Tp 為并行部分的執(zhí)行時(shí)間； S為加速比， E為效率。 Amdahl定律 Amdahl定律的基本出發(fā)點(diǎn)是：(1) 對(duì)于許多科學(xué)計(jì)算，實(shí)時(shí)性要求很高，即在這類應(yīng)用中計(jì)算時(shí)間是個(gè)關(guān)鍵性因素，而計(jì)算負(fù)載是固定不變的。為此，在一定的計(jì)算負(fù)載下，為滿足實(shí)時(shí)性的要求，可以通過(guò)增加處理器數(shù)目的方法來(lái)減少運(yùn)行時(shí)間，提高計(jì)算速度；(2) 因?yàn)楣潭ǖ挠?jì)算負(fù)載可以分布在多個(gè)處理器上，這樣增加了處理器就加快了執(zhí)行速度，從而達(dá)到了加速的目的。在這樣的動(dòng)機(jī)推動(dòng)下，1967年Amdahl推導(dǎo)出了固定

4、負(fù)載情況下的加速比公式： Amdahl定律 固定負(fù)載情況下的加速比公式： 由于W=Ws + Wp，上式右邊分子分母同除以W，則有 當(dāng) 時(shí)，加速比的極限為Amdahl定律這就是著名的Amdahl加速定律，它意味著隨著處理器數(shù)目的無(wú)限增大，并行系統(tǒng)所能達(dá)到的加速比存在上限，且為一個(gè)常數(shù)1/f，這個(gè)常數(shù)只取決于應(yīng)用本 身的性質(zhì)。這個(gè)結(jié)論在歷史上曾經(jīng)對(duì)并行系統(tǒng)的發(fā)展帶來(lái)了一種悲觀的影響。它帶來(lái)的兩種影響是，一是勸阻并行計(jì)算機(jī)廠商生產(chǎn)更大規(guī)模的并行計(jì)算機(jī)，二是促進(jìn) 了并行編譯計(jì)算的發(fā)展，以降低程序中串行部分的值。Amdahl定律的幾何意義可以清楚的用下面的圖來(lái)表示： Amdahl定律Amdahl定律 當(dāng)

5、處理器數(shù)目n=1024，加速比公式如下， Sn隨變化的情況如下圖：Amdahl定律實(shí)際上并行加速比不僅受限于程序的串行分量的比例，而且也受并行程序運(yùn)行時(shí)的額外開(kāi)銷的影響。如果考慮到這部分因素的影響，令Wo為額外開(kāi)銷，那么上面的公式應(yīng)該修改為：這種情形下的加速比極限為：結(jié)論：并行程序中的串行分量比例和并行額外開(kāi)銷越大，則加速比越小。 Gustafson定律 Gustafson定律的基本出發(fā)點(diǎn)是：(1) 對(duì)于很多大型計(jì)算，精度要求很高，即在此類應(yīng)用中精度是一個(gè)關(guān)鍵因素，而計(jì)算時(shí)間是固定不變的。此時(shí)為了提高精度，必須加大計(jì)算量，相應(yīng)的也必須增加處理器的數(shù)目來(lái)完成這部分計(jì)算，以保持計(jì)算時(shí)間不變；(2)

6、 除非學(xué)術(shù)研究，在實(shí)際應(yīng)用中沒(méi)有必要固定工作負(fù)載而使計(jì)算程序運(yùn)行在不同數(shù)目的處理器上，增多處理器必須相應(yīng)的增大問(wèn)題規(guī)模才有實(shí)際的意義。因此研究在給 定的時(shí)間內(nèi)用不同數(shù)目的處理器能夠完成多大的計(jì)算量是并行計(jì)算中一個(gè)很實(shí)際的問(wèn)題。(3) 對(duì)大多數(shù)問(wèn)題，問(wèn)題規(guī)模的改變只會(huì)改變計(jì)算中并行計(jì)算量，而不會(huì)改變串行計(jì)算量。 從這些動(dòng)機(jī)出發(fā)，Gustafson在1987年提出了變問(wèn)題規(guī)模的加速比模型： Gustafson定律 變問(wèn)題規(guī)模的加速比模型： 當(dāng)p充分大時(shí)，S與p幾乎成線性關(guān)系，其斜率為1-f，這就是Gustafson加速比定律，它意味著隨著處理器數(shù)目的增加，加速比幾乎與處理器數(shù) 目成比例的線性增加，

7、串行比例f不再是程序的瓶頸，這為并行計(jì)算系統(tǒng)的發(fā)展帶來(lái)了非常樂(lè)觀的結(jié)論。 Gustafson定律 Gustafson定律的幾何意義可以清楚的用下面的圖來(lái)表示： Gustafson定律 當(dāng)處理器數(shù)目n=1024，加速比Sn隨變化的情況如下： 可以用圖表示如下： Gustafson定律同樣的，當(dāng)考慮到并行程序運(yùn)行時(shí)的額外開(kāi)銷時(shí)，Gustafson定律應(yīng)該修改為：注意：Wo是p的函數(shù)，它可能會(huì)隨著p的改變而改變。要到達(dá)一般化的Gustafson定律所描述的線性加速比，當(dāng)p改變時(shí)，必須要控制額外開(kāi)銷的增長(zhǎng)，這在實(shí)際中往往是非常困難的。 Sun和Ni定律 Xian-He Sun和Lionel Ni于19

8、93年曾將Amdahl和Gustafson定律一般化，提出了存儲(chǔ)受限的加速定律。他們的基本思想是：只要存儲(chǔ)空間許可，應(yīng)該盡量增大問(wèn)題規(guī)模以產(chǎn)生更好或更精確的解（執(zhí)行時(shí)間可能略有增加）。換句話說(shuō)，假如有足夠的存儲(chǔ)容量，并且規(guī)?？蓴U(kuò)展的問(wèn)題滿足Gustafson定律規(guī)定的時(shí)間要求，那么 就有可能進(jìn)一步增大問(wèn)題規(guī)模求得更好或更精確的解。 Sun和Ni定律 給定一個(gè)存儲(chǔ)受限問(wèn)題，假定在單節(jié)點(diǎn)上使用了全部存儲(chǔ)容量M并在相應(yīng)于W的計(jì)算時(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)來(lái)反映存儲(chǔ)容量增加p倍時(shí)工作負(fù)載的

9、增加量，所以增加后的工作負(fù)載W=fW+ (1-f)G(p)W。那么，存儲(chǔ)受限的加速比公式為：Sun和Ni定律 Sun和Ni定律的幾何意義可以清楚的用下面的圖來(lái)表示： Sun和Ni定律 如果考慮到并行程序運(yùn)行時(shí)的額外開(kāi)銷Wo，則上面的公式應(yīng)該作相應(yīng)的修改：Sun和Ni定律 當(dāng)G(p)=1時(shí)，它變?yōu)?這就是Amdahl定律 當(dāng)G(p)=p時(shí)，它變?yōu)閒+p(1-f)，這就是Gustafson定律 當(dāng)G(p)p時(shí)，它相應(yīng)于計(jì)算負(fù)載比存儲(chǔ) 要求增加得快，此時(shí)Sun和Ni定律指出的加速比比Amdahl和Gustafson定律指出的都要高。有關(guān)加速比的討論 在實(shí)際應(yīng)用中，可供參考的加速比經(jīng)驗(yàn)公式為： 可以達(dá)

10、到線性加速比線性加速比的應(yīng)用問(wèn)題有矩陣相加、內(nèi)積運(yùn)算等等，這一類問(wèn)題幾乎沒(méi)有通信開(kāi)銷，而且單獨(dú)的計(jì)算之間幾乎沒(méi)有什么關(guān)系；對(duì)于分治類的應(yīng)用問(wèn)題，它類似于二叉樹(shù)，處于樹(shù)上的同級(jí)節(jié)點(diǎn)上的計(jì)算可并行執(zhí)行，但越靠近根，并行度將逐漸減少，此類問(wèn)題可能可以達(dá)到p/logp的加速比；對(duì)于通信 密集型的應(yīng)用問(wèn)題，它的加速比經(jīng)驗(yàn)公式可以參考下面的式子： S=1/C(p) 其中，C(p)是p個(gè)處理器的某一通信函數(shù)，或者為線性的或者為對(duì)數(shù)的。 有關(guān)加速比的討論 嚴(yán)格的線性加速比線性加速比對(duì)大多數(shù)應(yīng)用問(wèn)題來(lái)說(shuō)，是難以達(dá)到的，更不用說(shuō)超線性加速比。但在某些算法或者程序中，可能會(huì)出現(xiàn)超線性加速比現(xiàn)象，比如，在某些并行搜索

11、算法中，允許不同的處理器在不同的分支方向上同時(shí)搜索，當(dāng)某一處理器一旦迅速的找到了解，它就向其余的處理器發(fā)出中止搜索的信號(hào)，這就 會(huì)提前取消那些在串行算法中所做的無(wú)謂的搜索分枝，從而出現(xiàn)超線性加速比現(xiàn)象；在大多數(shù)的并行計(jì)算系統(tǒng)中，每個(gè)處理器都有少量的高速緩存，當(dāng)某一問(wèn)題執(zhí)行 在大量的處理器上，而所需要的數(shù)據(jù)都放在高速緩存中時(shí)，由于數(shù)據(jù)的復(fù)用，總的計(jì)算時(shí)間趨于減少，如果由于這種高速緩存效應(yīng)補(bǔ)償了由于通信造成的額外開(kāi)銷， 就有可能造成超線性加速比。 有關(guān)加速比的討論最后值得指出的是，加速比的含義對(duì)科學(xué)研究者和工程實(shí)用者可能有所不同。對(duì)一個(gè)給定的問(wèn)題，可能會(huì)有不止一個(gè)的串行算法，它們的運(yùn)行時(shí)間也不會(huì)完

12、全相同，這就帶來(lái)了不同的加速比的定義。研究者們使用絕對(duì)加速比絕對(duì)加速比的定義，即對(duì)于給定的問(wèn)題，加速比等于最佳串行算法所用的時(shí)間除以同一問(wèn)題的并行算法所用的時(shí)間。有關(guān)加速比的討論對(duì)最佳串行算法有幾個(gè)說(shuō)明。因?yàn)樽罴汛兴惴ㄒ彩峭ㄟ^(guò)實(shí)際運(yùn)行測(cè)出來(lái)的，按照串行算法運(yùn)行平臺(tái)的不同，絕對(duì)加速比也可以分成兩種。一種與具體的機(jī)器有關(guān)， 即串行計(jì)算機(jī)采用與并行計(jì)算機(jī)一樣的處理器；一種與具體的機(jī)器無(wú)關(guān)，此時(shí)的串行算法運(yùn)行時(shí)間是串行計(jì)算機(jī)上的最短執(zhí)行時(shí)間。但有的時(shí)候，對(duì)一個(gè)特定的問(wèn) 題，它的最佳串行算法是未知的，或者，它的串行算法所需要的運(yùn)行時(shí)間太長(zhǎng)，實(shí)際運(yùn)行它是不太現(xiàn)實(shí)的，在這些情況下，經(jīng)常用已知的最優(yōu)串行算法

13、來(lái)代替最佳串 行算法；而工程中使用相對(duì)加速比相對(duì)加速比的定義，即對(duì)于給定的問(wèn)題，加速比等于同一個(gè)算法在單處理器上運(yùn)行的時(shí)間除以在多處理器上的運(yùn)行時(shí)間。顯然，相對(duì)加速比的定義是比較寬松和實(shí)際的。 效率 只有理想的具有p個(gè)處理器的并行系統(tǒng)的加速比能夠達(dá)到p，在實(shí)際中，這種理想情形是不可能達(dá)到的，因?yàn)樵趫?zhí)行并行算法時(shí)，處理器不可能把它們100%的時(shí)間都用來(lái)執(zhí)行算法。比如，在計(jì)算n個(gè)數(shù)據(jù)和的時(shí)候，一部分的時(shí)間被用來(lái)進(jìn)行通信了。 效率效率被用來(lái)衡量一個(gè)處理器的計(jì)算能力被有效利用的比率。在一個(gè)理想并行系統(tǒng)中，加速比等于p，而效率等于1，而在實(shí)際系統(tǒng)中，加速比小于p，而效率在0到1之間取值，它描述了處理器被

14、有效利用的程度，用E來(lái)表示效率，它可以用下面的公式來(lái)計(jì)算： E=S/p效率在n個(gè)處理器的超立方體上完成n個(gè)數(shù)的加法：開(kāi)始時(shí)，每個(gè)處理器都存放了一個(gè)待加的數(shù)據(jù)，算法結(jié)束時(shí)，其中的一個(gè)處理器中已經(jīng)存放了n個(gè)數(shù)累加的結(jié)果。根據(jù)前面的討論結(jié)果，可以知道，在超立方體上完成n個(gè)數(shù)的加法的并行算法的效率為 開(kāi)銷 開(kāi)銷開(kāi)銷定義為一個(gè)并行系統(tǒng)在解一個(gè)問(wèn)題的時(shí)候，并行運(yùn)行時(shí)間與所用的處理器的乘積。開(kāi)銷反映了在解一個(gè)問(wèn)題時(shí)，系統(tǒng)中投入運(yùn)行的處理器所耗費(fèi)的總的時(shí)間。效率也可以表示成已知的最快的串行算法的運(yùn)行時(shí)間與在一個(gè)p處理器的并行系統(tǒng)上運(yùn)行對(duì)應(yīng)的并行算法的開(kāi)銷的比值。 在單處理器上解一個(gè)題的開(kāi)銷被定義為已知的最快的

15、串行算法的運(yùn)行時(shí)間，如果對(duì)一個(gè)特定的問(wèn)題，一個(gè)并行系統(tǒng)的開(kāi)銷與單處理器上的已知最快的串行算法的運(yùn)行時(shí)間成比例，那么，就稱這個(gè)系統(tǒng)是開(kāi)銷開(kāi)銷最優(yōu)最優(yōu)的。由于效率可以表示成串行開(kāi)銷與并行開(kāi)銷的比值，所以，一個(gè)開(kāi)銷最優(yōu)的并行系統(tǒng)的效率為 o(1)開(kāi)銷有的時(shí)候也被稱為工作或處理器-時(shí)間積，一個(gè)開(kāi)銷最優(yōu)的并行系統(tǒng)也被稱為pTp最優(yōu)系統(tǒng)。 開(kāi)銷 在n個(gè)處理器的超立方體上完成n個(gè)數(shù)的加法：開(kāi)始時(shí)，每個(gè)處理器都存放了一個(gè)待加的數(shù)據(jù)，算法結(jié)束時(shí)，其中的一個(gè)處理器中已經(jīng)存放了n個(gè)數(shù)累加的結(jié)果。 根據(jù)前面的討論結(jié)果，可以知道，在超立方體上完成n個(gè)數(shù)的加法的并行算法的處理器-時(shí)間積為 ，而串行運(yùn)行時(shí)間為 ，所以這個(gè)并

16、行系統(tǒng)并不是開(kāi)銷最優(yōu)的。在計(jì)算效率的時(shí)候也指出，這個(gè)并行系統(tǒng)的效率比1要低，這也說(shuō)明這個(gè)并行系統(tǒng)并不是開(kāi)銷最優(yōu)的。 粒度和數(shù)據(jù)映射在n個(gè)處理器的超立方體結(jié)構(gòu)的并行計(jì)算機(jī)上完成n個(gè)數(shù)據(jù)累加不是一個(gè)開(kāi)銷最優(yōu)的并行系統(tǒng)，這個(gè)并行算法中假定處理器的數(shù)目與數(shù)據(jù)的數(shù)目是一致的。但在實(shí)際 中，由于處理器數(shù)目是固定的，而輸入數(shù)據(jù)的數(shù)目則是可變的，因此每個(gè)處理器上往往會(huì)分配很多的數(shù)據(jù)，這相當(dāng)于增加每個(gè)處理器的計(jì)算粒度。用比系統(tǒng)中最大可能處理器數(shù)要少的處理器數(shù)來(lái)運(yùn)行并行算法稱為并行系統(tǒng)的處理器降規(guī)模（Scaling down）。一個(gè)降規(guī)模的方法是，設(shè)計(jì)一個(gè)并行算法使得每個(gè)處理器上一個(gè)數(shù)據(jù)，然后用少量的處理器來(lái)對(duì)大

17、量的處理器進(jìn)行仿真。如果有n個(gè)輸入數(shù)據(jù)，而僅僅 有p個(gè)處理器（p n），我們可以使用為n個(gè)處理器設(shè)計(jì)的并行算法，此時(shí)在程序員眼中，這實(shí)際上是n個(gè)虛擬處理器，在運(yùn)行時(shí)，用p個(gè)物理處理器來(lái)進(jìn)行仿真，每個(gè)處理器需要模 擬n/p個(gè)虛擬處理器。 粒度和數(shù)據(jù)映射當(dāng)處理器數(shù)目下降n/p倍，每個(gè)處理器上的計(jì)算量增加了n/p倍，因?yàn)楝F(xiàn)在每個(gè)處理器實(shí)際上需要完n/p個(gè)處理器的工作。如果虛擬處理器被恰當(dāng)?shù)挠成涞轿锢硖幚砥魃?，總的通信時(shí)間不超過(guò)原來(lái)的n/p倍，因此，總的并行運(yùn)行時(shí)間最多是原來(lái)的n/p倍，而處理器-時(shí)間積不會(huì)增加。因此，如果一個(gè)p處理器的并行系統(tǒng)是開(kāi)銷最優(yōu)的，用p個(gè)處理器來(lái)對(duì)n個(gè)處理器（p W后，系統(tǒng)的

18、效率也將降低，因此，問(wèn)題規(guī)模的增長(zhǎng)速度必須至少為 ，這樣才可能得到固定的效率，所以， 是等效率函數(shù)的漸進(jìn)下界，這和理想的可擴(kuò)展并行系統(tǒng)的等效率函數(shù)是 的結(jié)論是一致的 并發(fā)度與等效率函數(shù) 等效率函數(shù)的下界為 ，這是由一個(gè)并行系統(tǒng)的可以被并行執(zhí)行的操作數(shù)所決定的，定義一個(gè)并行算法中任意時(shí)刻都可以同時(shí)執(zhí)行的最大任務(wù)數(shù)為算法的并發(fā)度并發(fā)度。并發(fā)度衡量了問(wèn)題規(guī)模為W時(shí)，一個(gè)算法所能提供的并行操作的數(shù)目，它與并行體系結(jié)構(gòu)無(wú)關(guān)。如果C(W)是一個(gè)并行算法的并發(fā)度，那么對(duì)問(wèn)題規(guī)模W，不超過(guò)C(W)個(gè)處理器可以被有效利用。 并發(fā)度與等效率函數(shù)等效率度量指標(biāo)的最大優(yōu)點(diǎn)是，可以用簡(jiǎn)單的、可定量計(jì)算的、少量的參數(shù)就能

19、計(jì)算出等效率函數(shù)，并由其復(fù)雜度就可以指明算法的可擴(kuò)展性。這對(duì)于具有網(wǎng)絡(luò)互連結(jié)構(gòu)的并行計(jì)算機(jī)來(lái)說(shuō)是很合適的，因?yàn)門o是可以一步一步計(jì)算出來(lái)的。而且To是計(jì)算等效率函數(shù)的唯一關(guān)鍵參數(shù)，所以如果它不能夠方便的計(jì)算出來(lái)，則用等效率函數(shù)度量可擴(kuò)展性的方法就受到了限制。我們知道開(kāi)銷To通常包括了通信、同步、等待等額外計(jì)算開(kāi)銷。不幸的是，在共享存儲(chǔ)的并行計(jì)算機(jī)中，To則主要是非局部訪問(wèn)的讀/寫(xiě)時(shí)間、進(jìn)程調(diào)度時(shí)間、存儲(chǔ)競(jìng)爭(zhēng)時(shí)間以及Cache一致性維護(hù)時(shí)間，而這些時(shí)間是難以準(zhǔn)確計(jì)算的，所以用解析計(jì)算的方法不應(yīng)該是一種唯一的方法。1994年兩位中國(guó)學(xué)者Xian-He Sun和Xiao-Dong Zhang分別提出

20、了以實(shí)驗(yàn)測(cè)試為主要手段的兩種衡量可擴(kuò)展性的指標(biāo)，即等速度（isospeed）和平均延遲指標(biāo)。 等速度度量指標(biāo) 速度是一個(gè)非常重要的機(jī)器參數(shù)，一般在機(jī)器性能指標(biāo)中都會(huì)明確的給出，并常以每秒多少次浮點(diǎn)運(yùn)算來(lái)表明（浮點(diǎn)運(yùn)算的數(shù)目可以給出問(wèn)題規(guī)模W）。所以若用速度來(lái)度量可擴(kuò)展性，在理論上講是更為方便的，而等速度方法的基本出發(fā)點(diǎn)就是如此。在并行系統(tǒng)中，提高速度可以用增加處理器數(shù)目的方法，如果速度能夠隨處理器數(shù)目的增加而線性增長(zhǎng)（這意味著平均速度不變），則說(shuō)明這個(gè)系統(tǒng)具有很好的可擴(kuò)展性。首先需要給出嚴(yán)格的計(jì)算速度的定義。p個(gè)處理器的并行系統(tǒng)，W為問(wèn)題規(guī)模（這里指浮點(diǎn)操作個(gè)數(shù)），T為并行執(zhí)行時(shí)間，則定義并行

21、計(jì)算的速度V為問(wèn)題規(guī)模W與并行運(yùn)行時(shí)間T的商： V=W/T等速度度量指標(biāo)而p個(gè)處理器的并行系統(tǒng)的平均速度定義為并行計(jì)算速度V除以處理器個(gè)數(shù)p：根據(jù)平均速度的定義，定義等平均速度（簡(jiǎn)稱為等速度）可擴(kuò)展性度量指標(biāo)如下：對(duì)于運(yùn)行于并行計(jì)算機(jī)上的某個(gè)并行算法，當(dāng)處理器數(shù)目增加時(shí)，若增加一定的工作量能夠維持整個(gè)并行系統(tǒng)的平均速度不變，則稱該計(jì)算是可擴(kuò)展的。 注意，當(dāng)平均速度為常數(shù)時(shí)，也就是速度與處理器數(shù)目成線性比例增長(zhǎng)，也就是加速比與處理器數(shù)目成比例增長(zhǎng)。 等速度度量指標(biāo)按此定義，如果W是使用p個(gè)處理器時(shí)算法的問(wèn)題規(guī)模，令W表示當(dāng)處理器數(shù)目由p增大到p時(shí)，為了保持整個(gè)系統(tǒng)的平均速度不變所需要的問(wèn)題規(guī)模（工作量），則可以得到處理器數(shù)目從p增加到p時(shí)平均速度公式為 用上面的公式計(jì)算出的值介于0與1之間，值越大表示可擴(kuò)展性越好。 等速度度量指標(biāo)等速度度量指標(biāo)的最大優(yōu)點(diǎn)是使用機(jī)器速度指標(biāo)這一明確的物理量來(lái)度量可擴(kuò)展性，比較直觀。速度是由工作負(fù)載W和執(zhí)行時(shí)間T決定的，而W反映了應(yīng)用程序的性 質(zhì)，T反映了結(jié)構(gòu)和程序效率的影響；速度是各種結(jié)構(gòu)的及其相互可比較的量；執(zhí)行時(shí)間包含了計(jì)算和延遲這兩個(gè)主要的時(shí)間量；速度是比較容易測(cè)量的，因?yàn)閃可 由所執(zhí)行的浮點(diǎn)操作數(shù)決定。等速度度量指標(biāo)的缺點(diǎn)是僅用浮點(diǎn)操作數(shù)作為W時(shí)不全面的，某些非浮點(diǎn)運(yùn)算可能造成性能的主要變化；延