并行計(jì)算機(jī)性能課件

1

并行計(jì)算機(jī)性能針對(duì)一個(gè)并行系統(tǒng)，需討論計(jì)算和開(kāi)銷(xiāo)特征一、計(jì)算特征下表給出了3種商品化并行計(jì)算機(jī)系列的性能參數(shù)的歷史值23存儲(chǔ)器層次結(jié)構(gòu)：存儲(chǔ)器容量存儲(chǔ)器時(shí)延存儲(chǔ)器帶寬1996年前后計(jì)算機(jī)中這3個(gè)參數(shù)的典型值45二、并行性和通信開(kāi)銷(xiāo)

并行程序中的開(kāi)銷(xiāo)可分為3類(lèi)負(fù)載不平衡開(kāi)銷(xiāo)；并行性開(kāi)銷(xiāo)；通信開(kāi)銷(xiāo)(包括同步、通信和聚集)。

T=Tcomp+Tpar+Tinteract6說(shuō)明：有3種類(lèi)型的并行性操作。它們是并行性開(kāi)銷(xiāo)的來(lái)源:進(jìn)程管理；分組操作進(jìn)程查詢操作7通信開(kāi)銷(xiāo)的來(lái)源有3種類(lèi)型的操作同步聚集通信8巨大開(kāi)銷(xiāo):注意有關(guān)并行性和通信開(kāi)銷(xiāo)的兩個(gè)要點(diǎn)：通常比基本計(jì)算時(shí)間要大得多，在不同系統(tǒng)上變化很大。91011三、開(kāi)銷(xiāo)定量化1.問(wèn)題的提出應(yīng)對(duì)計(jì)算的并行性和通信開(kāi)銷(xiāo)進(jìn)行量化。122.開(kāi)銷(xiāo)測(cè)量條件進(jìn)行測(cè)量實(shí)驗(yàn)的確切條件必須清楚地加以說(shuō)明。以下是部分列表:所使用的數(shù)據(jù)結(jié)構(gòu)。所使用的編程語(yǔ)言、庫(kù)以及編譯器選擇。一般地，開(kāi)銷(xiāo)測(cè)量應(yīng)以批處理方式進(jìn)行，都會(huì)被執(zhí)行。13所使用的通信硬件和協(xié)議。因?yàn)樵谶@種方式下大多數(shù)生成路徑(productionrun)測(cè)量掛鐘時(shí)間或是CPU時(shí)間。一般來(lái)講，掛鐘時(shí)間更有用。143.開(kāi)銷(xiāo)測(cè)量方法雖然測(cè)量開(kāi)銷(xiāo)粗看起來(lái)非常簡(jiǎn)單，但要獲得精確測(cè)量結(jié)果卻是很具挑戰(zhàn)性的任務(wù)主要的原因有3種15乒乓方案：是測(cè)量點(diǎn)對(duì)點(diǎn)通信常用的方法:結(jié)點(diǎn)0執(zhí)行一個(gè)發(fā)送操作向結(jié)點(diǎn)1發(fā)送一個(gè)m字節(jié)的消息，后者執(zhí)行一個(gè)接收操作收到此消息結(jié)點(diǎn)1立即發(fā)送相同消息給結(jié)點(diǎn)016例題：測(cè)量時(shí)延的乒乓方案：

for(i=0；i<Runs；i++)

if(my_node_id==0){/*發(fā)送方*/

Tmp=Second()；

start_time=Second()；向結(jié)點(diǎn)1發(fā)送一個(gè)m字節(jié)消息；從結(jié)點(diǎn)1接收一個(gè)m字節(jié)消息；

end_time=Second()；17timer_overhead=start_time-tmp；total_time=end_time-start_time-timer_overhead；communication_time[i]=total_time／2；}elseif(my_node_id==1){/*接收方*/從結(jié)點(diǎn)0接收一個(gè)m字節(jié)消息；向結(jié)點(diǎn)0發(fā)送一個(gè)m字節(jié)消息；}}18熱土豆(hot_potato)方法(也稱(chēng)為救火隊(duì)方法)。該方法面向n個(gè)結(jié)點(diǎn)；方法是個(gè)循環(huán)的發(fā)送接收。

