計算機體系結構第13章

1、計算機組成與系統(tǒng)結構計算機組成與系統(tǒng)結構 王誠王誠 宋佳興宋佳興 清華大學計算機系清華大學計算機系 第第13 13章章 并行計算機體系結構并行計算機體系結構 3 本章主要內容本章主要內容 并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)結構概述 并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的互連網(wǎng)絡 SIMD計算機簡介計算機簡介 MIMD多處理機簡介多處理機簡介 MIMD多計算機簡介多計算機簡介 計算機系統(tǒng)結構的發(fā)展歷程計算機系統(tǒng)結構的發(fā)展歷程 硬件技術和系統(tǒng)結構硬件技術和系統(tǒng)結構軟件和應用軟件和應用 第一代第一代 （19451954） 電子管和繼電器。單電子管和繼電器。單CPU，以程序計，以程序計 數(shù)器數(shù)器P

2、C和累加器順序完成定點運算。和累加器順序完成定點運算。 機器語言或匯編語言。單機器語言或匯編語言。單 用戶。用用戶。用CPU程序控制程序控制I/O。 第二代第二代 （19551964） 晶體管和磁芯存儲器。用印制電路互晶體管和磁芯存儲器。用印制電路互 連。變址寄存器，浮點運算；多路存連。變址寄存器，浮點運算；多路存 儲器，儲器，I/O處理機。處理機。 有編譯程序支持的高級語有編譯程序支持的高級語 言，子程序庫，批處理監(jiān)言，子程序庫，批處理監(jiān) 控程序?？爻绦?。 第三代第三代 （19651974） 中小規(guī)模集成電路。多層印制電路。中小規(guī)模集成電路。多層印制電路。 微程序設計，流水線，高速緩存，先微

3、程序設計，流水線，高速緩存，先 行處理機。行處理機。 多道程序設計，分時操作多道程序設計，分時操作 系統(tǒng)，多用戶應用。系統(tǒng)，多用戶應用。 第四代第四代 （19751990） 大規(guī)模集成電路。半導體存儲器。多大規(guī)模集成電路。半導體存儲器。多 處理機，多計算機，向量超級計算機。處理機，多計算機，向量超級計算機。 用于并行處理的多處理機用于并行處理的多處理機 操作系統(tǒng)、專用語言和編操作系統(tǒng)、專用語言和編 譯器；并行處理或分布計譯器；并行處理或分布計 算的軟件工具和環(huán)境。算的軟件工具和環(huán)境。 第五代第五代 （1991現(xiàn)在）現(xiàn)在） 超大規(guī)模集成電路。高密度高速度處超大規(guī)模集成電路。高密度高速度處 理器和

4、存儲器芯片，可擴展體系結構，理器和存儲器芯片，可擴展體系結構， 因特網(wǎng)。因特網(wǎng)。 大規(guī)模并行處理，大規(guī)模并行處理，Java語語 言，分布式操作系統(tǒng)，萬言，分布式操作系統(tǒng)，萬 維網(wǎng)，維網(wǎng)，網(wǎng)格網(wǎng)格。 計算機系統(tǒng)結構的發(fā)展方向計算機系統(tǒng)結構的發(fā)展方向 第一個是改變馮第一個是改變馮.諾依曼機器的串行執(zhí)行模式諾依曼機器的串行執(zhí)行模式 n超標量計算機（并行執(zhí)行多條指令超標量計算機（并行執(zhí)行多條指令 ） n多處理機系統(tǒng)（共享集中或分布式存儲器）多處理機系統(tǒng)（共享集中或分布式存儲器） n大規(guī)模并行處理機大規(guī)模并行處理機MPP系統(tǒng)系統(tǒng) nPC或工作站組成的集群系統(tǒng)或工作站組成的集群系統(tǒng) 第二個是改變馮第二個是

5、改變馮.諾依曼機器的控制驅動方式諾依曼機器的控制驅動方式 n數(shù)據(jù)驅動方式：操作數(shù)到位即可運算，無序執(zhí)行數(shù)據(jù)驅動方式：操作數(shù)到位即可運算，無序執(zhí)行 n需求驅動方式：驅動方式與數(shù)據(jù)流相反，無序執(zhí)行需求驅動方式：驅動方式與數(shù)據(jù)流相反，無序執(zhí)行 n模式匹配驅動方式：非數(shù)值型應用，主要對象為符號模式匹配驅動方式：非數(shù)值型應用，主要對象為符號 第一個發(fā)展方向已經取得了重大進展，取得了一第一個發(fā)展方向已經取得了重大進展，取得了一 系列的成果。而第二個發(fā)展方向，大多數(shù)還屬于系列的成果。而第二個發(fā)展方向，大多數(shù)還屬于 探索、研究階段，還需要進行大量的工作。探索、研究階段，還需要進行大量的工作。 計算機系統(tǒng)結構的

6、分類方法計算機系統(tǒng)結構的分類方法 過去曾普遍將計算機系統(tǒng)分為過去曾普遍將計算機系統(tǒng)分為巨巨、大大、中中、小小、 微微型機五類。型機五類。 n劃分原則劃分原則：這種方法是按照規(guī)模、性能、速度以至價格：這種方法是按照規(guī)模、性能、速度以至價格 的一種大致劃分。的一種大致劃分。 n存在問題存在問題：只能對同時期的計算機大致分類，劃分的標：只能對同時期的計算機大致分類，劃分的標 準是隨時間而變化，每年左右降低一個等級；另外，準是隨時間而變化，每年左右降低一個等級；另外， 這種劃分方法不能反映機器的系統(tǒng)結構特征。這種劃分方法不能反映機器的系統(tǒng)結構特征。 n設計方法設計方法： w最高性能最高性能特殊用途計算

7、機特殊用途計算機 w最佳性能價格比最佳性能價格比 一般商用計算機一般商用計算機 w最低價格最低價格 家庭用計算機等家庭用計算機等 計算機系統(tǒng)結構的分類方法計算機系統(tǒng)結構的分類方法 計算機系統(tǒng)結構的分類方法計算機系統(tǒng)結構的分類方法 1966年，年，Michael.J.Flynn提出按指令流和數(shù)據(jù)提出按指令流和數(shù)據(jù) 流的多倍性對計算機系統(tǒng)結構進行分類。流的多倍性對計算機系統(tǒng)結構進行分類。 n指令流指令流 是指機器執(zhí)行的指令序列；是指機器執(zhí)行的指令序列； n數(shù)據(jù)流數(shù)據(jù)流 是由指令流調用的數(shù)據(jù)序列，包括輸入數(shù)據(jù)和是由指令流調用的數(shù)據(jù)序列，包括輸入數(shù)據(jù)和 中間結果；中間結果； n多倍性多倍性 是指在系統(tǒng)

8、最受限制的部件上，同時處于同一是指在系統(tǒng)最受限制的部件上，同時處于同一 執(zhí)行階段的指令或數(shù)據(jù)的最大數(shù)目。執(zhí)行階段的指令或數(shù)據(jù)的最大數(shù)目。 指令流指令流數(shù)據(jù)流數(shù)據(jù)流名稱名稱舉例舉例 1個個1個個SISD傳統(tǒng)的馮傳統(tǒng)的馮.諾依曼計算機諾依曼計算機 1個個多個多個SIMD向量計算機，陣列處理機向量計算機，陣列處理機 多個多個1個個MISD？ 多個多個多個多個MIMD多處理機，多計算機多處理機，多計算機 SISD體系結構體系結構 單一的指令流從存儲器取指令，以單一的數(shù)據(jù)流單一的指令流從存儲器取指令，以單一的數(shù)據(jù)流 從存儲器取操作數(shù)和將結果寫回存儲器。從存儲器取操作數(shù)和將結果寫回存儲器。 n單功能部件處

