第5章并行處理技術(shù)(簡)

主講人鄭曉薇計算機(jī)系統(tǒng)結(jié)構(gòu)第5章遼寧師范大學(xué)計算機(jī)科學(xué)系第五章并行處理技術(shù)5.1并行處理技術(shù)基本概念5.2SIMD并行計算機(jī)5.3計算機(jī)互連網(wǎng)絡(luò)并行處理技術(shù)是獲取高性能計算的重要途徑。并行處理技術(shù)主要是通過資源重復(fù)實現(xiàn)的，它既可實現(xiàn)數(shù)據(jù)并行性（如SIMD陣列處理機(jī)），還可以實現(xiàn)作業(yè)、任務(wù)的并行性（如MIMD多處理機(jī)）。本章學(xué)習(xí)SIMD陣列處理機(jī)有關(guān)概念，互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的相關(guān)知識。重點是（1）系統(tǒng)結(jié)構(gòu)中的并行性（2）SIMD陣列處理機(jī)，（3）互連網(wǎng)絡(luò)，（4）靜態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，（5）動態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)第五章要求

第五章并行處理技術(shù)

5.1計算機(jī)系統(tǒng)結(jié)構(gòu)中并行性的發(fā)展5.1.1并行性的基本概念1.并行性的定義所謂并行性(parallelism)是指在數(shù)值計算、數(shù)據(jù)處理、信息處理或是人工智能求解過程中可能存在某些可同時進(jìn)行運算或操作的部分。開發(fā)并行性的目的是為了能進(jìn)行并行處理，以提高計算機(jī)系統(tǒng)求解問題的效率。并行性有二重含義:即同時性(simultaneity)和并發(fā)性(concurrency)。同時性是指同一時刻發(fā)生的兩個或多個事件，如超標(biāo)量流水處理機(jī)中多條指令的并行解釋。而并發(fā)性則是指同一時間間隔內(nèi)發(fā)生的兩個或多個事件，如流水處理過程。并行處理著重開發(fā)計算過程中存在的并發(fā)事件。2.并行處理的概念所謂并行處理是指一種相對于串行處理的信息處理方式，它著重開發(fā)計算過程中存在的并發(fā)事件。在進(jìn)行并行處理時，其每次處理的規(guī)模大小可能是不同的，這可用并行性顆粒度(granularity)來表示。顆粒度是指計算時間與通信時間的比值。并行顆粒度用G表示：其中：Tw所有處理機(jī)進(jìn)行計算的時間總和，

Tc

所有處理機(jī)通信時間的總和當(dāng)Tw>Tc時，稱為粗粒度，G≥1（計算時間>通信時間）,當(dāng)Tc>Tw時，稱為細(xì)粒度，G＜1（通信時間>計算時間）由G的表達(dá)式可見，當(dāng)工作負(fù)載一定時，粒度愈細(xì)，表明通信開銷愈大；反之，粒度愈粗，表明通信開銷愈小。另一種描述：顆粒度的大小一般分為細(xì)粒度、中粒度和粗粒度三種，若程序段中指令條數(shù)小于500條，則稱為細(xì)粒度，500條到2000條指令之間則稱為中粒度，大于2000條則稱為粗粒度。粗粒度算法多用于計算上，如單頻地震碼和繪圖程序，非常粗粒度絕大部分時間用于計算，通信量很少，稱之為“難堪的并行應(yīng)用”或自然的并行應(yīng)用。細(xì)粒度的通信量較大，如非結(jié)構(gòu)的網(wǎng)格碼等。3.并行性的等級并行性有不同的等級，而且從不同角度來觀察時，會有不同的劃分方法。在程序執(zhí)行過程中，根據(jù)并行進(jìn)程中顆粒度的大小不同，通?？蓜澐殖梢韵挛鍌€等級：作業(yè)級、任務(wù)級、例行程序或子程序級、循環(huán)和迭代級以及語句和指令級，如圖5.1所示。圖5.1程序執(zhí)行過程中的不同層次的并行性粗細(xì)粗粒度并行性的開發(fā)主要采用MIMD方式，它開發(fā)的主要是功能并行性。而細(xì)粒度并行性的開發(fā)則主要采用SIMD方式，它開發(fā)的主要是數(shù)據(jù)并行性。5.1.2實現(xiàn)并行性技術(shù)的途徑1.時間重疊（time-interleaving）

時間重疊是指在并行性概念中引入時間因素，讓多個處理過程在時間上相互錯開，輪流重疊地使用同一套硬件設(shè)備的各個部分，以加快硬件周轉(zhuǎn)而贏得速度。2.資源重復(fù)（resource-replication）

資源重復(fù)是指在并行性概念中引入空間因素，通過重復(fù)設(shè)置硬件資源來提高可靠性或性能。多處理機(jī)本身就是資源重復(fù)的結(jié)果。例如陣列處理機(jī)，它通過設(shè)置多個處理單元，在同一控制器的控制下，各執(zhí)行部件同時對分配給自己的數(shù)據(jù)完成同一種運算，利用資源重復(fù)的方式來提高整個系統(tǒng)的性能。3.資源共享（resource-sharing）

資源共享是指利用軟件的方法讓多個任務(wù)按一定時間順序輪流地使用同一套資源，以提高其利用率，這樣相應(yīng)地也可以提高整個系統(tǒng)的性能。例如利用共享CPU、主存資源、大容量的磁盤存儲器等，以降低系統(tǒng)價格，提高設(shè)備利用率，如多道程序、分時系統(tǒng)、計算機(jī)網(wǎng)絡(luò)等。5.2SIMD并行處理機(jī)SIMD計算機(jī)是以單一控制部件控制下的多個處理單元構(gòu)成的陣列，也稱為陣列處理機(jī)。SIMD主要用于大量高速向量或矩陣運算的場合。向量處理機(jī)和陣列處理機(jī)都能對大量數(shù)據(jù)進(jìn)行向量處理，但它們之間有很大區(qū)別。陣列處理機(jī)的特點為：

1.陣列機(jī)是以單指令流多數(shù)據(jù)流方式工作的。2.陣列機(jī)采用資源重復(fù)方法引入空間因素，即在系統(tǒng)中設(shè)置多個相同的處理單元來開發(fā)并行性。3.陣列機(jī)是以某一類算法為背景的專用計算機(jī)。4.從處理單元來看，由于結(jié)構(gòu)都相同，因而可將陣列機(jī)看成是一個同構(gòu)型并行機(jī)。但它的控制器實質(zhì)上是一個標(biāo)量處理機(jī)，而為了完成I/O操作以及操作系統(tǒng)的管理，尚需一個前端機(jī)，因此實際的陣列機(jī)系統(tǒng)是由上述三部分構(gòu)成的一個異構(gòu)型多處理機(jī)系統(tǒng)。并行處理5.2.1陣列機(jī)的基本結(jié)構(gòu)由一個控制器CU，N個處理單元PE，M個存儲器模塊以及一個互連網(wǎng)絡(luò)部件IN組成。陣列機(jī)按存儲器形式分成兩種結(jié)構(gòu)。并行處理圖5.1分布式存儲器結(jié)構(gòu)的陣列處理機(jī)1．

