CA第五章-多處理機(jī)系統(tǒng)

多處理機(jī)系統(tǒng)<<上海大學(xué)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)>>課程組多處理機(jī)系統(tǒng)的定義

P.H.Enslow對(duì)多處理機(jī)作了下列定義：*包含兩個(gè)或兩個(gè)以上功能大致相同的處理器；*所有處理器共享一個(gè)公共內(nèi)存；*所有處理器共享I/O通道、控制器和外圍設(shè)備；*整個(gè)系統(tǒng)由統(tǒng)一的操作系統(tǒng)控制，在處理器和程序之間實(shí)現(xiàn)作業(yè)、任務(wù)、程序段、數(shù)組和數(shù)組元素等各級(jí)的全面并行。

多處理機(jī)的優(yōu)點(diǎn)

很高的性能價(jià)格比

：

單處理機(jī)的性能價(jià)格比隨其規(guī)模的增大而下降

很高的可靠性

：冗余度大、可維護(hù)性、可用性

很高的處理速度：多個(gè)處理器并行運(yùn)算

很好的模塊性：大量重復(fù)設(shè)置，結(jié)構(gòu)靈活性、可擴(kuò)充性、可重構(gòu)性

特性要求--進(jìn)程恢復(fù)能力

多處理機(jī)系統(tǒng)使用的處理機(jī)結(jié)構(gòu)應(yīng)能反映進(jìn)程和處理機(jī)是兩個(gè)不同的實(shí)體。如果某處理機(jī)發(fā)生故障，另一臺(tái)處理機(jī)應(yīng)能檢索到被中斷的進(jìn)程狀態(tài)，使被中斷的進(jìn)程能繼續(xù)運(yùn)行。沒有這個(gè)功能，系統(tǒng)的可靠性大大下降。大多數(shù)處理機(jī)把當(dāng)前正在運(yùn)行進(jìn)程狀態(tài)保存在內(nèi)部寄存器中，如何使其他處理器在必要時(shí)能訪問到進(jìn)程狀態(tài)，是恢復(fù)進(jìn)程的關(guān)鍵之一。在不太損失速度的前提下，把通用寄存器與處理機(jī)本身分開是可能的，在系統(tǒng)內(nèi)設(shè)置所有處理機(jī)共享的寄存器堆可以實(shí)現(xiàn)上述功能。

特性要求--有效的現(xiàn)場(chǎng)切換

現(xiàn)場(chǎng)切換操作是把當(dāng)前進(jìn)程狀態(tài)保存起來，然后通過恢復(fù)新進(jìn)程的狀態(tài)切換到被選中的準(zhǔn)備好運(yùn)行的進(jìn)程。切換操作可以在指令系統(tǒng)中設(shè)置一條專門指令來完成。該指令執(zhí)行的結(jié)果是將當(dāng)前進(jìn)程狀態(tài)或現(xiàn)場(chǎng)內(nèi)容保存起來，然后到主存儲(chǔ)器的緩沖區(qū)取另一個(gè)進(jìn)程狀態(tài)，該緩沖區(qū)稱為交換包。特性要求--大的物理地址空間和虛擬地址空間

多處理機(jī)系統(tǒng)內(nèi)的處理機(jī)必須能支持大的物理地址空間（即直接尋址空間要大），這是因?yàn)檫M(jìn)程需要訪問大量數(shù)據(jù)。例如，Pentium地址線32根，直接尋址空間可達(dá)4GB，能滿足需求。有了大的物理地址空間，還需要大的虛擬地址空間，把虛擬地址空間分段，便于模塊共享以及地址界限的檢查。

特性要求--高效率的同步原語(yǔ)

處理機(jī)設(shè)計(jì)時(shí)必須能提供作為同步原語(yǔ)基礎(chǔ)的某種不可再分的操作。這些同步原語(yǔ)需要有互斥機(jī)構(gòu)支持。當(dāng)兩個(gè)以上的進(jìn)程并發(fā)地運(yùn)行或相互交換數(shù)據(jù)時(shí)，需要互斥?；コ鈾C(jī)構(gòu)包含某種形式的讀—修改—寫存儲(chǔ)周期和排隊(duì)。信號(hào)燈（semaphore）是互斥機(jī)構(gòu)的一種。每個(gè)信號(hào)燈有其隊(duì)列，隊(duì)列中的項(xiàng)是被掛起來的進(jìn)程。信號(hào)燈操作是不可分操作，利用讀—修改—寫存儲(chǔ)周期，測(cè)試和修改信號(hào)燈。隊(duì)列操作也應(yīng)是不可分的。

特性要求--處理機(jī)之間有高效率的通信機(jī)構(gòu)

通信機(jī)構(gòu)可用硬件實(shí)現(xiàn)。它有助于實(shí)現(xiàn)處理機(jī)之間的同步。在非對(duì)稱多處理機(jī)系統(tǒng)中，不同的處理機(jī)之間經(jīng)常需要交換服務(wù)請(qǐng)求，硬件通信機(jī)構(gòu)作用更加明顯。在處理機(jī)發(fā)生故障時(shí)，通過該機(jī)構(gòu)發(fā)信號(hào)給其他正在運(yùn)行的處理機(jī)，并啟動(dòng)診斷過程或糾錯(cuò)過程。在緊密耦合的多處理機(jī)系統(tǒng)內(nèi)有共享存儲(chǔ)器，采用軟件方法實(shí)現(xiàn)多處理機(jī)之間的通信是可能的。每個(gè)處理機(jī)必須周期地檢查位于共享存儲(chǔ)器內(nèi)的“信箱”（緩沖區(qū)），檢查是否有信息給它。

