高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)_第1頁
已閱讀1頁,還剩49頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系高性能計(jì)算研究所鄭緯民 教授2007年9月,計(jì)算機(jī)科學(xué)與技術(shù)系研究生課程,高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),第一章 高等計(jì)算機(jī)的核心技術(shù)——并行處理第二章 加速比性能模型與可擴(kuò)展性分析第三章 互連與通信第四章 劃分與調(diào)度第五章 并行存儲器系統(tǒng)第六章 Cache Coherence第七章 Memory Consistency第八章 指令級并行處理第九章 微處理器設(shè)計(jì)與實(shí)

2、現(xiàn)方法第十章 網(wǎng)格計(jì)算,高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),第十一章 DSM第十二章 傳感器網(wǎng)絡(luò)第十三章 對等計(jì)算第十四章 海量網(wǎng)絡(luò)存儲器第十五章 多核CPU技術(shù)第十六章 可信計(jì)算系統(tǒng)第十七章 虛擬化技術(shù)第十八章 基于集群的海量數(shù)據(jù)處理,第二章 加速比性能模型與可擴(kuò)展性分析,2.1 加速比性能分析2.1.1 一般概念2.1.2 加速比2.1.3 三種加速比性能模型2.2 可

3、擴(kuò)展性分析,2.1 加速比性能模型,2.1.1 一般概念1.處理機(jī)—時間積處理機(jī)數(shù)目與處理時間的乘積用以度量這些處理機(jī)運(yùn)行時的資源利用率。若一程序在?P臺處理機(jī)上運(yùn)行的時間為Tp,則此P臺處理機(jī)在Tp時間間隔內(nèi)完成的工作最大數(shù)量為Tp * P。可將處理機(jī)實(shí)際工作曲線對時間的積分看成是這些處理機(jī)完成的有效工作量。效率為有效工作量與最大工作量之比。,2.并行度(Degree Of Parallelis

4、m—DOP)并行度(DOP)是在一定時間間隔內(nèi)執(zhí)行一個程序所用的處理機(jī)的數(shù)目。3.并行性分布圖 執(zhí)行一個給定的程序時DOP對時間的分布圖。DOP與對應(yīng)時間的間隔之積即為處理機(jī)要完成的工作或工作負(fù)載。 下圖所示為一個并行性分布圖。,,,,,,,,,,,,,,,,DOP,t1,t,t2,,并行性分布圖,2.1.2 加速比1. 絕對加速比將最好的串行算法與并行算法相比較. 定義一(與具體機(jī)器有關(guān))將最好

5、的串行算法在一臺上的運(yùn)行時間與并行算法在N臺運(yùn)行的時間相比。 定義二(與具體機(jī)器無關(guān))將最好的串行算法在最快的順序機(jī)上的執(zhí)行時間與并行算法在并行機(jī)上的運(yùn)行時間相比。,2.相對加速比同一并行算法在單節(jié)點(diǎn)上運(yùn)行時間與在多個相同節(jié)點(diǎn)構(gòu)成的處理機(jī)系統(tǒng)上的運(yùn)行時間之比。這種定義側(cè)重于描述算法和并行計(jì)算機(jī)本身的可擴(kuò)展性。,線性加速比:中間開銷小,通信少,弱耦合計(jì)算超線性加速比:當(dāng)應(yīng)用需要大內(nèi)存時可能出現(xiàn)病態(tài)加速比:加速比遞

6、減,可能是計(jì)算量太小,2.1.3 三種加速比性能模型,1.固定負(fù)載加速比性能模型—Amdahl定律在許多實(shí)時應(yīng)用領(lǐng)域,計(jì)算負(fù)載的大小常固定。在并行機(jī)中,此負(fù)載可分布至多臺并行執(zhí)行,獲得的加速比稱為fixed-load speedup。一個問題的負(fù)載可表示如下:W = Ws + Wp其中,Ws代表問題中不可并行化的串行部分負(fù)載, Wp表示可并行化的部分負(fù)載。 則n個節(jié)點(diǎn)情況下,加速比可以表示如下:,設(shè)串行因子α為串行部分所

