第6章陣列處理機(jī)

1、第6章 陣列處理機(jī),6.1 陣列處理機(jī)的原理 6.2 SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò) 6.3 共享主存構(gòu)形陣列處理機(jī)中并行存儲(chǔ)器的無沖突訪問 6.4 脈動(dòng)陣列處理機(jī),6.1 并行處理機(jī)原理,6.1.1陣列處理機(jī)的構(gòu)形和特點(diǎn) 1.陣列處理機(jī)的構(gòu)形 陣列處理機(jī)有兩種構(gòu)形，差別主要在于存儲(chǔ)器的組成方式和互連網(wǎng)絡(luò)的作用不同。　　圖6-1是采用分布式存儲(chǔ)器的陣列處理機(jī)構(gòu)形。,圖6-1具有分布式存儲(chǔ)器的陣列處理機(jī)構(gòu)形,為了高

2、速有效地處理向量數(shù)據(jù)，這種構(gòu)形要求能把數(shù)據(jù)合理地預(yù)分配到各個(gè)處理單元的局部存儲(chǔ)器中，使各處理單元PEi主要用自己的局存PEMi中的數(shù)據(jù)運(yùn)算。分布于各PEM的數(shù)據(jù)，可以經(jīng)系統(tǒng)數(shù)據(jù)總線從外部輸入，也可以用控制總線經(jīng)控制部件播送。在執(zhí)行向量指令時(shí)，可使用屏蔽位向量控制，讓某些PE不工作(不活躍)。運(yùn)算中，PE間可通過互連網(wǎng)絡(luò)(InterconnectionNetwork,ICN)來交換數(shù)據(jù)?；ミB網(wǎng)絡(luò)的連通路徑選擇也由控制部件統(tǒng)一控制。,處理單

3、元陣列通過控制部件接到管理處理機(jī)SC上。管理處理機(jī)是一種通用機(jī)，用于管理系統(tǒng)資源，完成系統(tǒng)維護(hù)、輸入/輸出、用戶程序的匯編及向量化編譯、作業(yè)調(diào)度、存儲(chǔ)分配、設(shè)備管理、文件管理等操作的功能。因此包括處理單元陣列、互連網(wǎng)絡(luò)和控制部件在內(nèi)的陣列處理部分，可以看成是系統(tǒng)的后端處理機(jī)。　　采用這種構(gòu)形的陣列處理機(jī)是SIMD的主流。典型機(jī)器有ILLIACⅣ、MPP、DAP、CM-2、MP-1、DAP600系列等。,圖6-2是采用集中式共享存儲(chǔ)器

4、的陣列處理機(jī)構(gòu)形。系統(tǒng)存儲(chǔ)器是由K個(gè)存儲(chǔ)分體(MM0～MMK-1)集中組成，經(jīng)互連網(wǎng)絡(luò)ICN為全部N個(gè)處理單元(PE0～PEN-1)所共享。為使各處理單元對長度為N的向量中各個(gè)元素都能同時(shí)并行處理，存儲(chǔ)分體個(gè)數(shù)K應(yīng)等于或多于處理單元數(shù)N。各處理單元在訪主存時(shí)，為避免發(fā)生分體沖突，也要求有合適的算法能將數(shù)據(jù)合理地分配到各個(gè)存儲(chǔ)分體中。,圖6-2具有集中式共享存儲(chǔ)器的陣列處理機(jī)構(gòu)形,與分布式存儲(chǔ)器構(gòu)形不同的另一個(gè)地方是互連網(wǎng)絡(luò)ICN的作用不

5、同。其互連網(wǎng)絡(luò)是用于在處理單元與存儲(chǔ)器分體之間進(jìn)行轉(zhuǎn)接構(gòu)成數(shù)據(jù)通路，希望各處理單元能高速靈活地動(dòng)態(tài)與不同的存儲(chǔ)分體相連，使盡可能多的PE能無沖突地訪問共享的主存模塊。因此有的陣列處理機(jī)稱它為對準(zhǔn)網(wǎng)絡(luò)(AlignmentNetwork)。　　采用這種構(gòu)形的典型機(jī)器有BSP。,2. 并行處理機(jī)的特點(diǎn) 并行處理機(jī)的單指令流多數(shù)據(jù)流處理方式和由它產(chǎn)生的特殊結(jié)構(gòu)是以諸如有限差分、矩陣、信號(hào)處理、線性規(guī)劃等一系列計(jì)算問題為背景

6、發(fā)展起來的。這些計(jì)算問題的共同特點(diǎn)是可以通過各種途徑把它們轉(zhuǎn)化成為對數(shù)組或向量的處理，而并行處理機(jī)正好利用多個(gè)處理單元對向量或數(shù)組所包含的各個(gè)分量同時(shí)計(jì)算， 從而獲得很高的處理速度。與同樣擅長于向量處理的流水線處理機(jī)相比，并行處理機(jī)利用的是資源重復(fù)，而不是時(shí)間重疊；利用并行性中的同時(shí)性，而不是并發(fā)性。它的每個(gè)處理單元要同等地?fù)?dān)負(fù)起各種運(yùn)算功能，但其設(shè)備利用率卻可能沒有多個(gè)單功能流水線部件那樣高。因此，只有在硬件價(jià)格有了大幅度下降及系統(tǒng)結(jié)

7、構(gòu)有了較大改進(jìn)的情況下，并行處理機(jī)才能具有較好的性能價(jià)格比。并行理機(jī)主要是靠增大處理單元個(gè)數(shù)來提高運(yùn)算速度，比起向量流水線處理機(jī)主要依靠縮短時(shí)鐘周期來說， 速度提高的潛力要大得多。,與流水線處理機(jī)不同的另一方面是陣列處理機(jī)使用簡單規(guī)整的互連網(wǎng)絡(luò)來確定處理單元間的連接?；ミB網(wǎng)絡(luò)的結(jié)構(gòu)形式限定了陣列處理機(jī)可用的解題算法，也會(huì)對系統(tǒng)多種性能指標(biāo)產(chǎn)生顯著影響，因此，互連網(wǎng)絡(luò)的設(shè)計(jì)是重點(diǎn)。　　陣列處理機(jī)在機(jī)間互連上比固定結(jié)構(gòu)的單功能流水線靈活