特性要求--指令系統(tǒng)

處理機(jī)的指令系統(tǒng)應(yīng)能支持實(shí)現(xiàn)具有過程級(jí)并發(fā)功能的高級(jí)語(yǔ)言，為有效的處理數(shù)據(jù)結(jié)構(gòu)提供充分條件。指令系統(tǒng)內(nèi)應(yīng)有過程連接、循環(huán)結(jié)構(gòu)、參數(shù)處理、多維下標(biāo)計(jì)算和地址界限檢查等指令。還需包括產(chǎn)生和結(jié)束程序內(nèi)部并行執(zhí)行通路的指令。設(shè)置特權(quán)指令。

Flynn分類法MichealFlynn(1972)提出指令流、數(shù)據(jù)流和多倍性概念，把不同的計(jì)算機(jī)分為四大類（下圖）：SISD（Single-InstructionSingle-Data,單處理機(jī)結(jié)構(gòu)）SIMD（Single-InstructionMulti-Data,帶分布存儲(chǔ)器）MISD（Multi-InstructionSingle-Data,搏動(dòng)式陣列）MIMD（Multi-InstructionMulti-Data,帶共享存儲(chǔ)器）并行處理機(jī)

在單機(jī)系統(tǒng)里主要是采用時(shí)間重疊技術(shù)。把一件工作按功能分割為若干相互聯(lián)系的部分，把每一部分指定給專門的部件完成，然后按時(shí)間重疊原則把各部分執(zhí)行過程在時(shí)間上重疊起來，使所有部件依次分工完成一組同樣的工作。

并行處理機(jī)主要是通過資源重復(fù)技術(shù)來實(shí)現(xiàn)并行處理的。它屬于單指令流多數(shù)據(jù)流（SIMD）計(jì)算機(jī)一類。

1.組成通常由1個(gè)控制器(CU)，多個(gè)處理器(PE)，m個(gè)存儲(chǔ)模塊(M)及1個(gè)互連網(wǎng)絡(luò)(ICN)組成。一、基本結(jié)構(gòu)并行處理機(jī)工作原理根據(jù)存儲(chǔ)模塊組成方式可有分布式和集中式兩種。ICN分布存集中式P0M0Pn-1Mn-1PE0PEn-1CUICNCUM0M1Mm-1······PE0PE1PEn-1···基本結(jié)構(gòu)的共同特點(diǎn)并行處理機(jī)的兩種基本結(jié)構(gòu)的共同特點(diǎn)：重復(fù)設(shè)置許多個(gè)同樣的處理單元PE（ProcessElement）；由ICN(InterConnectionNetwork)按照一定的方式相互連接；在統(tǒng)一的控制部件CU（ControlUnit）作用下；各PE對(duì)分配來的數(shù)據(jù)并行地完成同一條指令所規(guī)定的操作。

并行處理的特點(diǎn)

資源重復(fù)。它機(jī)利用眾多的處理單元對(duì)向量所包含的各個(gè)分量同時(shí)進(jìn)行運(yùn)算，獲得很高處理速度。

連接模式。它的處理單元間是通過ICN來通信的。不同的連接模式確定了它的不同結(jié)構(gòu)。

專用性。它直接與一定的算法相聯(lián)系，其效率取決于在多大程度上把計(jì)算問題歸結(jié)為向量數(shù)組處理。

復(fù)合性。整個(gè)系統(tǒng)是由三部分復(fù)合起來的一個(gè)多機(jī)系統(tǒng)，即多個(gè)處理單元組成陣列并行地處理向量；功能極強(qiáng)的控制部件實(shí)際上是一臺(tái)標(biāo)量處理機(jī)；系統(tǒng)的管理功能則由高性能單處理機(jī)擔(dān)負(fù)。

2.分布式結(jié)構(gòu)存儲(chǔ)模塊由每個(gè)PE自帶。3.集中式結(jié)構(gòu)各個(gè)PE共享m個(gè)存儲(chǔ)模塊。

特點(diǎn)：ICN：是單向的，PE→PE。

工作流程：特點(diǎn)：ICN：是雙向的，PE←→M。

工作流程：比較：分布式每個(gè)PE有局部存儲(chǔ)器，集中式共享存儲(chǔ)器。ICN的作用不同：分布式PE→PE，集中式PE←→M。

互連網(wǎng)絡(luò)基本概念并行計(jì)算機(jī)互連網(wǎng)絡(luò)基本功能

互連網(wǎng)絡(luò)ICN主要完成結(jié)點(diǎn)與結(jié)點(diǎn)間的連接，連接和控制方式不同，連接效果不同。并行處理機(jī)互聯(lián)網(wǎng)絡(luò)ICN是實(shí)現(xiàn)并行處理機(jī)中各處理單元之間或處理單元與存儲(chǔ)器之間的信息交換。互聯(lián)網(wǎng)絡(luò)的不同拓?fù)浣Y(jié)構(gòu)直接決定了并行處理機(jī)的結(jié)構(gòu)。