分布式存儲器陣列機(jī)。

圖5.2分布式存儲器陣列機(jī)特點：①

有N個相同的處理單元PE，PE由處理器和局部存儲器構(gòu)成，各個PE通過IN實現(xiàn)數(shù)據(jù)交換。②

CU中有自己的存儲器，由于存放系統(tǒng)程序和用戶程序，以及各PE的共享數(shù)據(jù)。CU主要做指令譯碼以及判別指令在何處執(zhí)行。③

各PE同步執(zhí)行來自CU的操作指令。CU可對PE進(jìn)行屏蔽，還控制互連網(wǎng)絡(luò)IN，使各PE的數(shù)據(jù)通過IN交換。并行處理SMK-1SM0主機(jī)控制部件存儲器（程序與數(shù)據(jù)）標(biāo)量處理機(jī)大容量存儲器陣列控制部件互連網(wǎng)絡(luò)PE0SM1PE1PEN-1標(biāo)量指令向量指令指令廣播總線網(wǎng)絡(luò)控制數(shù)據(jù)總線I/O用戶······圖5.3集中式共享存儲器結(jié)構(gòu)的陣列處理機(jī)2．

共享存儲器陣列機(jī)

Mn-1M1M0 INCU

PEn-1PE1PE0圖5.4共享存儲器陣列機(jī)特點：①

每個PE沒有局部存儲器。存儲器模塊以集中式供所有PE共享。②

互連網(wǎng)絡(luò)受CU控制。系統(tǒng)中的PE可與任一PE交換數(shù)據(jù)。陣列機(jī)的特征用公式描述：C=[N，F(xiàn)，I，M]

其中：

N：PE數(shù)，F(xiàn)：互連參數(shù)，I：指令集?？蛇M(jìn)行標(biāo)量、向量、數(shù)據(jù)傳送、網(wǎng)絡(luò)變換等操作。

M：屏蔽方式集合?？蓪E分為活躍和非活躍兩種PE子集。5.2.2陣列機(jī)并行算法陣列機(jī)可求解有限差分，矩陣計算，信號處理，圖像處理等一系列計算問題。因此，陣列機(jī)的研究必須與并行算法的研究密切結(jié)合，以使它的求解算法具有更強的適應(yīng)性和更廣的應(yīng)用面。并行處理1.矩陣加并行算法在陣列處理機(jī)上解決矩陣加算法問題比較簡單，屬于一維數(shù)組運算。設(shè)A和B是n×n階矩陣，A、B的和矩陣為C，它也是n×n階矩陣。矩陣加的算法為：

A+B=C=(cij)n×ncij=aij+bij并行處理【例】兩個8*8的矩陣A和B的求和運算[解]

只需把矩陣A和B居于相應(yīng)位置的一對分量存放在同一個PEM內(nèi)?，F(xiàn)令A(yù)的分量在全部64個PEM中存放的單元地址碼均為m，B的分量單元地址碼均為m+1，而C=A+B的結(jié)果分量均放在地址碼為m+2的單元內(nèi)，參見圖5.5。A（0，0）B（0，0）C（0，0）A（0，1）B（0，1）C（0，1）A（7，7）B（7，7）C（7，7）m+1mm+2PEM0PEM1PEM63圖5.5矩陣加法的存儲器分配與順序處理相比，由于64個處理單元并行操作，故速度可提高64倍。2.遞歸折疊求和算法對求累加和這樣的操作，為了加快并行計算，常采用遞歸折疊求和算法。【例】某一向量含有N個向量元素，現(xiàn)要求出這些元素的累加和。如在8個處理器上對8個向量元素的向量求累加和。如圖5.7，8個PE的遞歸折疊求和算法。[解]用陣列機(jī)的N個處理機(jī)來求和，且假定每個處理器已事先分配一個向量元素。A0+A1A0+A1+A2+A3A0+A1+A2+A3+A4+A5+A6+A7A0A2A3A4A5A6A7A1A2+A3A4+A5A6+A7A4+A5+A6+A7PE0PE1PE2PE3PE4PE5PE6PE7PE機(jī)向量值步1 步2 步3圖5.78個PE的遞歸折疊求和算法并行處理結(jié)論：

某些串行計算的問題可以用并行算法得到解決，并有較好的加速比。一般情況下，N個向量元素在N個處理器上求累加和只需要log2N次傳送操作和加法操作。而在串行計算中則需要N-1次加法操作。例N=8，LOG28=3（次）。

5.2.3典型SIMD計算機(jī)1.IlliacIV陣列處理機(jī)

IlliacIV陣列處理機(jī)是美國寶來公司和伊利諾大學(xué)合作研制生產(chǎn)的機(jī)器，它是最早(1972年)問世的SIMD計算機(jī)。

IlliacIV系統(tǒng)的總框圖參見圖5.9。實際上，它是一個由三種類型處理機(jī)聯(lián)合組成的多機(jī)系統(tǒng)：1.專門用于數(shù)組運算的處理部件(PU)陣列；

2.陣列控制器(CU)，它既是處理單元陣列的控制部分，又可以看作一臺相對獨立的小型標(biāo)量處理機(jī)；

3.一臺標(biāo)準(zhǔn)的B6700計算機(jī)，擔(dān)負(fù)IlliacIV輸入輸出系統(tǒng)和操作系統(tǒng)管理功能。。

圖5.9

IlliacIV系統(tǒng)的總框圖IlliacIV陣列：

IlliacIV陣列PU由64個處理單元(PE)、64個局部存儲器(PEM)和存儲器邏輯部件(MLU)組成。如圖5.10所示，這個陣列的64個處理部件PU0-PU63排列成8×8方陣。每一個PUi只和其上、下、左、右四個近鄰PUi-8(mod64)、PUi+8(mod64)、PUi-1(mod64)、PUi+1(mod64)有直接連接。按此規(guī)則，上下方向上同一列的PU兩端相連成一個環(huán)，左右方向上每一行的右端PU與下一行的左端PU相連，最下面一行的右端PU與最上面一行的左端PU相連，從而構(gòu)成了一個閉合的螺線形狀。。

