并行程序性能课件

1

並行程式性能2一、性能指標1.前言設順序程式C由一串A個分計算階段C1，C2，…Ck所組成DOPi是並行性下圖給出了一個階段並行程式342.基本指標從語義上講，上圖有順序執行的步Ci計算的工作負載，如上圖示可求總並行性開銷5當在n個處理器上執行工作負載時，步Ci並行執行時間：Tn(i)=T1(i)/n在n個結點上總的並行執行時間為：

63.極值指標

存在幾個極值指標以給出Pn、Tn和Sn的下限和上限。設T∞是關鍵路徑的長度，有：7使得Tn=T∞的n最小值稱為最大並行性，記為Nmax。可由Nmax=max1≤j

k(DOPi)計算該指標。持續加速比Pn的最大值P∞=W／T∞是它的上限。N個結點執行時間Tn的下限值為T1／n和T∞。Tn≥max(T1/n,T∞

)8平均並行性T1/T∞，是加速比的上限。即Sn≤T1/Tn。Brent已證明，若不計所有並行性和交互開銷，Tn受限於下列不等式：T1/n≤Tn

T1/n+T∞將Tn≥max(T1/n,T∞

)代入可得：max(T1/n

,T∞)≤

Tn

T1/n+T∞。這些不等式在估計並行執行時間時很有用。9下表基於階段並行模型性能的一些指標：10114.例題：STP中APT基準程式

為便於理解，STAP基準程式組中的APT程式可描述如下：其中變數N為問題參數。記號[.]變數house是一個含有約80KB資訊的矩陣，與N無關12For(j=0；j<N；j++)for(k=0；k<32；k++)fft(data[.][j][k])；ht(data[1][.][.]，house)；for(i=0；i<N；i++)bf(data[i][.][.],housedetect[i][.])For(j=0；j<N；j++)for(i=0；i<N；i++)td(detect[i][j]，target_report)；13145.例題：並行APT基準測試程式的性能指標15假設條件：每個計算步的工作負載由上圖(STP中APT圖）中值求得，以單SP2結點的Mflop和執行時間表示。並行性開銷忽略不計。在忽略不計所有通信開銷情況下，來預測性能指標的極端值，稱其為0_開銷預測。一個粗粒度階段並行演算法，參數N=256。16由上圖可知最大並行性為:max(8192，1，256，256)=8192總工作負載W=1447Mflop；順序執行時間T1=14．37s；關鍵路徑為17求得最大性能值P∞=W/T∞=1447/0.08=18087Mflop／s，而平均並行性為T1/T∞=14．37/0.08=180。186.例題：估計APT基準測試程式中的交互開銷可用上述表的運算式來估計運行在SP2上的並行APT程式的交互開銷。交互開銷是3種通信的和：T=Tcomp+Tpar+Tinteract19202122從上表和圖可見，16.7/n2MB的全交換開銷為：Tindex=80logn+0.03n1.29mμs=0.00008logn+0.5n-0.71秒廣播開銷的運算式為:Tbcast=52logn+(0.029logn)mμs=0.00237logn秒23歸約n個flop數所需時間為：20logn+23μs；其中由n個結點中的每一個提供一個flop數。在APT圖的歸約步中，組合了n個目標報告，每個有100個flop數。可保守地評估歸約開銷：Treduce=100(20logn+23)μs=0.002logn+0.0023秒24那麼總的交互開銷為：T0=Tinteract=0.5n-0.71+0.00445logn+0.0023；有以下說明：並行處理中的一個觀念是通信開銷隨所使用結點數的增加而增長。但由上面例子可見，這可能是錯的。在APT程式中當所使用結點不多於256時，總的通信開銷隨機器規模增加而減少。257.例題：APT基準測試程式期望執行時間來預測並行APT演算法在n<256結點的SP2上的執行時間。並計算當n=256時的平均顆粒度。使用n個結點的總執行時間為：T=Tcomp+Tpar+Tinteract=14.33/n+0.5n-0.71+0.00445logn+0.042326單SP2結點的總工作負載W=1447Mflop或14．37s。平均顆粒度為:W/T0=1447M/0.0479=30209對於每Mflop計算，平均的通信開銷為:1／30209=33μs27也可將執行時間作為工作負載。那麼平均顆粒度變為W/T0=14.37/0.0479=300

因此平均而言，對於每秒通信，256個結點共完成300s計算，或對於每秒通信，每個結點完成300／256=1．17s計算。28二、基準程式中的可用並行性關於並行成分的討論應用程式中潛在並行性有很寬的範圍。工程和科學代碼具有數據並行性，有很高的DOP。29數據的並行：Kumar(1988年)已報導過密集計算代碼在理想環境下於每個時鐘內可併發地執行500到3500個算術操作。指令級並行：要低得多。Wall指出指令級並行性的極限約在5左右，很少超過7。Bulter等(1991年)曾報導過當去除所有約束時，在某些科學程式中lLP可超過每週期17條指令。30某些程式跟蹤結果指出，如果體系結構和編譯器能完滿地工作，則在一個合理設計的超標量處理器上，可期待的lLP為每週期併發執行2.0到5.8條指令。下表中為PERFECT基準測試程式組中12個程式中的每一個給出了其平均並行性。

3132例題：3個STAP基準測試程式性能下表中示出了使用最小、最大和名義數據集時，STAP基準測試程式組中3個程式的某些性能指標。其中的輸入數據規模和工作負載由STAP基準測試程式規範給定。3334以