第六章向量處理機(jī)1目錄6.1向量的流水處理和向量流水機(jī)6.2陣列處理機(jī)的原理6.3SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò)6.4并行儲(chǔ)存器的無沖突訪問6.5脈動(dòng)陣列流水處理機(jī)26.3SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò)6.3.4基本的多級互連網(wǎng)絡(luò)1.多級立方體網(wǎng)絡(luò)STARAN網(wǎng)絡(luò)用作交換網(wǎng)絡(luò)時(shí)，采用級控制，實(shí)現(xiàn)的是交換函數(shù)。所謂交換(FLIP)函數(shù)是將一組元素首尾對稱地進(jìn)行交換。如果一組元素包含有2S個(gè)，則它是將所有第K個(gè)元素都與第(2S-(K+1))個(gè)元素相交換。表6-1列出了三級交換網(wǎng)絡(luò)在級控制信號采用各種不同組合情況下所實(shí)現(xiàn)的入、出端的連接。從表6-1可以看出，控制信號為111時(shí)，實(shí)現(xiàn)全交換，也稱鏡像交換，完成對這8個(gè)處理單元(元素)的一組8元交換，其變換圖像如下：3控制信號為111時(shí)，實(shí)現(xiàn)全交換，也稱鏡像交換，完成對這8個(gè)處理單元(元素)的一組8元交換，其變換圖像如下：入端排列01234567出端排列控制信號為001時(shí)，完成對這8個(gè)處理單元(元素)的4組2元交換，其變換圖像如下：

入端排列01234567出端排列103254764控制信號為010時(shí)，完成的功能相當(dāng)于在進(jìn)行4組2元交換后再進(jìn)行2組4元交換，其變換圖像如下： 入端排序10325476

出端排列23016745而控制信號為101時(shí)，相當(dāng)于實(shí)現(xiàn)上述兩種交換后再進(jìn)行1組8元交換，其變換圖像如下：

入端排序23016745端排列序547610325總之，不管控制信號是什么狀態(tài)，實(shí)現(xiàn)的都是交換函數(shù)功能。從表6-1水平方向不難看出，任何輸入端只要通過不同的級控制信號，總可以接到任何所需要的輸出端上。當(dāng)STARAN網(wǎng)絡(luò)用作移數(shù)網(wǎng)絡(luò)時(shí)，采用部分級控制，控制信號分組和控制結(jié)果列在表6-2中?？梢钥闯鏊鼈兌际菆?zhí)行各種不同的移數(shù)功能的。

62.多級混洗交換函數(shù)多級混洗交換網(wǎng)絡(luò)又稱OMEGA網(wǎng)絡(luò)，如圖6-16所示。它由N級相同的網(wǎng)絡(luò)組成，每一級都包含一個(gè)全混拓?fù)浜碗S后一列2N-1個(gè)四功能交換單元，采用單元控制方式。比較圖6-15和圖6-16可以發(fā)現(xiàn)，OMEGA網(wǎng)絡(luò)中各級編號的次序與多級立方體網(wǎng)絡(luò)正好相反。如果把OMEGA網(wǎng)絡(luò)的入端和出端位置對調(diào)，它就等同于間接二進(jìn)制N方體網(wǎng)絡(luò)。因此OMEGA網(wǎng)絡(luò)與間接二進(jìn)制N方體網(wǎng)絡(luò)只有兩點(diǎn)差別：前者數(shù)據(jù)流向是級號N-1、N-2、…、1、0,用四功能交換單元，后者數(shù)據(jù)流向相反，是級號0、1、…、N-1,用二功能交換單元。7圖6-16

N=8多級混洗交換網(wǎng)絡(luò)

