第一章 計算機系統(tǒng)結構的概念 山東大學

第七章多處理機多處理機具有兩個以上的處理機，在操作系統(tǒng)控制下，通過共享的主存或輸入/輸出子系統(tǒng)或高速通信網絡進行通信。多任務處理，協(xié)同求解，提高速度；利用冗余，提高可靠性、適應性、可用性。分為：同構型、異構型、分布型

目錄多處理機的概念、問題和硬件結構緊耦合多處理機多Cache的一致性問題多處理機的并行和性能多處理機的操作系統(tǒng)多處理機的發(fā)展多處理機屬于多指令流、多數據流系統(tǒng)多處理機系統(tǒng)由多個獨立的處理機組成，每個處理機都能夠獨立執(zhí)行自己的程序。實現更高一級的作業(yè)、任務之間的并行結構上：要用多個指令部件分別控制，通過機間互聯(lián)網絡實現通信算法上：不限于向量數組系統(tǒng)管理上：依靠軟件手段解決資源分配和管理，任務分配、處理機調度、進程同步和通訊多處理機與并行處理機的主要差別

方

面并行處理機多處理機

結構靈活性針對向量、數組處理而設計的，有專用性，雖然處理單元數多16384個，但設置有限的、固定的機間互連通路實現作業(yè)、任務、程序段的并行，適應算法，結構靈活多變，實現復雜的機間互連，避免爭用共享的硬件資源程序并行性實現操作級并行，并行性存在指令內部并行性還存在于指令外部，表現于多個任務間的并行

并行任務派生通過指令來反映數據間是否并行計算，并由指令直接啟動多個處理單元并行工作需要專門的指令或語句指明程序中各程序段的并發(fā)關系，并控制并發(fā)執(zhí)行進程同步實現指令內部對數據操作的并行實現指令、任務作業(yè)級的并行資源分配和任務調度處理單元數目固定，利用屏蔽手段，改變數目處理機數目不固定，復雜多處理機存在的技術問題

硬件結構上如何解決處理機、存儲器模塊及I/O子系統(tǒng)之間的互連如何最大限度地開發(fā)系統(tǒng)的并行性，實現多處理機各級的全面并行；如何分割任務的大小，任務的粒度大?。蝗绾螀f(xié)調好處理機中各并行執(zhí)行的任務和進程間的同步問題；如何將各個人物分配到一個或多個處理機上，解決好處理機調度、任務調度和資源分配問題，防止死鎖；系統(tǒng)發(fā)生故障，系統(tǒng)如何重新組織，正常工作

多處理機的硬件結構

緊耦合和松耦合

機間互連形式----性能的重要因素

存儲器的組織

緊耦合多處理機

是通過共享主存來實現處理機間通訊，通信速率受限于主存的頻率。減少主存沖突，采用模m多體交叉存取；是否帶專用Cache，有兩種各個處理機為同構型，同一類型、功能相同的多處理機；

處理機之間共享主存儲器，通過高速總線或高速開關連接。主存儲器有多個獨立的存儲模塊每個CPU能夠訪問任意一個存儲器模塊通過映象部件MAP把全局邏輯地址變換成局部物理地址通過互連網絡尋找合適的路徑，并分解訪問存儲器的沖突多個輸入輸出處理機IOP也連接在互連網絡上，I/O設備與CPU共享主存儲器。處理機個數不能太多，幾個到十幾個緊密偶合方式要求有很高通信頻帶。可以采用如下措施：采用高速互連網絡增加存儲器模塊個數，一般n?m，取1～2倍之間。每個存儲器模塊再分成多個小模塊，并采用流水線方式工作。每個CPU都有自己的局部存儲器LM。每個CPU設置一個Cache。MAPMMCPU-MM-IOP

互連網絡緊密耦合多處理機模型CPUMAPCPUMAPCPU…MMMM…IOPIOPIOP…IOP…IOPCPUMAPCacheLMCPU-IOP互聯(lián)網絡CPU-MM互聯(lián)網絡MAPMAPCPUMAPCacheLMCPUMAPCacheLM…IOP……MAPMAP…MAPMAP…帶二維共享存儲器和、局部Cache

及存儲器的多處理機松耦合多處理機

每一臺處理都由容量較大的局部存儲器，減少訪存沖突，不同處理機間或者通過通道互連實現通信，或者通過消息傳送系統(tǒng)（MTS）。

可看成分布系統(tǒng)；松耦合非層次型多處理機層次型總線形式的多處理機LM0IOP0互連網絡通過多輸入輸出輸出口連接的多處理機CPU0LM0IOP0CPU0……LM0IOP0CPU0LMIOP互連網絡通過消息傳送系統(tǒng)連接的松散耦合多處理機CPUCAS模塊０LMIOPCPUCAS模塊n-1處理機之間的連接頻帶比較低通過輸入輸出接口連接,處理機間互為外圍設備進行連接例如，IBM公司的機器，都可以通過通道到通道的連接器CTC把兩個不同計算機系統(tǒng)的IOP連接起來。通過并口或串口把多臺計算機連接起來例如，用串行口加一個MODEL撥號上網，也可以直接連接；多臺計算機之間的連接需要有多個接口。通過Ethernet網絡接口連接多臺計算機

速度達10Mb、100Mb、1Gb，Mynet已經達到1.28Gb和2.56Gb。當通信速度要求更高時，可以通過一個通道和仲裁開關CAS（ChannelandArbiterSwitch）直接在存儲器總線之間建立連接。CAS中有一個高速的通信緩沖存儲器。機間互聯(lián)形式

