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

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

多處理機的優(yōu)點

很高的性能價格比

：

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

很高的可靠性

：冗余度大、可維護性、可用性

很高的處理速度：多個處理器并行運算

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

特性要求--進程恢復能力

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

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

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

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

特性要求--高效率的同步原語

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

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

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

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

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

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

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

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

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

并行處理的特點

資源重復。它機利用眾多的處理單元對向量所包含的各個分量同時進行運算，獲得很高處理速度。

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

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

復合性。整個系統(tǒng)是由三部分復合起來的一個多機系統(tǒng)，即多個處理單元組成陣列并行地處理向量；功能極強的控制部件實際上是一臺標量處理機；系統(tǒng)的管理功能則由高性能單處理機擔負。

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

特點：ICN：是單向的，PE→PE。

工作流程：特點：ICN：是雙向的，PE←→M。

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

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

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

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

目標：低成本、高靈活性、高連接度、低延時、適合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ù)表示。一個互連網(wǎng)絡(luò)的連接特征可對應多個互連函數(shù)。1.立方體單級網(wǎng)絡(luò)（交換互連網(wǎng)絡(luò)）單級互連網(wǎng)絡(luò)只能實現(xiàn)有限的幾種連接。單級互連網(wǎng)絡(luò)出端編碼與連接的入端結(jié)點的編碼有一位相反。zyx010011110111000001101100

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

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

互連函數(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）注意：立方體坐標編號不能標錯。000001000001010011010011100101100101110111110111000001000001010011010011100101100101110111110111000001000001010011010011100101100101110111110111Cube0Cube1Cube2

連接圖：

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

應用：幾種互連函數(shù)反復調(diào)用，任意結(jié)點間可連接。2.PM2I單級網(wǎng)絡(luò)（循環(huán)移數(shù)網(wǎng)絡(luò)）出端編碼與連接的入端結(jié)點編碼相差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個互連函數(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é)點最大間距n/2=log2N/2≤log2N/2；互連函數(shù)個數(shù)2n。

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

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

全混洗互連函數(shù)：Shuffle(bn-1bn-2…b1b0)=(bn-2…b1b0bn-1)；全“0”或全“1”結(jié)點無法與其他結(jié)點連接，必須輔以交換互連函數(shù)，方可實現(xiàn)任意結(jié)點間連接。最簡單的交換互連函數(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é)任一單級互連網(wǎng)絡(luò)均可表示成N入N出的過程。(1)單級互連網(wǎng)絡(luò)特性任一單級互連網(wǎng)絡(luò)可實現(xiàn)部分結(jié)點(一對或幾對)間的連接，不能實現(xiàn)任意多對結(jié)點間的同時連接。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

多處理機的主要特點是各臺處理機共享一組存儲器和I/O設(shè)備。這種共享功能是通過兩個互聯(lián)網(wǎng)絡(luò)實現(xiàn)的：一個是處理機和存儲器模塊之間的互聯(lián)網(wǎng)絡(luò)；另一個是處理機和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)

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

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

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

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

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

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

動態(tài)優(yōu)先級算法

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

先來先服務(wù)算法

：按照接受到的請求先后順序予以處理。

總線形式

（時間分配）

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

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

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

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

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

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

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

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

SIMD：單指令流系統(tǒng)，并行操作相同，一個CU，控制、數(shù)據(jù)通訊簡單，通用性較差；

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

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

識別：隱式識別和向量指令，

支持：編譯程序和硬件；

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

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

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

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

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

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

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

·

·計算機模塊(結(jié)點機)PMI/ONI模塊N

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

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

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

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

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

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

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

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

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

動態(tài)一致性校驗

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

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