8假定OMEGA網(wǎng)絡(luò)也采用二功能交換單元，就可看成是N方體網(wǎng)絡(luò)的逆網(wǎng)絡(luò)?；净ミB網(wǎng)絡(luò)可以實(shí)現(xiàn)任一個(gè)入端與任一個(gè)出端之間的連接，但要同時(shí)實(shí)現(xiàn)兩對或多對的入、出端間的連接，就可能發(fā)生連接路徑上的沖突。由于OMEGA網(wǎng)絡(luò)與N方體網(wǎng)絡(luò)的數(shù)據(jù)入、出流向相反，因此它們產(chǎn)生沖突的狀況不同。例如，N方體網(wǎng)絡(luò)能同時(shí)實(shí)現(xiàn)5到0、7到1的連接，不能同時(shí)實(shí)現(xiàn)0到5、1到7的連接；而OMEGA網(wǎng)絡(luò)正好相反，能同時(shí)實(shí)現(xiàn)0到5和1到7的連接，不能同時(shí)實(shí)現(xiàn)5到0和7到1的連接。9當(dāng)然，由于OMEGA網(wǎng)絡(luò)采用四功能交換單元，因此允許同時(shí)實(shí)現(xiàn)一個(gè)處理單元與多個(gè)處理單元的連接，這是多級立方體網(wǎng)絡(luò)不可能辦到的。例如，只需將圖6-16中交換單元E、F置為下播狀態(tài)，C、I、J、K、L置為上播狀態(tài)，就能一次實(shí)現(xiàn)入端2與全部8個(gè)出端的連接。103.多級PM2I網(wǎng)絡(luò)N=8的多級PM2I網(wǎng)絡(luò)的結(jié)構(gòu)如圖6-17所示。它包含N級單元間連接，每一級都是把前后兩列各N=2N個(gè)單元按PM2I拓?fù)湎嗷ミB接起來。從第I級(0≤I≤N-1)來說，每一個(gè)入單元J(0≤J≤N-1)都有3根連接線分別通往出單元J、J+2IMODN和J-2IMODN，在圖6-17中，它們分別用點(diǎn)線、實(shí)線和虛線表示。前面已提到，單級PM2I網(wǎng)絡(luò)的最大距離為［N/2］，但組成多級PM2I網(wǎng)絡(luò)時(shí)仍用了N級，因此在這種網(wǎng)絡(luò)中提供了冗余路徑。例如，為實(shí)現(xiàn)由7將信息傳到2，可以經(jīng)7→3→3→2，或7→7→1→2，或7→3→1→2等多條路徑完成。這對提高可靠性和便于集成電路化都有好處。11圖6-17

N=8多級PM2I網(wǎng)絡(luò)

12控制這三類連接線的信號分別稱為平控H、下控D和上控U。為了簡化對這三類信號的產(chǎn)生，可將各級的單元分成兩組。對于第I級，讓H1I、DI1、UI1控制第I位為“0”的那些入單元，而讓HI2、DI2、UI2控制第I位為“1”的那些入單元，此種多級PM2I網(wǎng)絡(luò)稱為數(shù)據(jù)變換網(wǎng)絡(luò)(DATAMANIPULATOR)。可以采用單元控制增強(qiáng)對各級單元控制的靈活性，讓每一單元都有自己獨(dú)立的控制信號H、D、U,此種多級PM2I網(wǎng)絡(luò)稱為強(qiáng)化數(shù)據(jù)變換網(wǎng)絡(luò)ADM(AUGMENTEDDATAMANIPULATOR)，不過控制線多，成本較高。13靈活性由低到高的次序是：級控制立方體、部分級控制立方體、間接二進(jìn)制N方體、OMEGA、ADM,而復(fù)雜性和成本的次序也相應(yīng)增高。144.基準(zhǔn)網(wǎng)絡(luò)圖6-18是N=8的基準(zhǔn)網(wǎng)絡(luò)。它與二進(jìn)制立方體網(wǎng)絡(luò)的逆網(wǎng)絡(luò)相似，只是在第1級的級間連接不同。它采取從輸入到輸出的級間互連為恒等、逆全混、子逆全混和恒等置換，所用交換單元均為二功能，采取單元控制?；鶞?zhǔn)網(wǎng)絡(luò)在多級網(wǎng)絡(luò)中可作為中間介質(zhì)，模擬一種網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和功能。15圖6-18

N=8的基準(zhǔn)網(wǎng)絡(luò)

