第一章并行計算機(jī)模型

高級計算機(jī)系統(tǒng)結(jié)構(gòu)上海大學(xué)計算機(jī)學(xué)院徐煒民

1AdvancedComputerArchitecture《高級計算機(jī)系統(tǒng)結(jié)構(gòu)》這里的‘高級’其含義是指與本科教育中已經(jīng)介紹的‘常規(guī)’的系統(tǒng)結(jié)構(gòu)類型的區(qū)別，著重在模型、算法和并行處理上。計算機(jī)系統(tǒng)結(jié)構(gòu)是計算機(jī)專業(yè)本科教育中的骨干課程，是ACM和IEEE/CS聯(lián)合教程專題組所確定的主干課程。上海大學(xué)計算機(jī)學(xué)院計算機(jī)系統(tǒng)結(jié)構(gòu)課程被國家教育部列入“十五”規(guī)劃的重點(diǎn)建設(shè)課程。學(xué)習(xí)的困難：1。概念性強(qiáng)，形式描述弱2。面廣，強(qiáng)調(diào)工程實(shí)現(xiàn)3。背景機(jī)大而多，且著名，但不易全面介紹和了解2AdvancedComputerArchitecture

參考教材：(1)英文原版：KaiHwang,AdvancedComputerArchitecture–Parallelism,Scalability,Programmability(1993)

中譯本：高等計算機(jī)系統(tǒng)結(jié)構(gòu)：并行性、可擴(kuò)展性、可編程性（王鼎興等譯，1995）(2)英文原版：KaiHwang&ZhiweiXu,ScalableParallelComputingTechnology,Architecture,Programming(1998)

中譯本：可擴(kuò)展并行計算：技術(shù)、結(jié)構(gòu)與編程（陸鑫達(dá)等譯，2000）

(3)英文原版：DavidE.Culler,JaswinderPalSingh,AnoopGupta,ParallelComputerArchitecture–AHardware/SoftwareApproach[SecondEdition](1996)(4)英文原版：DavidA.Patterson,JohnL.Hennessy,ComputerArchitecture–AQuantitativeApproach[SecondEdition](1996)3AdvancedComputerArchitecture第一篇并行性理論1。并行計算機(jī)模型2。程序和網(wǎng)絡(luò)特性3?？蓴U(kuò)展性能原理第二篇硬件技術(shù)4。處理機(jī)與存儲器層次結(jié)構(gòu)5?？偩€，高速緩存和共享存儲器6。流水線與超標(biāo)量技術(shù)4AdvancedComputerArchitecture第三篇并行和可擴(kuò)展系統(tǒng)結(jié)構(gòu)7。多處理機(jī)和多計算機(jī)8。多向量機(jī)與SIMD計算機(jī)9?？蓴U(kuò)展，多線程與數(shù)據(jù)流系統(tǒng)結(jié)構(gòu)第四篇并行程序設(shè)計軟件10。并行模型，語言和編譯器11。并行程序開發(fā)與環(huán)境12。并行機(jī)的UNIX,Mach和OSF/15AdvancedComputerArchitecture

第一篇 并行性理論目前，衡量超級計算(supercomputing)仍用習(xí)慣的方法（小時、作業(yè)、程序數(shù)、程序可移植性）采用共享存儲器的向量多處理器系統(tǒng)仍是主流（CrayResearch,Fujitsu,IBM,Hitachi,NEC）。例如，1993年的C90用16臺處理器，Gigaflops=1610，9,500次/美元。九十年代，RISC標(biāo)量處理機(jī)可達(dá)5000次/美元?；谙鬟f的多計算機(jī)系統(tǒng)可達(dá)到Teraflops。

從廣義上講，可擴(kuò)展性反映了系統(tǒng)結(jié)構(gòu)、算法、軟件和環(huán)境之間的相互關(guān)系。它涉及到系統(tǒng)結(jié)構(gòu)的通用性、可擴(kuò)展性、可編程性、可實(shí)現(xiàn)性。

