13并行計算機體系結構

第13章并行計算機體系結構本章主要內(nèi)容并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)的設計問題并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的性能問題并行計算機系統(tǒng)的軟件問題SIMD計算機簡介MIMD多處理機簡介MIMD多計算機簡介2計算機系統(tǒng)結構的發(fā)展歷程硬件技術和系統(tǒng)結構軟件和應用第一代（1945～1954）電子管和繼電器。單CPU，以程序計數(shù)器PC和累加器順序完成定點運算。機器語言或匯編語言。單用戶。用CPU程序控制I/O。第二代（1955～1964）晶體管和磁芯存儲器。用印制電路互連。變址寄存器，浮點運算；多路存儲器，I/O處理機。有編譯程序支持的高級語言，子程序庫，批處理監(jiān)控程序。第三代（1965～1974）中小規(guī)模集成電路。多層印制電路。微程序設計，流水線，高速緩存，先行處理機。多道程序設計，分時操作系統(tǒng)，多用戶應用。第四代（1975～1990）大規(guī)模集成電路。半導體存儲器。多處理機，多計算機，向量超級計算機。用于并行處理的多處理機操作系統(tǒng)、專用語言和編譯器；并行處理或分布計算的軟件工具和環(huán)境。第五代（1991～現(xiàn)在）超大規(guī)模集成電路。高密度高速度處理器和存儲器芯片，可擴展體系結構，因特網(wǎng)。大規(guī)模并行處理，Java語言，分布式操作系統(tǒng)，萬維網(wǎng)，網(wǎng)格。3計算機系統(tǒng)結構的發(fā)展方向第一個是改變馮.諾依曼機器的串行執(zhí)行模式超標量計算機（執(zhí)行多條指令）多處理機系統(tǒng)（共享集中或分布式存儲器）大規(guī)模并行處理機MPP系統(tǒng)PC或工作站組成的機群系統(tǒng)4計算機系統(tǒng)結構的發(fā)展方向第二個是改變馮.諾依曼機器的控制驅動方式數(shù)據(jù)驅動方式：操作數(shù)到位即可運算，無序執(zhí)行.數(shù)據(jù)流計算機是一種數(shù)據(jù)驅動式系統(tǒng)結構的計算機，只要指令所需的操作數(shù)準備好就可以立即啟動執(zhí)行，一條指令的運算結果又流向下一條指令，作為下一條指令的操作數(shù)來驅動該條指令的啟動執(zhí)行。程序中各條指令的執(zhí)行順序僅由指令間的數(shù)據(jù)依賴關系決定。需求驅動方式：驅動方式與數(shù)據(jù)流相反，無序執(zhí)行.需求驅動方式是一個操作僅在要用到其輸出結果時才開始啟動，如果這個操作的操作數(shù)沒有準備好，那么它就去啟動能夠得到它的相應輸入操作數(shù)的其他操作，這樣的需求鏈一直延伸下去，直到遇到常數(shù)或者外部已經(jīng)輸入的數(shù)據(jù)為止，然后再反方向的執(zhí)行運算。歸約機就屬于需求驅動式系統(tǒng)結構的使用函數(shù)式程序設計語言的計算機。模式匹配驅動方式：非數(shù)值型應用，主要對象為符號.在模式匹配驅動方式中，計算的進行是由謂詞模式匹配來驅動的，而謂詞是代表客體之間關系的一種字符串模式，主要用來求解非數(shù)值的符號演算。面向智能的Lisp機、Prolog機和神經(jīng)網(wǎng)絡等就屬于這種模式匹配驅動式系統(tǒng)結構的計算機。第一個發(fā)展方向已經(jīng)取得了重大進展，取得了一系列的成果。而第二個發(fā)展方向，大多數(shù)還屬于探索、研究階段，還需要進行大量的工作。5計算機系統(tǒng)結構的分類方法過去曾普遍將計算機系統(tǒng)分為巨、大、中、小、微型機五類。劃分原則：這種方法是按照規(guī)模、性能、速度以至價格的一種大致劃分。存在問題：只能對同時期的計算機大致分類，劃分的標準是隨時間而變化，每５年左右降低一個等級；另外，這種劃分方法不能反映機器的系統(tǒng)結構特征。設計方法：最高性能 特殊用途最佳性能價格比 一般商用計算機最低價格 家用計算機等6

價最佳性能價格比

格最高性能巨型機大型機等性能線中型機小型機最低價格微型機(超微型機)

t-3t-2t-1