165.多級交叉開關(guān)網(wǎng)絡(luò)多級交叉開關(guān)(CLOS)網(wǎng)絡(luò)是一種非阻塞式網(wǎng)絡(luò)，圖6-19給出了一個(gè)三級交叉開關(guān)網(wǎng)絡(luò)的結(jié)構(gòu)。其網(wǎng)絡(luò)的入、出端口數(shù)均為N×R,輸入級有R個(gè)N×M的交叉開關(guān)，中間級有M個(gè)R×R的交叉開關(guān)，輸出級有R個(gè)M×N的交叉開關(guān)。當(dāng)M≥2N-1時(shí)，它就成了非阻塞網(wǎng)絡(luò)。所謂非阻塞網(wǎng)絡(luò)，指的是同時(shí)實(shí)現(xiàn)兩對或多對入、出端間的連接，均不會(huì)發(fā)送傳送路徑上的沖突(全排列網(wǎng)絡(luò)中介紹)，表示成N(M,N,R)。17圖6-19三級交叉開關(guān)網(wǎng)絡(luò)的結(jié)構(gòu)186.多級蝶式網(wǎng)絡(luò)圖6-21是由16個(gè)8×8交叉開關(guān)作為基本構(gòu)件組成的二級蝶式網(wǎng)絡(luò)，級間采用8路混洗，構(gòu)成了64×64的蝶式互連。再用其與64個(gè)8×8的交叉開關(guān)擴(kuò)展構(gòu)成512×512的三級蝶式互連網(wǎng)絡(luò)，如圖6-22所示。圖6-21中使用了16個(gè)8×8的交叉開關(guān)，圖6-22則共用了3×8×8=192個(gè)8×8的交叉開關(guān)。如果要構(gòu)造更大的蝶式網(wǎng)絡(luò)只需增加級數(shù)即可。但蝶式網(wǎng)絡(luò)不能實(shí)現(xiàn)播送，只是OMEGA網(wǎng)絡(luò)的一個(gè)有限制的子集。19圖6-21

用8×8交叉開關(guān)構(gòu)造的二級64×64的蝶式互連網(wǎng)絡(luò)

206.3.5全排列網(wǎng)絡(luò)如果互連網(wǎng)絡(luò)是從N個(gè)入端到N個(gè)出端的一到一的映射，就可以把它看成是對此N個(gè)端的重新排列，因此互連網(wǎng)絡(luò)的功能實(shí)際上就是用新排列來置換N個(gè)入端原有的排列。前面所介紹的各種基本多級網(wǎng)絡(luò)都能實(shí)現(xiàn)任意一個(gè)入端與任意一個(gè)出端間的連接，但要同時(shí)實(shí)現(xiàn)兩對或多對入、出端間的連接時(shí)，都有可能發(fā)生爭用數(shù)據(jù)傳送路徑的沖突。前面在多級立方體網(wǎng)絡(luò)和多級混洗交換網(wǎng)絡(luò)中已舉過這種例子。稱有這類性質(zhì)的互連網(wǎng)絡(luò)為阻塞式網(wǎng)絡(luò)(BLOCKINGNETWORK)，稱無這類性質(zhì)的互連網(wǎng)絡(luò)為非阻塞式網(wǎng)絡(luò)或全排列網(wǎng)絡(luò)。非阻塞式網(wǎng)絡(luò)連接靈活，但連線多、控制復(fù)雜、成本高。

216.4共享主存構(gòu)形的陣列處理機(jī)中并行儲(chǔ)存器的無沖突訪問在共享主存構(gòu)形的陣列處理機(jī)中，存儲(chǔ)器頻寬要與多個(gè)處理單元的速率匹配，存儲(chǔ)器就必須采用多體并行組成。此外，還要保證在各種訪問模式下，存儲(chǔ)器都能實(shí)現(xiàn)無沖突地工作。只有這樣，存儲(chǔ)器的實(shí)際頻寬才不會(huì)下降，從而使陣列處理機(jī)的數(shù)組并行處理的性能不至于下降。對數(shù)組訪問的模式是多樣的，可能要訪問數(shù)組的行、列、主對角線、次對角線的全部元素或其中某個(gè)子方陣。