8、，使相當(dāng)一部分專門問題上的工作性能比流水線處理機(jī)高得多，專用性強(qiáng)得多。如果習(xí)慣上把流水線處理機(jī)歸屬于通用計(jì)算機(jī)的話，陣列處理機(jī)則被看成是一種專用計(jì)算機(jī)，它是以一定數(shù)量的專門算法為背景的。另一方面，由于總希望陣列處理機(jī)解題算法的適應(yīng)性更強(qiáng)一些，應(yīng)用面更廣一些，因此，與流水線處理機(jī)不同，陣列處理機(jī)的結(jié)構(gòu)是和采用的并行算法緊密聯(lián)系在一起的。,如上所述，陣列處理機(jī)基本上是一臺(tái)專用于向量處理的計(jì)算機(jī)，但并不是所有的運(yùn)算都可以轉(zhuǎn)化為向量運(yùn)算，總有不

9、少標(biāo)量運(yùn)算。作為整個(gè)系統(tǒng)的等效速度來講，除向量運(yùn)算速度外，在很大程度上還受標(biāo)量運(yùn)算速度和編譯開銷的大小所影響。如果一臺(tái)機(jī)器的向量處理速度極高，甚至不受限制，而標(biāo)量速度只是每秒一億次浮點(diǎn)運(yùn)算，那么對于標(biāo)量運(yùn)算占10%的題目來講，系統(tǒng)總的等效速度最多也不會(huì)超過每秒十億次浮點(diǎn)運(yùn)算。所以，提高標(biāo)量的處理能力是很重要的，這就要求陣列處理機(jī)系統(tǒng)的控制部件必須是一臺(tái)具有高性能、強(qiáng)功能的標(biāo)量處理機(jī)，減少標(biāo)量運(yùn)算對系統(tǒng)性能的影響。,至于編譯時(shí)間的多少，則

10、不僅與陣列機(jī)結(jié)構(gòu)有關(guān)，也與機(jī)器語言的并行性程度有關(guān)，特別是想要提高陣列處理機(jī)的通用性，建立一個(gè)有向量化功能的高級語言編譯程序就是非常必要的了。正因?yàn)槿绱耍嚵刑幚頇C(jī)還必須用一臺(tái)高性能單處理機(jī)作為管理計(jì)算機(jī)來配合工作，運(yùn)行系統(tǒng)的全部管理程序。所以，陣列處理機(jī)實(shí)質(zhì)上是由專門對付數(shù)組運(yùn)算的處理單元陣列組成的處理機(jī)、專門從事處理單元陣列的控制及標(biāo)量處理的處理機(jī)和專門從事系統(tǒng)輸入/輸出及操作系統(tǒng)管理的處理機(jī)組成的一個(gè)異構(gòu)型多處理機(jī)系統(tǒng)。,6.1.

11、2　ILLIACⅣ的處理單元陣列結(jié)構(gòu)　　由于陣列處理機(jī)上的并行算法的研究是與結(jié)構(gòu)緊密聯(lián)系在一起的，因此，下面先介紹一下ILLIACⅣ陣列機(jī)上處理單元的互連結(jié)構(gòu)。ILLIACⅣ是采用如圖6-1所示的分布存儲(chǔ)器構(gòu)形，其處理單元陣列結(jié)構(gòu)如圖6-3所示。其中，PUi為處理部件，包含64位的算術(shù)處理單元PEi、所帶的局部存儲(chǔ)器PEMi和存儲(chǔ)邏輯部件MLU。64個(gè)處理部件PU0～PU63排列成8×8的方陣，任何一個(gè)PUi只與其上、下、

12、左、右4個(gè)近鄰PUi-8(mod64)、PUi+8(mod64)、PUi-1(mod64)和PUi+1(mod64)直接相連。,上下同一列兩端的PU連成環(huán)，左右每一行右端的PU與下一行左端的PU相連，最下面一行右端的PU與最上面一行左端的PU相連，從而形成一個(gè)閉合的螺線形狀，所以稱其為閉合螺線陣列。在這個(gè)陣列中，步距不等于±1或±8的任意單元之間可以用軟件尋找最短路徑進(jìn)行通信，其最短距離不超過7步。例如，信息由PU

13、63送PU10,可經(jīng)PU63→PU7→PU8→PU9→PU104步實(shí)現(xiàn)，信息由PU9送PU45可經(jīng)PU9→PU1→PU57→PU56→PU48→PU47→PU46→PU457步實(shí)現(xiàn)。普遍來講，　　　　　　個(gè)處理單元組成的陣列中，任意兩個(gè)處理單元之間的最短距離不超過　　　　步。,圖6-3　ILLIACⅣ處理單元的互連結(jié)構(gòu),ILLIACⅣ的處理單元是累加器型運(yùn)算器，把累加寄存器RGA中的數(shù)據(jù)和存儲(chǔ)器中來的數(shù)據(jù)進(jìn)行運(yùn)算，結(jié)果保留在累加寄存器

14、RGA中。每個(gè)處理單元內(nèi)有一個(gè)數(shù)據(jù)傳送寄存器RGR收發(fā)數(shù)據(jù)，實(shí)現(xiàn)數(shù)據(jù)在處理單元之間的傳送，并有一個(gè)屏蔽觸發(fā)器，用來控制讓該P(yáng)Ui是否被屏蔽掉，使之不參與向量指令的操作。,6.1.3ILLIACⅣ的并行算法舉例　　1.矩陣加　　陣列處理機(jī)解決矩陣加是最簡單的一維情況。兩個(gè)8×8的矩陣A、B相加，所得的結(jié)果矩陣C也是一個(gè)8×8的矩陣。只需把A、B、C居于相應(yīng)位置的分量存放在同一個(gè)PEM內(nèi)，且在全部64個(gè)PEM中，

15、讓A、B和C的各分量地址均對應(yīng)取相同的地址α、α+1和α+2，如圖6-4所示。這樣，實(shí)現(xiàn)矩陣加只需用下列三條ILLIACⅣ匯編指令：,LDA　　　ALPHA;全部(α)由PEMi送PEi的累加器RGAiADRN ALPHA+1 ;全部(α+1)與(RGAi)浮點(diǎn)加，結(jié)果送　RGAi STA 　 ALPHA+2 ;全部(RGAi)由PEi送PEMi的α+2單元 其中，0≤i≤63。,圖6-4矩陣相

16、加的存儲(chǔ)器分配舉例,2.矩陣乘　　矩陣乘是二維數(shù)組運(yùn)算，比矩陣加要復(fù)雜。設(shè)A、B和C為3個(gè)8×8的二維矩陣，給定A和B，計(jì)算C=A×B的64個(gè)分量可用公式,其中，0≤i≤7且0≤j≤7。,在SISD計(jì)算機(jī)上求解，可執(zhí)行FORTRAN語言編寫的下列程序：DO10I=0,7DO10J=0,7C(I,J)=0DO10K=0,7　10 C(I,J)=C(I,J)+A(I,K)*B(K,J),需