tt+1時期7計算機原理及系統(tǒng)結構第五十三講主講教師：趙宏偉學時：64第13章并行計算機體系結構計算機系統(tǒng)結構的分類方法1966年，Michael.J.Flynn提出按指令流和數(shù)據(jù)流的多倍性對計算機系統(tǒng)結構進行分類。指令流是指機器執(zhí)行的指令序列；數(shù)據(jù)流是由指令流調用的數(shù)據(jù)序列，包括輸入數(shù)據(jù)和中間結果；多倍性是指在系統(tǒng)最受限制的部件上，同時處于同一執(zhí)行階段的指令或數(shù)據(jù)的最大數(shù)目。指令流數(shù)據(jù)流名稱舉例1個1個SISD傳統(tǒng)的馮.諾依曼計算機1個多個SIMD向量計算機，陣列處理機多個1個MISD目前還沒有多個多個MIMD多處理機，多計算機10SISD體系結構處理器串行執(zhí)行指令；或者處理器內(nèi)采用指令流水線，以時間重疊技術實現(xiàn)了一定程度上的指令并行執(zhí)行；甚至于處理器是超標量處理器，內(nèi)有幾條指令流水線實現(xiàn)了更大程度上的指令并行執(zhí)行。但它們都是以單一的指令流從存儲器取指令，以單一的數(shù)據(jù)流從存儲器取操作數(shù)和將結果寫回存儲器。11SIMD體系結構有單一的控制部件，但是有多個處理部件。計算機以一個控制單元從存儲器取單一的指令流，一條指令同時作用到各個處理單元，控制各個處理單元對來自不同數(shù)據(jù)流的數(shù)據(jù)組進行操作。這種體系結構的典型代表是陣列處理機，一些學者認為將向量處理機也劃入此類。12MISD體系結構多個處理單元，各配有相應的控制單元。各個處理單元接收不同的指令，多條指令同時在一份數(shù)據(jù)上進行操作。這種計算機體系結構是一種比較奇怪的組合，這已經(jīng)被證明是不可能至少是不實際的，目前為止還不存在這種類型的計算機。13MIMD體系結構同時有多個處理單元，并且每個處理單元都配有相應的控制單元。各個處理單元可以接收不同的指令并對不同的數(shù)據(jù)流進行操作。大多數(shù)現(xiàn)代的并行計算機都屬于這一類，多處理機系統(tǒng)和多計算機系統(tǒng)都是MIMD型的計算機。14計算機系統(tǒng)結構的分類方法Flynn分類法的局限分類的對象主要是控制驅動方式下的串行處理和并行處理計算機。對于非控制驅動方式的計算機，就不適合采用Flynn分類法；把兩個不同等級的功能并列對待，通常，數(shù)據(jù)流受指令流控制從而造成MISD不存在；分類太粗，對流水線處理機的劃分不明確，標量流水線為SISD，向量流水線為SIMD。其他的分類方法美籍華人馮澤云教授在1972年提出了按最大并行度來定量描述各種計算機系統(tǒng)的馮氏分類法。WolfganHandler在馮氏分類法的基礎上，于1977年根據(jù)并行度和流水線提出了另外一種分類法。1978年由D.J.Kuck提出按控制流和執(zhí)行流分類。15并行計算機系統(tǒng)發(fā)展的原因應用的需求永遠是并行計算機系統(tǒng)發(fā)展的動力。隨著計算機速度的提高，人們對計算機性能的要求也越來越高。例如科學計算、工程和工業(yè)設計等都需要高性能計算。芯片的速度不可能無限地提高，并行計算機可以處理越來越復雜的問題。芯片的速度要受到光速的制約，但芯片的集成度還有發(fā)展的空間。大量商品化的處理器的出現(xiàn)為設計并行計算機系統(tǒng)提供了可能。并行計算機系統(tǒng)獲得快速發(fā)展和處理機間通信技術的發(fā)展密不可分。P33316并行計算機系統(tǒng)的分類按照Flynn分類法歸納的并行計算機體系結構圖譜