22不難看出，只要并行存儲(chǔ)體體數(shù)M為偶數(shù)，對M×M的正方形數(shù)組無論怎樣存放，都不可能同時(shí)實(shí)現(xiàn)行、列、主對角線、次對角線上的所有元素都能無沖突地訪問。盡管可以通過對不同的數(shù)組訪問模式采用不同的錯(cuò)位方案來滿足在該訪問模式下不發(fā)生沖突，但這將給編譯程序設(shè)計(jì)者增加很大負(fù)擔(dān)。能滿足上述這些要求的一種存儲(chǔ)方案是使并行存儲(chǔ)器分體數(shù)M大于每次要訪問的向量或數(shù)組元素的個(gè)數(shù)N(N在陣列處理機(jī)上就是處理單元數(shù))，且等于質(zhì)數(shù)，同時(shí)在多維數(shù)組的行、列等方向上采取不同的錯(cuò)開距離。23假設(shè)n×n的二維數(shù)組在并行存儲(chǔ)器中同一列兩個(gè)相鄰元素地址錯(cuò)開的距離為δ1,同一行兩個(gè)相鄰元素地址錯(cuò)開的距離為δ2,當(dāng)m取成22p+1(p為正整數(shù))時(shí)，實(shí)現(xiàn)無沖突訪問的充分條件是讓δ1=2p,δ2=1。圖6-27就是對4×4二維數(shù)組按上述規(guī)則存儲(chǔ)的一種方案。其中，p=1,m=5,δ1=2,δ2=1。24圖6-274×4數(shù)組錯(cuò)位存放的例子(m=5,n=4,δ1=2,δ2=1)25由圖6-27可知，對數(shù)組的行、列、主對角線、次對角線甚至數(shù)組中任意一個(gè)2×2的子方陣都可實(shí)現(xiàn)無沖突訪問。對于這種無沖突訪問的存儲(chǔ)方案，要求n×n二維數(shù)組A中的任意一個(gè)元素Aab應(yīng)放在下列地址處：體號地址j=(aδ1+bδ2+c)modm體內(nèi)地址i=a

26練習(xí)27實(shí)際上，并行存儲(chǔ)器中存放的數(shù)組大小是不固定的，多維數(shù)組各維的元素個(gè)數(shù)也不一定相等，它們還可以超出已選定的分體數(shù)M的值。因此，有N個(gè)處理單元的并行處理機(jī)，為了能并行訪問N個(gè)元素，且適應(yīng)任意規(guī)模的數(shù)組，可以先將多維數(shù)組或者非N×N方陣的二維數(shù)組按行或列的順序變換為一維數(shù)組，形成一個(gè)一維線性地址空間，地址用A表示。然后，將地址A所對應(yīng)的元素存放在體號地址j=amodm,體內(nèi)地址為i=［a/n］的單元中，就可以滿足無沖突訪問的要求。286.5脈動(dòng)陣列流水處理機(jī)（領(lǐng)會(huì)）6.5.1脈動(dòng)陣列結(jié)構(gòu)的原理

脈動(dòng)陣列結(jié)構(gòu)是由一組處理單元PE構(gòu)成的陣列。每個(gè)PE的內(nèi)部結(jié)構(gòu)相同，一般由一個(gè)加法/邏輯運(yùn)算部件或加法/乘法運(yùn)算部件再加上若干個(gè)鎖存器構(gòu)成，可完成少數(shù)基本的算術(shù)邏輯運(yùn)算操作。陣列內(nèi)所有處理單元的數(shù)據(jù)鎖存器都受同一個(gè)時(shí)鐘控制。運(yùn)算時(shí)數(shù)據(jù)在陣列結(jié)構(gòu)的各個(gè)處理單元間沿各自的方向同步向前推進(jìn)，就像血液受心臟有節(jié)奏地搏動(dòng)在各條血管中同步向前流動(dòng)一樣。因此，形象地稱其為脈動(dòng)陣列結(jié)構(gòu)。實(shí)際上，為了執(zhí)行多種計(jì)算，脈動(dòng)型系統(tǒng)內(nèi)的輸入數(shù)據(jù)流和結(jié)果數(shù)據(jù)流可以在多個(gè)不同方向上以不同速度向前搏動(dòng)。