圖5.10

IlliacIV處理部件的連接圖5.11Illiac網(wǎng)IlliacIV的陣列結(jié)構(gòu)又稱為閉合螺線陣列。如圖5.11這種連接方式既便于一維長向量(多至64個元素)的處理，又便于二維數(shù)組運算，以縮短處理單元之間的路徑距離。步距不等于+/-1或+/-8的任意處理單元間通信可用軟件方法尋找最短路徑進(jìn)行，其最短路徑都不會超過7步。推廣到一般情況，n×n個單元組成的陣列中，任意兩個處理單元之間的最短距離不會超過(n-1)步。5.3SIMD計算機(jī)互連網(wǎng)絡(luò)5.3.1互連網(wǎng)絡(luò)設(shè)計準(zhǔn)則在SIMD計算機(jī)中，在處理單元之間（具有分布式存儲器的并行處理機(jī)結(jié)構(gòu)形式）和處理單元與存儲體之間（具有集中式共享存儲器的并行處理機(jī)結(jié)構(gòu)形式）都要通過互連網(wǎng)絡(luò)實現(xiàn)信息交換?；ミB網(wǎng)絡(luò)性能對SIMD計算機(jī)系統(tǒng)的運算速度、處理單元的利用率、求解算法適應(yīng)性、拓?fù)浣Y(jié)構(gòu)靈活性以及成本等有很大影響，所以，它是SIMD計算機(jī)中重要的研究課題之一?；ミB網(wǎng)絡(luò)是一種由高速開關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)，用來實現(xiàn)計算機(jī)系統(tǒng)內(nèi)部多個處理機(jī)或多個功能部件之間的相互連接。當(dāng)前越來越多的并行計算機(jī)系統(tǒng)直接采用通用的微處理機(jī)作為結(jié)點用互連網(wǎng)絡(luò)連接而成。因此，互連網(wǎng)絡(luò)也由專用型向通用型發(fā)展。

衡量互連網(wǎng)絡(luò)性能的因素主要有結(jié)點的度、網(wǎng)絡(luò)直徑、網(wǎng)絡(luò)帶寬、可靠性和成本。在設(shè)計互連網(wǎng)絡(luò)時應(yīng)考慮以下的四個特征：

1.通信工作方式通信工作方式可分為同步和異步兩種。在同步方式中，各個PE對數(shù)據(jù)進(jìn)行并行操作都由統(tǒng)一的時鐘來加以同步。SIMD并行機(jī)都采用同步方式。異步方式則不用統(tǒng)一時鐘加以同步，各個處理單元根據(jù)需要相互建立動態(tài)連接。

2.控制策略控制策略分為集中和分散兩種。集中式控制由一個統(tǒng)一控制器對各個互連開關(guān)狀態(tài)加以控制，而分散式控制則由各個互連開關(guān)自身實行管理。一般的SIMD并行機(jī)都采用集中控制。

3.交換方式交換方式分為線路交換和分組交換兩種。

線路交換是在整個交換過程中，在源和目標(biāo)結(jié)點之間建立固定的物理通路，適用于成批數(shù)據(jù)傳送。

分組交換則把要傳送的一個信息分成多個分組，分別送入互連網(wǎng)絡(luò)。這些分組可通過不同的路由到達(dá)目標(biāo)結(jié)點。

SIMD并行機(jī)一般采用線路交換，因為處理單元間的聯(lián)接比較緊密。MIMD多機(jī)系統(tǒng)則往往采用分組交換方式。

4.網(wǎng)絡(luò)拓?fù)渚W(wǎng)絡(luò)拓?fù)浞譃殪o態(tài)和動態(tài)兩種。網(wǎng)絡(luò)拓?fù)涫侵富ミB網(wǎng)絡(luò)中各個結(jié)點間的連接關(guān)系，通常用圖來描述。5.3.2互連網(wǎng)絡(luò)與互連函數(shù)

若把處理單元看成結(jié)點，則互連網(wǎng)絡(luò)就是為輸入輸出兩組結(jié)點提供數(shù)據(jù)通路或映像。設(shè)輸入為N個，輸出為M個，則兩者之間的數(shù)據(jù)通路共有NM種，若限定為一對一映像，則只有N！種。一、

互連網(wǎng)絡(luò)的表示法為了反映不同互連網(wǎng)絡(luò)的連接特性，在輸入結(jié)點與輸出結(jié)點之間建立對應(yīng)關(guān)系，互連網(wǎng)絡(luò)通常采用以下兩種表示方法：

互連函數(shù)表示法

用輸入變量x表示輸入，用函數(shù)f(x)表示輸出，通過數(shù)學(xué)表達(dá)式建立輸入與輸出端的一一對應(yīng)關(guān)系。自變量和函數(shù)可以用二進(jìn)制表示，也可以用十進(jìn)制表示。例如輸入x用n位二進(jìn)制表示，可寫成xn-1xn-2…x1x0,互連函數(shù)則為f(xn-1xn-2…x1x0)。

互連函數(shù)反映了網(wǎng)絡(luò)輸入數(shù)組和輸出數(shù)組之間對應(yīng)的排列關(guān)系或置換關(guān)系，所以互連函數(shù)有時也稱為排列函數(shù)或置換函數(shù)。

圖形表示法用圖形表示輸入端與輸出端之間的一一對應(yīng)關(guān)系。二、常用的互連函數(shù)下面介紹常用的基本互連函數(shù)及其主要特征。1

恒等置換輸入編號和輸出編號相等，所實現(xiàn)的互換。表達(dá)式為：

I(xn-1xn-2…x1x0)=xn-1xn-2…x1x0其中xn-1xn-2…x1x0為輸入、輸出端的二進(jìn)制地址編號。恒等置換的變換圖為：0123456701234567輸入輸出x2x1x0x2x1x0E(xn-1xn-2…x1x0)=xn-1xn-2…x1x02

交換置換交換置換將輸入、輸出地址中的第0位交叉相連。表達(dá)式為：交換置換的變換圖為：0123456701234567輸入輸出x2x1x0x2x1x03

立方體置換

立方體置換是實現(xiàn)二進(jìn)制地址編碼中第k位位置不同的輸入端與輸出端之間的連接。其表達(dá)式為：

CK(xn-1xn-2…xK+1xkxK-1…x1x0)=xn-1xn-2…xK+1xkxK-1…x1x0上式是立方體置換的一般情形，它共有n=log2N種互連函數(shù)。當(dāng)結(jié)點數(shù)N＝8時，n=3，可得到常用的立方體互連函數(shù)：C0(x2x1x0)=x2x1x0