結(jié)構(gòu)特征(1)通信方式同步、異步(3)交換方式線路交換、分組交換(4)拓?fù)浣Y(jié)構(gòu)(2)控制策略集中、分散設(shè)計(jì)思路根據(jù)應(yīng)用需要（互連網(wǎng)絡(luò)屬性），選擇合理的特征方式，考慮互連網(wǎng)絡(luò)的性能因素，綜合加以合理組合。

目標(biāo)：低成本、高靈活性、高連接度、低延時(shí)、適合VLSI?；ミB網(wǎng)絡(luò)表示入端的編碼：x=（bn-1…b0)n=log2N

互連函數(shù)為基于bn-1…b0的排列、組合、移位、取反等操作的結(jié)果。出端的編碼：f(x)=(bn-1…b0)或其他形式?；ミB網(wǎng)絡(luò)的連接特征一般用互連函數(shù)表示。一個(gè)互連網(wǎng)絡(luò)的連接特征可對(duì)應(yīng)多個(gè)互連函數(shù)。1.立方體單級(jí)網(wǎng)絡(luò)（交換互連網(wǎng)絡(luò)）單級(jí)互連網(wǎng)絡(luò)只能實(shí)現(xiàn)有限的幾種連接。單級(jí)互連網(wǎng)絡(luò)出端編碼與連接的入端結(jié)點(diǎn)的編碼有一位相反。zyx010011110111000001101100

互連函數(shù)：Cube0=(b2b1b0)；Cube1=(b2b1b0)；Cube2=(b2b1b0)。

互連特性：交換功能--互連函數(shù)可逆；互連函數(shù)個(gè)數(shù)=log28=3；最大連接度=log28=3；結(jié)點(diǎn)最大間距=log28=3。出端編碼與連接的入端結(jié)點(diǎn)的編碼有一位相反。

互連函數(shù)：Cube0=(b2b1b0)（0，1）（2，3）（4，5）（6，7）Cube1=(b2b1b0)（0，2）（1，3）（4，6）（5，7）Cube2=(b2b1b0)（0，4）（1，5）（2，6）（3，7）注意：立方體坐標(biāo)編號(hào)不能標(biāo)錯(cuò)。000001000001010011010011100101100101110111110111000001000001010011010011100101100101110111110111000001000001010011010011100101100101110111110111Cube0Cube1Cube2

連接圖：

擴(kuò)展成超立方體：有n=log2N個(gè)互連函數(shù)；Cubei=(bn-1…bi…b0)；最大連接度=log2N；結(jié)點(diǎn)最大間距=log2N。

應(yīng)用：幾種互連函數(shù)反復(fù)調(diào)用，任意結(jié)點(diǎn)間可連接。2.PM2I單級(jí)網(wǎng)絡(luò)（循環(huán)移數(shù)網(wǎng)絡(luò)）出端編碼與連接的入端結(jié)點(diǎn)編碼相差2i。

互連函數(shù)：PM2I+i(j)=(j+2i)modN；n=log2N,0≤i≤n-1,PM2I-i(j)=(j-2i)modN；0≤j≤N-1共有2n個(gè)互連函數(shù)(2n-1種不同)。

連接圖：±0：順環(huán)圓周連接；±1：順環(huán)內(nèi)接n/2邊形連接；01234567±2：順環(huán)內(nèi)接n/4邊形連接；±(n-1)：順環(huán)內(nèi)直徑連接。設(shè)n=8，則各互聯(lián)循環(huán)為PM2+0：（01234567）PM2-0：（76543210）PM2+1：（0246）（1357）PM2-1：（6420）（7531）PM2±2：（04）（15）（26）（37）

互連特性：

最大連接度2n-1；結(jié)點(diǎn)最大間距n/2=log2N/2≤log2N/2；互連函數(shù)個(gè)數(shù)2n。

應(yīng)用：幾種互連函數(shù)混合，任意結(jié)點(diǎn)間可連接。

實(shí)例：閉合螺旋結(jié)構(gòu)為PM2I+0及PM2I±n/2互連函數(shù)。3.混洗交換單級(jí)網(wǎng)絡(luò)全混洗（二混洗）：000000001001010010011011100100101101110110111111三混洗：000000010010001101000101011001111000100110101011000000010010001101000101011001111000100110101011

全混洗互連函數(shù)：Shuffle(bn-1bn-2…b1b0)=(bn-2…b1b0bn-1)；全“0”或全“1”結(jié)點(diǎn)無法與其他結(jié)點(diǎn)連接，必須輔以交換互連函數(shù)，方可實(shí)現(xiàn)任意結(jié)點(diǎn)間連接。最簡(jiǎn)單的交換互連函數(shù)為Cube0，因此混洗交換網(wǎng)絡(luò)由全混洗和交換網(wǎng)絡(luò)組合而成。

交換互連函數(shù)：Exchange(bn-1bn-2…b1b0)=(bn-1bn-2…b1b0)；混洗交換互連函數(shù)：Exchange[Shuffle(bn-1bn-2…b1b0)]=(bn-2…b1b0bn-1)；