P33317并行計算機系統(tǒng)的分類MIMD體系結構多處理機系統(tǒng)——基于共享存儲器系統(tǒng)中只有唯一的地址空間，所有的處理器共享該地址空間。唯一的地址空間并不意味著在物理上只有一個存儲器。共享地址空間可以通過一個物理上共享的存儲器來實現(xiàn)，也可以通過分布式存儲器并在硬件和軟件的支持下實現(xiàn)。多計算機系統(tǒng)——基于消息傳遞每個處理器有自己的存儲器，該存儲器只能被該處理器訪問而不能被其它處理器直接訪問，這種存儲器稱為局部存儲器或私有存儲器。當處理器A需要向處理器B傳送數(shù)據(jù)時，A把數(shù)據(jù)以消息的形式發(fā)送給B。18并行性、可擴展性和可編程性并行性（Parallelism）的基本概念并行性是指在同一時刻或同一時間間隔內(nèi)完成兩種或兩種以上的工作。并行性還可以進一步分為同時性和并發(fā)性，前者指同一時刻發(fā)生的并行性，后者指同一時間間隔內(nèi)發(fā)生的并行性。并行的粒度問題粗、中、細三種不同的并行粒度，共享內(nèi)存的多處理機系統(tǒng)用于細粒度和中粒度并行計算，而消息傳遞型多計算機系統(tǒng)用于中粒度和粗粒度并行計算。P33519并行性、可擴展性和可編程性硬件資源的可擴展性（Scalability）是指通過增加處理器數(shù)目、投入更多的存儲器部件（高速緩存、主存、磁盤等），從而使系統(tǒng)具有更高的性能或功能。由于多處理機和多計算機主要是以資源重復手段實現(xiàn)并行處理的，因此它們是可擴展系統(tǒng)。而且，松散耦合的多計算機系統(tǒng)的可擴展性要好于緊密耦合的多處理機系統(tǒng)。并行計算機系統(tǒng)可編程性（Programmability）涉及到操作系統(tǒng)、編譯器、語言支持等多個方面的問題。到目前為止，可以說對并行計算機系統(tǒng)編程仍然是非常困難和費力的事情，這主要是因為人們原來所熟悉的順序編程不適合并行程序的設計特征。從體系結構的角度來看，多處理機有統(tǒng)一編址的全局共享存儲器，其可編程性要好于多計算機系統(tǒng)。20本章主要內(nèi)容并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)的設計問題并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的性能問題并行計算機系統(tǒng)的軟件問題SIMD計算機簡介MIMD多處理機簡介MIMD多計算機簡介21互連網(wǎng)絡概述并行計算機的通信體系結構是系統(tǒng)的核心兩個層次：底層的互連網(wǎng)絡；上層的語言、軟件工具包、編譯器、操作系統(tǒng)等提供的通信支持?；ミB網(wǎng)絡是并行計算機系統(tǒng)內(nèi)部的互連網(wǎng)絡定義：由開關元件按一定拓撲結構和控制方式構成的網(wǎng)絡以實現(xiàn)計算機系統(tǒng)內(nèi)部多個處理機或多個功能部件間的相互連接。與計算機網(wǎng)絡在工作原理、概念以及術語上有許多相同或相似之處；并且某些并行計算機系統(tǒng)中的互連網(wǎng)絡就是高速以太網(wǎng)和ATM網(wǎng)絡?；ミB網(wǎng)絡一般由以下五個部分組成CPU、內(nèi)存模塊、接口、鏈路和交換結點22接口、鏈路和交換結點接口：是從CPU和內(nèi)存取得信息并向另外的CPU和內(nèi)存發(fā)送信息的設備。典型設備如網(wǎng)絡接口卡。鏈路：是傳送數(shù)據(jù)位的物理信道。鏈路可以是電纜、雙絞線或者光纖；可以是串行的也可以是并行的，每種鏈路都有其最大帶寬；鏈路可以是單工的（單方向傳送）、半雙工的（某個時刻只能傳送一個方向的數(shù)據(jù)）和全雙工的（同時兩個方向傳送）；鏈路使用的時鐘機制可以是同步或是異步的。交換結點：是互連網(wǎng)絡的信息交換和控制站點，它是具有多個輸入端口和多個輸出端口的設備。能夠進行數(shù)據(jù)緩沖存儲和路徑選擇。P33623設計和分析互連網(wǎng)絡的幾個重要問題互連網(wǎng)絡的拓撲結構互連網(wǎng)絡的拓撲結構描述了鏈路和交換結點是如何組織安排的。拓撲結構可以用圖來表示，鏈路用邊表示，交換結點用結點表示?；ミB網(wǎng)絡的尋徑方式