7、占的比例。即,代入即得Amdahl’law:,不管采用多少處理機(jī),可望達(dá)到的最好加速比:,效率En可以表示為:,處理機(jī)數(shù)目n越大,效率En越低。Amdahl定律告訴我們:系統(tǒng)中某一部件由于采用某種更快的執(zhí)行方式后整個系統(tǒng)性能的提高與這種執(zhí)行方式的使用頻率或占總執(zhí)行時間的比例有關(guān)。,加速比的兩個決定因素:1.計(jì)算機(jī)執(zhí)行某個任務(wù)的總時間中可被改進(jìn)部分的時間所占的百分比,即可被改進(jìn)部分占用時間/改進(jìn)前整個任務(wù)的執(zhí)行時間,記為Fe

8、,它總小于1。2.改進(jìn)部分采用改進(jìn)措施后比沒有采用改進(jìn)措施前性能提高的倍數(shù),即改進(jìn)前改進(jìn)部分執(zhí)行時間/改進(jìn)后改進(jìn)部分執(zhí)行時間,記為Se。,例1:假設(shè)將某系統(tǒng)的某一部件的處理速度加快到10倍,但該部件的原處理時間僅為整個運(yùn)行時間的40%,則整個系統(tǒng)的性能提高了多少?解:Fe = 0.4,Se = 10,,例2:采用哪種實(shí)現(xiàn)技術(shù)來求浮點(diǎn)數(shù)平方根FPSQR的操作對系統(tǒng)的性能影響較大。假設(shè)FPSQR操作占整個測試程序執(zhí)

9、行時間的20%。一種實(shí)現(xiàn)方法是采用FPSQR硬件,使FPSQR操作的速度加快到10倍。另一種方法是使所有浮點(diǎn)數(shù)據(jù)指令的速度加快,使FP指令的速度加快到2倍,還假設(shè)FP指令占整個執(zhí)行時間的50%。請比較這兩種設(shè)計(jì)方案。解:Fe_FPSQR = 0.2,Se_FPSQR = 10, Fe_FP = 0.5,Se_FP = 2,,Amdahl’law又稱為固定規(guī)模加速比模型,問題規(guī)模不隨處理機(jī)變化而變化。固定問題

10、規(guī)模,看用并行技術(shù)能達(dá)到的最短時間是多少。在固定規(guī)模加速比模型下,負(fù)載和執(zhí)行時間隨系統(tǒng)中處理機(jī)數(shù)目n變化的情況如下圖:,,,Ws,Wp,Ws,Wp,Ws,Wp,Ws,Wp,Workload,N,1,2,3,4,固定負(fù)載,執(zhí)行時間隨N增加而減少,固定負(fù)載加速比模型下的負(fù)載和執(zhí)行時間情況,當(dāng)處理器數(shù)目n=1024,加速比Sn隨α變化的情況如下:,得出曲線如下圖:,91,Sn,α,1024,48,31,24,10,可以比較不同的α對加速比

11、帶來的不同影響:,α=0時得到理想加速比,當(dāng)α值增加時,加速比性能急劇下降。,結(jié)論:加速比曲線隨α的上升急劇下降,原因是存在順序部分Ws,無法用增加系統(tǒng)的處理機(jī)數(shù)目來解決。這一性質(zhì)在過去二十年間給人們造成了對并行處理非常悲觀的印象。影響:兩種意見: 1.勸阻制造商生產(chǎn)大規(guī)模并行計(jì)算機(jī)。 2.研究并行編譯器,以降低α的值,從而提高系統(tǒng)的性能。規(guī)定負(fù)載加速比模型的可能應(yīng)用范圍: 對時間要求嚴(yán)格的應(yīng)用問題。

12、,2.固定時間加速比性能模型—Gustafsun定律有許多應(yīng)用領(lǐng)域強(qiáng)調(diào)精度而不時運(yùn)行時間。1988年,Gustafsun提出了固定時間加速比模型。當(dāng)機(jī)器的規(guī)模擴(kuò)大時,解題的規(guī)模也隨著擴(kuò)大,從而得到更加精確的解,而使運(yùn)行時間保持不變。比如:有限元方法做結(jié)構(gòu)分析,流體動力學(xué)做天氣預(yù)報解PDE(偏微分方程組)就需要提高精度。粗格要求的計(jì)算量較少,而細(xì)格的計(jì)算量多,得到的精確度也較高。天氣預(yù)報模擬求解四維PDE,如果使每個實(shí)際