6AdvancedComputerArchitecture第一章 并行計算機(jī)模型并行性在不同的處理級別中可表現(xiàn)為多種形式：先行方式、流水線方式、向量化、并發(fā)性、同時性、數(shù)據(jù)并行性、劃分、交叉、重疊、多重性、重復(fù)、時間共享、空間共享、多任務(wù)處理、多道程序、多線程方式、分布式計算。7AdvancedComputerArchitecture一． 計算技術(shù)的現(xiàn)狀1．歷史演變：公元前500年，中國的算盤。1642年，法國BlaisePascal的機(jī)械加法器減法器。1827年，英國CharlesBabbage用于多項(xiàng)式計算的差分機(jī)。1941年，德國KonradZused用于通用的二進(jìn)制機(jī)械計算機(jī)。1944年，HowardAiken提出由IBM制造用于通用計算的HavardMarkI十進(jìn)制機(jī)電計算機(jī)。以后，就表現(xiàn)為所謂的“五代”計算機(jī)演變（表1－1）。8AdvancedComputerArchitectureIntel（Oct.2001）認(rèn)為：計算模式的演變過程EnterpriseCentralizedMainframesServerCentricWebDistributedSolutions包括 1.PeertoPeer 2.Wirelessandmobile 3.OneIP 4.XML9AdvancedComputerArchitecture2．現(xiàn)代計算機(jī)組成：（圖1－1）現(xiàn)代計算機(jī)是一種包括機(jī)器硬件、指令系統(tǒng)、系統(tǒng)軟件、應(yīng)用程序和用戶接口的集成系統(tǒng)。各種求解方法可能需要不同的計算資源，這與求解問題的性質(zhì)有關(guān)。10AdvancedComputerArchitecture11AdvancedComputerArchitecture馮諾依曼結(jié)構(gòu)的特點(diǎn)：使用單一處理部件來完成計算、存儲及通信功能；線性組織的定長存儲單元（地址）；存儲空間的單元是直接尋址的（地址）；使用低級機(jī)器語言，其指令完成基本操作碼的簡單操作；對計算進(jìn)行集中的順序控制（程序存儲）。首次提出“地址”和“程序存儲”的概念。馮諾依曼結(jié)構(gòu)是傳統(tǒng)計算機(jī)系統(tǒng)的理論“基石”?！凹械捻樞蚩刂啤笔怯嬎銠C(jī)發(fā)展的“瓶頸”，以后計算機(jī)理論的發(fā)展，出現(xiàn)了非馮諾依曼結(jié)構(gòu)的計算機(jī)系統(tǒng)。重要性在于多機(jī)和并行處理的概念是計算機(jī)發(fā)展的最主要的地方。12AdvancedComputerArchitecture計算機(jī)系統(tǒng)的層次結(jié)構(gòu):信息處理過程可以用控制流程的概念來描述，而實(shí)現(xiàn)描述控制流程的是有一定規(guī)則的字符集合的“計算機(jī)語言”。計算機(jī)語言并不專屬軟件范疇，它可以分屬計算機(jī)系統(tǒng)的各個層次，分別對該層次的控制流程進(jìn)行描述。基于對語言廣義的理解，可以把計算機(jī)系統(tǒng)看成由多級“虛擬”計算機(jī)所組成。從內(nèi)向外，層層相套，形成“洋蔥”式結(jié)構(gòu)的功能模型。（見圖1-6）例：用戶--建模--應(yīng)用程序--高級語言--匯編語言--操作系統(tǒng)--機(jī)器語言--微程序--硬布線邏輯13AdvancedComputerArchitecture14AdvancedComputerArchitecture虛擬計算機(jī)的概念洋蔥模型的每一層都是一個虛擬計算機(jī)，它只對“觀察者”而存在，它的功能體現(xiàn)在廣義語言上，對該語言提供解釋手段，然后作用在信息處理或控制對象上，并從對象上獲得必要的狀態(tài)信息。從某一層次的觀察者看來，他只能是通過該層次的語言來了解和使用計算機(jī)，至于內(nèi)部任何工作和實(shí)現(xiàn)是不必關(guān)心的。（即：虛擬計算機(jī)是由軟件實(shí)現(xiàn)的機(jī)器）虛擬計算機(jī)的組成，見圖1-7用虛擬計算機(jī)觀點(diǎn)定義的計算機(jī)系統(tǒng)的功能層次，見圖1-815AdvancedComputerArchitecture16AdvancedComputerArchitecture17AdvancedComputerArchitecture系列機(jī)概念先設(shè)計一種系統(tǒng)結(jié)構(gòu)（機(jī)器屬性），而后按這種系統(tǒng)結(jié)構(gòu)設(shè)計它的系統(tǒng)軟件，按器件狀況和硬件技術(shù)研究這種結(jié)構(gòu)的各種實(shí)現(xiàn)方法，并按照速度、價格等不同要求，分別提供不同速度、不同配置的各擋機(jī)器。（系列機(jī)必須保證用戶看到的機(jī)器屬性一致）例：IBMAS/400優(yōu)點(diǎn)：1。在使用共同系統(tǒng)軟件的基礎(chǔ)上，解決程序的兼容性問題；2。在統(tǒng)一數(shù)據(jù)結(jié)構(gòu)和指令系統(tǒng)的基礎(chǔ)上，便于組成多機(jī)系統(tǒng)和網(wǎng)絡(luò)；3。使用標(biāo)準(zhǔn)的總線規(guī)程，實(shí)現(xiàn)接插件和擴(kuò)展功能卡的兼容，便于實(shí)現(xiàn)OEM（OriginalEquipmentManufacture）。4。擴(kuò)大計算機(jī)應(yīng)用領(lǐng)域，提供用戶在同系列的多種機(jī)型內(nèi)選用最合適的機(jī)器的可能性；5。有利于機(jī)器的使用、維護(hù)和人員培訓(xùn)6。有利于計算機(jī)升級換代；7。有利于提高勞動生產(chǎn)率，增加產(chǎn)量、降低成本、促進(jìn)計算機(jī)的發(fā)展。18AdvancedComputerArchitecture3．Flynn分類法MichealFlynn(1972)提出指令流、數(shù)據(jù)流和多倍性概念，把不同的計算機(jī)分為四大類（圖1－3）：SISD（Single-InstructionSingle-Data,單處理機(jī)結(jié)構(gòu)）SIMD（Single-InstructionMulti-Data,帶分布存儲器）MISD（Multi-InstructionSingle-Data,搏動式陣列）MIMD（Multi-InstructionMulti-Data,帶共享存儲器）19AdvancedComputerArchitecture20AdvancedComputerArchitecture4．性能的系統(tǒng)屬性理想的計算機(jī)系統(tǒng)的性能要求機(jī)器功能和程序行為之間有良好的匹配。機(jī)器功能：好的硬件技術(shù)、改進(jìn)的系統(tǒng)結(jié)構(gòu)特性、有效的資源管理…程序行為：難預(yù)測，與應(yīng)用和運(yùn)行條件有密切的關(guān)系。如算法設(shè)計、數(shù)據(jù)結(jié)構(gòu)、語言效率、程序員的技能、編譯技術(shù)…21AdvancedComputerArchitecture