17、經(jīng)I、J、K三重循環(huán)完成。每重循環(huán)執(zhí)行8次，共需512次乘、加的時(shí)間，且每次還要包括執(zhí)行循環(huán)控制判別等其它操作所需的時(shí)間。如果在SIMD陣列處理機(jī)上運(yùn)算，可用8個(gè)處理單元并行計(jì)算矩陣C(I,J)的某一行或一列，即將J循環(huán)或I循環(huán)轉(zhuǎn)化成一維的向量處理，從而消去了一重循環(huán)。以消去J循環(huán)為例，可執(zhí)行用FORTRAN語言編寫的下列程序：,DO10I=0,7C(I,J)=0DO10K=0,710 　 C(I,J)=C(I,J)+A

18、(I,K)*B(K,J),圖6-5矩陣乘程序執(zhí)行流程圖,需要說明的是其執(zhí)行過程雖與SISD的類似，但實(shí)際的解決方式是不同的。每次控制部件執(zhí)行的PE類指令表面上是標(biāo)量指令，實(shí)際上已等效于向量指令，如向量取、向量存、向量加、向量乘等，是8個(gè)PE并行地執(zhí)行同一條指令。每次播送時(shí)，利用陣列處理機(jī)的播送功能將處理單元PEK中累加寄存器RGAK的內(nèi)容經(jīng)控制部件(CU)播送到全部8個(gè)處理單元的RGA中去?！　∪欢鵀榱俗尭鱾€(gè)處理單元PEi盡可能只訪問

19、所帶局部存儲(chǔ)器PEMi，以保證高速處理，就必須要求對矩陣A、B、C各分量在局部存儲(chǔ)器中的分布采用如圖6-6所示的方案。,圖6-6　矩陣乘的存儲(chǔ)器分配舉例,如果想把ILLIACⅣ的64個(gè)處理單元全部利用起來并行運(yùn)算，即把K循環(huán)的運(yùn)算也改為并行，還可進(jìn)一步提高速度，但需要在陣列存儲(chǔ)器中重新恰當(dāng)?shù)胤峙鋽?shù)據(jù)。同時(shí)還要使8個(gè)中間積A(I,K)×B(K,J)能夠并行相加(其中0≤K≤7)，這就要用到下面的累加和并行算法。即使如此，就K的并

20、行來說，速度的提高也不是8倍，而只是8/log28，接近于2.7倍。,3.累加和　　這是一個(gè)將N個(gè)數(shù)的順序相加轉(zhuǎn)為并行相加的問題。為得到各項(xiàng)累加的部分和與最后的總和，要用到處理單元中的活躍標(biāo)志位。只有處于活躍狀態(tài)的處理單元才能執(zhí)行相應(yīng)的操作。為敘述方便取N=8，即有8個(gè)數(shù)A(I)順序累加，其中0≤I≤7。　　在SISD計(jì)算機(jī)上可以寫成下列FORTRAN程序：C=0DO　10　I=0,710 C=C+A(I)這

21、是一個(gè)串行程序，需要8次加法時(shí)間。,在陣列處理機(jī)上用成對遞歸相加算法，只需log28=3次加法時(shí)間即可。首先，原始數(shù)據(jù)A(I)分別存放在8個(gè)PEM的α單元中，其中，0≤I≤7。然后，按下面的步驟求累加和： 　　(1)置全部PEi為活躍狀態(tài),0≤i≤7;　　(2)全部A(I)從PEMi的α單元讀到相應(yīng)PEi的累加寄存器RGAi中，0≤i≤7；　　(3)令K=0; 　　(4)將全部PEi的(RGAi)轉(zhuǎn)送到傳送寄存

22、器RGRi,0≤i≤7;,(5)將全部PEi的(RGRi)經(jīng)過互連網(wǎng)絡(luò)向右傳送2K步距，0≤i≤7；　　(6)令j=2K-1;　　(7)置PE0～PEj為不活躍狀態(tài)；　　(8)處于活躍狀態(tài)的所有PEi執(zhí)行(RGAi):=(RGAi)+(RGRi),j＜i≤7；　　(9)K:=K+1；　　(10)如K＜3，則轉(zhuǎn)回(4)，否則往下繼續(xù)執(zhí)行；　　(11)置全部PEi為活躍狀態(tài)，0≤i≤7;　　(12)將全部PEi

23、的累加寄存器內(nèi)容(RGAi)存入相應(yīng)PEMi的α+1單元中，0≤i≤7。,圖6-7描繪了陣列處理機(jī)上累加和的計(jì)算過程?？蛑械臄?shù)字表明各處理單元每次循環(huán)后相加的結(jié)果。圖中用數(shù)字0 ～ 7分別代表A(0)～A(7)。畫有陰影線的處理單元表示此時(shí)不活躍。另外，圖中對上述第(5)步中PE的(RGRi)在右移時(shí)超出PE7的內(nèi)容沒有表示出來，這是因?yàn)槿粲乙撇骄酁?K(mod8)，應(yīng)移入PE0～PEj，而這些PE在第(7)步將要置為不活躍，所以無論它

24、的RGR接收什么內(nèi)容都不會(huì)對執(zhí)行結(jié)果有影響。,圖6-7陣列處理機(jī)上累加和的計(jì)算過程,,6.2　SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò),6.2.1互連網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)與互連函數(shù)　　在SIMD計(jì)算機(jī)中，無論是處理單元之間，還是處理單元與存儲(chǔ)分體之間，都要通過互連網(wǎng)絡(luò)進(jìn)行信息交換。在大規(guī)模集成電路和微處理器飛速發(fā)展的今天，建造多達(dá)214～216個(gè)處理單元的陣列處理機(jī)已成為現(xiàn)實(shí)，但如果要求任意兩個(gè)處理單元之間都有直接的通路，則互連網(wǎng)絡(luò)的連線將多得無法實(shí)現(xiàn)

25、。因此，采取讓相鄰的處理單元之間只有有限的幾種直連方式，經(jīng)過一步或少量幾步傳送即可實(shí)現(xiàn)任何兩個(gè)處理單元間為完成解題算法所需的信息傳送。,SIMD系統(tǒng)的互連網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)是：結(jié)構(gòu)不要過分復(fù)雜，以降低成本；互連要靈活，以滿足算法和應(yīng)用的需要；處理單元間信息交換所需傳送步數(shù)要盡可能少，以提高速度性能；能用規(guī)整單一的基本構(gòu)件組合而成，或者經(jīng)多次通過或者經(jīng)多級連接來實(shí)現(xiàn)復(fù)雜的互連，使模塊性好，以便于用VLSI實(shí)現(xiàn)并滿足系統(tǒng)的可擴(kuò)充性。,為反映互連