29脈動(dòng)陣列結(jié)構(gòu)具有如下一些特點(diǎn)：(1)結(jié)構(gòu)簡單、規(guī)整，模塊化強(qiáng)，可擴(kuò)充好，非常適合用超大規(guī)模集成電路實(shí)現(xiàn)。(2)PE間數(shù)據(jù)通信距離短、規(guī)則，使數(shù)據(jù)流和控制流的設(shè)計(jì)、同步控制等均簡單規(guī)整。(3)脈動(dòng)陣列中所有PE能同時(shí)運(yùn)算，具有極高的計(jì)算并行性，可通過流水獲得很高的運(yùn)算效率和吞吐率。輸入數(shù)據(jù)能被多個(gè)處理單元重復(fù)使用，大大減輕了陣列與外界的I/O通信量，降低了對系統(tǒng)主存和I/O系統(tǒng)頻寬的要求。(4)脈動(dòng)陣列結(jié)構(gòu)的構(gòu)形與特定計(jì)算任務(wù)和算法密切相關(guān)，具有某種專用性，限制了應(yīng)用范圍，這對VLSI是不利的。30發(fā)展通用脈動(dòng)陣列結(jié)構(gòu)的途徑主要有三種：（1）一種途徑是通過增設(shè)附加的硬件，對陣列的拓?fù)浣Y(jié)構(gòu)和互連方式用可編程開關(guān)進(jìn)行重構(gòu)，即經(jīng)程序重新配置陣列的結(jié)構(gòu)。（2）第二種途徑是用軟件把不同的算法映像到固定的陣列結(jié)構(gòu)上。這一方法依賴于面向并行運(yùn)算所采用的程序語言、操作系統(tǒng)、編譯程序和軟件開發(fā)工具的設(shè)計(jì)。（3）第三種途徑是探尋與問題大小無關(guān)的脈動(dòng)處理方法，以及VLSI運(yùn)算系統(tǒng)的分割矩陣算法，使它們可以克服陣列只能求解固定大小題目的缺陷，同時(shí)探尋發(fā)展適合一類計(jì)算問題的通用算法和相應(yīng)的設(shè)置方案。31第七章多處理機(jī)主講人：梅藝凡32目錄7.1多處理機(jī)的概念、問題和硬件結(jié)構(gòu)7.2緊耦合處理機(jī)多Cache的一致性問題7.3多處理機(jī)的并行性和性能7.4多處理機(jī)的操作系統(tǒng)7.5多處理機(jī)的發(fā)展337.1多處理機(jī)的概念、問題和硬件結(jié)構(gòu)7.1.1多處理機(jī)的基本概念和要解決的技術(shù)問題基本概念：多處理機(jī)指有兩臺(tái)以上的處理機(jī)，共享I/O子系統(tǒng)，機(jī)間經(jīng)共享主存或高速通信網(wǎng)絡(luò)通信，在統(tǒng)一操作系統(tǒng)控制下，協(xié)同求解大而復(fù)雜問題的計(jì)算機(jī)系統(tǒng)。使用多處理機(jī)的目的：（1）通過多臺(tái)處理機(jī)對多個(gè)作業(yè)、任務(wù)的進(jìn)行并行執(zhí)行來提高解題速度，從而提高系統(tǒng)的整體性能；（2）使用冗余的多個(gè)處理機(jī)通過重新組織來提高系統(tǒng)的可靠性、適應(yīng)性和可用性。34與陣列處理機(jī)比較陣列處理機(jī)是操作級并行，并行性存在于指令內(nèi)部，是開發(fā)并發(fā)行中的同時(shí)性；多處理機(jī)系統(tǒng)是作業(yè)級并行，存在于指令外部，較難識別，是開發(fā)并行性中的并發(fā)性。35多處理機(jī)的主要技術(shù)問題1、硬件上處理好處理機(jī)、I/O通道、存儲(chǔ)模塊的互連問題。2、軟件上最大限度開發(fā)系統(tǒng)的并行性，以實(shí)現(xiàn)多處理機(jī)各級的全面并行。3、確定任務(wù)粒度問題，即如何選擇任務(wù)和子任務(wù)的大小。4、進(jìn)程同步問題。5、任務(wù)分配，資源分配，防止死鎖問題。6、當(dāng)系統(tǒng)中某個(gè)處理機(jī)發(fā)生故障后的恢復(fù)問題。7、多處理機(jī)機(jī)數(shù)增多后，如何能給編程者提供良好的編程環(huán)境問題。367.1.2多處理機(jī)的硬件結(jié)構(gòu)1.多處理機(jī)有緊耦合和松耦合兩種（1）緊耦合多處理機(jī)緊耦合多處理機(jī)是通過共享主存實(shí)現(xiàn)處理機(jī)間通訊的,其通訊速率受限于主存頻寬。各處理機(jī)與主存經(jīng)互連網(wǎng)絡(luò)連接，處理機(jī)數(shù)受限于互連網(wǎng)絡(luò)帶寬及各處理機(jī)訪主存沖突的概率。