9、理機單功能部件處理機：IBM1401，VAX-11 n多功能部件多功能部件處理機：處理機：IBM360/370，CDC6600 n流水線處理機：流水線處理機：指標量流水線處理機指標量流水線處理機 IS DS CUPUMM SISD SIMD體系結構體系結構 單一的控制部件，多個處理部件。計算機以一個單一的控制部件，多個處理部件。計算機以一個 控制單元從存儲器取單一的指令流，一條指令同控制單元從存儲器取單一的指令流，一條指令同 時作用到各個處理單元，控制各個處理單元對來時作用到各個處理單元，控制各個處理單元對來 自不同數(shù)據(jù)流的數(shù)據(jù)組進行操作。這種體系結構自不同數(shù)據(jù)流的數(shù)據(jù)組進行操作。這種體系結構

10、 的典型代表是陣列處理機和向量流水處理機。的典型代表是陣列處理機和向量流水處理機。 I IS S D DS S1 1 PU MM DS2 CUPU DSn MM PU SIMD MISD體系結構體系結構 多個處理單元，各配有相應的控制單元。各個處多個處理單元，各配有相應的控制單元。各個處 理單元接收不同的指令，多條指令同時在一份數(shù)理單元接收不同的指令，多條指令同時在一份數(shù) 據(jù)上進行操作。這種計算機體系結構已經被證明據(jù)上進行操作。這種計算機體系結構已經被證明 是不可能至少是不實際的，目前為止還不存在這是不可能至少是不實際的，目前為止還不存在這 種類型的計算機。種類型的計算機。 DS IS1 CU

11、1PU1 MM IS2 IS2 CU2PU2 MM CUn PUn ISn MISD MIMD體系結構體系結構 同時有多個處理單元，并且每個處理單元都配有相應的控同時有多個處理單元，并且每個處理單元都配有相應的控 制單元。各個處理單元可以接收不同的指令并對不同的數(shù)制單元。各個處理單元可以接收不同的指令并對不同的數(shù) 據(jù)流進行操作。據(jù)流進行操作。 大多數(shù)現(xiàn)代的并行計算機都屬于這一類，多處理機系統(tǒng)和大多數(shù)現(xiàn)代的并行計算機都屬于這一類，多處理機系統(tǒng)和 多計算機系統(tǒng)都是多計算機系統(tǒng)都是MIMD型的計算機。例如型的計算機。例如IBM3081、 IBM3084、UNIVAC-1100/80、 CRAY-2

12、IS1 DS1 CU1PU1 MM IS2 DS2 CU2 PU2 MM ISn DSn CUn PUn MIMD 計算機系統(tǒng)結構的分類方法計算機系統(tǒng)結構的分類方法 Flynn分類法的局限分類法的局限 n分類的對象主要是控制驅動方式下的串行處理和并行分類的對象主要是控制驅動方式下的串行處理和并行 處理計算機。對于非控制驅動方式的計算機，就不適處理計算機。對于非控制驅動方式的計算機，就不適 合采用合采用Flynn分類法；分類法； n把兩個不同等級的功能并列對待，通常，數(shù)據(jù)流受指把兩個不同等級的功能并列對待，通常，數(shù)據(jù)流受指 令流控制從而造成令流控制從而造成MISD不存在；不存在； n分類太粗，對

13、流水線處理機的劃分不明確，標量流水分類太粗，對流水線處理機的劃分不明確，標量流水 處理機為處理機為SISD，向量流水處理機為，向量流水處理機為SIMD。 其他的分類方法其他的分類方法 n美籍華人馮澤云教授在美籍華人馮澤云教授在1972年提出了按年提出了按最大并行度最大并行度來來 定量描述各種計算機系統(tǒng)的馮氏分類法。定量描述各種計算機系統(tǒng)的馮氏分類法。 nWolfgan Handler在馮氏分類法的基礎上，于在馮氏分類法的基礎上，于1977 年根據(jù)年根據(jù)并行度和流水線并行度和流水線提出了另外一種分類法。提出了另外一種分類法。 n1978年由年由 D. J. Kuck提出按提出按控制流和執(zhí)行流控制

14、流和執(zhí)行流分類。分類。 并行計算機系統(tǒng)的分類并行計算機系統(tǒng)的分類 按照按照Flynn分類法歸納的并行計算機體系結構圖譜分類法歸納的并行計算機體系結構圖譜 SIMD體系結構體系結構 向量計算機向量計算機 n可以在一個向量的每個元素上執(zhí)行相同的操作，可以在一個向量的每個元素上執(zhí)行相同的操作， 一般來說向量處理機是以流水線式一般來說向量處理機是以流水線式ALU為核心，為核心， 實現(xiàn)向量各個元素的并行計算采用的是時間重實現(xiàn)向量各個元素的并行計算采用的是時間重 疊技術。疊技術。 陣列計算機陣列計算機 n這類計算機采用資源重復方法引入空間因素，這類計算機采用資源重復方法引入空間因素， 即在系統(tǒng)中設置多個相

15、同的處理單元來開發(fā)并即在系統(tǒng)中設置多個相同的處理單元來開發(fā)并 行性。此外，它是利用并行性中的同時性，所行性。此外，它是利用并行性中的同時性，所 有處理單元必須同時進行相同操作。有處理單元必須同時進行相同操作。 MIMD體系結構體系結構 多處理機系統(tǒng)多處理機系統(tǒng)基于共享存儲器基于共享存儲器 n系統(tǒng)中只有唯一的地址空間，所有的處理器共享該地系統(tǒng)中只有唯一的地址空間，所有的處理器共享該地 址空間。址空間。 n共享地址空間可以通過一個物理上共享的存儲器來實共享地址空間可以通過一個物理上共享的存儲器來實 現(xiàn)，也可以通過分布式存儲器并在硬件和軟件的支持現(xiàn)，也可以通過分布式存儲器并在硬件和軟件的支持 下實現(xiàn)

16、。下實現(xiàn)。 多計算機系統(tǒng)多計算機系統(tǒng)基于消息傳遞基于消息傳遞 n每個處理器有自己的存儲器，該存儲器只能被該處理每個處理器有自己的存儲器，該存儲器只能被該處理 器訪問而不能被其它處理器直接訪問，這種存儲器稱器訪問而不能被其它處理器直接訪問，這種存儲器稱 為局部存儲器或私有存儲器。為局部存儲器或私有存儲器。 n當處理器當處理器A需要向處理器需要向處理器B傳送數(shù)據(jù)時，傳送數(shù)據(jù)時，A把數(shù)據(jù)以消把數(shù)據(jù)以消 息的形式發(fā)送給息的形式發(fā)送給B。 并行計算機系統(tǒng)發(fā)展的原因并行計算機系統(tǒng)發(fā)展的原因 應用的需求永遠是并行計算機系統(tǒng)發(fā)展的動力應用的需求永遠是并行計算機系統(tǒng)發(fā)展的動力 n隨著計算機速度的提高，人們對計算

