并行計算機模型

《并行計算機模型》由會員分享，可在線閱讀，更多相關(guān)《并行計算機模型（58頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,Advanced Computer Architecture,*,高級計算機系統(tǒng)結(jié)構(gòu),上海大學(xué)計算機學(xué)院,徐煒民,1,Advanced Computer Architecture,高級計算機系統(tǒng)結(jié)構(gòu),這里的,高級,其含義是指與本科教育中已經(jīng)介紹的常規(guī)的系統(tǒng)結(jié)構(gòu)類型的區(qū)別，著重在模型、算法和并行處理上。,計算機系統(tǒng)結(jié)構(gòu)是計算機專業(yè)本科教育中的骨干課程，是,ACM,和,IEEE/CS,聯(lián)合,教程專題組所確定的主干課程。,上海大學(xué)計算機學(xué)院計算機系統(tǒng)結(jié)構(gòu)課程被國家教育部列入,“,十五,”,規(guī)劃的重點建設(shè)課程。,學(xué)習(xí)

2、的困難：,1。概念性強，形式描述弱,2。面廣，強調(diào)工程實現(xiàn),3。背景機大而多，且著名，但不易全面介紹和了解,2,Advanced Computer Architecture,參考教材：,(1)英文原版：,Kai,Hwang,Advanced Computer Architecture Parallelism,Scalability,Programmability(1993),中譯本：高等計算機系統(tǒng)結(jié)構(gòu)：并行性、可擴展性、可編程性（王鼎興等譯，1995）,(2)英文原版：,Kai,Hwang,&,Zhiwei Xu,Scalable Parallel Computing Technology,A

3、rchitecture,Programming(1998),中譯本：可擴展并行計算：技術(shù)、結(jié)構(gòu)與編程（陸鑫達等譯，2000）,(3)英文原版：,David E.,Culler,Jaswinder,Pal Singh,Anoop Gupta,Parallel Computer Architecture A Hardware/Software Approach Second Edition(1996),(4),英文原版：,David A.Patterson,John L.,Hennessy,Computer Architecture A Quantitative Approach Second E

4、dition(1996),3,Advanced Computer Architecture,第一篇 并行性理論,1。并行計算機模型,2。程序和網(wǎng)絡(luò)特性,3?？蓴U展性能原理,第二篇 硬件技術(shù),4。處理機與存儲器層次結(jié)構(gòu),5。總線，高速緩存和共享存儲器,6。流水線與超標(biāo)量技術(shù),4,Advanced Computer Architecture,第三篇 并行和可擴展系統(tǒng)結(jié)構(gòu),7。多處理機和多計算機,8。多向量機與,SIMD,計算機,9?？蓴U展，多線程與數(shù)據(jù)流系統(tǒng)結(jié)構(gòu),第四篇 并行程序設(shè)計軟件,10。并行模型，語言和編譯器,11。并行程序開發(fā)與環(huán)境,12。并行機的,UNIX,Mach,和,OSF/1,5

5、,Advanced Computer Architecture,第一篇并行性理論,目前，衡量,超級計算,(,supercomputing),仍用習(xí)慣的方法（小時、作業(yè)、程序數(shù)、程序可移植性）,采用共享存儲器的向量多處理器系統(tǒng)仍是主流（,Cray Research,Fujitsu,IBM,Hitachi,NEC）。,例如，1993年的,C90,用 16臺處理器，,Gigaflops,=16,10,，9,500,次/美元。,九十年代，,RISC,標(biāo)量處理機可達5000次/美元。基于消息傳遞的多計算機系統(tǒng)可達到,Teraflops,。,從廣義上講，可擴展性反映了系統(tǒng)結(jié)構(gòu)、算法、軟件和環(huán)境之間的相互關(guān)

6、系。它涉及到系統(tǒng)結(jié)構(gòu)的通用性、可擴展性、可編程性、可實現(xiàn)性。,6,Advanced Computer Architecture,第一章并行計算機模型,并行性在不同的處理級別中可表現(xiàn)為多種形式：先行方式、流水線方式、向量化、并發(fā)性、同時性、數(shù)據(jù)并行性、劃分、交叉、重疊、多重性、重復(fù)、時間共享、空間共享、多任務(wù)處理、多道程序、多線程方式、分布式計算。,7,Advanced Computer Architecture,一計算技術(shù)的現(xiàn)狀,1歷史演變：,公元前500年，中國的算盤。,1642年，法國,Blaise,Pascal,的機械加法器減法器。,1827年，英國,Charles,Babbage,用于