為了減少各處理機(jī)同時(shí)訪問同一存儲(chǔ)器模塊的沖突，存儲(chǔ)器模塊數(shù)M應(yīng)等于或略大于處理機(jī)數(shù)P。37每臺(tái)處理機(jī)自帶局部存儲(chǔ)器，不僅可以減少訪主存信息量，降低訪主存沖突概率，也可以減少處理機(jī)---存儲(chǔ)器互連網(wǎng)絡(luò)的沖突。如果再自帶專用CACHE就可以進(jìn)一步減少這類沖突。同構(gòu)/異構(gòu)--PE類型相同/不同；對稱/非對稱—每個(gè)PE與部分/全部的I/O通道連接。常見結(jié)構(gòu)：同構(gòu)對稱式和異構(gòu)非對稱式多機(jī)系統(tǒng)?；ミB網(wǎng)絡(luò)：實(shí)現(xiàn)PE←→PEM、PE←→I/O通道、

PE←→中斷信號間的連接?；ミB網(wǎng)絡(luò)控制—分布式控制(消息傳遞機(jī)制)。38（2）松耦合多處理機(jī)松耦合多處理機(jī)中，每臺(tái)處理機(jī)都有一個(gè)容量較大的局部存儲(chǔ)器，用于存儲(chǔ)經(jīng)常用的指令和數(shù)據(jù)，以減少緊耦合系統(tǒng)中存在的訪主存沖突。消息傳送系統(tǒng)常采用分時(shí)總線或環(huán)形、星形、樹形等拓?fù)浣Y(jié)構(gòu)。松耦合多處理機(jī)較適合做粗粒度的并行計(jì)算?；ミB網(wǎng)絡(luò)：實(shí)現(xiàn)結(jié)點(diǎn)(非PE與PSM)間互連?？刂啤植际娇刂?消息傳遞機(jī)制)。結(jié)點(diǎn)結(jié)構(gòu)：是完整的處理機(jī)系統(tǒng)；當(dāng)結(jié)點(diǎn)為多處理機(jī)系統(tǒng)時(shí)，構(gòu)成了層次系統(tǒng)。392.機(jī)間互連形式多處理機(jī)機(jī)間互連的形式是決定多處理機(jī)性能的一個(gè)重要因素。在滿足高通訊速率、低成本的條件下，互連還應(yīng)靈活多樣，以實(shí)現(xiàn)各種復(fù)雜的乃至不規(guī)則的互連而不發(fā)生沖突。（1）總線形式單總線方式結(jié)構(gòu)簡單、成本低，系統(tǒng)增減模塊方便，但對總線的失效敏感，處理機(jī)機(jī)數(shù)增加會(huì)增大總線沖突概率，使系統(tǒng)效率急劇下降。40（A）提高總線形式的系統(tǒng)效率的辦法一是用優(yōu)質(zhì)高頻同軸電纜來提高總線的傳輸速率。二是用多總線方式來減少訪總線的沖突概率。（B）多種總線仲裁算法靜態(tài)優(yōu)先級算法為每個(gè)連到總線的部件分配一固定的優(yōu)先級。固定時(shí)間片算法是把總線按固定大小時(shí)間片輪流提供給部件使用。動(dòng)態(tài)優(yōu)先級算法是總線上各部件優(yōu)先級可根據(jù)情況按一定規(guī)則動(dòng)態(tài)改變。先來先服務(wù)算法是按接收到訪問總線請求的先后順序來響應(yīng)。41（2）環(huán)形互連形式構(gòu)造一種邏輯總線,讓各臺(tái)處理機(jī)之間點(diǎn)點(diǎn)相連成環(huán)狀,稱環(huán)形互連。在這種多處理機(jī)上，消息的傳遞過程是由發(fā)送進(jìn)程將信息送到環(huán)上，經(jīng)環(huán)形網(wǎng)絡(luò)不斷向下一臺(tái)處理機(jī)傳遞，直到此信息又回到發(fā)送者為止。發(fā)送信息的處理機(jī)擁有一個(gè)唯一的令牌，它是普通傳送的信息中不會(huì)出現(xiàn)的特定標(biāo)記。同時(shí)只能有一臺(tái)處理機(jī)可持有這個(gè)令牌。發(fā)送者在發(fā)送信息時(shí)，環(huán)上其他處理機(jī)都處于接收信息的狀態(tài)。42優(yōu)點(diǎn)：由于環(huán)形互連是點(diǎn)點(diǎn)連接，不是總線式連接，其物理參數(shù)容易得到控制，非常適合于有高通訊帶寬的光纖通訊。有效帶寬可以得到最充分的利用。缺點(diǎn)：信息在每個(gè)接口處都會(huì)有一個(gè)單位的傳輸延遲，當(dāng)互連的處理機(jī)機(jī)數(shù)增加時(shí)，環(huán)中的信息傳輸延遲將增大。43（3）交叉開關(guān)形式（空間分配）單總線互連結(jié)構(gòu)最簡單，但爭用總線最嚴(yán)重。交叉開關(guān)形式則不同于單總線。它用縱橫開關(guān)陣列將橫向的處理機(jī)P及I/O通道與縱向的存儲(chǔ)器模塊M連接起來。改進(jìn)：用一系列較小開關(guān)串聯(lián)或并聯(lián)，形成多級交叉開關(guān)，減少其復(fù)雜性。交叉開關(guān)方式不適宜連接過多的處理機(jī)。44（4）多端口存儲(chǔ)器形式將控制、仲裁、轉(zhuǎn)換機(jī)構(gòu)移到存儲(chǔ)器中。每個(gè)存儲(chǔ)器端口與一個(gè)PE或I/O通道相連。多端口存儲(chǔ)器形式不適宜連接過多的處理機(jī)。45（5）蠕蟲穿洞尋徑網(wǎng)絡(luò)（6）開關(guān)樞紐結(jié)構(gòu)形式參照多端口存儲(chǔ)器的思想，把互連結(jié)構(gòu)的開關(guān)設(shè)置在各處理機(jī)或接口內(nèi)部，組成分布式結(jié)構(gòu)，則稱為開關(guān)樞紐結(jié)構(gòu)形式。每一臺(tái)處理機(jī)通過它的開關(guān)樞紐與其他多臺(tái)處理機(jī)連接組成各種有分布結(jié)構(gòu)的多處理機(jī)。開關(guān)樞紐的選擇，應(yīng)使組成的多處理機(jī)有較佳的拓?fù)浣Y(jié)構(gòu)和良好的互連特性，特別是要適應(yīng)處理機(jī)機(jī)數(shù)很多的情況。理想的拓?fù)浣Y(jié)構(gòu)應(yīng)該是：所用開關(guān)樞紐數(shù)量少，每個(gè)開關(guān)樞紐的端口數(shù)不多，能以較短的路徑把數(shù)量很多的處理機(jī)連接起來，實(shí)現(xiàn)快速而靈活的通訊；不改變模塊本身的結(jié)構(gòu)，就可使系統(tǒng)規(guī)模得到任意擴(kuò)充。463.儲(chǔ)存器的組織（自行看書，考試沒有要求）477.2緊耦合多處理機(jī)多CACHE的一致性問題（領(lǐng)會(huì)）7.2.1多CACHE的一致性問題的產(chǎn)生當(dāng)主存中同一個(gè)信息塊在多個(gè)CACHE中都有時(shí)，會(huì)出現(xiàn)多個(gè)CACHE之間的相應(yīng)信息塊的內(nèi)容不一致的問題。將一個(gè)尚未執(zhí)行完而被掛起的進(jìn)程調(diào)度到另一個(gè)空閑的處理機(jī)上去執(zhí)行，使系統(tǒng)中各處理機(jī)的負(fù)荷保的均衡，會(huì)造成CACHE與主存的不一致。當(dāng)系統(tǒng)發(fā)生繞過CACHE的輸入/輸出操作時(shí)，也會(huì)導(dǎo)致多個(gè)CACHE塊之間及CACHE與主存對應(yīng)塊的內(nèi)容不一致。487.2.2多CACHE的一致性問題的解決辦法（1）解決進(jìn)程遷移引起的多CACHE不一致性可以通過禁止進(jìn)程遷移的辦法予以解決，也可以在進(jìn)程掛起時(shí)，靠硬件方法將CACHE中該進(jìn)程改寫的信息塊強(qiáng)制寫回主存相應(yīng)位置的辦法來解決。（2）以硬件為基礎(chǔ)實(shí)現(xiàn)多CACHE的一致性最普遍采用的辦法叫做監(jiān)視CACHE的協(xié)議法，即各個(gè)處理機(jī)中的CACHE控制器隨時(shí)都在監(jiān)視著其他CACHE的行動(dòng)。適用于總線互連的多處理機(jī)系統(tǒng)中。49在其他多處理機(jī)系統(tǒng)中，通常采用基于目錄協(xié)議。CACHE目錄中存放的內(nèi)容是大量的指針，用以指明塊拷貝的地址，每個(gè)目錄項(xiàng)還有一個(gè)重寫位，指明是否有一個(gè)CACHE允許寫入數(shù)據(jù)。根據(jù)CACHE目錄的存放形式，有集中式和分布式兩種。根據(jù)目錄的結(jié)構(gòu)，目錄協(xié)議分成三類： 全映射(FULL-MAP)目錄：存放全局存儲(chǔ)器每個(gè)塊的有關(guān)數(shù)據(jù)。 有限(LIMITED)目錄：每個(gè)目錄項(xiàng)的指針數(shù)固定。 鏈?zhǔn)?CHAINED)目錄：把目錄分布到所有CACHE中。507.3多處理機(jī)的并行性和性能（綜合應(yīng)用）