17、機性能的要求也隨著計算機速度的提高，人們對計算機性能的要求也 越來越高。例如科學計算、工程和工業(yè)設計等都需要越來越高。例如科學計算、工程和工業(yè)設計等都需要 高性能計算。高性能計算。 n芯片的速度不可能無限地提高，并行計算機可以處理芯片的速度不可能無限地提高，并行計算機可以處理 越來越復雜的問題。芯片的速度要受到光速的制約，越來越復雜的問題。芯片的速度要受到光速的制約， 但芯片的集成度還有發(fā)展的空間。但芯片的集成度還有發(fā)展的空間。 大量商品化的處理器的出現(xiàn)為設計并行計算機系大量商品化的處理器的出現(xiàn)為設計并行計算機系 統(tǒng)提供了可能統(tǒng)提供了可能 并行計算機系統(tǒng)獲得快速發(fā)展和處理機間通信技并行計算機系

18、統(tǒng)獲得快速發(fā)展和處理機間通信技 術的發(fā)展密不可分術的發(fā)展密不可分 18 本章主要內容本章主要內容 并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)結構概述 并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的互連網(wǎng)絡 SIMD計算機簡介計算機簡介 MIMD多處理機簡介多處理機簡介 MIMD多計算機簡介多計算機簡介 互連網(wǎng)絡概述互連網(wǎng)絡概述 并行計算機的通信體系結構是系統(tǒng)的核心并行計算機的通信體系結構是系統(tǒng)的核心 n兩個層次兩個層次：底層的互連網(wǎng)絡；上層的語言、軟件工具：底層的互連網(wǎng)絡；上層的語言、軟件工具 包、編譯器、操作系統(tǒng)等提供的通信支持。包、編譯器、操作系統(tǒng)等提供的通信支持。 互連網(wǎng)絡是并行計算機系統(tǒng)內部的互連

19、網(wǎng)絡互連網(wǎng)絡是并行計算機系統(tǒng)內部的互連網(wǎng)絡 n由開關元件按一定拓撲結構和控制方式構成的網(wǎng)絡以由開關元件按一定拓撲結構和控制方式構成的網(wǎng)絡以 實現(xiàn)計算機系統(tǒng)內部多個處理機或多個功能部件間的實現(xiàn)計算機系統(tǒng)內部多個處理機或多個功能部件間的 相互連接。相互連接。 n與計算機網(wǎng)絡在工作原理、概念以及術語上有許多相與計算機網(wǎng)絡在工作原理、概念以及術語上有許多相 同或相似之處；并且某些并行計算機系統(tǒng)中的互連網(wǎng)同或相似之處；并且某些并行計算機系統(tǒng)中的互連網(wǎng) 絡就是高速以太網(wǎng)和絡就是高速以太網(wǎng)和ATM網(wǎng)絡。網(wǎng)絡。 互連網(wǎng)絡一般由以下五個部分組成互連網(wǎng)絡一般由以下五個部分組成 nCPU、內存模塊、內存模塊、接口接

20、口、鏈路鏈路和和交換結點交換結點 接口、鏈路和交換結點接口、鏈路和交換結點 接口：接口：是從是從CPU和內存取得信息并向另外的和內存取得信息并向另外的CPU和內和內 存發(fā)送信息的設備。典型設備如網(wǎng)絡接口卡。存發(fā)送信息的設備。典型設備如網(wǎng)絡接口卡。 鏈路：鏈路：是傳送數(shù)據(jù)位的物理信道。鏈路可以是電纜、是傳送數(shù)據(jù)位的物理信道。鏈路可以是電纜、 雙絞線或者光纖；可以是串行的也可以是并行的，每雙絞線或者光纖；可以是串行的也可以是并行的，每 種鏈路都有其最大帶寬；鏈路可以是單工的（單方向種鏈路都有其最大帶寬；鏈路可以是單工的（單方向 傳送）、半雙工的（某個時刻只能傳送一個方向的數(shù)傳送）、半雙工的（某個時

21、刻只能傳送一個方向的數(shù) 據(jù)）和全雙工的（同時兩個方向傳送）；鏈路的時鐘據(jù)）和全雙工的（同時兩個方向傳送）；鏈路的時鐘 機制可以是同步或是異步的。機制可以是同步或是異步的。 交換結點：交換結點：是互連網(wǎng)絡的信息交換和控制站點，它是是互連網(wǎng)絡的信息交換和控制站點，它是 具有多個輸入端口和多個輸出端口的設備。能夠進行具有多個輸入端口和多個輸出端口的設備。能夠進行 數(shù)據(jù)緩沖存儲和路徑選擇。數(shù)據(jù)緩沖存儲和路徑選擇。 設計和分析互連網(wǎng)絡的幾個重要問題設計和分析互連網(wǎng)絡的幾個重要問題 互連網(wǎng)絡的拓撲結構互連網(wǎng)絡的拓撲結構 n互連網(wǎng)絡的拓撲結構描述了鏈路和交換結點是如何組互連網(wǎng)絡的拓撲結構描述了鏈路和交換結點

22、是如何組 織安排的。拓撲結構可以用圖來表示，鏈路用邊表示，織安排的。拓撲結構可以用圖來表示，鏈路用邊表示， 交換結點用結點表示。交換結點用結點表示。 互連網(wǎng)絡的尋徑方式互連網(wǎng)絡的尋徑方式 n交換結點所做的工作就是接收到達輸入端口的分組然交換結點所做的工作就是接收到達輸入端口的分組然 后把分組發(fā)送到正確的輸出端口，具有多種不同的工后把分組發(fā)送到正確的輸出端口，具有多種不同的工 作方式。作方式。 互連網(wǎng)絡的尋徑算法互連網(wǎng)絡的尋徑算法 n尋徑算法：決定一個分組從源結點到達目的結點的過尋徑算法：決定一個分組從源結點到達目的結點的過 程中經過的結點序列的算法。程中經過的結點序列的算法。 互連網(wǎng)絡的分類互

23、連網(wǎng)絡的分類 靜態(tài)網(wǎng)絡靜態(tài)網(wǎng)絡 n靜態(tài)網(wǎng)絡靜態(tài)網(wǎng)絡(Static Networks)是指結點間有著是指結點間有著 固定連接通路且在程序執(zhí)行期間，這種連接保固定連接通路且在程序執(zhí)行期間，這種連接保 持不變的網(wǎng)絡。持不變的網(wǎng)絡。 動態(tài)網(wǎng)絡動態(tài)網(wǎng)絡 n動態(tài)網(wǎng)絡動態(tài)網(wǎng)絡(Dynamic Networks)由開關單元構由開關單元構 成，可按應用程序的要求動態(tài)地改變連接狀態(tài)。成，可按應用程序的要求動態(tài)地改變連接狀態(tài)。 如總線、交叉開關，多級交換網(wǎng)絡等。如總線、交叉開關，多級交換網(wǎng)絡等。 互連網(wǎng)絡的參數(shù)互連網(wǎng)絡的參數(shù) 結點度結點度：與結點相連接的邊數(shù)，表示節(jié)點所需要的端口：與結點相連接的邊數(shù)，表示節(jié)點所需要