交換結點所做的工作就是接收到達輸入端口的分組然后把分組發(fā)送到正確的輸出端口，具有多種不同的工作方式?；ミB網(wǎng)絡的尋徑算法尋徑算法：決定一個分組從源結點到達目的結點的過程中經(jīng)過的結點序列的算法。24互連網(wǎng)絡的分類靜態(tài)網(wǎng)絡靜態(tài)網(wǎng)絡(StaticNetworks)是指結點間有著固定連接通路且在程序執(zhí)行期間，這種連接保持不變的網(wǎng)絡。動態(tài)網(wǎng)絡動態(tài)網(wǎng)絡(DynamicNetworks)由開關單元構成，可按應用程序的要求動態(tài)地改變連接狀態(tài)。如總線、交叉開關，多級交換網(wǎng)絡等。25互連網(wǎng)絡的參數(shù)結點度：與結點相連接的邊數(shù)，表示節(jié)點所需要的端口數(shù)，根據(jù)鏈路到結點的方向，結點度可以進一步表示為：結點度=入度+出度，其中入度是進入結點的鏈路數(shù)，出度是從結點出來的鏈路數(shù)。鏈路的長度：鏈路中包含的邊數(shù)距離：與兩個結點之間相連的最少邊數(shù)。網(wǎng)絡直徑：網(wǎng)絡中任意兩個結點間距離的最大值。網(wǎng)絡規(guī)模：網(wǎng)絡中結點數(shù)，表示該網(wǎng)絡功能連結部件的多少。等分寬度：某一網(wǎng)絡被切成相等的兩半時，沿切口的最小邊數(shù)稱為該網(wǎng)絡的等分寬度。對稱性：從任何結點看，拓撲結構都一樣，這種網(wǎng)絡實現(xiàn)和編程都很容易。P33726靜態(tài)互連網(wǎng)絡線性陣列對N個結點的線性陣列，有N-1條鏈路，直徑為N-1（任意兩點之間距離的最大值）度為2不對稱，等分寬度為1。N很大時，通信效率很低。27環(huán)形對N個結點的環(huán)，考慮相鄰結點數(shù)據(jù)傳送方向：雙向環(huán)：鏈路數(shù)為N，直徑N/2，度為2，對稱，等分寬度為2。單向環(huán)：鏈路數(shù)為N，直徑N-1，度為2，對稱，等分寬度為2。靜態(tài)互連網(wǎng)絡28帶弦環(huán)對圖中12個結點的帶弦雙向環(huán)結點度為3：鏈路數(shù)為18，直徑4（比如紅色結點），度為3，不對稱，等分寬度為2。結點度為4：鏈路數(shù)為24，直徑3（比如紅色結點），度為4，對稱，等分寬度為8。度為3的帶弦環(huán)度為4的帶弦環(huán)靜態(tài)互連網(wǎng)絡29計算機原理及系統(tǒng)結構第五十四講主講教師：趙宏偉學時：64靜態(tài)互連網(wǎng)絡全鏈接全鏈接是帶弦環(huán)的一種特殊情形。鏈接中的每個結點和其他結點之間都有單一的直接鏈路。如下圖中8個結點的全鏈接：有28條鏈路，直徑為1，度為7，對稱，等分寬度為16。314層的二叉樹靜態(tài)互連網(wǎng)絡樹形一棵K層完全二叉樹應有N=2K-1個結點，最大結點度為3，直徑為2（K-1）（即右邊任意一個葉子結點到左邊任意一個葉子結點）。不對稱，等分寬度為1。32帶環(huán)樹二叉胖樹樹形的擴展這兩種結構都可以緩解根結點的瓶頸問題33靜態(tài)互連網(wǎng)絡星形星形實際上是一種二層樹（如右圖）。有N個結點的星形網(wǎng)絡，有N-1條鏈路，直徑為2，最大結點度為N-1，非對稱，等分寬度為1。34靜態(tài)互連網(wǎng)絡網(wǎng)格形有N個結點的rr網(wǎng)，有2N-2r條鏈路，直徑為2(r-1)，結點度為4，非對稱，等分寬度為r。其中35靜態(tài)互連網(wǎng)絡二維環(huán)網(wǎng)形有N個結點的rr網(wǎng)，有2N條鏈路，直徑為2r/2，結點度為4，對稱。其中36靜態(tài)互連網(wǎng)絡超立方體一個n-立方體由N=2n個結點構成，它們分布在n維上，每維有兩個結點。直徑為n，結點度為n，對稱。3-立方體4-立方體37帶環(huán)3-立方體靜態(tài)互連網(wǎng)絡帶環(huán)立方體一個帶環(huán)n-立方體由N=2n個結點環(huán)構成，每個結點環(huán)是一個有n個結點的環(huán)，所以結點總數(shù)為n2n個，結點度為3，對稱。38靜態(tài)互連網(wǎng)絡特性一覽表P33839動態(tài)互連網(wǎng)絡網(wǎng)絡特點動態(tài)網(wǎng)絡中的連接不固定，在程序執(zhí)行過程中可根據(jù)需要改變。網(wǎng)絡的開關元件有源，鏈路可通過設置這些開關的狀態(tài)來重構。只有在網(wǎng)絡邊界上的開關元件才能與處理機相連。動態(tài)網(wǎng)絡主要有總線、交叉開關、多級交換網(wǎng)絡。40動態(tài)互連網(wǎng)絡總線（Bus）總線實際上是連接處理器、存儲器和I/O等外圍設備的一組導線和插座。它在某一時刻只能用于一對源和目的之間傳輸數(shù)據(jù)。當有多對源和目的請求使用總線時，要進行總線仲裁。當CPU數(shù)目較多時對總線爭用嚴重（<=32個）。線性陣列與總線的區(qū)別線性陣列：允許不同的源結點和目的結點對并發(fā)使用系統(tǒng)的不同部分。總線：通過切換與其相連的許多結點來實現(xiàn)時分特性，同一時刻只有一對結點在傳送數(shù)據(jù)。41C