多處理機(jī)的并行性既存在于指令內(nèi)部，也存在于指令外部，因此，必須利用算法、程序語言、編譯、操作系統(tǒng)及指令、硬件等多種途徑來開拓。517.3.1并行算法1.并行算法的定義和分類并行算法是指可同時(shí)執(zhí)行的多個(gè)進(jìn)程的合集，各進(jìn)程可相互作用、協(xié)調(diào)和并發(fā)操作。按運(yùn)算基本對象，可分為數(shù)值型和非數(shù)值型：基于代數(shù)運(yùn)算，如矩陣等稱為數(shù)值型并行算法；基于關(guān)系運(yùn)算，如選擇、排序等主要對符號操作的稱為非數(shù)值型并行算法。按并行進(jìn)程間的操作順序不同，可分為同步型、異步型和獨(dú)立型3種。根據(jù)任務(wù)的大小不同，又分為細(xì)粒度、中粒度和粗粒度3種。522.多處理機(jī)并行算法的研究思路將大的程序分解成可由足夠多的并行處理的過程（進(jìn)程、任務(wù)、程序段）。每個(gè)過程被看成一個(gè)結(jié)點(diǎn)，將過程之間的關(guān)聯(lián)關(guān)系用結(jié)點(diǎn)組成的樹來描述。運(yùn)算的級數(shù)就是樹的高度，用TP代表。P為所需處理機(jī)的數(shù)目，稱順序運(yùn)算的級數(shù)T1與P臺(tái)處理機(jī)運(yùn)算的級數(shù)TP的比為加速比，用SP代表。而SP/P=EP稱為效率?？梢?，SP>=1時(shí)，會(huì)使EP<=1，即運(yùn)算的加速總是伴隨著效率的下降。53例如：E1=A+BX+CX2+DX3,利用霍納法可得到：