C1(x2x1x0)=x2x1x0C2(x2x1x0)=x2x1x0C0方體置換，即交換置換C1方體置換C2方體置換0123456701234567輸入輸出C1(x2x1x0)=x2x1x0C2(x2x1x0)=x2x1x00123456701234567輸入輸出C1方體置換C2方體置換立方體置換的變換圖為：三維的立方體單級網(wǎng)絡(luò)的3種互連函數(shù)：Cube0、Cube1和Cube2，立方體的連接方式如圖所示。從圖中可以看出，Cube函數(shù)下標(biāo)數(shù)字0（或1、2）表示相連的入端和出端的二進(jìn)制標(biāo)號只在右起第0位（或第1位、第2位）上有差別，即僅在該位上的代碼“0”、“1”互反，其余各位代碼都相同。推廣到n維的情形，立方體單級網(wǎng)絡(luò)共有n=log2N種互連函數(shù)，即：

Cubei（Pn-1…Pi…P1P0）=Pn-1…Pi…P1P0其中，Pi為入端標(biāo)號的二進(jìn)制代碼第i位，且0≤i≤n-1。對于n維立方體單級網(wǎng)絡(luò)，要實現(xiàn)任意兩個處理單元之間的連接，最多需使用n次不同的互連函數(shù)，因此n維立方體單級網(wǎng)絡(luò)的最大距離為n。4

均勻洗牌置換（1）均勻洗牌置換又稱全混洗置換。將輸入端分成數(shù)目相等的兩半，前一半和后一半按序一個隔一個地從頭依次與輸出端相連，類似洗撲克牌。其實質(zhì)就是把輸入端二進(jìn)制地址循環(huán)左移一位。其函數(shù)表示為：σ(xn-1xn-2…x1x0)=xn-2xn-3…x1x0xn-1若N=8，n=3：σ(x2x1x0)=x1x0x20123456701234567輸入輸出000——000001——010010——100011——110100——001101——011110——101111——111在此互連網(wǎng)絡(luò)中，如果經(jīng)過n=log2N次全混洗連接后，除了編號為全“0”和全“1”的處理器外，各個處理器都遇到了與其它處理器連接的機(jī)會。為了解決單一的全混洗互連網(wǎng)絡(luò)不能實現(xiàn)二進(jìn)制編號為全“0”和全“1”的處理器與其它任何處理器的連接，可以和Cube0交換互連函數(shù)聯(lián)合使用。同時采用了全混洗和交換的單級互連網(wǎng)絡(luò)稱為混洗交換單級互連網(wǎng)絡(luò)，其連接圖如下：圖中黑線表示全混，紅線表示交換。在混洗交換網(wǎng)絡(luò)中，最遠(yuǎn)的兩個入、出端號是全“0”和全“1”，它們的連接，需要經(jīng)過n次交換和n-1次混洗，所以混洗交換網(wǎng)絡(luò)的最大距離為2n-1。圖8個處理單元的全混交換互連網(wǎng)絡(luò)連接圖（2）子洗牌置換σ（k）(xn-1xn-2…xK+1xkxK-1…x1x0)=xn-1xn-2…xK+1xK-1…x1x0xk將xk移到最右邊。子洗牌是將數(shù)據(jù)分成若干組，對每個子組完成均勻洗牌變換。0123456701234567輸入輸出若N=8，n=3：σ(x2x1x0)=x2x0x1000——000001——010010——001011——011100——100101——110110——101111——111（3）超洗牌置換σ（k）(xn-1xn-2…xn+kxn-k-1xn-K-2…x1x0)=xn-2xn-3…xn+kxn-k-1xn-1xn-K-2…x1x0將xn-1移到xn-k-1xn-K-2之間。超洗牌對整組進(jìn)行均勻洗牌變換，但增加了數(shù)據(jù)變換寬度。0123456701234567輸入輸出若N=8，n=3：σ(x2x1x0)=x1x2x0000——000001——001010——100011——101100——010101——011110——110111——111（4）逆均勻洗牌置換逆均勻洗牌是均勻洗牌的逆函數(shù)，與均勻洗牌兩者的輸入端和輸出端正好互換位置。逆均勻洗牌函數(shù)是將輸入端二進(jìn)制地址編碼循環(huán)右移一位而得到相應(yīng)地輸出端地址。其互連函數(shù)為：σ(xn-1xn-2…x1x0)=x0xn-1xn-2xn-3…x10123456701234567輸入輸出（a）均勻洗牌置換0123456701234567輸入輸出（b）逆均勻洗牌置換均勻洗牌與逆均勻洗牌是兩種十分有用的互連函數(shù)，以它們代表的鏈路與以交換置換代表的開關(guān)多級組合起來可構(gòu)成Omega網(wǎng)絡(luò)與逆Omega網(wǎng)絡(luò)。σ函數(shù)可用于多項式求值、矩陣轉(zhuǎn)置、FFT等并行運算和并行排序。并行處理5蝶式置換名稱源于FFT變換時其圖形狀如蝴蝶。蝶式變換與交換變換的多級組合可作為構(gòu)成方體多級網(wǎng)絡(luò)的基礎(chǔ)。

（1）蝶式置換是將輸入二進(jìn)制地址的最高位和最低位互換位置，所以蝶式互連函數(shù)定義為：

β(xn-1xn-2…x1x0)=x0xn-2…x1xn-1

0123456701234567輸入輸出若N=8，n=3：β(x2x1x0)=x0x1x2000——000001——100010——010011——110100——001101——101110——011111——111（2）子蝶式置換將xk和x0

互換位置。β(xn-1xn-2…xK+1xkxK-1…x1x0)=xn-1xn-2…xK+1x0xK-1…x1xk0123456701234567輸入輸出若N=8，n=3，則子蝶式置換與子洗牌置換一樣：β(x2x1x0)=x2x0x1000——000001——010010——001011——011100——100101——110110——101111——111（3）超蝶式置換將xn-1和xn-k-1

互換。β

（k）(xn-1xn-2…xn+kxn-k-1xn-K-2…x1x0)=xn-k-1xn-2…xn-kxn-1xn-K-2…x1x0若N=8，n=3，則超蝶式置換與超洗牌置換一樣：β(x2x1x0)=x1x2x00123456701234567輸入輸出000——000001——001010——100011——101100——010101——011110——110111——1116反位序置換

（1）反位序置換是將輸入端二進(jìn)制地址的位序顛倒過來求得相應(yīng)輸出端的地址。其互連函數(shù)表示如下：ρ(xn-1xn-2…x1x0)=x0x1…xn-2xn-1