7、多項式計算的差分機。,1941年，德國,Konrad Zused,用于通用的二進制機械計算機。,1944年，,Howard,Aiken,提出由,IBM,制造用于通用計算的,Havard,Mark I,十進制機電計算機。,以后，就表現(xiàn)為所謂的“五代”計算機演變（表11）。,8,Advanced Computer Architecture,Intel（Oct.2001）,認(rèn)為：,計算模式的演變過程,Enterprise Centralized Mainframes,Server Centric Web,Distributed Solutions,包括,1.,Peer to Peer,2.Wirel

8、ess and mobile,3.One IP,4.XML,9,Advanced Computer Architecture,2現(xiàn)代計算機組成：（圖11）,現(xiàn)代計算機是一種包括機器硬件、指令系統(tǒng)、系統(tǒng)軟件、應(yīng)用程序和用戶接口的集成系統(tǒng)。各種求解方法可能需要不同的計算資源，這與求解問題的性質(zhì)有關(guān)。,10,Advanced Computer Architecture,11,Advanced Computer Architecture,馮諾依曼結(jié)構(gòu)的特點,：,使用單一處理部件來完成計算、存儲及通信功能；,線性組織的定長存儲單元（地址）；,存儲空間的單元是直接尋址的（地址）；,使用低級機器語言，其指令

9、完成基本操作碼的簡單操作；,對計算進行集中的順序控制（程序存儲）。,首次提出,“,地址,”,和,“,程序存儲,”,的概念。,馮諾依曼結(jié)構(gòu)是傳統(tǒng)計算機系統(tǒng)的理論,“,基石,”,。,“,集中的順序控制,”,是計算機發(fā)展的,“,瓶頸,”,，以后計算機理論的發(fā)展，出現(xiàn)了非馮諾依曼結(jié)構(gòu)的計算機系統(tǒng)。,重要性在于多機和并行處理的概念是計算機發(fā)展的最主要的地方。,12,Advanced Computer Architecture,計算機系統(tǒng)的層次結(jié)構(gòu),:,信息處理過程可以用控制流程的概念來描述，而實現(xiàn)描述控制流程的是有一定規(guī)則的字符集合的,“,計算機語言,”,。,計算機語言并不專屬軟件范疇，它可以分屬計算機

10、系統(tǒng)的各個層次，分別對該層次的控制流程進行描述。,基于對語言廣義的理解，可以把計算機系統(tǒng)看成由多級,“,虛擬,”,計算機所組成。從內(nèi)向外，層層相套，形成,“,洋蔥,”,式結(jié)構(gòu)的功能模型。（見圖1-6）,例：用戶-建模-應(yīng)用程序-高級語言-匯編語言-操作系統(tǒng)-機器語言-微程序-硬布線邏輯,13,Advanced Computer Architecture,14,Advanced Computer Architecture,虛擬計算機的概念,洋蔥模型的每一層都是一個虛擬計算機，它只對,“,觀察者,”,而存在，它的功能體現(xiàn)在廣義語言上，對該語言提供解釋手段，然后作用在信息處理或控制對象上，并從對象上

11、獲得必要的狀態(tài)信息。從某一層次的觀察者看來，他只能是通過該層次的語言來了解和使用計算機，至于內(nèi)部任何工作和實現(xiàn)是不必關(guān)心的。,（即：虛擬計算機是由軟件實現(xiàn)的機器）,虛擬計算機的組成，見圖1-7,用虛擬計算機觀點定義的計算機系統(tǒng)的功能層次，見圖1-8,15,Advanced Computer Architecture,16,Advanced Computer Architecture,17,Advanced Computer Architecture,系列機概念,先設(shè)計一種系統(tǒng)結(jié)構(gòu)（機器屬性），而后按這種系統(tǒng)結(jié)構(gòu)設(shè)計它的系統(tǒng)軟件，按器件狀況和硬件技術(shù)研究這種結(jié)構(gòu)的各種實現(xiàn)方法，并按照速度、價格等