連接圖：012345674.總結(jié)任一單級(jí)互連網(wǎng)絡(luò)均可表示成N入N出的過程。(1)單級(jí)互連網(wǎng)絡(luò)特性任一單級(jí)互連網(wǎng)絡(luò)可實(shí)現(xiàn)部分結(jié)點(diǎn)(一對(duì)或幾對(duì))間的連接，不能實(shí)現(xiàn)任意多對(duì)結(jié)點(diǎn)間的同時(shí)連接。

單級(jí)互連網(wǎng)絡(luò)含義：某些連接方法或拓?fù)浣Y(jié)構(gòu)。(2)單級(jí)互連網(wǎng)絡(luò)應(yīng)用利用單級(jí)互連網(wǎng)絡(luò)的特性作為實(shí)際IN的拓?fù)浣Y(jié)構(gòu)；通過交換開關(guān)作為IN的可變因素；通過交換開關(guān)多次控制實(shí)現(xiàn)IN的結(jié)點(diǎn)間任意互連。

陣列機(jī)結(jié)構(gòu)

陣列機(jī)系統(tǒng)是并行處理機(jī)最常見的結(jié)構(gòu)形式，它是由大量的處理機(jī)按一定規(guī)則的幾何形式構(gòu)成陣列形式。最早陣列機(jī)是ILLIACⅣ，它是由4個(gè)處理機(jī)陣列構(gòu)成，每個(gè)陣列里由64個(gè)處理單元和1個(gè)控制部件組成。

陣列機(jī)結(jié)構(gòu)(cont.)ILLIACⅣ陣列機(jī)結(jié)構(gòu)（如圖5-9所示）。64個(gè)PE按矩形排列成8×8方陣，PE只與自己四邊相鄰的PE相連。任意二個(gè)不相鄰PE的通信可以通過選擇最短路徑的算法，由軟件來實(shí)現(xiàn)。每個(gè)PE包括處理機(jī)外，還有自身的附屬存儲(chǔ)器PEM和存儲(chǔ)器邏輯部件MLU。同時(shí)還有包含I/O在內(nèi)的特殊總線結(jié)構(gòu)互聯(lián)。像這種陣列機(jī)結(jié)構(gòu)又稱閉合螺線結(jié)構(gòu)，也是陣列機(jī)系統(tǒng)結(jié)構(gòu)中最常見的一種結(jié)構(gòu)形式。

陣列機(jī)結(jié)構(gòu)(cont.)陣列機(jī)的處理屬于SIMD形式（單指令流多數(shù)據(jù)流），它最適合作向量數(shù)組運(yùn)算。每個(gè)處理單元相當(dāng)于一個(gè)向量數(shù)組元素的運(yùn)算，包括定點(diǎn)和浮點(diǎn)的多種運(yùn)算操作。對(duì)于是陣列機(jī)處理單元個(gè)數(shù)的倍數(shù)的向量數(shù)組運(yùn)算尤為合適。如PE=64，則16，32，64，128，256，512???陣列向量數(shù)組就很方便地使陣列機(jī)發(fā)揮最佳效能。陣列機(jī)結(jié)構(gòu)(cont.)陣列機(jī)中PE之間的互聯(lián)通信是由互聯(lián)寄存器來實(shí)現(xiàn)的。當(dāng)PE執(zhí)行互聯(lián)指令時(shí)，由本PE的互聯(lián)寄存器與相鄰PE互聯(lián)寄存器進(jìn)行信息交換。陣列機(jī)結(jié)構(gòu)(cont.)陣列機(jī)的操作分公共操作和本地操作。公共操作是指陣列機(jī)中的所有PE同時(shí)執(zhí)行的操作，它一般由邏輯控制器來調(diào)度。本地操作是每個(gè)PE自己的操作，它由PE的指令譯碼、執(zhí)行。像指令操作那樣，陣列機(jī)的存儲(chǔ)器有雙重變址機(jī)構(gòu)，除了邏輯控制器的公共變址外，還有每個(gè)PE自己的單獨(dú)變址。這樣既節(jié)省了公共數(shù)據(jù)和指令所占的存儲(chǔ)空間，又增加各PE對(duì)存儲(chǔ)器數(shù)據(jù)分配的靈活性。陣列機(jī)結(jié)構(gòu)(cont.)一般，每個(gè)PE都配有狀態(tài)寄存器，它標(biāo)志了目前本PE處于活動(dòng)狀態(tài)還是處于屏蔽狀態(tài)；運(yùn)算結(jié)果是否有錯(cuò)；矩陣邊緣處于何種連接等等各種狀態(tài)信息。

高性能計(jì)算機(jī)分三大類PVP向量型超級(jí)計(jì)算機(jī)，如國(guó)防科技大學(xué)研制的銀河I（1億次/秒）、銀河II（10億次/秒）。MPP大規(guī)模并行處理超級(jí)計(jì)算機(jī)，如國(guó)防科技大學(xué)研制的銀河III（130億次/秒）、中國(guó)科學(xué)院計(jì)算機(jī)技術(shù)研究所研制的曙光1000（25億次/秒）、中國(guó)江南計(jì)算機(jī)技術(shù)研究所研制的神威I（3840億次/秒）。Cluster集群計(jì)算機(jī)，中國(guó)科學(xué)院計(jì)算機(jī)技術(shù)研究所研制的曙光2000-II（1100億次/秒）、