（2）子反位序置換若N=8，n=3，則子反位序置換與子蝶式置換和子洗牌置換一樣：ρ(x2x1x0)=x2x0x1（3）超反位序置換若N=8，n=3，則超反位序置換與超蝶式置換和超洗牌置換一樣：ρ(x2x1x0)=x1x2x08移數(shù)置換它是將輸入端數(shù)組循環(huán)移動一定的位置向輸出端傳輸。其表達(dá)式表示為：

a(x)=(x+k)modN 0≤x≤N其中：k為常數(shù)，表示移過的位置值?？蓪?shù)組分成若干子數(shù)組，在子數(shù)組內(nèi)進(jìn)行循環(huán)移數(shù)置換。表達(dá)式為兩個：

a(x)(n-1):r=（n-1）：r

高半段為原值

a(x)(r-1):0=((x)(r-1):0+k)mod2r

低半段為x+k若N=8，n=3，k=2,r=0，則a(x2x1x0)不分段。x+k=x+2：0123456701234567輸入輸出000——010001——011010——100011——101100——110101——111110——000111——001(1)移數(shù)置換k=2(2)段內(nèi)移數(shù)置換k=1,r=20123456701234567輸入輸出000——001001——010010——011011——000100——101101——110110——111111——100若N=8，n=3，k=1,r=2,則a(x2x1x0)的高半段為原值,低半段為x+k=x+1(x2x1x0)：9加減2i置換PM2I函數(shù)也是一種移數(shù)置換，其表達(dá)式表示為：PM2＋i(x)=x+2imodNPM2-i(x)=x-2imodN其中，0≤x≤N－1，0≤i≤n－1，n=log2N，N為結(jié)點數(shù)。顯然，PM2I互連網(wǎng)絡(luò)共有2n個互連函數(shù)。(a)i=0，x+2i=x+10123456701234567輸入輸出000——001001——010010——011011——100100——101101——110110——111111——000(b)i=+1，x+2i=x+20123456701234567輸入輸出000——010001——011010——100011——101100——110101——111110——000111——001(c)i=+2，x+2i=x+40123456701234567輸入輸出000——100001——101010——110011——111100——000101——001110——010111——011例如，對于N=8，各互連循環(huán)為：

PM2+0：（01234567）PM2-0：（76543210）PM2+1：（0246）（1357）PM2-1：（6420）（7531）PM2±2：（04）（15）（26）（37）N=8PM2I置換圖形如下：PM2I單級網(wǎng)絡(luò)的最大距離為┌n/2┐。在下圖中給出了PM2I互連網(wǎng)絡(luò)的部分連接圖。

Illiac函數(shù)是構(gòu)成IlliacⅣ陣列的基礎(chǔ)，它是PM2I函數(shù)的一個特例。

SIMD并行處理機(jī)ILLIAC-Ⅳ中的64個處理單元間的互連，實際上就是只采用了PM2I互連網(wǎng)絡(luò)中的PM2±0和PM2±3這四個互連函數(shù)。IlliacⅣ陣列計算機(jī)采用PM2±0和PM2±n/2四個互連函數(shù)構(gòu)成移數(shù)網(wǎng)絡(luò)進(jìn)行各處理器的連接，如圖5.13所示。該網(wǎng)絡(luò)可以用四個PM2I函數(shù)表示。圖5.13用移數(shù)函數(shù)構(gòu)成IlliacⅣ陣列互連網(wǎng)絡(luò)結(jié)點：1-6結(jié)點：3-95.4互連網(wǎng)絡(luò)的特性參數(shù)

網(wǎng)絡(luò)通常是用有向邊或無向邊連接有限個結(jié)點的圖來表示的?；ミB網(wǎng)絡(luò)的主要特性參數(shù)有：

網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點的個數(shù)稱為網(wǎng)絡(luò)規(guī)模，它表示該網(wǎng)絡(luò)所能連接的部件多少。

結(jié)點度：與結(jié)點相連接的邊數(shù)(通道數(shù))稱為結(jié)點度，包括入度和出度。進(jìn)入結(jié)點的邊數(shù)叫入度，從結(jié)點出來的邊數(shù)則叫出度。結(jié)點度反映了結(jié)點所需的I/O端口數(shù)。

距離：兩個結(jié)點之間相連的最少邊數(shù)。網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個結(jié)點之間距離的最大值，用結(jié)點之間的連接邊數(shù)表示。結(jié)點間的線長：兩個結(jié)點間連線的長度，用米、公里等表示。等分寬度：又稱為對剖寬度。當(dāng)某一網(wǎng)絡(luò)被切成相等的兩半時，沿切口的最小邊數(shù)(通道)稱為通道等分寬度，用b表示。而線等分寬度就是B＝b×w。其中w為通道寬度(用位表示)。該參數(shù)主要反映了網(wǎng)絡(luò)最大流量。

對稱性：從任何結(jié)點看到拓?fù)浣Y(jié)構(gòu)都是相同的網(wǎng)絡(luò)稱為對稱網(wǎng)絡(luò)。對稱網(wǎng)絡(luò)比較容易實現(xiàn)，編程也較容易。上述特性參數(shù)，在進(jìn)行系統(tǒng)設(shè)計時，需要綜合考慮。如果網(wǎng)絡(luò)直徑太大，必然導(dǎo)致網(wǎng)絡(luò)延時加大；如果結(jié)點度數(shù)增加，路徑增加，網(wǎng)絡(luò)直徑減小，延時減小，但是這將帶來成本增加。

互連網(wǎng)絡(luò)種類互連網(wǎng)絡(luò)通?？梢苑譃閮纱箢悾挫o態(tài)互連網(wǎng)絡(luò)和動態(tài)互連網(wǎng)絡(luò)。

靜態(tài)網(wǎng)絡(luò)(StaticNetworks)是指處理單元間有著固定連接的一類網(wǎng)絡(luò)，在程序執(zhí)行期間，這種點到點的鏈接保持不變。

動態(tài)網(wǎng)絡(luò)(dynamicNetworks)是用交換開關(guān)構(gòu)成的，可按運行程序的要求動態(tài)地改變連接狀態(tài)。下面先對靜態(tài)網(wǎng)絡(luò)進(jìn)行討論。5.5靜態(tài)互連網(wǎng)絡(luò)在靜態(tài)互連網(wǎng)絡(luò)中，每一個開關(guān)元件固定地與一個結(jié)點相連，建立該結(jié)點與鄰近結(jié)點之間的連接通路，直接實現(xiàn)兩結(jié)點之間的通信。