26、特性，每種互連網(wǎng)絡(luò)可用一組互連函數(shù)定義。如果把互連網(wǎng)絡(luò)的N個(gè)入端和N個(gè)出端(N=2n)各自用0、1、…、N-1的整數(shù)編號(hào)代表，則互連函數(shù)就是表示互連網(wǎng)絡(luò)的出端號(hào)和入端號(hào)的一一對應(yīng)關(guān)系。定義互連網(wǎng)絡(luò)的互連函數(shù)為對于所有的入端0、1、…、j、…、N-1，同時(shí)存在入端j連至出端f(j)的函數(shù)對應(yīng)關(guān)系。在實(shí)現(xiàn)處理單元間的互連時(shí)，互連網(wǎng)絡(luò)的入端和出端實(shí)際上是同一組處理單元的出端和入端，對互連網(wǎng)絡(luò)來說，就是同一個(gè)結(jié)點(diǎn)?；ミB函數(shù)可以直接用結(jié)點(diǎn)間的連線

27、圖表示，但有時(shí)顯得繁瑣，也難以體現(xiàn)出連接上的內(nèi)在規(guī)律。因此，常用另一種簡單的函數(shù)式表示，即把所有入端x和出端f(x)都用二進(jìn)制編碼，從兩者的二進(jìn)制編碼上找出其函數(shù)規(guī)律。下面將看到這種表示的例子。,6.2.2互連網(wǎng)絡(luò)應(yīng)抉擇的幾個(gè)問題　　在確定PE之間通信的互連網(wǎng)絡(luò)時(shí)，需要對操作方式、控制策略、交換方法和網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)作出抉擇。　　操作方式有同步、異步及同步與異步組合三種?，F(xiàn)有的陣列處理機(jī)根據(jù)其SIMD性質(zhì)均采用同步操作方式，讓所

28、有PE按時(shí)鐘同步操作。異步或組合操作方式一般多用于多處理機(jī)。　　典型的互連網(wǎng)絡(luò)是由許多開關(guān)單元和互連線路組成的，互連通路的路徑選擇是通過置定開關(guān)單元的工作狀態(tài)來控制的，這種置定可以有集中或分布兩種控制策略。多數(shù)現(xiàn)有的SIMD互連網(wǎng)絡(luò)采用由集中控制部件對全部開關(guān)單元執(zhí)行集中控制的策略。,交換方法主要有線路交換、包交換及線路與包交換組合三種。線路交換是在源和目的間建立實(shí)際的連接通路，一般適合于大批數(shù)據(jù)傳輸。包交換是將數(shù)據(jù)置于包內(nèi)傳送，不

29、用建立實(shí)際的連接通路，對短數(shù)據(jù)信息傳送特別有效。SIMD互連網(wǎng)絡(luò)多采用硬連的線路交換，包交換則多用于多處理機(jī)和計(jì)算機(jī)網(wǎng)絡(luò)中。,網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)指的是互連網(wǎng)絡(luò)入、出端可以連接的模式，有靜態(tài)和動(dòng)態(tài)兩種。在靜態(tài)拓?fù)浣Y(jié)構(gòu)中，兩個(gè)PE之間的鏈?zhǔn)枪潭ǖ模偩€不能重新配置成與其他PE相連。而動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)中，兩個(gè)PE之間的鏈通過置定網(wǎng)絡(luò)的開關(guān)單元狀態(tài)可以重新配置。靜態(tài)拓?fù)溆幸痪S的線型，二維的環(huán)型、星型、樹型、胖樹型、網(wǎng)絡(luò)型、脈動(dòng)陣列型，三維的弦環(huán)型、立方

30、體型、環(huán)立方體型，以及其他復(fù)雜的連接形式。由于靜態(tài)網(wǎng)絡(luò)靈活性、適應(yīng)性差，很少使用，因此只討論動(dòng)態(tài)網(wǎng)絡(luò)。,動(dòng)態(tài)網(wǎng)絡(luò)有單級和多級兩類。動(dòng)態(tài)單級網(wǎng)絡(luò)只有有限的幾種連接，必須經(jīng)循環(huán)多次通過，才能實(shí)現(xiàn)任意兩個(gè)處理單元之間的信息傳送，故稱此動(dòng)態(tài)單級網(wǎng)絡(luò)為循環(huán)網(wǎng)絡(luò)。動(dòng)態(tài)多級網(wǎng)絡(luò)是由多個(gè)單級網(wǎng)絡(luò)串聯(lián)組成的，以實(shí)現(xiàn)任意兩個(gè)處理單元之間的連接。將多級互連網(wǎng)絡(luò)循環(huán)使用可實(shí)現(xiàn)復(fù)雜的互連，稱循環(huán)多級網(wǎng)絡(luò)或多級循環(huán)網(wǎng)絡(luò)。　　循環(huán)互連網(wǎng)絡(luò)的模型如圖6-8所示。入

31、端傳送寄存器DTRi和出端傳送寄存器DTRo除了各自與處理單元PE0～PEN-1相連分別接收和送出數(shù)據(jù)外，在不同的循環(huán)中還可以通過多路開關(guān)MUX向單級互連網(wǎng)絡(luò)送入DTRi數(shù)據(jù)，或送入在上一循環(huán)中DTRo從單級互連網(wǎng)絡(luò)接收的數(shù)據(jù)，經(jīng)單級互連網(wǎng)絡(luò)轉(zhuǎn)送再送回各自有關(guān)的DTRo，作為下一次循環(huán)的輸入。循環(huán)互連網(wǎng)絡(luò)比多級互連網(wǎng)絡(luò)節(jié)省設(shè)備，但通過時(shí)間長，并對網(wǎng)絡(luò)控制要求較高。,圖6-8循環(huán)互連網(wǎng)絡(luò)的模型,6.2.3基本的單級互連網(wǎng)絡(luò)　　1.立