13、方向(X,Y,Z)的格點(diǎn)距離減少10倍,并以同一幅度增加時間步,那么可以說格點(diǎn)增加了104倍,因而工作負(fù)載也至少增大了10000倍。,模型提出的背景:固定負(fù)載模型有缺陷:因?yàn)锳mdahl’law中,α取決于問題及并行編譯器的效率,無法描述系統(tǒng)固有的特性。加速比的公式:,其中,Wp’=nWp和Ws+Wp=Ws’+Wp’/n作為固定時間的條件。 Ws’+Wp’/n表示在擴(kuò)大負(fù)載后在增加處理機(jī)臺數(shù)的情況下的平均負(fù)載(執(zhí)行時間),它應(yīng)當(dāng)

14、和負(fù)載沒有擴(kuò)大情況下的平均負(fù)載(執(zhí)行時間)Ws+Wp相等。即有Ws+Wp=Ws’+Wp’/n。同時,負(fù)載的串行部分并沒有改變,即有Ws=Ws’。,在固定時間加速比模型下,負(fù)載和執(zhí)行時間隨系統(tǒng)中處理機(jī)數(shù)目n變化的情況如下圖:,,,Ws,Wp,Ws,Wp,Ws,Wp,Ws,Wp,Workload,N,1,2,3,4,Ts,Tp,2,Ts,Tp,3,Ts,Tp,4,并行負(fù)載不斷增加,執(zhí)行時間固定,固定時間加速比模型下的負(fù)載和執(zhí)行時間情況,增大

15、問題規(guī)模的辦法使所有處理機(jī)保持忙碌狀態(tài),在問題擴(kuò)大到與可用的計(jì)算能力匹配時,程序中的順序部分就不再是瓶頸了。當(dāng)處理器數(shù)目n=1024,加速比Sn隨α變化的情況如下:,Sn’,α,1024,1014,1004,993,983,3.受限于存儲器的加速比模型1993年,由Sun和Ni提出。大型科學(xué)計(jì)算和工程設(shè)計(jì)需要較大的存儲空間,許多應(yīng)用問題是存儲器受限,而不是CPU受限或者I/O受限。比如:在分布存儲系統(tǒng)中常遇到,總存

16、儲容量隨節(jié)點(diǎn)數(shù)線性增加,許多節(jié)點(diǎn)集合起來解一個大題?;舅枷耄阂诖鎯臻g有限條件下解盡可能大的問題,這同樣需要擴(kuò)展工作負(fù)載,才能提供較高的加速比、較高的精度和較好的資源利用率。,加速比可以表示如下:,其中:在單個處理機(jī)上順序執(zhí)行的工作負(fù)載與問題的規(guī)?;蛳到y(tǒng)的規(guī)模無關(guān),即:,而G(n)反映的是存儲容量增加n倍時并行工作負(fù)載增加的倍數(shù)。,討論:1.G(n) = 1,即為固定負(fù)載的情況;2.G(n) = n,即存

17、儲器增加n倍,負(fù)載也增加n倍,為固定時間的情形;3.G(n) > n,計(jì)算負(fù)載的增加情況比存儲器增加快,會有較高的加速比。比較三種加速比,對于相同的處理機(jī)數(shù)量,有:,在受限于存儲器的加速比模型下,負(fù)載和執(zhí)行時間隨系統(tǒng)中處理機(jī)數(shù)目n變化的情況如下圖:,,,Ws,Wp,Ws,Wp,Ws,Wp,Ws,Wp,Workload,N,1,2,3,4,Ts,Tp,1,Ts,Tp,2,Ts,Tp,3,Ts,Tp,4,規(guī)模擴(kuò)展的工作負(fù)載,