曙光3000（4030億次/秒）、清華大學(xué)研制的THNPSC-1（320億次/秒）、,上海大學(xué)研制的自強(qiáng)2000（4500億次/秒）。大規(guī)模并行處理機(jī)(MPP)1979年，美國(guó)NASA-Goddard中心與Goodyear宇航公司合作研制一臺(tái)用于處理遙感衛(wèi)星圖片的大規(guī)模SIMD陣列機(jī)獲得成功。由于這臺(tái)機(jī)器用了128*128=16384個(gè)可并行工作的微處理機(jī)，因此被定名為大規(guī)模并行處理機(jī)MPP（MassivelyParallelProcessor）。MPP可對(duì)變長(zhǎng)的操作數(shù)按位片進(jìn)行算術(shù)運(yùn)算。MPP有一個(gè)微程序控制器，能夠十分靈活地定義向量、標(biāo)量和I/O操作的指令系統(tǒng)，整個(gè)MPP系統(tǒng)均用微處理器芯片和SRAM芯片組成。

大規(guī)模并行處理機(jī)(cont.)陣列部件ARU（ARrayUnit）由128*128個(gè)PE構(gòu)成一個(gè)二維陣列，以SIMD方式工作。每個(gè)PE有一個(gè)1027位SRAM，有奇偶校驗(yàn)功能每個(gè)PE是位片式微處理機(jī)，與四周近鄰相連。程序員可在平面、水平圓柱、垂直圓柱、開螺線、閉螺線等五種陣列拓?fù)渲腥芜x一種，增加了陣列機(jī)結(jié)構(gòu)的靈活性。

大規(guī)模并行處理機(jī)(cont.)在陣列中增加了4列冗余PE，使陣列的物理結(jié)構(gòu)為132列*128行。陣列硬件出現(xiàn)故障時(shí)可旁路掉故障列方法，使陣列邏輯結(jié)構(gòu)仍為128*128。每個(gè)PE內(nèi)有一個(gè)串行加法器及用一個(gè)移位寄存器實(shí)現(xiàn)位串式加法。PE陣列的時(shí)鐘周期為100ns。陣列控制器ACU是微程序控制器，對(duì)PE陣列處理進(jìn)行管理，完成標(biāo)量運(yùn)算以及控制數(shù)據(jù)在PE陣列上移位。

大規(guī)模并行處理機(jī)(cont.)程序和數(shù)據(jù)管理部件PDMU（ProgramandDataManagementUnit）是一臺(tái)后端小型計(jì)算機(jī)，其作用是管理陣列中的數(shù)據(jù)流，將程序裝入控制器，進(jìn)行系統(tǒng)的測(cè)試和診斷并提供程序開發(fā)手段等。MPP系統(tǒng)運(yùn)行方式有兩種，獨(dú)立方式由用戶在終端予以操作控制；在線方式由外接計(jì)算機(jī)予以控制。MPP與外接計(jì)算機(jī)之間的數(shù)據(jù)傳輸速率為6MB/s，按高速數(shù)據(jù)方式運(yùn)行時(shí)，數(shù)據(jù)通過128位外部接口傳輸，其速率可達(dá)320MB/s。

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

常用的松散耦合和緊密耦合這兩種形式

松散耦合多處理機(jī)結(jié)構(gòu)：互聯(lián)常用通道或通信線路來實(shí)現(xiàn)，它們連接的頻帶較低。緊密耦合多處理機(jī)結(jié)構(gòu)：通常是高速總線或高速開關(guān)實(shí)現(xiàn)機(jī)間互聯(lián)，以共享存儲(chǔ)器。

多處理機(jī)的基本結(jié)構(gòu)通道連接的多處理機(jī)結(jié)構(gòu)：

每臺(tái)計(jì)算機(jī)是獨(dú)立的，它們之間通過通道適配器連接。在進(jìn)行通信時(shí)，發(fā)送的計(jì)算機(jī)可以把接受的計(jì)算機(jī)認(rèn)為是自己的一個(gè)I/O設(shè)備，從而能完成兩個(gè)主存儲(chǔ)器之間的數(shù)據(jù)傳送。

多處理機(jī)的基本結(jié)構(gòu)(cont.)信息傳輸系統(tǒng)連接的多處理機(jī)結(jié)構(gòu)：計(jì)算機(jī)模塊通過一個(gè)信息傳輸系統(tǒng)連接起來。信息傳輸系統(tǒng)是耦合程度較低的，常用簡(jiǎn)單的分時(shí)總線及環(huán)形、星形等拓?fù)浣Y(jié)構(gòu)的系統(tǒng)。每個(gè)計(jì)算機(jī)模塊可以是獨(dú)立的計(jì)算機(jī)，它有處理單元、存儲(chǔ)器、I/O部件。而模塊與信息傳輸系統(tǒng)則通過通道仲裁開關(guān)相連。通道仲裁開關(guān)的作用除使要通信的計(jì)算機(jī)模塊與被通信的計(jì)算機(jī)模塊在信息傳輸系統(tǒng)里連接起來外，還起到多個(gè)模塊同時(shí)申請(qǐng)信息傳輸系統(tǒng)時(shí)，決定本模塊是提出申請(qǐng)還是延緩提出申請(qǐng)，故稱有仲裁作用。