32、方體單級網(wǎng)絡(luò)　　立方體單級網(wǎng)絡(luò)(Cube)的名稱來源于圖6-9所示的三維立方體結(jié)構(gòu)。立方體的每個(gè)頂點(diǎn)(網(wǎng)絡(luò)的結(jié)點(diǎn))代表一個(gè)處理單元，共有8個(gè)處理單元，用zyx三位二進(jìn)制碼編號(hào)。它所能實(shí)現(xiàn)的入、出端連接如同立方體各頂點(diǎn)間能實(shí)現(xiàn)的互連一樣，即每個(gè)處理單元只能直接連到其二進(jìn)制編號(hào)的某一位取反的其他3個(gè)處理單元上。如010只能連到000、011、110，不能直接連到對角線上的001、100、101、111。所以，三維的立方體單級網(wǎng)絡(luò)有3種互

33、連函數(shù)：Cube0、Cube1和Cube2，其連接方式如圖6-10中的實(shí)線所示。Cubei函數(shù)表示相連的入端和出端的二進(jìn)制編號(hào)只在右起第i位(i=0,1,2) 上0、1互反，其余各位代碼都相同。,圖6-9三維立方體結(jié)構(gòu),圖6-10立方體單級網(wǎng)絡(luò)連接示意 (a)Cube0;(b)Cube1;(c)Cube2,推廣到n維時(shí)，N個(gè)結(jié)點(diǎn)的立方體單級網(wǎng)絡(luò)共有n=log2N種互連函數(shù)，即,式中，Pi為入端標(biāo)號(hào)二進(jìn)制碼的第i位，且0≤i≤n-1。當(dāng)

34、維數(shù)n＞3時(shí)稱超立方體(HyperCube)網(wǎng)絡(luò)。　　顯而易見，單級立方體網(wǎng)絡(luò)的最大距離為n，即反復(fù)使用單級網(wǎng)絡(luò)，最多經(jīng)n次傳送就可以實(shí)現(xiàn)任意一對入、出端間的連接。而且任意兩個(gè)結(jié)點(diǎn)之間至少有n條不同的路徑可走，容錯(cuò)性強(qiáng)，只是距離小于n的兩個(gè)結(jié)點(diǎn)之間各條路徑的長度可能不等。,2.PM2I單級網(wǎng)絡(luò)　　PM2I單級網(wǎng)絡(luò)是“加減2i”(Plus－Minus2i)單級網(wǎng)絡(luò)的簡稱。能實(shí)現(xiàn)與j號(hào)處理單元直接相連的是號(hào)為j±2i的處

35、理單元，即,式中，0≤j≤N-1,0≤i≤n-1,n=log2N。它共有2n個(gè)互連函數(shù)。由于PM2+(n-1)=PM2-(n-1),因此PM2I互連網(wǎng)絡(luò)只有2n-1種互連函數(shù)是不同的。對于N=8的三維PM2I互連網(wǎng)絡(luò)的互連函數(shù)，有PM2+0、PM2-0、PM2+1、PM2-1、PM2±2等5個(gè)不同的互連函數(shù)，它們分別為,PM2+0:(01234567) 　 PM2-0:(76543210) 　PM

36、2+1:(0246)(1357) 　 PM2-1:(6420)(7531) 　 PM2±2:(04)(15)(26)(37)其中，(01234567)表示0連到1，與此同時(shí)，1連到2,2連到3,…，7連到0。圖6-11只畫出了其中3種互連函數(shù)的情況，PM2-0和PM2-1的連接與PM2+0和PM2+1的差別只是連接的箭頭方向相反而已?？梢娫赑M2I中，0可以直接連到1、2、4、6、7上，比立方體單級網(wǎng)絡(luò)只能

37、直接連到1、2、4的要靈活。,圖6-11　PM2I互連網(wǎng)絡(luò)的部分連接圖,3.混洗交換單級網(wǎng)絡(luò)　　混洗交換單級網(wǎng)絡(luò)(ShuffleExchange)包含兩個(gè)互連函數(shù)，一個(gè)是全混(PerfectShuffle)，另一個(gè)是交換(Exchange)。圖6-12表示8個(gè)處理單元間的全混連接?？梢钥闯觯溥B接規(guī)律是把全部按編碼順序排列的處理單元從當(dāng)中分為數(shù)目相等的兩半，前一半和后一半在連接至出端時(shí)正好一一隔開。正像洗撲克牌時(shí)先把整副牌分為兩

38、半，再通過洗牌達(dá)到“全混”，這也是“混洗”這個(gè)名詞的由來。用互連函數(shù)表示為,式中,n=log2N, Pn-1Pn-2…P1P0為入端編號(hào)的二進(jìn)制碼。,圖6-12　8個(gè)處理單元間的全混連接,Shuffle函數(shù)還有一個(gè)重要特性。如果把它再作一次Shuffle函數(shù)變換，得到的是一組新的代碼，即Pn-3…P0Pn-1Pn-2。這樣每全混一次，新的最高位就被移至最低位。當(dāng)經(jīng)過n次全混后，全部N個(gè)處理單元便又恢復(fù)到最初的排列次序。在多次全混的過程中

39、，除了編號(hào)為全“0”和全“1”的處理單元外，各個(gè)處理單元都遇到了與其他多個(gè)處理單元連接的機(jī)會(huì)。　　由于單純的全混互連網(wǎng)絡(luò)不能實(shí)現(xiàn)二進(jìn)制編號(hào)為全“0”和全“1”的處理單元與其他處理單元的連接，因此還需增加Cube0交換函數(shù)。這就是全混交換單級網(wǎng)絡(luò)，其N=8的連接如圖6-13所示。其中，實(shí)線表示交換，虛線表示全混。,圖6-13　N=8時(shí)全混交換互連網(wǎng)絡(luò)連接圖,4.蝶形單級網(wǎng)絡(luò)蝶形單級網(wǎng)絡(luò)(Butterfly)的互連函數(shù)為,Butter

40、fly (Pn-1Pn-2…P1P0)=P0Pn-2…P1Pn-1,即將二進(jìn)制地址的最高位和最低位相互交換位置。　　圖6-14為N=8個(gè)處理單元之間用蝶形單級互連網(wǎng)絡(luò)互連的情況。它實(shí)現(xiàn)的是0→0、1→4、2→2、3→6、4→1、5→5、6→3、7→7的同時(shí)連接。,圖6-148個(gè)處理單元間的蝶形單級互連,6.2.4基本的多級互連網(wǎng)絡(luò)　　最基本的多級互連網(wǎng)絡(luò)就是與上述前3種單級互連網(wǎng)絡(luò)相對應(yīng)組成的多級立方體互連網(wǎng)絡(luò)、多級混洗交換網(wǎng)絡(luò)