幾種靜態(tài)互連網(wǎng)絡(luò)拓?fù)潇o態(tài)的互連網(wǎng)絡(luò)拓?fù)?，用維數(shù)來分類。所謂維數(shù)(dimension)，就是它們畫在n維空間時才能使各條鏈路不會相交。

5.5.1線性陣列線性陣列(lineararray)是一種一維網(wǎng)絡(luò)，其中N個結(jié)點用N-1條鏈路連成一行，16個結(jié)點的線性陣列(lineararray)如圖5.16(a)所示。其內(nèi)部結(jié)點度為2，端結(jié)點度為1。網(wǎng)絡(luò)直徑為N-1，N較大時，網(wǎng)絡(luò)直徑就比較大，等分帶寬為1。線性陣列是連接最簡單的拓?fù)浣Y(jié)構(gòu)，這種結(jié)構(gòu)不具有對稱性，當(dāng)N很大時，通信效率很低。5.5.2環(huán)和帶弦環(huán)用一條附加鏈路將線性陣列的兩個端結(jié)點連接在一起，就構(gòu)成了環(huán)形網(wǎng)絡(luò)，或簡稱環(huán)(ring)，16個結(jié)點的環(huán)形結(jié)構(gòu)如圖5.16(b)所示。環(huán)可以分為單向環(huán)和雙向環(huán)兩種。單向環(huán)只有一個方向，順時針方向或逆時針方向。雙向環(huán)有兩個方向，當(dāng)其中的一個單向環(huán)出現(xiàn)故障時，另一個環(huán)還可以繼續(xù)工作。單向環(huán)和雙向環(huán)結(jié)構(gòu)的結(jié)點度均為2，并且它們都是對稱的。單向環(huán)的網(wǎng)絡(luò)直徑為N-1，雙向環(huán)的網(wǎng)絡(luò)直徑為[N/2]。圖5.16線性陣列、環(huán)、度為3和4的兩種帶弦環(huán)、循環(huán)移數(shù)網(wǎng)絡(luò)、全連接等6種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分別增加一條和兩條附加鏈路就可以得到結(jié)點度分別為3和4的帶弦環(huán)(chordalring)，含16個結(jié)點的度為3和4的帶弦環(huán)結(jié)構(gòu)分別如圖5.16(c)和5.16(d)所示。從圖中可以看出，增加的鏈路愈多，則結(jié)點度愈高，網(wǎng)絡(luò)直徑愈小。

5.5.3循環(huán)移數(shù)網(wǎng)絡(luò)和全連接圖5.16(e)所示的是一個結(jié)點數(shù)為16的循環(huán)移數(shù)(barrelshifter)網(wǎng)絡(luò)，它是將環(huán)上每個結(jié)點到與其距離為2整數(shù)冪的結(jié)點之間增加一條附加鏈而構(gòu)成的。即如果|j-i|=2r，r=0，1，2，…，n-1，網(wǎng)絡(luò)規(guī)模N=2n，則結(jié)點i與結(jié)點j連接。循環(huán)移數(shù)網(wǎng)絡(luò)的結(jié)點度為2n-1，網(wǎng)絡(luò)直徑為n/2。16個結(jié)點的全連接網(wǎng)絡(luò)(completelyconnectednetwork)如圖5.16(f)所示，任意兩個結(jié)點間都有固定的線路進(jìn)行連接。全連接網(wǎng)絡(luò)是一個對稱的網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)規(guī)模為N時，結(jié)點度為N-1，網(wǎng)絡(luò)直徑為1，鏈路數(shù)為N(N-1)/2。5.5.4樹形和星形

一棵5層31個結(jié)點的二叉樹(binarytree)如圖5.17(a)所示。頂部的一個結(jié)點稱為根，底部的16個結(jié)點稱為葉子。其它的稱為中間結(jié)點。除了葉子結(jié)點之外，每個結(jié)點都有兩個孩子結(jié)點。一般來說，一棵h層完全平衡二叉樹應(yīng)有N=2h-1個結(jié)點。最大結(jié)點度為3，網(wǎng)絡(luò)直徑為2(h-1)。

星形(star)是一種2層樹，若結(jié)點的個數(shù)為N，則結(jié)點度為N-1，網(wǎng)絡(luò)直徑為2。如圖5.17(b)所示的是一個結(jié)點數(shù)為9的星形網(wǎng)絡(luò)。圖5.17二叉樹、星形、二叉胖樹等3種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

5.5.5胖樹形為了解決二叉樹中根結(jié)點可能會成為性能的瓶頸這一不足之處，設(shè)計了二叉胖樹(binaryfattree)形結(jié)構(gòu)，各結(jié)點之間的連接如圖5.17(c)所示。胖樹的鏈路數(shù)從葉結(jié)點往根結(jié)點上行方向逐漸增多，它就象一棵真實的樹形結(jié)構(gòu)，愈靠近根的方向，其枝叉就愈粗。

5.5.6網(wǎng)格形和環(huán)網(wǎng)形一個3×3網(wǎng)格(mesh)形網(wǎng)絡(luò)如圖5.18(a)所示。此結(jié)構(gòu)以各種變體形式在ILLIACIV、MPP、DAP、CM-2等中得到了實現(xiàn)。N=rk結(jié)點的k維網(wǎng)格的內(nèi)部結(jié)點度為2k，網(wǎng)格直徑為k(r-1)，由于邊結(jié)點、角結(jié)點和中間結(jié)點的度不相同，圖5.18(a)所示的純網(wǎng)格形是一種不對稱的網(wǎng)絡(luò)結(jié)構(gòu)。圖5.18網(wǎng)格型、Illiac網(wǎng)、環(huán)形網(wǎng)、搏動式陣列等4種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖5.18(d)是為完成矩陣相乘而專門設(shè)計的博動式陣列(systolicarray)，是為某些數(shù)據(jù)流算法而設(shè)計的應(yīng)用驅(qū)動陣列結(jié)構(gòu)。靜態(tài)博動式陣列可在多個方向上使數(shù)據(jù)流變成以流水線方式工作。由于結(jié)構(gòu)固定，搏動式陣列要求匹配給定算法的通信結(jié)構(gòu)。因此，搏動式陣列一旦為給定應(yīng)用優(yōu)化后，就難以有效實現(xiàn)其它算法。