局部總線CAIFPMCPU板I/O總線…存儲器總線IFC存儲器存儲器板C

局部總線CAIFPMCPU板I/O總線存儲器總線IFC存儲器存儲器板…系統(tǒng)總線（在底板上）

IF

局部總線緩存器IFIOPI/O板磁盤打印機C局部總線緩存器IFIF網(wǎng)絡接口卡以太網(wǎng)IF:專用邏輯接口C:專用控制器P:處理器M:局部存儲器CA:高速緩存IOP:I/O處理器42動態(tài)互連網(wǎng)絡交叉開關（CrossbarSwitcher）交叉開關是一種高帶寬網(wǎng)絡，它可以在輸入端和輸出端之間建立動態(tài)連接在每個輸入端和輸出端的交叉點上都有交叉點開關。該開關可以根據(jù)需要置為“開”或“關”狀態(tài)，從而使不同的輸入端和輸出端導通。交叉開關的硬件復雜性為n2數(shù)量級，造價昂貴。但是其帶寬和尋徑性能在這三種動態(tài)網(wǎng)絡中最好。如果網(wǎng)絡規(guī)模小，它是一種理想的選擇（<=64個）。43交叉開關44動態(tài)互連網(wǎng)絡多級交換網(wǎng)絡開關單元：a個輸入a個輸出的開關單元記作aa的開關單元，其中，a是2的整數(shù)倍。常見的有22、44、88等。根據(jù)開關單元功能的多少，22又可以分為兩功能和四功能開關。直通交換上播下播45動態(tài)互連網(wǎng)絡多級交換網(wǎng)絡級間互連模式均勻洗牌、蝶式、多路洗牌、縱橫開關及立方體連結等控制方式級控制：每級只有一個控制信號單元控制：每個開關一個控制信號部分級控制：幾個開關合用一個控制信號多級交換網(wǎng)絡是總線和交叉開關的折衷。它的主要優(yōu)點在于采用模塊結構，可擴展性好（>64）46Ω多級交換網(wǎng)絡0123456701234567第0級第1級第2級47計算機原理及系統(tǒng)結構第五十五講主講教師：趙宏偉學時：64互連網(wǎng)絡的尋徑方式多種不同的設計方案電路交換：預約資源（端口和緩沖區(qū)），預先建立固定交換結點鏈路，分組能夠全速發(fā)送。存儲轉發(fā)分組交換：不預約資源，各個交換結點緩存整個分組。需要有緩存策略：輸入緩存、輸出緩存、公共緩沖區(qū)虛擬直通尋徑：當分組第一個單元不能移動時，分組的其余單元可以繼續(xù)向第一個單元所在的結點傳送。蟲蝕尋徑：當?shù)谝粋€單元不能移動時，通知源結點，源結點就停止傳送，因此分組就像一條蟲子一樣停留在兩個或者更多個交換結點中。P33949互連網(wǎng)絡的尋徑方式50互連網(wǎng)絡的尋徑方式51互連網(wǎng)絡的尋徑算法源尋徑和分布式尋徑在源尋徑中，源結點預先決定穿過互連網(wǎng)絡的完整的路徑，使用路徑中每個結點的端口號的列表來表示。在分布式尋徑算法中，每個交換結點自己決定把到達的分組發(fā)送到哪個輸出端口。一般來說在各個交換結點都設立一個路徑表，而分組的頭部含有一個尋徑字段說明分組的目的地址和選擇路徑的依據(jù)。靜態(tài)尋徑算法和自適應尋徑算法算法對所有到相同目的結點的分組都做出相同的決策，那么這樣的尋徑算法就稱為靜態(tài)的。算法在做路徑選擇時考慮了當前情況，該算法就是自適應的。P34152本章主要內(nèi)容并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)的設計問題并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的性能問題并行計算機系統(tǒng)的軟件問題SIMD計算機簡介MIMD多處理機簡介MIMD多計算機簡介53并行計算機系統(tǒng)的性能問題硬件性能指標重要的性能指標是CPU和輸入/輸出的速度以及互連網(wǎng)絡的性能。互連網(wǎng)絡的性能有兩個重要的指標：延時（Latency）和帶寬（Bandwidth）。延遲時間是指從CPU發(fā)送分組至接收到響應的時間間隔。對分帶寬、聚集帶寬和平均帶寬（按照CPU能力計算）。軟件性能指標最關鍵的性能指標是加速比（speedup）：一個程序在有n個處理器的計算機上運行和在只有一個處理器的計算機上運行相比快多少倍。P34254并行計算機系統(tǒng)的性能問題P34255并行計算機系統(tǒng)的性能問題理想的加速比不可能達到的部分原因是幾乎所有的程序都有串行部分。假定一個程序在單處理器計算機上運行需要T秒，其中一部分是串行代碼，所占比例記為f，那么剩余的（1－f）就是可以并行的。后一部分代碼運行在n個CPU上而且沒有任何其它開銷，那么在最理想的情況下，執(zhí)行時間可以從（1－f）T減少到（1－f）T/n。串行部分加并行部分的整個執(zhí)行時間就是fT＋（1－f）T/n。加速比就是原來程序的執(zhí)行時間除以新的程序的執(zhí)行時間：56本章主要內(nèi)容并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)的設計問題并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的性能問題并行計算機系統(tǒng)的軟件問題SIMD計算機簡介MIMD多處理機簡介MIMD多計算機簡介57并行計算機軟件的四種設計方法第一種方法是為普通的串行語言增加特殊的函數(shù)庫。這種方法的問題在于只是在很少的庫函數(shù)中實現(xiàn)了并行性，而大量的程序代碼仍然是串行的。第二種方法是為編程語言增加包括通信和控制原語的庫函數(shù)。程序員仍然使用傳統(tǒng)的編程語言編程，但是程序員需要使用這些原語來創(chuàng)建和管理并行性。第三種方法是為現(xiàn)有的編程語言增加一些特殊的結構，比如可以很容易地創(chuàng)建新的并行進程的能力，并行執(zhí)行循環(huán)的能力和同時對一個向量的所有元素執(zhí)行算術運算的能力。第四種方法是發(fā)明一種全新的用于并行處理的語言。使用新語言的一個顯而易見的優(yōu)勢是這樣的語言肯定很適合于并行處理，但是缺點也同樣明顯，程序員必須學習一種新語言。P34458本章主要內(nèi)容并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)的設計問題并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的性能問題并行計算機系統(tǒng)的軟件問題SIMD計算機簡介MIMD多處理機簡介MIMD多計算機簡介59SIMD計算機單指令流多數(shù)據(jù)流計算機用于解決使用向量和陣列這樣比較規(guī)整的數(shù)據(jù)結構的復雜科學計算和工程計算問題。只有一個控制單元，每次只能執(zhí)行一條指令，但是這一條指令可以同時對多個數(shù)據(jù)進行操作。SIMD計算機可以分為陣列處理機和向量處理機兩大類。60陣列處理機設計陣列處理機基本思想用一個單一的控制單元提供信號驅動多個處理單元同時運行，如下圖所示。每個處理器單元都由CPU或者是功能增強的ALU和本地內(nèi)存組成。由于所有的處理單元都是由一個控制單元驅動的，因此它們的執(zhí)行是同步的。各種陣列處理機的不同之處處理單元的結構：處理單元的結構可能很簡單，也可能很復雜。處理單元如何連接：從原理上來說前面列出的拓撲結構都是可行的，網(wǎng)格是比較常用的結構。處理單元自治能力：每個處理單元都可以選擇執(zhí)行或不執(zhí)行某條指令。沒有那個公司的產(chǎn)品在市場上取得較大的成功，從并行計算機系統(tǒng)體系結構來看，陣列處理機沒有好的發(fā)展前景。P34561ILLIACIV型陣列處理機62向量處理機向量處理機在商業(yè)上取得了很大成功。CrayResearch公司設計的系列計算機，從Cray-1到后來的C90和T90，在科學計算領域占據(jù)了數(shù)十年的統(tǒng)治地位。從數(shù)學的概念上講，標量是指單個量，而向量是指一組標量。例如，有一個數(shù)組A＝（a1，a2，a3，…，an），其中括號內(nèi)的每一個元素ai就是一個標量。而A稱為向量，它由一組標量組成。向量處理方式：引入向量數(shù)據(jù)表示，需要向量指令處理。標量處理：for（i＝0；i＜N；i＋＋）A[i]＝B[i]＋C[i]