由于機(jī)器性能會隨程序而變化，因此，應(yīng)該在一定范圍內(nèi)或按調(diào)和分布來描述性能。描述性能的一些術(shù)語和公式：時鐘頻率：CPU是由一個恒定周期（τ，以ns表示）的時鐘驅(qū)動。周期的倒數(shù)是時鐘頻率f=1/τ，以MHz表示

CPI(CyclePerInstruction)：一條指令的周期數(shù)。不針對某類指令，則表示給定的指令系統(tǒng)和綜合程序的平均值。22AdvancedComputerArchitecture

性能因子：五個

Ic－已知程序的指令條數(shù)或指令計數(shù)，

p－指令譯碼和執(zhí)行所需的處理機(jī)周期數(shù)，

m－所需的存儲器訪問次數(shù)，

k－存儲周期與處理機(jī)周期之比，k值與存儲器技術(shù)及處理機(jī)—存儲器互連方法有關(guān)。存儲周期比處理機(jī)周期τ大k倍。

T－執(zhí)行程序所需的CPU時間。一條指令執(zhí)行的過程一般分為取指令、譯碼、取操作數(shù)、執(zhí)行、存儲結(jié)果五個階段。其中譯碼和執(zhí)行由CPU完成，稱處理機(jī)周期；取指令、取操作數(shù)（有可能操作二次）和存儲結(jié)果是對存儲器操作，稱存儲器周期。