多處理機(jī)的基本結(jié)構(gòu)(cont.)緊密耦合多處理機(jī)結(jié)構(gòu)是真正的MPP：多個(gè)處理器通過互聯(lián)網(wǎng)絡(luò)（它是由高速開關(guān)來組成的）共享集中的主存儲(chǔ)器（它由若干個(gè)存儲(chǔ)模塊組成）和多個(gè)輸入輸出設(shè)備。當(dāng)某個(gè)處理機(jī)要訪問主存儲(chǔ)器，只需通過它的存儲(chǔ)映象部件（MAP），就可以把全局的邏輯地址變換成局部的物理地址（即某一存儲(chǔ)模塊內(nèi)的物理地址）?；ヂ?lián)網(wǎng)絡(luò)不僅要提供高速的傳輸通路，而且具有選擇有效路徑、仲裁訪問沖突等功能。對(duì)于輸入輸出設(shè)備的訪問也與訪問存儲(chǔ)器一樣，只是它們的界面通過輸入輸出處理機(jī)（IOP）來進(jìn)行。

多處理機(jī)的互聯(lián)網(wǎng)絡(luò)

多處理機(jī)的主要特點(diǎn)是各臺(tái)處理機(jī)共享一組存儲(chǔ)器和I/O設(shè)備。這種共享功能是通過兩個(gè)互聯(lián)網(wǎng)絡(luò)實(shí)現(xiàn)的：一個(gè)是處理機(jī)和存儲(chǔ)器模塊之間的互聯(lián)網(wǎng)絡(luò)；另一個(gè)是處理機(jī)和I/O子系統(tǒng)（I/O接口和I/O設(shè)備）之間的互聯(lián)網(wǎng)絡(luò)?；ヂ?lián)網(wǎng)絡(luò)可以采用不同的物理形式，一般可有四種基本結(jié)構(gòu)。

1.總線結(jié)構(gòu)

多處理機(jī)結(jié)構(gòu)最簡(jiǎn)單互聯(lián)系統(tǒng)是把所有功能模塊（或部件）連接到一條公共通信通路上，如圖5-16所示。公共通信通路也稱為時(shí)分或公共總線。這種總線結(jié)構(gòu)的特點(diǎn)是簡(jiǎn)單、容易實(shí)現(xiàn)，也容易擴(kuò)展（重構(gòu)）?？偩€是一個(gè)無源部件，通信完全由發(fā)送和接收的總線接口控制。由于總線是共享資源，所以必須有總線請(qǐng)求和仲裁的機(jī)構(gòu)，以避免發(fā)生總線沖突。

1.總線結(jié)構(gòu)(cont.)總線仲裁方法有靜態(tài)的或動(dòng)態(tài)的優(yōu)先級(jí)方法、先進(jìn)先出（FIFO）隊(duì)列方法、串行優(yōu)先鏈方法和總線控制器（或仲裁器）方法。當(dāng)一個(gè)處理機(jī)要占用總線時(shí)，首先需測(cè)試總線狀態(tài)是否“忙”（busy），若是忙，則等待，等到空閑時(shí)（即不“忙”），發(fā)出總線請(qǐng)求信號(hào)，經(jīng)仲裁后，等到總線響應(yīng)信號(hào)，才可以占用總線，與目的部件進(jìn)行通信。在一個(gè)處理機(jī)占用總線進(jìn)行通信過程中，哪怕比其優(yōu)先級(jí)高的處理機(jī)需占用總線，也不能終止（中斷）原來已在進(jìn)行中的通信過程。

1.總線結(jié)構(gòu)(cont.)單總線結(jié)構(gòu)簡(jiǎn)易而可靠。但總線接口線路出現(xiàn)任何一個(gè)故障會(huì)造成系統(tǒng)癱瘓。

為了提高總線通信效率，設(shè)置在同一時(shí)間可進(jìn)行多條總線通信，但增加了系統(tǒng)的復(fù)雜性。影響總線性能的因素有：總線上主控設(shè)備（即能掌握、占用總線的部件）數(shù)量、總線仲裁算法、控制集中程度、數(shù)據(jù)寬度、數(shù)據(jù)傳輸同步和錯(cuò)誤檢測(cè)等。

1.總線結(jié)構(gòu)(cont.)總線仲裁算法：靜態(tài)優(yōu)先級(jí)算法：給每一個(gè)設(shè)備一個(gè)唯一的優(yōu)先級(jí)。

固定時(shí)間片算法：把帶寬分成固定長(zhǎng)度的時(shí)間片，按循環(huán)方式順序分配給每個(gè)設(shè)備。

動(dòng)態(tài)優(yōu)先級(jí)算法

：優(yōu)先級(jí)予以動(dòng)態(tài)調(diào)整，使每個(gè)設(shè)備均有機(jī)會(huì)占用總線?！敖谧钌偈褂肔RU”算法和旋轉(zhuǎn)菊花鏈RDC算法。

先來先服務(wù)算法

：按照接受到的請(qǐng)求先后順序予以處理。

總線形式

（時(shí)間分配）

最常見PE、PEM、I/O通道均連在總線上，采用分時(shí)或多路轉(zhuǎn)換技術(shù)實(shí)現(xiàn)數(shù)據(jù)傳遞，是最簡(jiǎn)單的連接方式?？偩€仲裁算法：靜態(tài)優(yōu)先級(jí)算法、平等算法、動(dòng)態(tài)優(yōu)先級(jí)算法、先來先服務(wù)算法等。對(duì)外設(shè)一般采用優(yōu)先級(jí)算法；對(duì)PE采用均等算法。實(shí)現(xiàn)方法：集中式：由總線控制器控制；分布式：中機(jī)構(gòu)分散到各PE中。提高總線效率方法：改善傳輸介質(zhì)和增加總線數(shù)量總線互連方式不適宜連接過多的處理機(jī)。2.交叉開關(guān)