19集合通信條件：設(shè)分布式存儲(chǔ)器多計(jì)算機(jī)中n個(gè)結(jié)點(diǎn)中的每一個(gè)均執(zhí)行以下的SPMD程序。使用路障來(lái)同步測(cè)量進(jìn)程中的異步操作。20for(i=0；i<Runs；i++){

Barriersynchronization；Tmp=Second()；start_time=Second()；for(j=0；j<Iterations；j++)The_collective_routine_being_measured；End_time=Second()；21Timer_overhead=start_time-tmp；Total_time=end_time-start_time–timer_overhead；Local_time=total_time/Iterations；Communication_time[i]=maximumOfallnlocaltimevalues；}22改用集合操作的通用化乒乓方法：for(i=0；i<Runs；i++){if(my_node_id==0){tmp=Second()；start_time=Second();結(jié)點(diǎn)0向所有n個(gè)結(jié)點(diǎn)廣播一個(gè)空消息；For(j=0；i<Iterations；j++)23thecollective_routine_being_measured；所有結(jié)點(diǎn)向結(jié)點(diǎn)0完成一個(gè)空歸約；

if(my_node_id=0){end_time=Second()；timer_overhead=start_time-tmp；Communication_time[i]=end_time-start_time-

timer_overhead}244.開(kāi)銷(xiāo)表達(dá)式經(jīng)測(cè)量獲得開(kāi)銷(xiāo)數(shù)據(jù)，有3種表示方法：用表格來(lái)表示數(shù)據(jù)。例如，下表給出了在SP2上運(yùn)行專(zhuān)有MPL通信庫(kù)所測(cè)得的點(diǎn)對(duì)點(diǎn)通信的定時(shí)結(jié)果。2526以曲線來(lái)表示數(shù)據(jù)如下圖所示。其優(yōu)點(diǎn)是曲線可示出通信開(kāi)銷(xiāo)增長(zhǎng)趨向。

2728表達(dá)式表示例如，將所測(cè)得的定時(shí)數(shù)據(jù)用最小二乘法適當(dāng)?shù)丶右詳M合。就可將SP2上的點(diǎn)對(duì)點(diǎn)通信開(kāi)銷(xiāo)表示成消息長(zhǎng)度的線性函數(shù)：t=46+0.035mμs如果加以擬合，它與曲線之間的誤差是很小的，如上圖所表明的那樣。295.點(diǎn)對(duì)點(diǎn)通信表達(dá)式Hockney提出操作通信時(shí)間(以μs表示)特征的1個(gè)模型，其中的通信開(kāi)銷(xiāo)t(m)是消息長(zhǎng)度m(以字節(jié)表示)的線性函數(shù)：

t(m)=t0+m／r∞式中t0是以μs表示的啟動(dòng)時(shí)間，而r∞是漸近帶寬，單位MB／s。30Hockney還引入了兩個(gè)附加的參數(shù)。半峰值長(zhǎng)度記為m1/2字節(jié)，是達(dá)到半漸近帶寬所需的消息長(zhǎng)度。特殊性能，記為

0MB／s，用來(lái)表明短消息帶寬。314個(gè)參數(shù)t0、r∞

、

m1/2、

0MB中的兩個(gè)是獨(dú)立的。另兩個(gè)可用以下關(guān)系推得：t0=m1/2

／r∞=1/

0其中m1/2是表示系統(tǒng)支持短消息通信好壞程序的參數(shù)。

32例如：SP2的t(m)=46+0.035m。啟動(dòng)開(kāi)銷(xiāo)為t0=46μs；漸近帶寬為：r∞=1／0.035=28.57MB／s，以及半峰值消息長(zhǎng)度為：m1/2

=t0×r∞=1314字節(jié)。336.集合通信

將式Hockney表達(dá)式擴(kuò)展成如下：通信開(kāi)銷(xiāo)T(m,n)現(xiàn)改為是m和n兩者的函數(shù)。但啟動(dòng)時(shí)延仍只依賴于n。漸近帶寬變?yōu)閞∞(n)。

T(m,n)=t0(n)+m/r∞(n)34在將測(cè)得的定時(shí)數(shù)據(jù)與不同的t0(n)和r∞(n)形式擬合可推得如表中所示的4個(gè)集合操作的公式35367.集合計(jì)算測(cè)量了3種代表性的集合計(jì)算操作：路障、歸約和掃描。它們擬合曲線開(kāi)銷(xiāo)表達(dá)式如下表所示。注意當(dāng)處理器數(shù)超過(guò)256時(shí)，路障開(kāi)銷(xiāo)為762μs，相當(dāng)于執(zhí)行762x266=202,692flop所需的時(shí)間。現(xiàn)在可以回答這樣問(wèn)題，是否應(yīng)使用同步算法?3738短