T=Ic×CPI×τ

=Ic×(p＋m×k)×τ

23AdvancedComputerArchitecture系統(tǒng)屬性：四個指令系統(tǒng)結(jié)構(gòu)編譯技術(shù)處理機(jī)實(shí)現(xiàn)和控制技術(shù)高速緩存與存儲器層次結(jié)構(gòu)MIPS速率：每秒百萬次，表示CPU的執(zhí)行速度吞吐率：系統(tǒng)在單位時間內(nèi)能執(zhí)行多少個程序24AdvancedComputerArchitectureMIPS速率：(MillionInstructionPerSecond)每秒百萬次，表示CPU的執(zhí)行速度。MISP速率=Ic/(T×106)=f/(CPI×106)=(f×Ic)/(C×106)C是執(zhí)行已知程序所需的時鐘周期總數(shù)。25AdvancedComputerArchitecture吞吐率：Wp（處理機(jī)吞吐率）：處理機(jī)在單位時間內(nèi)能執(zhí)行多少個程序。Wp=f/(Ic×CPI)

Ws（系統(tǒng)吞吐率）：系統(tǒng)在單位時間內(nèi)能執(zhí)行多少個程序。Ws<Wp（Ws有額外系統(tǒng)開銷：I/O、編譯、OS…）26AdvancedComputerArchitecture并行程序設(shè)計方法：有二種并行程序設(shè)計方法：隱式并行性和顯式并行性。隱式并行性：常用傳統(tǒng)的語言編程成順序源編碼，經(jīng)并行編譯器編譯成并行目標(biāo)碼執(zhí)行。（語言容易，編譯器難）顯式并行性：需要并行語言來編程，編譯器僅保持并行性和把資源分配給目標(biāo)機(jī)器。（語言難，編譯器容易）27AdvancedComputerArchitecture28AdvancedComputerArchitecture多處理機(jī)與多計算機(jī)從不同角度分析，有三種模型結(jié)構(gòu)組織模型理論模型復(fù)雜性模型先討論結(jié)構(gòu)組織模型29AdvancedComputerArchitecture

1．共享存儲型多處理機(jī)：l 均勻存儲器存取-UMA模型（UMA－UniformMemoryAccess）l 非均勻存儲器存取-NUMA模型（NUMA－NonuniformMemoryAccess）l 只用高速緩存的存儲器結(jié)構(gòu)-COMA模型（COMA－CacheOnlyMemoryArchitecture）30AdvancedComputerArchitecture1．共享存儲型多處理機(jī)：（1） 均勻存儲器存?。║MA－UniformMemoryAccess）UMA模型（圖1－6）適用于多用戶的一般應(yīng)用和分時應(yīng)用。它可以在限時應(yīng)用中用來加快單個大程序的執(zhí)行。所有處理器均勻（所謂均勻是指所有處理器對所有存儲字具有相同的存取時間）共享物理存儲器。各處理機(jī)之間的通信是通過共享存儲器的共享變量來實(shí)現(xiàn)的。這一類多處理機(jī)由于對資源的高度共享,常稱緊耦合系統(tǒng)(tightlycoupledsystem)。系統(tǒng)互聯(lián)常采用總線、交叉開關(guān)、多級網(wǎng)絡(luò)。

31AdvancedComputerArchitecture32AdvancedComputerArchitecture對稱多處理機(jī)系統(tǒng)(symmetricmulti-processor)

所有處理機(jī)都能同樣訪問所有外圍設(shè)備；所有處理機(jī)都能同樣運(yùn)行執(zhí)行程序，如操作系統(tǒng)的內(nèi)核、I/O服務(wù)程序。

不對稱處理機(jī)系統(tǒng)(asymmtricmulti-processor)只有一臺或一組處理機(jī)（MP主處理機(jī)）執(zhí)行操作系統(tǒng)并操縱I/O，其余處理機(jī)（AP附屬處理機(jī)）沒有I/O能力。33AdvancedComputerArchitecture