當(dāng)不斷增加總線數(shù)目，使每個(gè)存儲(chǔ)器模塊有它自己?jiǎn)为?dú)可用的通路形成的互聯(lián)網(wǎng)絡(luò)稱為無阻塞交叉開關(guān)。它的特點(diǎn)是開關(guān)和功能部件的接口非常簡(jiǎn)單，而且支持所有存儲(chǔ)器模塊同時(shí)通信。每個(gè)交叉點(diǎn)不僅能切換并行傳播，而且必須能解決在同一存儲(chǔ)器周期內(nèi)訪問同一個(gè)存儲(chǔ)器模塊的多個(gè)請(qǐng)求之間的沖突。通常用預(yù)設(shè)的優(yōu)先級(jí)來處理沖突。交叉開關(guān)形式

（空間分配）是總線形式的極端，總線數(shù)=PE數(shù)+PEM數(shù)+I/O通道數(shù)，是一種全相聯(lián)形式，控制、仲裁、轉(zhuǎn)換機(jī)構(gòu)均在開關(guān)中。

改進(jìn)：用一系列較小開關(guān)串聯(lián)或并聯(lián)，形成多級(jí)交叉開關(guān)，減少其復(fù)雜性。交叉開關(guān)方式不適宜連接過多的處理機(jī)。3.多端口存儲(chǔ)器

如果把分布在交叉開關(guān)矩陣網(wǎng)絡(luò)上的控制、轉(zhuǎn)接、優(yōu)先級(jí)仲裁等邏輯功能轉(zhuǎn)移到存儲(chǔ)器模塊的接口上，就形成了多端口存儲(chǔ)器系統(tǒng)，如圖5-25所示。這種系統(tǒng)既適合單處理機(jī)，也適合于多處理機(jī)。

將控制、仲裁、轉(zhuǎn)換機(jī)構(gòu)移到存儲(chǔ)器中。每個(gè)端口與一個(gè)PE或I/O通道相連。多端口存儲(chǔ)器形式不適宜連接過多的處理機(jī)。3.多端口存儲(chǔ)器(cont.)對(duì)于訪問存儲(chǔ)器的沖突，常用的解決方法是每個(gè)存儲(chǔ)器端口分配一個(gè)永久優(yōu)先級(jí)，而各個(gè)主控模塊相對(duì)于某個(gè)存儲(chǔ)器模塊有一個(gè)優(yōu)先級(jí)別序列。例如對(duì)于M0而言，其能接收主控模塊的訪問優(yōu)先次序?yàn)镻0、P1、I/O0、I/O1；對(duì)于M1而言，則為P0、P1、I/O1、I/O0；對(duì)于M3而言，則為P1、P0、I/O1、I/O0；對(duì)于M3而言，則為P1、P0、I/O1、I/O0。

4.多級(jí)互連網(wǎng)絡(luò)形式是介于總線(N)與交叉開關(guān)(N2)中間的一種(Nlog2N)。多級(jí)互連網(wǎng)絡(luò)適宜于PE數(shù)較多的系統(tǒng)。a×b交叉開關(guān)a入b出，輸入基于a編碼，輸出基于b編碼。入端→出端受阻后，重新申請(qǐng)，性能受建立時(shí)間限制；設(shè)置緩沖器性能有所改善，適合于包交換網(wǎng)絡(luò)。an×bn互連網(wǎng)絡(luò)交叉開關(guān)為a×b開關(guān)，由n級(jí)構(gòu)成。

比較：交叉開關(guān)時(shí)結(jié)點(diǎn)數(shù)為an×bn，多級(jí)互連網(wǎng)絡(luò)時(shí)結(jié)點(diǎn)數(shù)為a×b×n2，明顯降低了復(fù)雜性。多處理機(jī)系統(tǒng)結(jié)構(gòu)并行處理機(jī)屬SIMD結(jié)構(gòu)，較適合向量處理；一、多處理機(jī)與并行處理機(jī)區(qū)別多處理機(jī)屬M(fèi)IMD結(jié)構(gòu)，可進(jìn)行更高層次的并行處理。1.結(jié)構(gòu)與通用性

SIMD：?jiǎn)沃噶盍飨到y(tǒng)，并行操作相同，一個(gè)CU，控制、數(shù)據(jù)通訊簡(jiǎn)單，通用性較差；

MIMD：多指令流系統(tǒng)，并行操作不同，多個(gè)CU，控制、數(shù)據(jù)通訊復(fù)雜，通用性較強(qiáng)。2.程序并行性

SIMD：操作級(jí)并行（數(shù)據(jù)并行），

識(shí)別：隱式識(shí)別和向量指令，

支持：編譯程序和硬件；

MIMD：任務(wù)級(jí)并行（數(shù)據(jù)、功能并行），

識(shí)別：顯式指令、編譯程序、OS和硬件等，

支持：專用指令，OS對(duì)任務(wù)的分派和調(diào)度。3.任務(wù)派生