總線形式

環(huán)形互連形式

交叉開關形式

多端口存儲器形式蠕蟲穿洞尋徑網絡開關樞紐結構形式

總線形式

多個處理機、存儲器模塊和外圍設備通過接口與公用總線相連，采用分時或多路轉接技術傳送。

結構簡單，成本低，增減模塊方便，但對總線的失效敏感。

IBMStretch、UNIVACLarg提高總線的系統(tǒng)效率：采用優(yōu)質高頻同軸電纜，用光纖；采用多總線方式減少沖突概率；總線仲裁算法靜態(tài)優(yōu)先級算法：為每一個連到總線的部件分配一固定的優(yōu)先級固定時間片算法：把總線按固定大小時間片，輪流提供給部件使用適合同步總線，時鐘同步動態(tài)優(yōu)先級算法：讓總線上各部件優(yōu)先級可根據情況按一定規(guī)則動態(tài)地改變先來先服務算法：按接受到訪問總線請求先后順序來響應環(huán)形互連形式

總線形成環(huán)形互連。令牌（Token）點點連接，物理參數容易控制適合于高帶寬的光纖；

P6P7P5P4P0P1P3P2級間采用環(huán)形互連的多處理機交叉開關形式

包含一組縱橫開關陣列。是總線方式的極端?？偩€數=m+I+n,m：存儲器模塊數，n：處理機數，I：I/o設備數，一般：M>=I+N交叉開關陣列復雜例子：美國。C.MMP、S-1PnPnM1M2MmI/O1I/Oi交叉開關形式多端口存儲器形式

如果每個存儲器模塊有多各訪問端口，且將分布在交叉開關矩陣中的控制、轉換和優(yōu)先級仲裁邏輯分別移到相應存儲器模塊的接口中。

I/O1I/O1M1M1M4M3M2P1P2四端口存儲器形式的結構UNIVACCRAY_XMP蠕蟲穿洞尋徑網絡Wormhole。Dally于1986年提出。機間采用小容量緩沖存儲器，實現消息分組尋徑存儲轉發(fā)之用曙光1000多處理機蟲蝕尋徑(wormhole)把包分成更小的片。每個結點的尋徑器中有片緩沖區(qū)。用頭片直接開辟一條從輸入結點到輸出結點的路徑。每個消息中的片以流水方式在網絡中向前“蠕動”。當消息的頭片到達一個結點A的尋徑器后，尋徑器根據頭片的尋徑消息立即做出路由選擇特點每個結點的緩沖器的需求量小，易于用VLSI實現。較低的網絡傳輸延遲。所有的片以流水方式向前傳送，時間并行性。而在存儲轉發(fā)中，消息是整個的從一個結點“跳”向另一個結點，通道的使用時串行的。所以它的傳輸延遲基本上正比于消息在網絡中傳輸的距離。Wormhole與線路開關的網絡傳輸延遲正比于消息包的長度，傳輸距離對它的影響很小（消息包較長時的情況）。通道共享性好、利用率高。對通道的預約和釋放是結合在一起的一個完整的過程：占有一段新的通道后將立即放棄用過的一段舊通道。易于實現Multicast和Broadcast。允許尋徑器復制消息包的片并把它們從多個輸出通道輸出。Wormhole方式中，同一個包中所有的片象不可分離的同伴一樣以流水方式順序的傳送。包可看作是一列火車，由火車頭（頭片）和被牽引的車廂（數據片）組成。線路交換Wormhole存儲轉發(fā)開關樞紐結構形式

把互連結構的開關設置在各個處理機或其接口內部，組成分布式結構。美國加州大學伯克利分校設計的樹形多處理機X-TREE

存儲器的組織

并行存儲器的構成

多Cache的一致性問題

并行存儲器的構成有高位交叉和低位交叉

低位交叉：按物理地址順序輪流地分布在各個存儲模塊中。不連續(xù)，步距為m向量、流水或陣列處理機中采用低位交叉高位交叉：按物理地址順序從模塊0到模塊m-1依次連續(xù)分布。連續(xù)多處理機中采用高位交叉；(n-1)*mimm0(n-1)*m+1im+1m+11n*m-1(i+1)m-12m-1m-1模塊0模塊1模塊m-1模塊內部單元號模塊號log2nlog2mm個模塊的低位交叉編址n-1i102n-1n+in+1nM*n-1(m-1)n+i(m-1)*n+1(m-1)*n模塊0模塊1模塊m-1模塊內部單元號模塊號log2nlog2mm個模塊的高位交叉編址本地存儲器（HomeMemory）：處理機常用到的存儲器模塊；M0M1Mm-1Pp-1Pp-1Pp-1處理機存儲器互連網絡PMIN-本地存儲器的概念§2緊耦合多處理機多Cache的一致性問題多Cache的一致性問題的產生多Cache的一致性問題的解決辦法多Cache的一致性問題

每一個處理機都有自己專用的Cache，但主存中同一個信息塊在多個Cache中都有時，會出現信息不一致情況；寫直達法---保證一個；進程遷移----將一個尚未執(zhí)行完而被掛起的進程調度到另一個空閑的處理機上去執(zhí)行；對于進程遷移的Cache不一致性----禁止進程遷移多Cache的一致性問題的解決辦法解決進程遷移引起的多Cache