NUMA模型NUMA模型的共享存儲器物理上是分布在所有處理機(jī)的本地存儲器上，這些存儲器的集合組成全局地址空間。由于訪問本地存儲器快，訪問遠(yuǎn)程存儲器慢（經(jīng)過互聯(lián)網(wǎng)絡(luò)），所以訪問時間取決于存儲字所在位置。圖1-7b表示了層次結(jié)構(gòu)NUMA模型。處理機(jī)被分成若干機(jī)群（cluster），每個機(jī)群內(nèi)可以是UMA模型或NUMA模型，但整個系統(tǒng)被認(rèn)為NUMA模型。34AdvancedComputerArchitecture

35AdvancedComputerArchitecture

COMA模型COMA模型是NUMA模型的一種特例。由全部高速緩存組成全局地址空間，訪問遠(yuǎn)程緩存是通過分布在各處理機(jī)上的高速緩存目錄來進(jìn)行的。圖1-836AdvancedComputerArchitecture

37AdvancedComputerArchitecture

2．分布存儲型多處理機(jī)(1)系統(tǒng)由多個結(jié)點(diǎn)（由處理機(jī)、本地存儲器、I/O設(shè)備組成的自治的計算機(jī)）通過消息傳遞網(wǎng)絡(luò)互相連接。圖1-938AdvancedComputerArchitecture

39AdvancedComputerArchitecture

(2)消息傳遞型多計算機(jī)的演變：l 第一代（1983-1987）基于處理機(jī)板技術(shù)，采用超立方體結(jié)構(gòu)和軟件控制的消息交換方法。（IntelIpsc/1）l 第二代（1988-1992）用網(wǎng)絡(luò)連結(jié)的系統(tǒng)結(jié)構(gòu)、硬件消息尋徑、中粒度分布計算的軟件環(huán)境。（IntelParagon）

l 第三代（1993-）處理機(jī)與通信工 具在同一芯片上實(shí)現(xiàn)的細(xì)粒度多計算環(huán)境。 （MITJ-Machine）40AdvancedComputerArchitecture

(3)消息傳遞型多計算機(jī)研究的重要問題：l 消息尋徑方式l 網(wǎng)絡(luò)的流控制策略l 死鎖避免l 虛擬通道l 消息傳遞原語

l 程序分解技術(shù)41AdvancedComputerArchitecture

多向量機(jī)和SIMD計算機(jī)1．向量超級計算機(jī)向量計算機(jī)往往是在標(biāo)量處理機(jī)與向量處理機(jī)的“混合物”,程序與數(shù)據(jù)由主機(jī)加載到主存儲器；全部指令由標(biāo)量控制器譯碼，若是標(biāo)量操作或程序控制操作則有標(biāo)量處理機(jī)的標(biāo)量功能流水線執(zhí)行；若是向量操作則送入向量控制器，由主存儲器與向量功能流水線執(zhí)行向量數(shù)據(jù)流。圖1-1142AdvancedComputerArchitecture

43AdvancedComputerArchitecture

2．SIMD超級計算機(jī)SIMD計算機(jī)的操作模型可以用五元組表示：M=（N，C，I，M，R）式中：N：機(jī)器的處理單元（PE-ProcessorElement）數(shù)C：由控制部件（CU-ControlUnit）直接執(zhí)行的指令集，包括標(biāo)量與程序流控制指令；I：由CU廣播到所有PE進(jìn)行并行執(zhí)行的指令集，包括算邏運(yùn)算、數(shù)據(jù)尋徑、屏蔽操作、PE執(zhí)行的局部操作；M：屏蔽方案集，把PE劃分為允許操作與禁止操作兩種子集；

R：數(shù)據(jù)尋徑功能集，互連網(wǎng)絡(luò)中PE間通信所需的 各種設(shè)置模式。圖1-1244AdvancedComputerArchitecture

45AdvancedComputerArchitecture

