第一章 計算機系統(tǒng)結(jié)構(gòu)的概念 山東大學(xué)

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

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

方

面并行處理機多處理機

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

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

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

多處理機的硬件結(jié)構(gòu)

緊耦合和松耦合

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

存儲器的組織

緊耦合多處理機

是通過共享主存來實現(xiàn)處理機間通訊，通信速率受限于主存的頻率。減少主存沖突，采用模m多體交叉存?。皇欠駧Ｓ肅ache，有兩種各個處理機為同構(gòu)型，同一類型、功能相同的多處理機；

處理機之間共享主存儲器，通過高速總線或高速開關(guān)連接。主存儲器有多個獨立的存儲模塊每個CPU能夠訪問任意一個存儲器模塊通過映象部件MAP把全局邏輯地址變換成局部物理地址通過互連網(wǎng)絡(luò)尋找合適的路徑，并分解訪問存儲器的沖突多個輸入輸出處理機IOP也連接在互連網(wǎng)絡(luò)上，I/O設(shè)備與CPU共享主存儲器。處理機個數(shù)不能太多，幾個到十幾個緊密偶合方式要求有很高通信頻帶?？梢圆捎萌缦麓胧翰捎酶咚倩ミB網(wǎng)絡(luò)增加存儲器模塊個數(shù)，一般n?m，取1～2倍之間。每個存儲器模塊再分成多個小模塊，并采用流水線方式工作。每個CPU都有自己的局部存儲器LM。每個CPU設(shè)置一個Cache。MAPMMCPU-MM-IOP

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

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

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

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

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

總線形式

環(huán)形互連形式

交叉開關(guān)形式

多端口存儲器形式蠕蟲穿洞尋徑網(wǎng)絡(luò)開關(guān)樞紐結(jié)構(gòu)形式

總線形式

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

結(jié)構(gòu)簡單，成本低，增減模塊方便，但對總線的失效敏感。

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

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

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

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

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

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

把互連結(jié)構(gòu)的開關(guān)設(shè)置在各個處理機或其接口內(nèi)部，組成分布式結(jié)構(gòu)。美國加州大學(xué)伯克利分校設(shè)計的樹形多處理機X-TREE

存儲器的組織

并行存儲器的構(gòu)成

多Cache的一致性問題

并行存儲器的構(gòu)成有高位交叉和低位交叉

低位交叉：按物理地址順序輪流地分布在各個存儲模塊中。不連續(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模塊內(nèi)部單元號模塊號log2nlog2mm個模塊的低位交叉編址n-1i102n-1n+in+1nM*n-1(m-1)n+i(m-1)*n+1(m-1)*n模塊0模塊1模塊m-1模塊內(nèi)部單元號模塊號log2nlog2mm個模塊的高位交叉編址本地存儲器（HomeMemory）：處理機常用到的存儲器模塊；M0M1Mm-1Pp-1Pp-1Pp-1處理機存儲器互連網(wǎng)絡(luò)PMIN-本地存儲器的概念§2緊耦合多處理機多Cache的一致性問題多Cache的一致性問題的產(chǎn)生多Cache的一致性問題的解決辦法多Cache的一致性問題

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