高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)

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ī)，,