向量處理：A＝B＋C

63向量處理機向量處理方法例子：D＝A×(B＋C)其中A、B、C、D都是長度為N的向量。橫向處理方法：逐個求向量D中N個分量?？v向處理方法：先求B＋C各個分量得向量K，然后計算D＝A×K?？v橫處理方法：分組處理，組內(nèi)采用縱向處理，組間采用橫向處理。最簡單的向量處理結構向量處理和流水線結合對語言結構和編譯程序提出新的要求P34664本章主要內(nèi)容并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)的設計問題并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的性能問題并行計算機系統(tǒng)的軟件問題SIMD計算機簡介MIMD多處理機簡介MIMD多計算機簡介65共享內(nèi)存的多處理機具有多個CPU并且所有的CPU共享同一個映射到共享物理內(nèi)存上的虛擬地址空間。多處理機系統(tǒng)有時也被稱為共享內(nèi)存系統(tǒng)（SharedMemorySystem）。從軟件的角度來說，多處理機系統(tǒng)很容易擴展。任何一個處理器都可以通過執(zhí)行LOAD/STORE指令訪問內(nèi)存。兩個處理器之間可以通過很簡單的方式進行通信，只要一個處理器把數(shù)據(jù)寫入內(nèi)存而另一個處理器從內(nèi)存中把數(shù)據(jù)讀出就可以了。多處理機系統(tǒng)也有磁盤、網(wǎng)絡適配器和其它的輸入/輸出設備。如果在一個系統(tǒng)中，每個CPU都能平等地訪問所有的內(nèi)存模塊和輸入/輸出設備，而且在操作系統(tǒng)看來這些CPU是可以互換的，那么這種系統(tǒng)就是對稱多處理機系統(tǒng)SMP（SymmetricMultiProcessor）。多處理機系統(tǒng)中只有一個操作系統(tǒng)，操作系統(tǒng)負責管理一系列的表。這種單一系統(tǒng)映像是多處理機系統(tǒng)區(qū)別于多計算機系統(tǒng)的主要特點。P34866共享內(nèi)存的多處理機67UMA多處理機系統(tǒng)UMA系統(tǒng)特點物理存儲器被所有處理器均勻共享所有處理器訪問任何存儲字需相同的時間每臺處理器可帶私有高速緩存或私有內(nèi)存基于總線的UMA多處理機系統(tǒng)P34968NUMA多處理機系統(tǒng)NUMA系統(tǒng)特點所有的CPU都看到一個單一的地址空間使用LOAD和STORE指令訪問遠程內(nèi)存訪問遠程內(nèi)存比訪問本地內(nèi)存慢NUMA系統(tǒng)中的處理器可使用高速緩存NC-NUMA與CC-NUMA不使用Cache的NUMA系統(tǒng)被稱為NC-NUMA多處理機系統(tǒng)，也就是說這種系統(tǒng)中不隱藏遠程內(nèi)存的訪問時間。如果使用了Cache，那么系統(tǒng)就被稱為CC-NUMA多處理機系統(tǒng)。P35669NUMA多處理機系統(tǒng)NC-NUMA多處理機系統(tǒng)CC-NUMA多處理機系統(tǒng)P35670Cache一致性問題與Cache一致性協(xié)議Cache一致性問題產(chǎn)生原因現(xiàn)代并行計算機中，處理器往往帶有Cache。一個內(nèi)存數(shù)據(jù)在整個系統(tǒng)內(nèi)可能有多份拷貝。這就引發(fā)了Cache一致性問題。Cache一致性協(xié)議由Cache、CPU和內(nèi)存共同實現(xiàn)的防止多個Cache中出現(xiàn)相同數(shù)據(jù)的不同版本的規(guī)則集合就組成了Cache一致性協(xié)議。Cache一致性協(xié)議通?？梢苑譃閮深惐O(jiān)聽總線的協(xié)議基于目錄的協(xié)議71Cache一致性問題與Cache一致性協(xié)議監(jiān)聽總線的協(xié)議在監(jiān)聽總線協(xié)議中，所有的處理器都監(jiān)聽總線，當某個處理器修改了私有Cache中的數(shù)據(jù)后，它在總線上廣播無效信息或更新后的數(shù)據(jù)，以使其它副本無效或得到更新。監(jiān)聽總線協(xié)議適用于互連網(wǎng)絡可以實現(xiàn)廣播功能的并行系統(tǒng)。基于目錄的協(xié)議基本思想：當處理機數(shù)目較多時，一般不用總線結構，而采用多級交換網(wǎng)絡，而多級交換網(wǎng)絡實現(xiàn)廣播功能代價很大。那么能不能只發(fā)送給存放該副本的Cache?基于目錄的協(xié)議是用一個目錄來記錄系統(tǒng)中哪些處理機的Cache中有指定存儲塊的副本。當一臺處理機希望寫某個共享塊時，通過目錄向有該塊的副本的那些處理機“點對點”的發(fā)無效信號，使所有其它的副本無效。72基于監(jiān)聽總線的兩種Cache一致性協(xié)議寫直達Cache一致性協(xié)議對Cache行中的數(shù)據(jù)進行寫操作的同時，將對應的存儲器中的內(nèi)容也進行修改，任意時刻都保持存儲器中的數(shù)據(jù)是最新的。寫回Cache一致性協(xié)議寫操作不直接寫入內(nèi)存。相反，當Cache行被修改后，Cache中的某一位被設置以表示該Cache行中的數(shù)據(jù)是正確的而內(nèi)存中的數(shù)據(jù)是過時的。當然最終該行將會被寫回內(nèi)存，但是可能是在多次寫操作之后了。73監(jiān)聽型Cache按此協(xié)議進行讀寫操作時的四種情況寫直達Cache一致性基本協(xié)議存在多種變化遠程寫命中采用更新策略（UpdateStrategy）還是無效策略（InvalidateStrategy）當Cache寫缺失時是否把相應的字調入Cache，這就是是否采用寫分配策略（Write-allocatePolicy）。寫直達Cache一致性協(xié)議操作本地請求遠程請求讀缺失從內(nèi)存取數(shù)據(jù)讀命中使用本地Cache的數(shù)據(jù)寫缺失修改內(nèi)存中的數(shù)據(jù)寫命中修改Cache和內(nèi)存將Cache項置為失效P35174寫回Cache一致性協(xié)議MESI協(xié)議：它是用協(xié)議中用到的四種狀態(tài)首字母來命名的。這個協(xié)議中每個Cache項都處于下面四種狀態(tài)之一：無效（Invalid）：該Cache項包含的數(shù)據(jù)無效。共享（Shared）：多個Cache項中都有這行數(shù)據(jù)，內(nèi)存中的數(shù)據(jù)是最新的。獨占（Exclusive）：沒有其它的Cache項包括這行數(shù)據(jù)，內(nèi)存中的數(shù)據(jù)是最新的。修改（Modified）：該項的數(shù)據(jù)是有效的，但內(nèi)存中的數(shù)據(jù)是無效的，而且在其它Cache項中沒有該項數(shù)據(jù)的拷貝。P35275I無效M修改S共享E專有↑↓+×↑↑+寫丟失寫監(jiān)聽命中讀丟失(有共享)寫監(jiān)聽命中↓×寫命中使無效讀丟失(無共享)讀監(jiān)聽命中寫監(jiān)聽命中讀監(jiān)聽命中寫命中讀命中寫命中讀命中讀命中讀監(jiān)聽命中注：行填入行寫回主存先讀后修改無效處理↓