SIMD：向量指令表示及控制，隱式并行、效率低；

MIMD：專用指令表示及控制，顯式并行、效率高。三、多處理機(jī)結(jié)構(gòu)1.緊耦合系統(tǒng)(TCS)

特點(diǎn)：通過共享主存實(shí)現(xiàn)機(jī)間通訊。PPINPIOIND1PMpPMINM1······I/O通道···PM--局存CM--高速緩存P--處理器D--外部設(shè)備···PM1DDMM

互連網(wǎng)絡(luò)：實(shí)現(xiàn)PE←→PEM、PE←→I/O通道、PE←→中斷信號(hào)間的連接。2.松耦合系統(tǒng)(LCS)消息傳送系統(tǒng)MTSPMI/ONI模塊1NI--結(jié)點(diǎn)機(jī)接口·

·

·計(jì)算機(jī)模塊(結(jié)點(diǎn)機(jī))PMI/ONI模塊N

特點(diǎn)：通過消息傳送系統(tǒng)實(shí)現(xiàn)機(jī)間通訊；每個(gè)模塊是一個(gè)獨(dú)立的處理機(jī)，整個(gè)系統(tǒng)可看成是一個(gè)分布系統(tǒng)。

互連網(wǎng)絡(luò)：MTS有總線、環(huán)形、多級(jí)網(wǎng)絡(luò)等種類；

結(jié)構(gòu)：有層次和非層次兩種結(jié)構(gòu)。多處理機(jī)系統(tǒng)的存儲(chǔ)器結(jié)構(gòu)

在多處理機(jī)系統(tǒng)中，為了減少訪存沖突，主存采用并行存儲(chǔ)器結(jié)構(gòu)。多個(gè)存儲(chǔ)模塊可采用低位交叉編址技術(shù)，也可采用高位交叉編址技術(shù)。能為某處理機(jī)進(jìn)程放置大多數(shù)頁(yè)面的存儲(chǔ)器模塊稱為該處理機(jī)宿主存儲(chǔ)器，圖5-31所示。如果該處理器的現(xiàn)行進(jìn)程全部活動(dòng)頁(yè)面在宿主存儲(chǔ)器內(nèi)，而且該存儲(chǔ)器不包含其他處理機(jī)的頁(yè)面，則處理機(jī)不會(huì)遇到存儲(chǔ)沖突。

多處理機(jī)系統(tǒng)的存儲(chǔ)器結(jié)構(gòu)(cont.)多處理機(jī)系統(tǒng)中常采用二維存儲(chǔ)器結(jié)構(gòu)，如圖5-32所示。有n個(gè)同樣容量的存儲(chǔ)模塊，排成l列（體），每一列有m個(gè)模塊組成。各列之間按高位交叉編址，而列內(nèi)各模塊為按低位交叉編址，每列有一個(gè)列控制器連到互聯(lián)網(wǎng)絡(luò)。

多處理機(jī)系統(tǒng)的cache結(jié)構(gòu)

當(dāng)每個(gè)處理機(jī)都有自己專用的cache時(shí)，對(duì)應(yīng)主存中某一個(gè)單元的數(shù)據(jù)，在各個(gè)cache中可能會(huì)出現(xiàn)相應(yīng)的多個(gè)副本，當(dāng)對(duì)其中某一個(gè)副本進(jìn)行一次修改操作，就會(huì)產(chǎn)生cache中數(shù)據(jù)不一致性。無論cache采用“寫回法”或“寫直接法”，都不能解決多個(gè)cache不一致問題。

靜態(tài)一致性校驗(yàn)

只讓該進(jìn)程的獨(dú)用信息（指令和操作數(shù)據(jù)）和共享的只讀信息進(jìn)入本處理機(jī)的cache，而對(duì)于共享的可寫（即可修改）的信息不準(zhǔn)進(jìn)入cache，只可留在主存中。這種方法增加了互聯(lián)網(wǎng)絡(luò)和主存的競(jìng)爭(zhēng)，因此，性能較差。減少競(jìng)爭(zhēng)的方法是增加一個(gè)共享cache--sc（sharedcache），共享信息均在sc內(nèi)，而取指令和獨(dú)用數(shù)據(jù)則通過獨(dú)用cache--pc（privatecache），其結(jié)構(gòu)如圖5-33所示。

動(dòng)態(tài)一致性校驗(yàn)

基本思想是在若干個(gè)cache中使同一個(gè)信息（指令、數(shù)據(jù)）始終保持動(dòng)態(tài)一致。一種方法是廣播法：即當(dāng)每個(gè)處理機(jī)每次寫cache時(shí)，不僅寫入自己的cache和共享的主存中，而且還把信息送到所有cache，如果其他cache有與自己cache相同的目標(biāo)行，則也進(jìn)行改寫。

動(dòng)態(tài)一致性校驗(yàn)(cont.)另一種時(shí)目錄法。在快速ram中構(gòu)建一個(gè)目錄表，如圖5-34所示。它有兩個(gè)部分：存在表（presenttable）是二維的，其中每一項(xiàng)P（i,c）表示第i塊是在第c個(gè)cache中，修改表（modifiedtable）是一維的，其中每項(xiàng)M（i）表示第i塊是否被修改過。在每個(gè)cache中還有一個(gè)本地標(biāo)志（可