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

1

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

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

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

19集合通信條件：設(shè)分布式存儲(chǔ)器多計(jì)算機(jī)中n個(gè)結(jié)點(diǎn)中的每一個(gè)均執(zhí)行以下的SPMD程序。使用路障來同步測量進(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.開銷表達(dá)式經(jīng)測量獲得開銷數(shù)據(jù)，有3種表示方法：用表格來表示數(shù)據(jù)。例如，下表給出了在SP2上運(yùn)行專有MPL通信庫所測得的點(diǎn)對點(diǎn)通信的定時(shí)結(jié)果。2526以曲線來表示數(shù)據(jù)如下圖所示。其優(yōu)點(diǎn)是曲線可示出通信開銷增長趨向。

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

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

0MB／s，用來表明短消息帶寬。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)開銷為t0=46μs；漸近帶寬為：r∞=1／0.035=28.57MB／s，以及半峰值消息長度為：m1/2

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

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

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