E1=A+X(B+X(C+X(D)))。這是在單處理機(jī)上執(zhí)行的典型算法。共需要3個(gè)乘加循環(huán)6級運(yùn)算，但不適合于在多處理機(jī)上運(yùn)行，因?yàn)樗鼰o法利用上其他的處理機(jī)。用3臺(tái)處理機(jī)只需4級運(yùn)算就夠了。將這兩式的運(yùn)算過程表示為樹形流程圖分別為下圖所示。54不同算法影響樹高的例子+*+*****+xdacbxxxxx+*+*+*axbxcdx55既然可把運(yùn)算過程表示成樹形結(jié)構(gòu)，那么，提高運(yùn)算的并行性就是如何對樹進(jìn)行變換，減少運(yùn)算的級數(shù)，即降低樹高。樹型結(jié)構(gòu)可以用交換律、結(jié)合律、分配律來交換。方法：首先從算術(shù)表達(dá)式的最直接形式出發(fā)，利用交換律把相同的運(yùn)算集中在一起。然后利用結(jié)合律把參加這些運(yùn)算的操作數(shù)（稱原子）配對，盡可能并行運(yùn)算。從而組成樹高最小的子樹。最后再把這些子樹結(jié)合起來。56練習(xí)577.3.2程序并行性的分析任務(wù)間能否并行,除了算法外