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

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

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

方

面并行處理機(jī)多處理機(jī)

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

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

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

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

緊耦合和松耦合

機(jī)間互連形式----性能的重要因素

存儲(chǔ)器的組織

緊耦合多處理機(jī)

是通過(guò)共享主存來(lái)實(shí)現(xiàn)處理機(jī)間通訊，通信速率受限于主存的頻率。減少主存沖突，采用模m多體交叉存取；是否帶專用Cache，有兩種各個(gè)處理機(jī)為同構(gòu)型，同一類型、功能相同的多處理機(jī)；

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

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

及存儲(chǔ)器的多處理機(jī)松耦合多處理機(jī)

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

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

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

總線形式

環(huán)形互連形式

交叉開關(guān)形式

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

總線形式

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

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

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

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

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

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

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

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

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

存儲(chǔ)器的組織

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

多Cache的一致性問(wèn)題

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

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

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