24、的端口 數(shù)，根據(jù)鏈路到結點的方向，結點度可以進一步表示為：數(shù)，根據(jù)鏈路到結點的方向，結點度可以進一步表示為： 結點度結點度 = 入度入度 + 出度出度，其中，其中入度入度是進入結點的鏈路數(shù)，是進入結點的鏈路數(shù)， 出度出度是從結點出來的鏈路數(shù)。是從結點出來的鏈路數(shù)。 鏈路的長度鏈路的長度：鏈路中包含的邊數(shù)：鏈路中包含的邊數(shù) 距離距離：與兩個結點之間相連的最少邊數(shù)。：與兩個結點之間相連的最少邊數(shù)。 網(wǎng)絡直徑網(wǎng)絡直徑：網(wǎng)絡中任意兩個結點間距離的最大值。：網(wǎng)絡中任意兩個結點間距離的最大值。 網(wǎng)絡規(guī)模網(wǎng)絡規(guī)模：網(wǎng)絡中結點數(shù)，表示該網(wǎng)絡功能連結部件的：網(wǎng)絡中結點數(shù)，表示該網(wǎng)絡功能連結部件的 多少。多少。

25、等分寬度等分寬度：某一網(wǎng)絡被切成相等的兩半時，沿切口的最：某一網(wǎng)絡被切成相等的兩半時，沿切口的最 小邊數(shù)稱為該網(wǎng)絡的等分寬度。小邊數(shù)稱為該網(wǎng)絡的等分寬度。 對稱性對稱性：從任何結點看，拓撲結構都一樣，這種網(wǎng)絡實：從任何結點看，拓撲結構都一樣，這種網(wǎng)絡實 現(xiàn)和編程都很容易?，F(xiàn)和編程都很容易。 靜態(tài)互連網(wǎng)絡靜態(tài)互連網(wǎng)絡 線性陣列線性陣列 n對對N個結點的線性陣列，有個結點的線性陣列，有N-1條鏈路，直徑條鏈路，直徑 為為N-1（任意兩點之間距離的最大值）度為（任意兩點之間距離的最大值）度為2 不對稱，等分寬度為不對稱，等分寬度為1。N很大時，通信效率很大時，通信效率 很低。很低。 環(huán)形環(huán)形 n對對

26、N個結點的環(huán)，考慮相個結點的環(huán)，考慮相 鄰結點數(shù)據(jù)傳送方向：鄰結點數(shù)據(jù)傳送方向： 雙向環(huán)雙向環(huán)：鏈路數(shù)為：鏈路數(shù)為N，直，直 徑徑 N/2 ，度為，度為2，對稱，對稱， 等分寬度為等分寬度為2。 單向環(huán)單向環(huán)：鏈路數(shù)為：鏈路數(shù)為N，直，直 徑徑N-1，度為，度為2，對稱，對稱， 等分寬度為等分寬度為2。 靜態(tài)互連網(wǎng)絡靜態(tài)互連網(wǎng)絡 靜態(tài)互連網(wǎng)絡靜態(tài)互連網(wǎng)絡 全鏈接全鏈接 n全鏈接是帶弦環(huán)的一全鏈接是帶弦環(huán)的一 種特殊情形。鏈接中種特殊情形。鏈接中 的每個結點和其他結的每個結點和其他結 點之間都有單一的直點之間都有單一的直 接鏈路。接鏈路。 n如下圖中如下圖中8個結點的全個結點的全 鏈接：有鏈接：

27、有28條鏈路，條鏈路， 直徑為直徑為1，度為，度為7，對，對 稱，等分寬度為稱，等分寬度為16。 4層的二叉樹 層的二叉樹 靜態(tài)互連網(wǎng)絡靜態(tài)互連網(wǎng)絡 樹形樹形 n一棵一棵K層完全二叉樹應有層完全二叉樹應有N = 2K - 1個結點，最大結點個結點，最大結點 度為度為3，直徑為，直徑為2（K - 1）（即右邊任意一個葉子結點（即右邊任意一個葉子結點 到左邊任意一個葉子結點）。不對稱，等分寬度為到左邊任意一個葉子結點）。不對稱，等分寬度為1。 帶環(huán)樹帶環(huán)樹二叉胖樹二叉胖樹 樹形的擴展樹形的擴展 這兩種結構都可以緩解根結點的瓶頸問題這兩種結構都可以緩解根結點的瓶頸問題 靜態(tài)互連網(wǎng)絡靜態(tài)互連網(wǎng)絡 星形

28、星形 n星形實際上是一種二層樹（如右圖）。有星形實際上是一種二層樹（如右圖）。有N個結點的個結點的 星形網(wǎng)絡，有星形網(wǎng)絡，有N - 1條鏈路，直徑為條鏈路，直徑為2，最大結點度，最大結點度 為為N - 1，非對稱，等分寬度為，非對稱，等分寬度為1。 靜態(tài)互連網(wǎng)絡靜態(tài)互連網(wǎng)絡 網(wǎng)格形網(wǎng)格形 n有有N個結點的個結點的r r 網(wǎng)，有網(wǎng)，有2N - 2r 條鏈路，直徑為條鏈路，直徑為 2(r-1)，結點度結點度 為為4，非對稱，非對稱， 等分寬度為等分寬度為r。 n其中其中 Nr 靜態(tài)互連網(wǎng)絡靜態(tài)互連網(wǎng)絡 二維環(huán)網(wǎng)形二維環(huán)網(wǎng)形 n有有N個結點的個結點的r r網(wǎng)，網(wǎng)， 有有2N條鏈路，直徑條鏈路，直徑

29、為為2 r/2 ，結點度，結點度 為為4，對稱。，對稱。 n其中其中Nr 靜態(tài)互連網(wǎng)絡靜態(tài)互連網(wǎng)絡 超立方體超立方體 n一個一個n-立方體由立方體由N = 2n個結點構成，它們分布在個結點構成，它們分布在n維維 上，每維有兩個結點。直徑為上，每維有兩個結點。直徑為n，結點度為，結點度為n，對稱。，對稱。 3-立方體立方體 4-立方體立方體 帶環(huán)帶環(huán)3-立方體立方體 靜態(tài)互連網(wǎng)絡靜態(tài)互連網(wǎng)絡 帶環(huán)立方體帶環(huán)立方體 n一個帶環(huán)一個帶環(huán)n-立方體立方體 由由N = 2n個個結點環(huán)結點環(huán) 構成，每個結點環(huán)構成，每個結點環(huán) 是一個有是一個有n個結點的個結點的 環(huán)，所以結點總數(shù)環(huán)，所以結點總數(shù) 為為n2n

30、個，結點度為個，結點度為 3，對稱。，對稱。 靜態(tài)互連網(wǎng)絡特性一覽表 動態(tài)互連網(wǎng)絡動態(tài)互連網(wǎng)絡 網(wǎng)絡特點網(wǎng)絡特點 n動態(tài)互連網(wǎng)絡中的連接不固定，在程序執(zhí)行過動態(tài)互連網(wǎng)絡中的連接不固定，在程序執(zhí)行過 程中可根據(jù)需要改變。程中可根據(jù)需要改變。 n網(wǎng)絡的開關元件有源，鏈路可通過設置這些開網(wǎng)絡的開關元件有源，鏈路可通過設置這些開 關的狀態(tài)來重構。關的狀態(tài)來重構。 n只有在互連網(wǎng)絡邊界上的開關元件才能與處理只有在互連網(wǎng)絡邊界上的開關元件才能與處理 機相連。機相連。 n動態(tài)互連網(wǎng)絡主要有動態(tài)互連網(wǎng)絡主要有總線、交叉開關、多級交總線、交叉開關、多級交 換網(wǎng)絡換網(wǎng)絡。 動態(tài)互連網(wǎng)絡動態(tài)互連網(wǎng)絡 總線（總線（B