41、和多級PM2I網(wǎng)絡(luò)，此外，還介紹一下基準(zhǔn)網(wǎng)絡(luò)。　　不同的多級互連網(wǎng)絡(luò)，在所用的交換開關(guān)、拓?fù)浣Y(jié)構(gòu)和控制方式上各有不同。　　交換開關(guān)是具有兩個(gè)入端和兩個(gè)出端的交換單元，用作各種多級互連網(wǎng)絡(luò)的基本構(gòu)件。不論入端或出端，如果令居于上方的都用i表示，居于下方的都用j表示，則可以定義下列4種開關(guān)狀態(tài)或連接方式：,(1)直連—i入連i出，j入連j出；(2)交換—i入連j出，j入連i出；(3)上播—i入連i出和j出，j入懸空；(4

42、)下播—j入連i出和j出，i入懸空。,只有前兩種功能的稱二功能交換單元，有全部四種功能的稱四功能交換單元。兩個(gè)入端同時(shí)連到一個(gè)出端會(huì)發(fā)生信息傳送的沖突，是不允許的。此外，還可以有第5種開關(guān)狀態(tài)，即i入連j入,i出連j出，稱此為返回。它可用來實(shí)現(xiàn)入端與入端相連，出端與出端相連，從而將N個(gè)入端和N個(gè)出端的網(wǎng)絡(luò)變?yōu)?N個(gè)處理單元的互連網(wǎng)絡(luò)。,拓?fù)浣Y(jié)構(gòu)是各級間出端與入端互連的模式。上述前3種單級互連網(wǎng)絡(luò)的連接模式均可用來組合構(gòu)成不同的多級互連網(wǎng)

43、絡(luò)。　　控制方式是對各個(gè)交換開關(guān)進(jìn)行控制的方式，以多級立方體網(wǎng)絡(luò)為例，它可以有3種：　　(1)級控制——同一級的所有開關(guān)只用一個(gè)控制信號(hào)控制，同時(shí)只能處于同一種狀態(tài)；　　(2)單元控制——每一個(gè)開關(guān)都有自己獨(dú)立的控制信號(hào)控制，可各自處于不同的狀態(tài)；　　(3)部分級控制——第i級的所有開關(guān)分別用i+1個(gè)信號(hào)控制，0≤i≤n-1，n為級數(shù)。,1.多級立方體網(wǎng)絡(luò)　　多級立方體網(wǎng)絡(luò)有STARAN網(wǎng)絡(luò)、間接二進(jìn)制n方體網(wǎng)絡(luò)等。

44、以8個(gè)處理單元為例，其普遍結(jié)構(gòu)如圖6-15所示。它們的共同特點(diǎn)是：第i級(0≤i≤n-1)交換單元處于交換狀態(tài)時(shí)，實(shí)現(xiàn)的是Cubei互連函數(shù)，且都采用二功能交換單元。兩者的差別僅在于控制方式上；STARAN網(wǎng)絡(luò)采用級控制(稱交換網(wǎng)絡(luò))和部分級控制(其中可實(shí)現(xiàn)移數(shù)功能的稱移數(shù)網(wǎng)絡(luò))，而間接二進(jìn)制n方體網(wǎng)絡(luò)用單元控制。因此，后者具有更大的連接靈活性。,圖6-15　N=8多級立方體互連網(wǎng)絡(luò),STARAN網(wǎng)絡(luò)用作交換網(wǎng)絡(luò)時(shí)，采用級控制，實(shí)現(xiàn)的

45、是交換函數(shù)。所謂交換(Flip)函數(shù)是將一組元素首尾對稱地進(jìn)行交換。如果一組元素包含有2s個(gè)，則它是將所有第k個(gè)元素都與第(2s-(k+1))個(gè)元素相交換。表6-1列出了三級交換網(wǎng)絡(luò)在級控制信號(hào)采用各種不同組合情況下所實(shí)現(xiàn)的入、出端的連接。　　從表6-1可以看出，控制信號(hào)為111時(shí)，實(shí)現(xiàn)全交換，也稱鏡像交換，完成對這8個(gè)處理單元(元素)的一組8元交換，其變換圖像如下：,入端排列01234567出端排列76543210,控制

46、信號(hào)為001時(shí)，完成對這8個(gè)處理單元(元素)的4組2元交換，其變換圖像如下： 入端排列01234567出端排列10325476,表6-1 三級STARAN交換網(wǎng)絡(luò)實(shí)現(xiàn)的入、出端連接及　　　所執(zhí)行的交換函數(shù)功能 (ki為第i級控制信號(hào)),控制信號(hào)為010時(shí)，完成的功能相當(dāng)于在進(jìn)行4組2元交換后再進(jìn)行2組4元交換，其變換圖像如下：1 0 3 2 5 4 7 6出端排列　2 3 0 1

47、6 7 4 5而控制信號(hào)為101時(shí)，相當(dāng)于實(shí)現(xiàn)上述兩種交換后再進(jìn)行1組8元交換，其變換圖像如下：,總之，不管控制信號(hào)是什么狀態(tài)，實(shí)現(xiàn)的都是交換函數(shù)功能。從表6-1水平方向不難看出，任何輸入端只要通過不同的級控制信號(hào)，總可以接到任何所需要的輸出端上。　　當(dāng)STARAN網(wǎng)絡(luò)用作移數(shù)網(wǎng)絡(luò)時(shí)，采用部分級控制，控制信號(hào)分組和控制結(jié)果列在表6-2中?？梢钥闯鏊鼈兌际菆?zhí)行各種不同的移數(shù)功能的。,表6-2三級移數(shù)網(wǎng)絡(luò)能實(shí)現(xiàn)的入、出端連接及移數(shù)

48、函數(shù)功能,2.多級混洗交換網(wǎng)絡(luò)　　多級混洗交換網(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ò)中各級編號(hào)的次序與多級立方體網(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ù)流向是級號(hào)n-1、

49、n-2、…、1、0,用四功能交換單元，后者數(shù)據(jù)流向相反，是級號(hào)0、1、…、n-1,用二功能交換單元。,圖6-16　N=8多級混洗交換網(wǎng)絡(luò),假定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

50、到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的連接。有一種辦法可以把二者統(tǒng)一起來，就是將入端和出端重新編號(hào)。,仍比較圖6-15與圖6-16，可以發(fā)現(xiàn)如果把編號(hào)Pn-1Pn-2…P1P0和P0P1…Pn-2Pn-1互換，例如，對于n=3，就是把1、4互換，3、6互換，那么兩張圖上所有交換單元上的處理單元編號(hào)配對就變成一樣的了。于是表6-1和表6-