MESI協(xié)議狀態(tài)轉換規(guī)則76針對總線不同活動，進行不同的響應處理器讀請求：有效態(tài)(M/S/E)行讀命中，狀態(tài)不變；讀丟失時，分配新行并讀入數(shù)據(jù)，狀態(tài)從I變至S或E。處理器寫請求：有效態(tài)(M/S/E)行寫命中，M/E變?yōu)镸，S先成為“獨有”(其它Cache共享拷貝無效)后再進入M態(tài)；寫丟失時，不按寫分配法寫存后不讀入，按寫分配法先讀入此行(I)修改后變?yōu)镸態(tài),兩種方法均有先“獨有”(其它Cache共享拷貝無效)的處理過程。Cache讀監(jiān)聽命中：S態(tài)不變，E態(tài)變?yōu)镾態(tài)，M態(tài)搶占總線寫回主存后，變?yōu)镾態(tài)。Cache寫監(jiān)聽命中：有效態(tài)(S/E)行變?yōu)镮態(tài)，M態(tài)搶占總線寫回主存后，變?yōu)镮態(tài)。77MESI協(xié)議工作過程P35278本章主要內(nèi)容并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)的設計問題并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的性能問題并行計算機系統(tǒng)的軟件問題SIMD計算機簡介MIMD多處理機簡介MIMD多計算機簡介79基于消息傳遞的多計算機系統(tǒng)在多計算機體系結構中，每個CPU