18、執(zhí)行時間稍有增加,受限于存儲器的加速比模型下的負(fù)載和執(zhí)行時間情況,例:n維矩陣乘法:A * B = C,其中A、B、C都是n*n的方陣。為得到C的每一個元素需要進(jìn)行n次乘法、n次加法,所以總的計(jì)算量為:(n+n)*n2 = 2n3。需要的存儲量為3n2(兩個源矩陣,一個結(jié)果矩陣)。如果n臺計(jì)算機(jī)組成多計(jì)算機(jī)系統(tǒng),則存儲容量擴(kuò)大n倍,那么矩陣的維數(shù)(原來為n)也可以增加了,設(shè)為N倍,那么加速比為多少? 解:存儲容量變?yōu)椋簄M

19、 = n* 3n2 = 3n3,而N維需要的存儲量為3N2,計(jì)算量變?yōu)?N3,則有:,4.并行計(jì)算的應(yīng)用模型隨機(jī)器規(guī)模的增大,工作負(fù)載增長的模式如下圖:,工作負(fù)載(問題規(guī)模),n,θ(指數(shù)),γ(線性),β(亞線性),α(常數(shù)),上圖中:采用受限于存儲器的加速比模型中給出的公式,θ曲線對應(yīng)的G(n) = n1.5γ曲線對應(yīng)的G(n) = nβ曲線對應(yīng)的G(n) = 0.5nα曲線對應(yīng)的G(n) = 1

20、則有加速比公式:,給定一個程序,假設(shè)Ws/Wp = 0.4,那么效率為:,相應(yīng)的處理器數(shù)目—效率曲線如下圖:,效率,n,θ(指數(shù)),γ(線性),β(亞線性),α(常數(shù)),結(jié)論:1.如果工作負(fù)載(問題規(guī)模)保持不變,那么效率E隨機(jī)器規(guī)模的增大而迅速下降,其原因是開銷h比機(jī)器規(guī)模增加得快,為了使效率保持在一定的水平上,我們可以按比例增大機(jī)器規(guī)模和問題規(guī)模。2.如果工作負(fù)載按指數(shù)增長模式,效率要保持恒定或保持良好的加速比,必須

21、使問題規(guī)模猛增才行,這樣就會超過存儲器或I/O限制,而問題規(guī)模只允許在計(jì)算機(jī)存儲器可用的限度以內(nèi)增長。,并行計(jì)算機(jī)的應(yīng)用模型如下圖:,,,,通信界限,存儲器界限,,,受限于存儲器模型,工作負(fù)載(問題規(guī)模),機(jī)器規(guī)模,固定負(fù)載模型,固定時間模型,第二章 加速比性能模型與可擴(kuò)展性分析,2.1 加速比性能分析2.2 可擴(kuò)展性分析2.2.1 可擴(kuò)展性2.2.2 可擴(kuò)展性分析,2.2 可擴(kuò)展性分析,2.2.1 可擴(kuò)展性

22、1.可擴(kuò)展性與可編程性,,,增加可擴(kuò)展性,增加可編程性,分布存儲的消息傳遞型多計(jì)算機(jī),共享存儲型多處理機(jī),理想并行計(jì)算機(jī),,,2.可擴(kuò)展性指標(biāo)機(jī)器規(guī)模(n)時鐘頻率(f)問題規(guī)模(s)CPU時間(T)I/O需求(d)存儲容量(m)通信開銷(h)計(jì)算機(jī)價格(c)程序設(shè)計(jì)開銷(p),3.可擴(kuò)展性的直觀定義對任意數(shù)量(n)的處理機(jī)和任意規(guī)模(s)的問題,若所有算法的系統(tǒng)效率 E = 1, 則系統(tǒng)

23、是可擴(kuò)展的。,4.規(guī)??蓴U(kuò)展性系統(tǒng)性能隨處理機(jī)數(shù)量線性增長,包括:處理速度和效率存儲速度和容量互連帶寬和時延I/O速度和容量軟件開銷規(guī)??蓴U(kuò)展性與空間局部性、時間局部性以及部件瓶頸都有關(guān)系。例子:Cray Y-MP:16臺處理機(jī)范圍可伸縮CM-2:8K-64K臺處理機(jī)范圍可伸縮CM-5:1024-16K臺處理機(jī)范圍可伸縮KSR-1:8-1088臺處理機(jī)范圍可伸