PRAM和VLSI模型并行計算機(jī)的理論模型是從物理模型抽象得到的.算法和芯片設(shè)計者利用理論模型為開發(fā)并行算法提供了一種方便的框架(無需關(guān)心實(shí)現(xiàn)細(xì)節(jié)或物理約束條件.這些模型可為并行計算機(jī)求的理論性能界限或芯片制作前估算芯片區(qū)的VLSI復(fù)雜性和執(zhí)行時間.當(dāng)將實(shí)際機(jī)器與聯(lián)想機(jī)器(不考慮結(jié)點(diǎn)間通信開銷)作比較時,抽象模型在分析可擴(kuò)展性和可編程性方面是十分有用的.46AdvancedComputerArchitecture

并行隨機(jī)存取機(jī)(RAM-RandomAccessMachine)隨機(jī)存取機(jī)(RAM-RandomAccessMachine)并行隨機(jī)存取機(jī)(PRAM-ParallelRandomAccessMachine)計算的易解性(tractability)：時間復(fù)雜性，空間復(fù)雜性，NP

完全性目的：利用復(fù)雜性模型可方便討論在并行計算機(jī)上實(shí)現(xiàn)算法的漸近特性.47AdvancedComputerArchitecture

時間復(fù)雜性和空間復(fù)雜性計算機(jī)求解一個規(guī)模為s的問題的算法復(fù)雜性取決于所需的執(zhí)行時間和存儲空間。所以：時間復(fù)雜性是問題規(guī)模的函數(shù)（時間復(fù)雜性函數(shù)是算法的漸近時間復(fù)雜性）。通常考慮最壞情況下的時間復(fù)雜性。空間復(fù)雜性也是問題規(guī)模的函數(shù)（空間復(fù)雜性函數(shù)是算法的漸近空間復(fù)雜性）。通?？紤]大問題的數(shù)據(jù)存儲，而程序存儲和輸入數(shù)據(jù)的存儲一般不考慮。48AdvancedComputerArchitecture

串行復(fù)雜性：串行算法的時間復(fù)雜性并行復(fù)雜性：并行算法的時間復(fù)雜性一般認(rèn)為：并行復(fù)雜性比串行復(fù)雜性低，或相近確定性算法：每個操作步驟是唯一確定的；與實(shí)際計算機(jī)上程序執(zhí)行的過程是一致的。不確定性算法：目前沒有這類的實(shí)際機(jī)器。49AdvancedComputerArchitecture

NPC（NP完全問題）：如果存在一多項(xiàng)式p(s)，對任何問題規(guī)模s的時間復(fù)雜性為O(p(s))，則某算法即具有多項(xiàng)式復(fù)雜性。具有多項(xiàng)式復(fù)雜性算法的問題稱為P類，能以多項(xiàng)式時間用不確定性算法求解的問題集稱為NP類。P類問題是計算易解的，NP-P類問題是難解的，用確定性算法模擬不確定性算法可能是指數(shù)量級的時間，又稱具有指數(shù)時間復(fù)雜性的問題。∵P∈NP，目前不知道：P=NP或P≠NP，推測有NP完全=NPC，NPC∈NP，NPC∩P=φ。用P模擬NP是指數(shù)級時間假如任何NP完全問題是多項(xiàng)式時間可解問題，則P=NP。結(jié)論：只能用近似算法求解某些NP完全問題。圖1-1350AdvancedComputerArchitecture

PRAM模型（Fortune&Wyllie1978）此前有RAM模型(Sheperdson&Sturgis1963)主要描述單機(jī)系統(tǒng)PRAM模型如圖1-14，可開發(fā)并行算法和分析可擴(kuò)展性及復(fù)雜性。多PE共享全局可尋址存儲器，按照同步地讀存儲器、計算、寫存儲器循環(huán)方式運(yùn)行。由于共享存儲器，存在對存儲器并發(fā)讀和并發(fā)寫的控制。51AdvancedComputerArchitecture

存儲器修改的四種可能選擇：互斥讀（ER）：在每一循環(huán)中最多有一臺PE從任何一存儲單元讀操作（限制較大）互斥寫（EW）：每次最多有一臺PE對存儲單元寫入內(nèi)容并發(fā)讀（CR）：多臺PE在同時對同一存儲單元讀取同一信息并發(fā)寫（CW）：同時寫入同一單元（會產(chǎn)生混亂，要有避免沖突的策略）52AdvancedComputerArchitecture

由此形成四種PRAM模型方案：EREW-PRAM模型：禁止一臺以上PE同時讀/寫同一存儲單元（限制最大的PRAM模型）CREW-PRAM模型：