31、us） n總線實際上是連接處理器、存儲器和總線實際上是連接處理器、存儲器和I/O等外等外 圍設備的一組導線和插座圍設備的一組導線和插座 n它在某一時刻只能用于一對它在某一時刻只能用于一對源和目的源和目的之間傳輸之間傳輸 數(shù)據(jù)數(shù)據(jù) n當有多對源和目的請求使用總線時，要進行總當有多對源和目的請求使用總線時，要進行總 線仲裁。當線仲裁。當CPU數(shù)目較多時對總線爭用嚴重數(shù)目較多時對總線爭用嚴重 （=32個）個） I/O總線總線I/O總線總線 C 局部總線局部總線 CAIF PM CPU板板 存儲器總線存儲器總線 IFC 存儲器存儲器 存儲器板存儲器板 C 局部總線局部總線 CAIF PM CPU板板

32、存儲器總線存儲器總線 IFC 存儲器存儲器 存儲器板存儲器板 系統(tǒng)總線（在底板上）系統(tǒng)總線（在底板上） IF 局部總線局部總線 緩存器緩存器IF IOP I/O板板 磁盤磁盤打印機打印機 C 局部總線局部總線 緩存器緩存器IF IF 網(wǎng)絡接口卡網(wǎng)絡接口卡 以太網(wǎng)以太網(wǎng) IF:IF:專用邏輯接口專用邏輯接口 C:C:專用控制器專用控制器 P:P:處理器處理器 M:M:局部存儲器局部存儲器 CA:CA:高速緩存高速緩存 IOP:I/OIOP:I/O處理器處理器 動態(tài)互連網(wǎng)絡動態(tài)互連網(wǎng)絡 交叉開關（交叉開關（Crossbar Switcher） n交叉開關是一種高帶寬網(wǎng)絡，它可以在輸入端交叉開關是一

33、種高帶寬網(wǎng)絡，它可以在輸入端 和輸出端之間建立動態(tài)連接和輸出端之間建立動態(tài)連接 n在每個輸入端和輸出端的交叉點上都有交叉點在每個輸入端和輸出端的交叉點上都有交叉點 開關。該開關可以根據(jù)需要置為開關。該開關可以根據(jù)需要置為“開開”或或“關關” 狀態(tài)，從而使不同的輸入端和輸出端導通。狀態(tài)，從而使不同的輸入端和輸出端導通。 n交叉開關的硬件復雜性為交叉開關的硬件復雜性為n2數(shù)量級，造價昂貴。數(shù)量級，造價昂貴。 但是其帶寬和尋徑性能在這三種動態(tài)網(wǎng)絡中最但是其帶寬和尋徑性能在這三種動態(tài)網(wǎng)絡中最 好。如果網(wǎng)絡規(guī)模小，它是一種理想的選擇好。如果網(wǎng)絡規(guī)模小，它是一種理想的選擇 （64） 多級交換網(wǎng)絡多級交換網(wǎng)

34、絡 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第第0級級第第1級級第第2級級 無阻塞的無阻塞的交換交換 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第第0級級第第1級級第第2級級 有阻塞的有阻塞的交換交換 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第第0級級第第1級級第第2級級 F G H J I 互連網(wǎng)絡的尋徑方式互連網(wǎng)絡的尋徑方式 電路交換：電路交換： n預約資源（端口和緩沖區(qū)），預先建立固定交換結點鏈路，分組預約資源（端口和緩沖區(qū)），預先建立固定交換結點鏈路，分組 能夠全速發(fā)送。建立鏈路時間長，資源利用率低。能夠全速發(fā)送。建

35、立鏈路時間長，資源利用率低。 存儲轉發(fā)：存儲轉發(fā)： n不預約資源，各個交換結點緩存整個分組，靈活有效。需要的緩不預約資源，各個交換結點緩存整個分組，靈活有效。需要的緩 沖區(qū)大，網(wǎng)絡時延長。沖區(qū)大，網(wǎng)絡時延長。 虛擬直通尋徑：虛擬直通尋徑： n分組分成更小的單元，第一個單元到達節(jié)點即開始尋徑，當?shù)谝环纸M分成更小的單元，第一個單元到達節(jié)點即開始尋徑，當?shù)谝?個單元阻塞不能移動時，分組其余單元可以繼續(xù)向第一個單元所個單元阻塞不能移動時，分組其余單元可以繼續(xù)向第一個單元所 在的結點傳送。在的結點傳送。 蟲蝕尋徑：蟲蝕尋徑： n分組分成更小的單元，各個單元在在節(jié)點中流水方式前進，當分分組分成更小的單元，

36、各個單元在在節(jié)點中流水方式前進，當分 組的第一個單元不能移動時，分組的各個單元停留在多個交換結組的第一個單元不能移動時，分組的各個單元停留在多個交換結 點中。較小的分組單元緩沖區(qū)，阻塞占用多個結點。點中。較小的分組單元緩沖區(qū)，阻塞占用多個結點。 互連網(wǎng)絡的尋徑算法互連網(wǎng)絡的尋徑算法 源尋徑和分布式尋徑源尋徑和分布式尋徑 n在源尋徑中，源結點預先決定穿過互連網(wǎng)絡的完整的在源尋徑中，源結點預先決定穿過互連網(wǎng)絡的完整的 路徑，使用路徑中每個結點的端口號的列表來表示。路徑，使用路徑中每個結點的端口號的列表來表示。 n在分布式尋徑算法中，每個交換結點自己決定把到達在分布式尋徑算法中，每個交換結點自己決定

37、把到達 的分組發(fā)送到哪個輸出端口。一般來說在各個交換結的分組發(fā)送到哪個輸出端口。一般來說在各個交換結 點都設立一個路徑表，而分組的頭部含有一個尋徑字點都設立一個路徑表，而分組的頭部含有一個尋徑字 段說明分組的目的地址和選擇路徑的依據(jù)。段說明分組的目的地址和選擇路徑的依據(jù)。 靜態(tài)尋徑算法和自適應尋徑算法靜態(tài)尋徑算法和自適應尋徑算法 n算法對所有到相同目的結點的分組都做出相同的決策，算法對所有到相同目的結點的分組都做出相同的決策， 那么這樣的尋徑算法就稱為靜態(tài)的。那么這樣的尋徑算法就稱為靜態(tài)的。 n算法在做路徑選擇時考慮了當前情況，該算法就是自算法在做路徑選擇時考慮了當前情況，該算法就是自 適應的

38、。適應的。 47 本章主要內容本章主要內容 并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)結構概述 并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的互連網(wǎng)絡 SIMD計算機簡介計算機簡介 MIMD多處理機簡介多處理機簡介 MIMD多計算機簡介多計算機簡介 SIMD計算機計算機 單指令流多數(shù)據(jù)流計算機用于解決使用向量和陣單指令流多數(shù)據(jù)流計算機用于解決使用向量和陣 列這樣比較規(guī)整的數(shù)據(jù)結構的復雜科學計算和工列這樣比較規(guī)整的數(shù)據(jù)結構的復雜科學計算和工 程計算問題。程計算問題。 只有一個控制單元，每次只能執(zhí)行一條指令，但只有一個控制單元，每次只能執(zhí)行一條指令，但 是這一條指令可以同時對多個數(shù)據(jù)進行操作。是這一條指令可以