51、2中所列STARAN網(wǎng)絡(luò)的互連函數(shù)，在按上述規(guī)則對處理單元重新編號(hào)后，便都適合于omega網(wǎng)絡(luò)，而且所有在前者運(yùn)行的SIMD程序都能向上兼容。當(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è)出端的連接。,3.多級PM2I網(wǎng)絡(luò)　　N=8的多級PM2

52、I網(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+2imodN和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將

53、信息傳到2，可以經(jīng)7→3→3→2，或7→7→1→2，或7→3→1→2等多條路徑完成。這對提高可靠性和便于集成電路化都有好處?？刂七@三類連接線的信號(hào)分別稱為平控H、下控D和上控U。為了簡化對這三類信號(hào)的產(chǎn)生，可將各級的單元分成兩組。對于第i級，讓H1i、Di1、Ui1控制第i位為“0”的那些入單元，而讓Hi2、Di2、Ui2控制第i位為“1”的那些入單元，此種多級PM2I網(wǎng)絡(luò)稱為數(shù)據(jù)變換網(wǎng)絡(luò)(DataManipulator)?？梢圆捎脝卧?/p>

54、控制增強(qiáng)對各級單元控制的靈活性，讓每一單元都有自己獨(dú)立的控制信號(hào)H、D、U,此種多級PM2I網(wǎng)絡(luò)稱為強(qiáng)化數(shù)據(jù)變換網(wǎng)絡(luò)ADM(AugmentedDataManipulator)，不過控制線多，成本較高。,圖6-17　N=8多級PM2I網(wǎng)絡(luò),ADM的拓?fù)浣Y(jié)構(gòu)和控制方式使它可以完全模仿omega網(wǎng)絡(luò)的四功能交換單元。拿x、y(x＜y)兩個(gè)入單元來說，Hx、Hy為直連，Dx、Uy為交換，Uy、Hy為下播，Dx、Hx為上播。因此，ADM可以實(shí)現(xiàn)

55、omega網(wǎng)絡(luò)的全部連接，而且其組合數(shù)還要更多。利用數(shù)據(jù)變換網(wǎng)絡(luò)可以實(shí)現(xiàn)各種靈活的移數(shù)、重復(fù)、間隔、展開等函數(shù)變換。,比較上述各種多級網(wǎng)絡(luò)，靈活性由低到高的次序是：級控制立方體、部分級控制立方體、間接二進(jìn)制n方體、omega、ADM,而復(fù)雜性和成本的次序也相應(yīng)增高。雖然這些網(wǎng)絡(luò)的設(shè)計(jì)者都提出了各自的網(wǎng)絡(luò)用途，例如STARAN網(wǎng)絡(luò)和omega網(wǎng)絡(luò)都是為了進(jìn)行存儲(chǔ)器與處理單元之間的數(shù)據(jù)變換，間接二進(jìn)制n方體網(wǎng)絡(luò)是為了連接成微處理器陣列，但從

56、上面對各種網(wǎng)絡(luò)共同性的分析可以看出，它們對多種應(yīng)用場合都是適合的。,4.基準(zhǔn)網(wǎng)絡(luò)　　圖6-18是N=8的基準(zhǔn)網(wǎng)絡(luò)。它與二進(jìn)制立方體網(wǎng)絡(luò)的逆網(wǎng)絡(luò)相似，只是在第1級的級間連接不同。它采取從輸入到輸出的級間互連為恒等、逆全混、子逆全混和恒等置換，所用交換單元均為二功能，采取單元控制。,圖6-18　N=8的基準(zhǔn)網(wǎng)絡(luò),5.多級交叉開關(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)

57、絡(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)。,圖6-19三級交叉開關(guān)網(wǎng)絡(luò)的結(jié)構(gòu),圖6-20是一個(gè)N(3,2,2)的三級交叉開關(guān)網(wǎng)絡(luò)。入、出端各有4個(gè)，如采用一

58、級交叉開關(guān)實(shí)現(xiàn)共需4×4=16個(gè)交叉點(diǎn)，每個(gè)交叉點(diǎn)為四中選1，可能比三級交叉開關(guān)實(shí)現(xiàn)要便宜，盡管每個(gè)結(jié)點(diǎn)只需二中選1。一般來說，N(m,n,r)的多級交叉開關(guān)交叉結(jié)點(diǎn)總數(shù)為,C=r(n×m)+m(r×r)+r(m×n)=mr(2n+r),而一級交叉開關(guān)結(jié)點(diǎn)數(shù)為n2個(gè)。因此，當(dāng)n值較大時(shí)，使mr(2n+r)＜n2，這時(shí)，采用多級交叉開關(guān)網(wǎng)絡(luò)互連，既保證了無阻塞連接，也降低了互連網(wǎng)絡(luò)的成本，而且便于工

59、程實(shí)現(xiàn)。,圖6-20N(3,2,2)多級交叉開關(guān)互連網(wǎng)絡(luò),6.多級蝶式網(wǎng)絡(luò)　　圖6-21是由16個(gè)8×8交叉開關(guān)作為基本構(gòu)件組成的二級蝶式網(wǎng)絡(luò)，級間采用8路混洗，構(gòu)成了64×64的蝶式互連?！　≡儆闷渑c64個(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=

60、192個(gè)8×8的交叉開關(guān)。如果要構(gòu)造更大的蝶式網(wǎng)絡(luò)只需增加級數(shù)即可。但蝶式網(wǎng)絡(luò)不能實(shí)現(xiàn)播送，只是omega網(wǎng)絡(luò)的一個(gè)有限制的子集。,圖6-21　用8×8交叉開關(guān)構(gòu)造的二級64×64的蝶式互連網(wǎng)絡(luò),圖6-22用8×8交叉開關(guān)作為基本構(gòu)件擴(kuò)充成512×512的三級蝶式互連網(wǎng)絡(luò),6.2.5全排列網(wǎng)絡(luò)　　如果互連網(wǎng)絡(luò)是從N個(gè)入端到N個(gè)出端的一到一的映射，就可以把它看成是對此N個(gè)端的重新排列，

61、因此互連網(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ù)雜、成本高。

62、,阻塞式網(wǎng)絡(luò)在一次傳送中不可能實(shí)現(xiàn)N個(gè)端的任意排列。大家知道N個(gè)端的全部排列有N!種?？墒?，用單元控制的n=log2N級間接二進(jìn)制n方體網(wǎng)絡(luò)(因?yàn)?到1映像，用不上播送，所以開關(guān)只需用二功能)，每級有N/2個(gè)開關(guān)，n級互連網(wǎng)絡(luò)共用(N·log2N)/2個(gè)二功能的交換開關(guān)，這樣，全部開關(guān)處于不同狀態(tài)的總數(shù)為2(N·log2N)/2，即NN/2種。當(dāng)N為大于2的整數(shù)時(shí)，總有NN/2＜N!，就是說它無法實(shí)現(xiàn)所有N!種排列。