24、縮,5.換代(時間)可擴(kuò)展性對系統(tǒng)各部分更換成新技術(shù)后,性能隨之易擴(kuò)展,要求算法、S/W均能兼容運(yùn)行。,6.問題可擴(kuò)展性問題規(guī)模擴(kuò)大時,系統(tǒng)仍能很好的運(yùn)行,或說問題規(guī)模擴(kuò)展到很大時,系統(tǒng)能在給定粒度下高效運(yùn)行。,2.2.2 可擴(kuò)展性1.恒等效率概念(Isoefficiency)恒等效率定義為一個并行算法在并行計(jì)算機(jī)上實(shí)現(xiàn)時,為保持效率E固定所需的工作負(fù)載與機(jī)器規(guī)模n的相對關(guān)系。設(shè):W = W(s)為工作負(fù)載,

25、 h = h (s,n)為通信開銷,它隨s、n增加而增大。其中,s為問題規(guī)模,n為機(jī)器規(guī)模。則效率可以表示為:,問題的關(guān)鍵在于W(s)與h(s,n)之間的相對增長速度。機(jī)器規(guī)模一定,開銷h的增長比工作負(fù)載W要慢。因而,對一定規(guī)模的機(jī)器來說,效率會隨問題規(guī)模增大而提高。所以,假若工作負(fù)載W隨機(jī)器規(guī)模適當(dāng)增加,那么就有希望保持效率不變。 對于已知的算法來說,為了保持恒定的效率,工作負(fù)載W可能需要對n以多項(xiàng)式或指數(shù)

26、規(guī)律增長。不同的算法可能需要不同的工作負(fù)載增長速率以便在n增加時保持效率不致下降。 一般并行算法的恒定效率函數(shù)是n的多項(xiàng)式函數(shù),即它們?yōu)镺(nk),k ? 1。n的冪越小,并行系統(tǒng)的可擴(kuò)展性越大(系統(tǒng)包括算法和結(jié)構(gòu)的組合)。,2.恒等效率函數(shù)并行程序執(zhí)行時間 Tp = (T1+T0)/p,其中,T1為總工作負(fù)載串行執(zhí)行時間,T0為多節(jié)點(diǎn)總通信延時,p為節(jié)點(diǎn)數(shù)。那么,加速比為:,而T1 = W tc,W為以操作次數(shù)

27、計(jì)算的總工作負(fù)載,tc為每個操作的平均執(zhí)行時間。,如前面所述,工作負(fù)載W與開銷h均可以表示成n與s的函數(shù),所以,效率也可以表示如下:,為了使E保持不變,工作負(fù)載W(s)應(yīng)該與開銷h(s,n)成比例增長,由此可以得出以下條件:,如果工作負(fù)載W(s)與fE(n)一樣快的增長,那么已知算法結(jié)構(gòu)組合就能使效率保持恒定。這個結(jié)論和前面的結(jié)論是一致的。此時, W(s)與fE(n)是相同的,只要求出了W(s)的數(shù)量級,就可知道fE(n)了。為了得

28、到恒等效率,只要使W(s)與h(s,n)同一個數(shù)量級就可以了。,例1:矩陣乘法的W(s) = O(s3)(其中s為維數(shù)),還設(shè)h(s,n)= O(nlogn+s2n0.5)。求fE(n) 。 解:,要滿足W與h同數(shù)量級的條件,需要在兩式中選出大的:,例2:W(s) = O(s3),h(s,n)= O(nlogn+s2n1/3logn)。求fE(n) 。 解:,比較兩個式子,選出較大的:,例3:W(s

29、) = O(s3),h(s,n)= O(nlogn+s3)。求fE(n) 。 解:,第二個式子顯然成立,故,例4:在n臺處理機(jī)網(wǎng)格和超立方體計(jì)算機(jī)上分別計(jì)算1維s點(diǎn)的FFT,其工作負(fù)載W(s) = O(slogs),已知:超立方體計(jì)算機(jī)上:h1(s,n)= O(nlogn+slogn),網(wǎng)格計(jì)算機(jī)上:h2(s,n)= O(nlogn+sn0.5), 問哪一種擴(kuò)展性好? 解:對超立方體計(jì)算機(jī),,

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論