39、同時對多個數(shù)據(jù)進行操作。 SIMD計算機可以分為陣列處理機和向量處理機計算機可以分為陣列處理機和向量處理機 兩大類。兩大類。 陣列處理機陣列處理機 設計陣列處理機基本思想設計陣列處理機基本思想 n用一個單一的控制單元提供信號驅動多個處理單元同時運行，如用一個單一的控制單元提供信號驅動多個處理單元同時運行，如 下圖所示。每個處理器單元都由下圖所示。每個處理器單元都由CPU或者是功能增強的或者是功能增強的ALU和本和本 地內存組成。地內存組成。 n由于所有的處理單元都是由一個控制單元驅動的，因此它們的執(zhí)由于所有的處理單元都是由一個控制單元驅動的，因此它們的執(zhí) 行是同步的。行是同步的。 各種陣列處理

40、機的不同之處各種陣列處理機的不同之處 n處理單元的結構：處理單元的結構可能很簡單，也可能很復雜。處理單元的結構：處理單元的結構可能很簡單，也可能很復雜。 n處理單元如何連接：從原理上來說前面列出的拓撲結構都是可行處理單元如何連接：從原理上來說前面列出的拓撲結構都是可行 的，網(wǎng)格是比較常用的結構。的，網(wǎng)格是比較常用的結構。 n處理單元自治能力：每個處理單元都可以選擇執(zhí)行或不執(zhí)行某條處理單元自治能力：每個處理單元都可以選擇執(zhí)行或不執(zhí)行某條 指令。指令。 沒有那個公司的產品在市場上取得較大的成功，陣列處理沒有那個公司的產品在市場上取得較大的成功，陣列處理 機沒有好的發(fā)展前景。機沒有好的發(fā)展前景。 I

41、LLIAC IV型陣列處理機型陣列處理機 向量處理機向量處理機 向量處理機在商業(yè)上取得了很大成功。向量處理機在商業(yè)上取得了很大成功。Cray Research公公 司設計的系列計算機，從司設計的系列計算機，從Cray-1到后來的到后來的C90和和T90，在，在 科學計算領域占據(jù)了數(shù)十年的統(tǒng)治地位?？茖W計算領域占據(jù)了數(shù)十年的統(tǒng)治地位。 從數(shù)學的概念上講，標量是指單個量，而向量是指一組標從數(shù)學的概念上講，標量是指單個量，而向量是指一組標 量。例如，有一個數(shù)組量。例如，有一個數(shù)組A（a1，a2，a3，an），其），其 中括號內的每一個元素中括號內的每一個元素ai就是一個標量。而就是一個標量。而A稱為

42、向量，稱為向量， 它由一組標量組成。它由一組標量組成。 向量處理方式：引入向量數(shù)據(jù)表示，需要向量指令處理。向量處理方式：引入向量數(shù)據(jù)表示，需要向量指令處理。 標量處理：標量處理： forfor（i i0 0；i iN N；i i） Ai AiBiBiCiCi 向量處理：向量處理： A AB BC C 向量處理機向量處理機 向量處理方法向量處理方法 n例子：例子：D=A(BC) 其中其中 A、B、C、D都是長度為都是長度為N 的向量。的向量。 n橫向處理方法：逐個求向量橫向處理方法：逐個求向量 D中中N個分量個分量 。 n縱向處理方法：先求縱向處理方法：先求BC 各個分量得向量各個分量得向量K，

43、然后計，然后計 算算D=AK。 n縱橫處理方法：分組處理，縱橫處理方法：分組處理， 組內采用縱向處理，組間采組內采用縱向處理，組間采 用橫向處理。用橫向處理。 最簡單的向量處理結構最簡單的向量處理結構 向量處理和流水線結合向量處理和流水線結合 對語言結構和編譯程序提對語言結構和編譯程序提 出新的要求出新的要求 53 本章主要內容本章主要內容 并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)結構概述 并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的互連網(wǎng)絡 SIMD計算機簡介計算機簡介 MIMD多處理機簡介多處理機簡介 MIMD多計算機簡介多計算機簡介 共享內存的多處理機共享內存的多處理機 具有多個具有多個CPU并

44、且所有的并且所有的CPU共享同一個映射到共享物共享同一個映射到共享物 理內存上的虛擬地址空間。多處理機系統(tǒng)有時也被稱為共理內存上的虛擬地址空間。多處理機系統(tǒng)有時也被稱為共 享內存系統(tǒng)（享內存系統(tǒng)（Shared Memory System）。）。 從軟件的角度來說，多處理機系統(tǒng)很容易擴展。任何一個從軟件的角度來說，多處理機系統(tǒng)很容易擴展。任何一個 處理器都可以通過執(zhí)行處理器都可以通過執(zhí)行LOAD/STORE指令訪問內存。兩指令訪問內存。兩 個處理器之間可以通過很簡單的方式進行通信，只要一個個處理器之間可以通過很簡單的方式進行通信，只要一個 處理器把數(shù)據(jù)寫入內存而另一個處理器從內存中把數(shù)據(jù)讀處理器

45、把數(shù)據(jù)寫入內存而另一個處理器從內存中把數(shù)據(jù)讀 出就可以了。出就可以了。 多處理機系統(tǒng)也有磁盤、網(wǎng)絡適配器和其它的輸入多處理機系統(tǒng)也有磁盤、網(wǎng)絡適配器和其它的輸入/輸出輸出 設備。如果在一個系統(tǒng)中，每個設備。如果在一個系統(tǒng)中，每個CPU都能平等地訪問所有都能平等地訪問所有 的內存模塊和輸入的內存模塊和輸入/輸出設備，而且在操作系統(tǒng)看來這些輸出設備，而且在操作系統(tǒng)看來這些 CPU是可以互換的，那么這種系統(tǒng)就是對稱多處理機系統(tǒng)是可以互換的，那么這種系統(tǒng)就是對稱多處理機系統(tǒng) SMP（Symmetric MultiProcessor）。）。 共享內存的多處理機共享內存的多處理機 UMA多處理機系統(tǒng)多處理

46、機系統(tǒng) UMA系統(tǒng)特點系統(tǒng)特點 n物理存儲器被所有處理器均勻共享物理存儲器被所有處理器均勻共享 n所有處理器訪問任何存儲字需相同的時間所有處理器訪問任何存儲字需相同的時間 n每臺處理器可帶私有高速緩存或私有內存每臺處理器可帶私有高速緩存或私有內存 基于總線的基于總線的UMA多處理機系統(tǒng)多處理機系統(tǒng) NUMA多處理機系統(tǒng)多處理機系統(tǒng) NUMA系統(tǒng)特點系統(tǒng)特點 n所有的所有的CPU都看到一個單一的地址空間都看到一個單一的地址空間 n使用使用LOAD和和STORE指令訪問遠程內存指令訪問遠程內存 n訪問遠程內存比訪問本地內存慢訪問遠程內存比訪問本地內存慢 nNUMA系統(tǒng)中的處理器可使用高速緩存系統(tǒng)中