63、以N=8的三級網(wǎng)絡(luò)為例，共12個(gè)二功能交換開關(guān)，只有212=4096種不同狀態(tài)，最多只能控制對端子的4096種排列，不可能實(shí)現(xiàn)全部8!=40320種排列，所以多對入、出端要求同時(shí)連接時(shí)就可能發(fā)生沖突。,然而，只要對這個(gè)多級互連網(wǎng)絡(luò)通行兩次，每次通行時(shí)讓各開關(guān)處于不同狀態(tài)就可滿足對N個(gè)端子的全部N!種排列。因?yàn)榇藭r(shí)全部開關(guān)的總狀態(tài)數(shù)有NN/2·NN/2=NN種，足以滿足N!種不同排列的開關(guān)狀態(tài)要求。這種只要經(jīng)過重新排列已有入、出

64、端對的連接，就可完成所有可能的入、出端間的連接而不發(fā)生沖突的互連網(wǎng)絡(luò)稱為可重排列網(wǎng)絡(luò)([WTBZ]RearrangeableNetwork)。實(shí)現(xiàn)時(shí)，可以在上述任何一種基本多級互連網(wǎng)絡(luò)的出端設(shè)置鎖存器，使數(shù)據(jù)在時(shí)間上順序通行兩次，這實(shí)際上就是循環(huán)多級互連網(wǎng)絡(luò)的實(shí)現(xiàn)思路。,用多級網(wǎng)絡(luò)也可以實(shí)現(xiàn)全排列網(wǎng)絡(luò)。將log2N級的N個(gè)入端和N個(gè)出端的互連網(wǎng)絡(luò)和它的逆網(wǎng)絡(luò)連在一起，這樣可以省去中間完全重復(fù)的一級，得到總級數(shù)為2log2N-1級的全排

65、列網(wǎng)絡(luò)。圖6-23就是以三級基準(zhǔn)網(wǎng)絡(luò)和它的逆網(wǎng)絡(luò)連在一起，省出中間重復(fù)的一級后構(gòu)成的全排列網(wǎng)絡(luò)，稱此網(wǎng)絡(luò)為[WTBZ]Benes網(wǎng)絡(luò)。該網(wǎng)絡(luò)至少有兩個(gè)以上的通道能滿足一對結(jié)點(diǎn)的互連要求，即數(shù)據(jù)尋徑不惟一，有較多的冗余，這有利于選擇合適的路徑傳送，可靠性、靈活性較好。,圖6-23多級全排列網(wǎng)絡(luò)舉例([WTBZ]Benes網(wǎng)絡(luò)),,6.3　共享主存構(gòu)形陣列處理機(jī)中并行存儲(chǔ)器的無沖突訪問,在共享主存構(gòu)形的陣列處理機(jī)中，存儲(chǔ)器頻寬要與多個(gè)處理單

66、元的速率匹配，存儲(chǔ)器就必須采用多體并行組成。此外，還要保證在各種訪問模式下，存儲(chǔ)器都能實(shí)現(xiàn)無沖突地工作。只有這樣，存儲(chǔ)器的實(shí)際頻寬才不會(huì)下降，從而使陣列處理機(jī)的數(shù)組并行處理的性能不至于下降。對數(shù)組訪問的模式是多樣的，可能要訪問數(shù)組的行、列、主對角線、次對角線的全部元素或其中某個(gè)子方陣。,首先，以一維數(shù)組為例，假定并行存儲(chǔ)器分體數(shù)m為4，交叉存放一維數(shù)組a0、a1、a2、…,如圖6-24所示。那么，每次訪問相連的m個(gè)元素，并依此不間斷地訪

67、問下去，是不會(huì)發(fā)生訪存沖突的。然而，若遇到按2變址，訪問奇數(shù)或偶數(shù)下標(biāo)的元素時(shí)，則因訪存沖突會(huì)使存儲(chǔ)器的實(shí)際頻寬降低一半。在并行遞歸算法中，對向量子集的各元素逐次按2的整數(shù)冪相間訪問，是典型的訪問模式。例如，先是相連訪問，然后按2、4、8等變址。對于這類算法，并行存儲(chǔ)器體數(shù)取成傳統(tǒng)的2的整數(shù)冪就不適應(yīng)了。所以，從這點(diǎn)出發(fā)，并行存儲(chǔ)的分體數(shù)m應(yīng)取成質(zhì)(素)數(shù)，才能較好地避免存儲(chǔ)器訪問的沖突。只要變址跳距與m互質(zhì)，存儲(chǔ)器訪問就總能無沖突地進(jìn)

68、行。,圖6-24一維數(shù)組的存儲(chǔ)(m=4),對于多維數(shù)組，設(shè)計(jì)存儲(chǔ)器方案所考慮的問題就要復(fù)雜一些了。為簡單起見，下面以二維數(shù)組來討論，其結(jié)論同樣也適用于多維數(shù)組。假設(shè)主存有m個(gè)分體并行，從中訪問有n個(gè)元素的數(shù)組子集。這n個(gè)元素的變址跳距對于二維數(shù)組的行、列、主對角線、次對角線都是不一樣的，但要求都能實(shí)現(xiàn)無沖突訪問。如果設(shè)m=n=4,一個(gè)4×4的二維數(shù)組直接按行存儲(chǔ)的方案如圖6-25所示。雖然，同時(shí)訪問某一行、主對角線或次對角線上

69、的所有元素時(shí)，都可以無沖突地訪問，但要同時(shí)訪問某一列的元素時(shí)，由于它們集中存放在同一存儲(chǔ)分體內(nèi)，會(huì)產(chǎn)生訪存沖突，因此每次只能訪問其中的一個(gè)元素，使實(shí)際頻寬降低到1/4。,圖6-25　4×4數(shù)組的直接按行存儲(chǔ)(m=n=4),為了能使行或列的各元素都能并行訪問，采取將數(shù)據(jù)在存儲(chǔ)器中錯(cuò)位存放，如圖6-26所示。但是該方案可造成主對角線上各元素的并行訪問沖突，致使實(shí)際頻寬下降一半，次對角線上各元素的訪問則都發(fā)生沖突，使實(shí)際頻寬降低成與