5.5.7超立方體超立方體(hypercube)應(yīng)稱為2元n維立方體。一個有8個結(jié)點的3-立方體，即2元3維立方體如圖5.19(a)所示。一個n-立方體由N=2n個結(jié)點組成，它們分布在n維上，每維有2個結(jié)點。4-立方體可通過將兩個3-立方體的相應(yīng)結(jié)點互連組成，如圖5.19(b)所示。圖5.192元3維立方體、2元4維立方體和帶環(huán)3-立方體等3種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖7.15Return010011超立方體拓?fù)涞奶匦裕合噜徑Y(jié)點的二進(jìn)制編號僅差一位，而兩個結(jié)點間的距離正好等于這兩個結(jié)點二進(jìn)制編號間不同的位數(shù)。它是在線性陣列拓?fù)浜腿B接拓?fù)渲g的一個比較合理的折衷方案。當(dāng)然在N很大時，它的度數(shù)也將很大，硬件成本因而也將很高。5.5.8帶環(huán)立方體帶環(huán)立方體(cube-connectedcycles)結(jié)構(gòu)是從超立方體改進(jìn)而來的，如圖5.19(c)所示。一個3-立方體（2元3維立方體）可改成帶環(huán)3-立方體(3-Cube-ConnectedCycles，簡稱3-CCC)。構(gòu)成的辦法是將3-立方體的角結(jié)點(頂角)用一個結(jié)點環(huán)來代替，如圖5.19(d)所示。其它鏈路的連接方法與5.19(b)相似。

5.5.9k元n-立方體網(wǎng)絡(luò)環(huán)形、網(wǎng)格形、環(huán)網(wǎng)形、2元n維立方體(超立方體)和Omega網(wǎng)絡(luò)都是k元-n立方體網(wǎng)絡(luò)(k-aryn-cubenetwork)系列的拓?fù)渫瑯?gòu)體。如圖5.20所示，就是一種4元-3立方體網(wǎng)絡(luò)。圖5.204元-3立方體網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)（未畫出隱藏部分的結(jié)點和連接）在k元-n立方體網(wǎng)絡(luò)中，參數(shù)k是基數(shù)或者說是沿每個方向的結(jié)點數(shù)，n是立方體的維數(shù)。這兩個數(shù)與網(wǎng)絡(luò)中結(jié)點數(shù)N的關(guān)系為：

N=kn，(n=logkN)表5.1靜態(tài)網(wǎng)絡(luò)特性一覽表網(wǎng)絡(luò)特性結(jié)點度網(wǎng)絡(luò)直徑鏈路數(shù)等分帶寬對稱性網(wǎng)絡(luò)規(guī)模和說明線性陣列2N-1N-11非N個結(jié)點環(huán)形2[N/2]N2是N個結(jié)點全連接N-11N(N-1)/2(N/2)2是N個結(jié)點二叉樹32(h-1)N-11非樹高h(yuǎn)=┏log2N┓星形N-12N-1[N/2]非N個結(jié)點2D網(wǎng)格42(r-1)2N-2rr非r×r網(wǎng)格，N=r2Illiac網(wǎng)4r-12N2r非與N=r2的帶弦環(huán)等效2D環(huán)網(wǎng)42[r/2]2N2r是N=r2個結(jié)點超立方體nnnN/2N/2是N個結(jié)點，n=log2N維數(shù)3-CCC32k-1+[k/2]3N/2N/(2k)是N=k×2k個結(jié)點環(huán)長k≥3K元n-立方體2nn[k/2]nN2kn-1是N=kn個結(jié)點n維環(huán)網(wǎng)n[r/2]n[r/2]nN2rn-1是N=rn個結(jié)點n-CCC32k-1+[k/2]3N/2N/2是N=2n個結(jié)點例5.2設(shè)計一種采用加、乘和數(shù)據(jù)尋徑操作的算法，分別在下面兩種計算機(jī)系統(tǒng)上用最短的時間來計算表達(dá)式S=A1×B1+A2×B2+…+A32×B32。假設(shè)加法和乘法分別需要2個和4個單位時間，從存儲器取指令、取數(shù)據(jù)、譯碼的時間忽略不計，所有的指令和數(shù)據(jù)已裝入有關(guān)的PE。試確定下列每種情況的最小計算時間。(1)一臺串行計算機(jī)，處理機(jī)中有一個加法器和乘法器，同一時刻只有其中一個可以使用。這種單處理機(jī)系統(tǒng)不需要數(shù)據(jù)尋徑操作。(2)一臺有8個PE(PE0，PE1，…，PE7)的SIMD計算機(jī)，8個PE連成雙向環(huán)結(jié)構(gòu)。每個PE用1個單位時間可以把數(shù)據(jù)直接送給它的相鄰PE。操作數(shù)Ai和Bi最初存放在PEj(mod8)中，其中i=1，2，…，32。每個PE可在不同時刻執(zhí)行加法或乘法。(3)若將(2)中8個PE之間的連接由雙向環(huán)結(jié)構(gòu)改為單向環(huán)結(jié)構(gòu)，結(jié)果又如何？解：(1)采用單處理機(jī)系統(tǒng)串行處理所需的時間為：

t=32×4+31×2=190(單位時間)(2)根據(jù)題意，畫出8個PE的連接圖和操作數(shù)的初始存放位置如圖5.21所示。數(shù)據(jù)尋徑操作的算法如下：①每個PE同時執(zhí)行乘法4次，加法3次；②PE0PE7、PE1PE2、PE6PE5、PE3PE4同時傳遞和1次，再加法1次；③PE7PE6PE5、PE2PE3PE4同時傳遞和2次，再加法1次；④PE4PE5傳遞和1次，最后加法1次。因此，采用8個PE并行處理所需的最小時間為：

t=4×4+3×2+1+2+2+2+1+2=32(單位時間)圖5.218個PE的連接圖和操作數(shù)的初始存放位置示意圖(3)若將(2)中8個PE之間的連接由雙向環(huán)結(jié)構(gòu)改為單向環(huán)結(jié)構(gòu)，8個PE的連接圖和操作數(shù)的初始存放位置如圖5.22所示。圖5.228個PE的連接圖和操作數(shù)的初始存放位置示意圖數(shù)據(jù)尋徑操作的算法如下：①每個PE同時執(zhí)行乘法4次，加法3次；②PE0PE1、PE2PE3、PE4PE5、PE6PE7同時傳遞和，再加法1次；③PE1PE2PE3、PE5PE6PE7同時傳遞和2次，再加法1次；④PE3PE4PE5PE6PE7傳遞和4次，最后加法1次。因此，采用8個PE并行處理所需的最小時間為：

t=4×4+3×2+1+2+2+2+4+2=35(單位時間)推廣到一般情形，假設(shè)處理器的個數(shù)N=2m，進(jìn)行一次乘法所需的時間為t1，進(jìn)行一次加法所需的時間為t2，相鄰PE之間傳送數(shù)據(jù)所需的時間為t3，在計算下述表達(dá)式時