47、的處理器可使用高速緩存 NC-NUMA與與CC-NUMA n不使用不使用Cache的的NUMA系統(tǒng)被稱為系統(tǒng)被稱為NC-NUMA多處理多處理 機系統(tǒng)，這種系統(tǒng)中不隱藏遠程內存的訪問時間。機系統(tǒng)，這種系統(tǒng)中不隱藏遠程內存的訪問時間。 n如果使用了如果使用了Cache，那么系統(tǒng)就被稱為，那么系統(tǒng)就被稱為CC-NUMA多多 處理機系統(tǒng)。處理機系統(tǒng)。 NUMA多處理機系統(tǒng)多處理機系統(tǒng) NC-NUMA多處理機系統(tǒng)多處理機系統(tǒng) CC-NUMA多處理機系統(tǒng)多處理機系統(tǒng) Cache一致性問題與一致性問題與Cache一致性協(xié)議一致性協(xié)議 Cache一致性問題產生原因一致性問題產生原因 n現(xiàn)代并行計算機中，處理器

48、往往帶有現(xiàn)代并行計算機中，處理器往往帶有Cache。一個內。一個內 存數(shù)據(jù)在整個系統(tǒng)內可能有多份拷貝。這就引發(fā)了存數(shù)據(jù)在整個系統(tǒng)內可能有多份拷貝。這就引發(fā)了 Cache一致性問題一致性問題。 什么是什么是Cache一致性協(xié)議？一致性協(xié)議？ n由由Cache、CPU和內存共同實現(xiàn)的防止多個和內存共同實現(xiàn)的防止多個Cache中中 出現(xiàn)相同數(shù)據(jù)的不同版本的規(guī)則集合就組成了出現(xiàn)相同數(shù)據(jù)的不同版本的規(guī)則集合就組成了Cache 一致性協(xié)議一致性協(xié)議。 Cache一致性協(xié)議通?？梢苑譃閮深愐恢滦詤f(xié)議通常可以分為兩類 n監(jiān)聽總線的協(xié)議監(jiān)聽總線的協(xié)議 n基于目錄的協(xié)議基于目錄的協(xié)議 Cache一致性問題與一致性

49、問題與Cache一致性協(xié)議一致性協(xié)議 監(jiān)聽總線的協(xié)議監(jiān)聽總線的協(xié)議 n在監(jiān)聽總線協(xié)議中，所有的處理器都監(jiān)聽總線，當某個處理器在監(jiān)聽總線協(xié)議中，所有的處理器都監(jiān)聽總線，當某個處理器 修改了私有修改了私有Cache中的數(shù)據(jù)后，它在總線上廣播無效信息或更中的數(shù)據(jù)后，它在總線上廣播無效信息或更 新后的數(shù)據(jù)，以使其它副本無效或得到更新。新后的數(shù)據(jù)，以使其它副本無效或得到更新。 n監(jiān)聽總線協(xié)議適用于互連網(wǎng)絡可以實現(xiàn)廣播功能的并行系統(tǒng)。監(jiān)聽總線協(xié)議適用于互連網(wǎng)絡可以實現(xiàn)廣播功能的并行系統(tǒng)。 基于目錄的協(xié)議基于目錄的協(xié)議 n基本思想：當處理機數(shù)目較多時，一般不用總線結構，而采用基本思想：當處理機數(shù)目較多時，一

50、般不用總線結構，而采用 多級交換網(wǎng)絡，而多級交換網(wǎng)絡實現(xiàn)廣播功能代價很大。多級交換網(wǎng)絡，而多級交換網(wǎng)絡實現(xiàn)廣播功能代價很大。那么那么 能不能只發(fā)送給存放該副本的能不能只發(fā)送給存放該副本的Cache? n基于目錄的協(xié)議是用一個目錄來記錄系統(tǒng)中哪些處理機的基于目錄的協(xié)議是用一個目錄來記錄系統(tǒng)中哪些處理機的 Cache中有指定存儲塊的副本。當一臺處理機希望寫某個共享中有指定存儲塊的副本。當一臺處理機希望寫某個共享 塊時，通過目錄向有該塊的副本的那些處理機塊時，通過目錄向有該塊的副本的那些處理機“點對點點對點”的發(fā)的發(fā) 無效信號，使所有其它的副本無效。無效信號，使所有其它的副本無效。 基于監(jiān)聽總線的兩

51、種基于監(jiān)聽總線的兩種Cache一致性協(xié)議一致性協(xié)議 寫直達寫直達Cache一致性協(xié)議一致性協(xié)議 n對對Cache行中的數(shù)據(jù)進行寫操作的同時，將對行中的數(shù)據(jù)進行寫操作的同時，將對 應的存儲器中的內容也進行修改，任意時刻都應的存儲器中的內容也進行修改，任意時刻都 保持存儲器中的數(shù)據(jù)是最新的。保持存儲器中的數(shù)據(jù)是最新的。 寫回寫回Cache一致性協(xié)議一致性協(xié)議 n寫操作不直接寫入內存。相反，當寫操作不直接寫入內存。相反，當Cache行被行被 修改后，修改后，Cache中的某一位被設置以表示該中的某一位被設置以表示該 Cache行中的數(shù)據(jù)是正確的而內存中的數(shù)據(jù)是行中的數(shù)據(jù)是正確的而內存中的數(shù)據(jù)是 過時

52、的。當然最終該行將會被寫回內存，但是過時的。當然最終該行將會被寫回內存，但是 可能是在多次寫操作之后了?？赡苁窃诙啻螌懖僮髦罅恕?監(jiān)聽型監(jiān)聽型Cache按此協(xié)議進行讀寫操作時的四種情況按此協(xié)議進行讀寫操作時的四種情況 寫直達寫直達Cache一致性基本協(xié)議存在多種變化一致性基本協(xié)議存在多種變化 n遠程寫命中采用更新策略（遠程寫命中采用更新策略（Update Strategy）還是無效策略）還是無效策略 （Invalidate Strategy） n當當Cache寫缺失時是否把相應的字調入寫缺失時是否把相應的字調入Cache，這就是是否采用，這就是是否采用 寫分配策略（寫分配策略（Write-a

53、llocate Policy）。）。 寫直達寫直達Cache一致性協(xié)議一致性協(xié)議 操作操作本地請求處理本地請求處理遠程請求處理遠程請求處理 讀缺失讀缺失從內存取數(shù)據(jù)從內存取數(shù)據(jù) 讀命中讀命中使用本地使用本地Cache的數(shù)據(jù)的數(shù)據(jù) 寫缺失寫缺失修改內存中的數(shù)據(jù)修改內存中的數(shù)據(jù) 寫命中寫命中修改修改Cache和內存和內存將將Cache項置為失效項置為失效 寫回寫回Cache一致性協(xié)議一致性協(xié)議 MESI協(xié)議：它是用協(xié)議中用到的四種狀態(tài)首字協(xié)議：它是用協(xié)議中用到的四種狀態(tài)首字 母來命名的。這個協(xié)議中每個母來命名的。這個協(xié)議中每個Cache項都處于下項都處于下 面四種狀態(tài)之一：面四種狀態(tài)之一： n無效