12、不同要求，分別提供不同速度、不同配置的各擋機器。（系列機必須保證用戶看到的機器屬性一致）,例：,IBM AS/400,優(yōu)點：,1。在使用共同系統(tǒng)軟件的基礎(chǔ)上，解決程序的兼容性問題；,2。在統(tǒng)一數(shù)據(jù)結(jié)構(gòu)和指令系統(tǒng)的基礎(chǔ)上，便于組成多機系統(tǒng)和網(wǎng)絡(luò)；,3。使用標(biāo)準(zhǔn)的總線規(guī)程，實現(xiàn)接插件和擴展功能卡的兼容，便于實現(xiàn),OEM（Original Equipment Manufacture）。,4。,擴大計算機應(yīng)用領(lǐng)域，提供用戶在同系列的多種機型內(nèi)選用最合適的機器的可能性；,5。有利于機器的使用、維護和人員培訓(xùn),6。有利于計算機升級換代；,7。有利于提高勞動生產(chǎn)率，增加產(chǎn)量、降低成本、促進計算機的發(fā)展。,1

13、8,Advanced Computer Architecture,3,Flynn,分類法,Micheal,Flynn(1972),提出指令流、數(shù)據(jù)流和多倍性概念，把不同的計算機分為四大類（圖13）：,SISD（Single-Instruction Single-Data,單處理機結(jié)構(gòu)）,SIMD（Single-Instruction Multi-Data,帶分布存儲器）,MISD（Multi-Instruction Single-Data,搏動式陣列）,MIMD（Multi-Instruction Multi-Data,帶共享存儲器）,19,Advanced Computer Architec

14、ture,20,Advanced Computer Architecture,4性能的系統(tǒng)屬性,理想的計算機系統(tǒng)的性能要求機器功能和程序行為之間有良好的匹配。,機器功能：好的硬件技術(shù)、改進的系統(tǒng)結(jié)構(gòu)特性、有效的資源管理,程序行為：難預(yù)測，與應(yīng)用和運行條件有密切的關(guān)系。如算法設(shè)計、數(shù)據(jù)結(jié)構(gòu)、語言效率、程序員的技能、編譯技術(shù),21,Advanced Computer Architecture,由于機器性能會隨程序而變化，因此，應(yīng)該在一定范圍內(nèi)或按調(diào)和分布來描述性能。,描述性能的一些術(shù)語和公式：,時鐘頻率：,CPU,是由一個恒定周期（,，,以,ns,表示）的時鐘驅(qū)動。周期的倒數(shù)是時鐘頻率,f=1/，

15、,以,MHz,表示,CPI(Cycle Per Instruction)：,一條指令的周期數(shù)。不針對某類指令，則表示給定的指令系統(tǒng)和綜合程序的平均值。,22,Advanced Computer Architecture,性能因子,：五個,Ic,已知程序的指令條數(shù)或指令計數(shù)，,p ,指令譯碼和執(zhí)行所需的處理機周期數(shù)，,m ,所需的存儲器訪問次數(shù)，,k ,存儲周期與處理機周期之比，,k,值與存儲器技術(shù)及處 理機存儲器互連方法有關(guān)。存儲周期比處理機周期,大,k,倍。,T,執(zhí)行程序所需的,CPU,時間。一條指令執(zhí)行的過程一般分為取指令、譯碼、取操作數(shù)、執(zhí)行、存儲結(jié)果五個階段。其中譯碼和執(zhí)行由,CPU,

16、完成，稱處理機周期；取指令、取操作數(shù)（有可能操作二次）和存儲結(jié)果是對存儲器操作，稱存儲器周期。,T=,Ic,CPI =,Ic,(pmk),23,Advanced Computer Architecture,系統(tǒng)屬性：四個,指令系統(tǒng)結(jié)構(gòu),編譯技術(shù),處理機實現(xiàn)和控制技術(shù),高速緩存與存儲器層次結(jié)構(gòu),MIPS,速率：每秒百萬次，表示,CPU,的執(zhí)行速度,吞吐率：系統(tǒng)在單位時間內(nèi)能執(zhí)行多少個程序,24,Advanced Computer Architecture,MIPS,速率,：(,Million Instruction Per Second),每秒百萬次，表示,CPU,的執(zhí)行速度。,MISP,速率=,Ic,/(T10,6,)=f/(CPI10,6,)=(f,Ic,)/(C10,6,),C,是執(zhí)行已知程序所需的時鐘周期總數(shù)。,25,Advanced Computer Architecture,吞吐率,：,Wp,（,處理機吞吐率）：,處理機在單位時間內(nèi)能執(zhí)行多少個程序。,Wp,=f/(,Ic,CPI),Ws（,系統(tǒng)吞吐率）：,系統(tǒng)在單位時間內(nèi)能執(zhí)行多少個程序。,Ws,Wp,（Ws,有額外系統(tǒng)開銷