S=ΣAi×Bi

ni=1(1)若各處理器之間采用雙向環(huán)連接，計算上述表示式所需的總的時間為：

┏n/N┓t1+(┏n/N┓-1)t2+mt2+2m-1t3其中：①每個PE同時執(zhí)行┏n/N┓次乘法，(┏n/N┓-1)次加法，總的運算時間為┏n/N┓t1+(┏n/N┓-1)t2；②采用折疊算法后，并行加法運算所花的總的時間為mt2；③數(shù)據(jù)傳送所花的總的時間為2m-1t3。(2)若各處理器之間采用單向環(huán)連接，計算上述表示式所需的總的時間為：

┏n/N┓t1+(┏n/N┓-1)t2+mt2+(2m-1)t3

其中：①每個PE同時執(zhí)行┏n/N┓次乘法，(┏n/N┓-1)次加法，總的運算時間為┏n/N┓t1+(┏n/N┓-1)t2；②采用折疊算法后，并行加法運算所花的總的時間為mt2；③數(shù)據(jù)傳送所花的總的時間為(2m-1)t3。5.6動態(tài)互連網(wǎng)絡(luò)動態(tài)互連網(wǎng)絡(luò)設(shè)置有源開關(guān)，因而可根據(jù)需要借助控制信號對連接通路加以重新組合，實現(xiàn)所要求的通信模式。下面介紹總線網(wǎng)絡(luò)、多級互連網(wǎng)絡(luò)和交叉開關(guān)網(wǎng)絡(luò)。5.6.1

總線系統(tǒng)

多處理機(jī)總線系統(tǒng)實際上是一組導(dǎo)線和插座用于處理與總線相連的處理機(jī)、存儲模塊和外圍設(shè)備間的數(shù)據(jù)業(yè)務(wù)。

總線：PCI、VME、Multics、Sbus、MicroChannel

圖5.21總線系統(tǒng)5.6.2交叉開關(guān)網(wǎng)絡(luò)交叉開關(guān)網(wǎng)絡(luò)的帶寬和互連特性最好。交叉點能在(源，目的)之間形成動態(tài)連接，每個交叉點開關(guān)在對偶間提供一條專用連接通路，開關(guān)可根據(jù)程序的要求動態(tài)設(shè)置“開”或“關(guān)”。

交叉開關(guān)互連由一組二維陣列的開關(guān)組成，如圖5.22所示。它將橫向的處理機(jī)P及縱向的存儲器模塊M連接起來。陣列中的總線條數(shù)等于所有處理數(shù)p與存儲器模塊數(shù)m之和。只要m≥p就必然可以使每個處理機(jī)都能有一套總線與某一存儲器模塊相連，從而可以大大加寬帶寬。圖5.22交叉開關(guān)互連例如，由16×16交叉開關(guān)構(gòu)成的單級網(wǎng)絡(luò)將有256個交叉點，若用8個4×4交叉開關(guān)模塊構(gòu)成的二級16×16的交叉開關(guān)網(wǎng)絡(luò)，如圖5.23所示，則僅需128個交叉點，比起單級交叉開關(guān)來可節(jié)省一半設(shè)備量。采用多級交叉開關(guān)網(wǎng)絡(luò)雖然降低了硬件復(fù)雜性，但是時延隨著網(wǎng)絡(luò)級數(shù)的增加而增大。圖5.23用8個4×4交叉開關(guān)模塊構(gòu)成的二級16×16的交叉開關(guān)網(wǎng)絡(luò)5.6.3多級網(wǎng)絡(luò)互聯(lián)1開關(guān)元件一個a×b開關(guān)模塊有a個輸入和b個輸出。一個二元開關(guān)則與a＝b＝2的2×2開關(guān)模塊相對應(yīng)。2×2開關(guān)是最簡單的開關(guān)模塊，又稱為開關(guān)元件。它有兩個輸入x、y，兩個輸出z0、z1，一個控制端s。當(dāng)s=0時，兩個輸入直線輸出，當(dāng)s=1時，兩個輸入交叉輸出。如圖5.24所示。圖5.24開關(guān)狀態(tài)(a)直送xyz1z0(b)交叉xyz1z0(d)下播xyz1z0(c)上播xyz1z02級間連接模式各種多級網(wǎng)絡(luò)的區(qū)別就在于所用開關(guān)模塊、控制方式和級間連接(ISC)模式的不同。常用的ISC級間連接模式有均勻洗牌、蝶式、多路洗牌、縱橫交叉、立方體連接等。3控制方式控制方式是對各個開關(guān)模塊進(jìn)行控制的方式，它可以有三種：(1)級控制每一級的所有開關(guān)只用一個控制信號控制，同時只能處于同一種狀態(tài)；(2)單元控制每一個開關(guān)都有自己單獨的控制信號控制，可各自處于不同的狀態(tài)；(3)部分級控制第i級的所有開關(guān)分別用i+1個信號控制，0≤i≤n-1,n為級數(shù)。4多級網(wǎng)絡(luò)舉例

MIMD和SIMD計算機(jī)都使用多級互連網(wǎng)絡(luò)MIN。MIN(multistageinterconnectionnetwork)。一種通用多級網(wǎng)絡(luò)如圖5.25所示，其中每一級都用了多個a×b開關(guān)，相鄰各級開關(guān)之間都有固定的級間連接。為了在輸入和輸出之間建立所需的連接，可用動態(tài)設(shè)置開關(guān)的狀態(tài)來實現(xiàn)。

圖5.25【例1】

使用開關(guān)元件的一個8×8三級互連網(wǎng)絡(luò)。8個輸入結(jié)點0-7號，8個輸出結(jié)點，中間有3級開關(guān)。一個輸入數(shù)據(jù)從源結(jié)點到達(dá)目的結(jié)點需要log28=3級開關(guān)元件。每個開關(guān)元件有兩個輸入兩個輸出，因此共需用3×4=12個開關(guān)元件。一般地，若使用n級開關(guān)元件，輸入輸出可各有2n個結(jié)點（如3級，23=8個結(jié)點），共需用n×2n-1個開關(guān)元件。如圖5.26所示，開關(guān)均為直送模式，級間采用子洗牌和均勻洗牌連接模式。輸入連接到輸出稱為一個配置。本例的配置為:(0,0),(1,4),(2,2),(3,6),(4,1),(5,5),(6,3),(7,7)圖5.268×8三級互連網(wǎng)絡(luò)輸入輸出0145672301456723子洗牌均勻洗牌輸入輸出配置(0,0),(1,4),(2,2),(3,6),