54、（無效（Invalid）：該：該Cache項包含的數(shù)據(jù)無效。項包含的數(shù)據(jù)無效。 n共享（共享（Shared）：多個：多個Cache項中都有這行數(shù)據(jù)，內項中都有這行數(shù)據(jù)，內 存中的數(shù)據(jù)是最新的。存中的數(shù)據(jù)是最新的。 n獨占（獨占（Exclusive）：沒有其它的：沒有其它的Cache項包括這行數(shù)項包括這行數(shù) 據(jù)，內存中的數(shù)據(jù)是最新的。據(jù)，內存中的數(shù)據(jù)是最新的。 n修改（修改（Modified）：該項的數(shù)據(jù)是有效的，但內存中：該項的數(shù)據(jù)是有效的，但內存中 的數(shù)據(jù)是無效的，而且在其它的數(shù)據(jù)是無效的，而且在其它Cache項中沒有該項數(shù)項中沒有該項數(shù) 據(jù)的拷貝。據(jù)的拷貝。 I無效無效 M修改修改 S共享

55、共享 E獨占獨占 + + 寫丟失寫丟失 寫監(jiān)聽命中寫監(jiān)聽命中 讀丟失讀丟失( (有共享有共享) ) 寫監(jiān)聽命中寫監(jiān)聽命中 寫命中寫命中 使無效使無效 讀丟失讀丟失 ( (無共享無共享) ) 讀監(jiān)聽命中讀監(jiān)聽命中 寫監(jiān)寫監(jiān) 聽命中聽命中 讀監(jiān)聽讀監(jiān)聽 命中命中 寫命中寫命中 讀命中讀命中 寫命中寫命中 讀命中讀命中 讀命中讀命中 讀監(jiān)聽命中讀監(jiān)聽命中 注：注： 行填入行填入行寫回主存行寫回主存先讀后修改先讀后修改無效處理無效處理 MESI協(xié)議狀態(tài)轉換規(guī)則協(xié)議狀態(tài)轉換規(guī)則 針對總線不同活動，進行不同的響應針對總線不同活動，進行不同的響應 處理器讀請求：處理器讀請求：有效態(tài)有效態(tài)(M/S/E)行讀命

56、中，狀態(tài)不變；行讀命中，狀態(tài)不變； 讀丟失時，分配新行并讀入數(shù)據(jù)，狀態(tài)從讀丟失時，分配新行并讀入數(shù)據(jù)，狀態(tài)從I變至變至S或或E。 處理器寫請求：處理器寫請求：有效態(tài)有效態(tài)(M/S/E)行寫命中，行寫命中，M/E變?yōu)樽優(yōu)镸， S先成為先成為“獨有獨有”(其它其它Cache共享拷貝無效共享拷貝無效)后再進入后再進入M態(tài)；態(tài)； 寫丟失時，不按寫分配法寫存后不讀入，按寫分配法先讀入寫丟失時，不按寫分配法寫存后不讀入，按寫分配法先讀入 此行此行(I)修改后變?yōu)樾薷暮笞優(yōu)镸態(tài)，兩種方法均有先態(tài)，兩種方法均有先“獨有獨有”(其它其它 Cache共享拷貝無效共享拷貝無效) 的處理過程。的處理過程。 Cache

57、讀監(jiān)聽命中：讀監(jiān)聽命中：S態(tài)不變，態(tài)不變，E態(tài)變?yōu)閼B(tài)變?yōu)镾態(tài)，態(tài)，M態(tài)搶占態(tài)搶占 總線寫回主存后，變?yōu)榭偩€寫回主存后，變?yōu)镾態(tài)。態(tài)。 Cache寫監(jiān)聽命中：寫監(jiān)聽命中：有效態(tài)有效態(tài)(S/E)行變?yōu)樾凶優(yōu)镮態(tài)，態(tài)，M態(tài)搶占態(tài)搶占 總線寫回主存后，變?yōu)榭偩€寫回主存后，變?yōu)镮態(tài)。態(tài)。 MESI 協(xié)協(xié) 議議 工工 作作 過過 程程 舉舉 例例 67 本章主要內容本章主要內容 并行計算機系統(tǒng)結構概述并行計算機系統(tǒng)結構概述 并行計算機系統(tǒng)的互連網(wǎng)絡并行計算機系統(tǒng)的互連網(wǎng)絡 SIMD計算機簡介計算機簡介 MIMD多處理機簡介多處理機簡介 MIMD多計算機簡介多計算機簡介 基于消息傳遞的多計算機系統(tǒng)基于消息傳

58、遞的多計算機系統(tǒng) 在多計算機體系結構中，每個在多計算機體系結構中，每個CPU都有自己的私有內存，私都有自己的私有內存，私 有內存只能供自己使用而其它的有內存只能供自己使用而其它的CPU則不能訪問。每個則不能訪問。每個CPU 都有自己獨立的物理地址空間。都有自己獨立的物理地址空間。 多計算機系統(tǒng)中沒有硬件實現(xiàn)的共享內存這一特點也在很大多計算機系統(tǒng)中沒有硬件實現(xiàn)的共享內存這一特點也在很大 程度上影響了其軟件體系結構。多計算機系統(tǒng)中的程度上影響了其軟件體系結構。多計算機系統(tǒng)中的CPU不能不能 通過讀寫共享內存進行通信，在系統(tǒng)中通信是通過使用互連通過讀寫共享內存進行通信，在系統(tǒng)中通信是通過使用互連 網(wǎng)

59、絡傳遞消息來實現(xiàn)的，多計算機系統(tǒng)的編程比多處理機系網(wǎng)絡傳遞消息來實現(xiàn)的，多計算機系統(tǒng)的編程比多處理機系 統(tǒng)的編程要復雜的多。統(tǒng)的編程要復雜的多。 多計算機系統(tǒng)中的每個結點都由一個或者多個多計算機系統(tǒng)中的每個結點都由一個或者多個CPU、RAM、 磁盤以及其它的輸入磁盤以及其它的輸入/輸出設備和通信處理器組成。而且每輸出設備和通信處理器組成。而且每 個結點上都有操作系統(tǒng)，至少是操作系統(tǒng)核心部分。多計算個結點上都有操作系統(tǒng)，至少是操作系統(tǒng)核心部分。多計算 機系統(tǒng)具有良好的可擴展性，與多處理機系統(tǒng)相比可以達到機系統(tǒng)具有良好的可擴展性，與多處理機系統(tǒng)相比可以達到 更大的規(guī)模。更大的規(guī)模。 基于消息傳遞的

60、多計算機系統(tǒng)基于消息傳遞的多計算機系統(tǒng) 基于消息傳遞的多計算機系統(tǒng)基于消息傳遞的多計算機系統(tǒng) 通用多計算機體系結構通用多計算機體系結構 n每個結點都由一個或者多個每個結點都由一個或者多個CPU、RAM、磁盤以及其、磁盤以及其 它的輸入它的輸入/輸出設備和通信處理器組成。輸出設備和通信處理器組成。 n通信處理器通過互連網(wǎng)絡相互連接起來。可以使用多種通信處理器通過互連網(wǎng)絡相互連接起來。可以使用多種 不同的拓撲結構，交換策略和尋徑算法。不同的拓撲結構，交換策略和尋徑算法。 兩種不同的多計算機系統(tǒng)兩種不同的多計算機系統(tǒng) MPP系統(tǒng)系統(tǒng) nMPP系統(tǒng)是由成百上千臺處理機組成的大規(guī)模并行計算系統(tǒng)是由成百上