【文章內(nèi)容簡(jiǎn)介】 ，直徑也是 n。 圖 超立方體結(jié)構(gòu) 是把立方體中每一個(gè)結(jié)點(diǎn)用一個(gè)包含多個(gè)結(jié)點(diǎn)的環(huán)代替。如圖 所示，是把 3立方體中的頂角結(jié)點(diǎn)換成包含 3個(gè)結(jié)點(diǎn)的環(huán)，而構(gòu)成的帶環(huán)立方體結(jié)構(gòu)，簡(jiǎn)稱 3CCC(Cube Connected Cycles)。若要組成帶環(huán) k立方體，只需將 k立方體的每一個(gè)頂角結(jié)點(diǎn)用 k個(gè)結(jié)點(diǎn)組成的環(huán)代替，這樣就構(gòu)成一個(gè)有 N=k 2k個(gè)結(jié)點(diǎn)的帶環(huán) k立方體。 圖 帶環(huán) 3立方體 在構(gòu)成帶環(huán)立方體網(wǎng)絡(luò)時(shí)，環(huán)中的結(jié)點(diǎn)數(shù) k一般與立方體的維數(shù)相等。 n立方體網(wǎng)絡(luò)結(jié)構(gòu) 在 k元 n立方體網(wǎng)絡(luò)中， k表示基數(shù)，即每一方向上的結(jié)點(diǎn)數(shù)，n表示立方體的維數(shù)。這樣，網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù) N=kn(n=logkN)。 圖 4元 3立方體的網(wǎng)絡(luò)結(jié)構(gòu) (隱藏部分的結(jié)點(diǎn)沒有畫出 )，每個(gè)方向上有一條雙向通信鏈路。實(shí)際上，環(huán)型、網(wǎng)格型、環(huán)網(wǎng)型、二元 n維立方體 (超立方體 )以及 Omega網(wǎng)絡(luò)都是 k元 n立方體（ kary ncube work）系列的拓?fù)渫瑯?gòu)體。 按照習(xí)慣，低維 k元 n立方體稱為環(huán)網(wǎng)，高維二元 n立方體稱為超立方體。 圖 4元 3立方體網(wǎng)絡(luò)結(jié)構(gòu) 靜態(tài)互連網(wǎng)絡(luò)特性 各種陣列機(jī)或大規(guī)模并行處理機(jī)系統(tǒng)中的靜態(tài)互連網(wǎng)絡(luò)已經(jīng)很多，而且各有特色。概括起來(lái)如表 。其中 d表示連接度， D表示網(wǎng)絡(luò)直徑， l表示鏈路數(shù)， B表示等分帶寬。 表 靜態(tài)互連網(wǎng)絡(luò)特性表 網(wǎng)絡(luò)類型 連接度 d 網(wǎng)絡(luò)直徑 D 鏈路數(shù) l 等分帶寬 B 對(duì)稱性 網(wǎng)絡(luò)規(guī)模與說(shuō)明 線性陣列 2 N1 N1 1 非 N個(gè)結(jié)點(diǎn) 環(huán)形 2 [N/2] N 2 是 N個(gè)結(jié)點(diǎn) 全連接 N1 1 N(N1)/2 (N/2)2 是 N個(gè)結(jié)點(diǎn) 二叉樹 3 2(h1) N1 1 非 樹高 h=log2(N+1) 星形 N1 2 N1 [N/2] 非 N個(gè)結(jié)點(diǎn) 2D網(wǎng)絡(luò) 4 2(r1) 2N2r r 非 r r網(wǎng)絡(luò) , r= √ N Illiac網(wǎng) 4 r1 2N 2r 非 與 r=√ N的帶 弦 環(huán)網(wǎng)等效 2D環(huán)網(wǎng) 4 2[r/2] 2N 2r 是 r r環(huán)網(wǎng) , r=√ N 超立方體 n n nN/2 N/2 是 N個(gè)結(jié)點(diǎn) ,n=log2N(維數(shù) ) 3CCC 3 2k1+[k/2] 3N/2 N/(2k) 是 N=k 2k結(jié)點(diǎn) ,環(huán)長(zhǎng) k≥3 k元 n立方體 2n n[k/2] nN 2kn1 是 N=kn個(gè)結(jié)點(diǎn) n維環(huán)網(wǎng) n(r/2) n[r/2] nN 2rn1 是 N=rn個(gè)結(jié)點(diǎn) 說(shuō)明： []表示取整 動(dòng)態(tài)互連網(wǎng)絡(luò) 總線互連方式 交叉開關(guān)互連方式 多級(jí)網(wǎng)絡(luò)互連方式 動(dòng)態(tài)互連網(wǎng)絡(luò)是用開關(guān)或裁決器提供動(dòng)態(tài)連接特性，在運(yùn)行過程中由程序來(lái)確定具體的連接方式，常見的動(dòng)態(tài)互連網(wǎng)絡(luò)有總線互連方式、交叉開關(guān)互連方式、多級(jí)互連方式及組合互連方式等。 總線互連方式 總線連接方式是多機(jī)互連的一種最簡(jiǎn)單的方式。多個(gè)處理機(jī)、存儲(chǔ)器模塊及 I/O部件通過各自的接口部件連接在一條共用總線上；或是多個(gè)由 CPU、局部存儲(chǔ)器和 I/O部件組成的計(jì)算機(jī)模塊通過各自的接口部件與一條總線連接。 總線結(jié)構(gòu)多處理機(jī)系統(tǒng)如圖 ，構(gòu)成系統(tǒng)總線的各種線路分布在底板上，通過插槽與各處理模塊連接。系統(tǒng)總線一般受某一主 CPU模塊或總線裁決器控制。當(dāng)某一模塊需要通信時(shí)首先向主 CPU或總線裁決器發(fā)總線請(qǐng)求信號(hào)；在獲取總線后發(fā)送地址，以確定從設(shè)備；然后與從設(shè)備進(jìn)行一次通信，通信完后，釋放總線。 圖 總線結(jié)構(gòu)多處理機(jī)系統(tǒng) 在各處理模塊內(nèi)部設(shè)有本地或者局部總線，用來(lái)連接模塊內(nèi)部的部件或者器件。設(shè)在 CPU模塊中的局部總線稱為本地總線，設(shè)在存儲(chǔ)器模塊中的稱為存儲(chǔ)器總線；設(shè)在 I/O模塊中的稱為I/O總線。各模塊之間使用統(tǒng)一的總線標(biāo)準(zhǔn)，比如 PCI、 VME、Multibus、 Sbus、 Microchanne、 IEEE Futurebus等。 多層總線結(jié)構(gòu)如圖 ，各處理機(jī)采用底層總線實(shí)現(xiàn)互連，構(gòu)成一個(gè)機(jī)群，底層總線也稱為機(jī)群總線。在各機(jī)群內(nèi)部， CC表示機(jī)群緩沖存儲(chǔ)器， P表示處理器。在上層，各機(jī)群通過外部總線實(shí)現(xiàn)互連，構(gòu)成大的機(jī)群系統(tǒng)，這種外部總線也稱為機(jī)群間總線。 圖 多層總線結(jié)構(gòu)多處理機(jī)系統(tǒng) 另外，各機(jī)群通過上層總線與共享存儲(chǔ)器連接，通過共享存儲(chǔ)器實(shí)現(xiàn)數(shù)據(jù)交換或者通信；亦可與大型外部設(shè)備連接，共享系統(tǒng)中的大型外部設(shè)備。 在構(gòu)成多層總線結(jié)構(gòu)的多處理機(jī)系統(tǒng)時(shí)，因?yàn)楦鳈C(jī)群使用的總線標(biāo)準(zhǔn)不一定相同，因此需要使用網(wǎng)橋?qū)崿F(xiàn)標(biāo)準(zhǔn)轉(zhuǎn)換，并進(jìn)行地址分配和連接。 交叉開關(guān)互連方式 1. 單級(jí)交叉開關(guān)互連網(wǎng)絡(luò) 是通過開關(guān)把多個(gè)處理機(jī)、存儲(chǔ)器模塊以及 I/O設(shè)備連接起來(lái)，形成一種網(wǎng)絡(luò)結(jié)構(gòu)。它引入空間重復(fù)因素，可為每一個(gè)端口提供更高的帶寬。一般由一組二維開關(guān)陣列組成，如圖 ，通過開關(guān)把處理機(jī) Pi與存儲(chǔ)器Mi連接起來(lái)?？刂崎_關(guān)的通與斷可實(shí)現(xiàn)某兩個(gè)結(jié)點(diǎn)的連接?？偩€的條數(shù)等于所有處理機(jī)數(shù) p與存儲(chǔ)器模塊數(shù) m之和。只要 m≥p， 必然使每一個(gè)處理 圖 交叉開關(guān)互連網(wǎng)絡(luò) 機(jī)都能有一套總線與某一存儲(chǔ)器模塊連接，可提高系統(tǒng)的帶寬。 為了處理多個(gè)處理機(jī)同時(shí)使用某 一存儲(chǔ)器而引起的沖突，在縱橫交 叉開關(guān)互連網(wǎng)絡(luò)中需要設(shè)置裁決部件。若 p個(gè)處理機(jī)還要與 i個(gè) I/O設(shè)備 連接，則陣列機(jī)中總線的條數(shù)等于 p+m+i。只有m≥p+i時(shí)，才能實(shí)現(xiàn)無(wú)阻塞連接。 2. 多級(jí)交叉開關(guān)互連網(wǎng)絡(luò) 圖 4個(gè) 4 4交叉開關(guān)陣列構(gòu)成的二級(jí) 16 16交叉開關(guān)互連網(wǎng)絡(luò)。顯然，如果使用單級(jí)交叉開關(guān)實(shí)現(xiàn) 16 16的互連網(wǎng)絡(luò)，則需要 256個(gè)交叉開關(guān)。采用二級(jí)網(wǎng)絡(luò)結(jié)構(gòu)，則僅需要 128個(gè)交叉開關(guān)，使硬件節(jié)省一半，且結(jié)構(gòu)簡(jiǎn)單。但是，延時(shí)將隨著級(jí)數(shù)的增加而增加。 圖 二級(jí) 16 16交叉開關(guān)互連網(wǎng)絡(luò) 多級(jí)網(wǎng)絡(luò)互連方式 多級(jí)互連網(wǎng)絡(luò) MIN(Multistage interconnection work)是把多個(gè)單級(jí)互連網(wǎng)絡(luò)通過交換開關(guān)或交叉開關(guān)串連起來(lái)而構(gòu)成的網(wǎng)絡(luò)，可通過改變開關(guān)狀態(tài)實(shí)現(xiàn)不同的連接，以滿足系統(tǒng)需要。常見的有多級(jí)立方體互連網(wǎng)絡(luò)、多級(jí)混洗交換網(wǎng)絡(luò)（ Omega網(wǎng)絡(luò)）、多級(jí) PM2I網(wǎng)絡(luò)、多級(jí) BENES可重排網(wǎng)絡(luò)及多級(jí) CLOS網(wǎng)絡(luò)等。 構(gòu)成多級(jí)互連網(wǎng)絡(luò)三要素，包括交換開關(guān)、拓?fù)浣Y(jié)構(gòu)和控制方式。 （ 1）交換開關(guān)：是構(gòu)成多級(jí)互連網(wǎng)絡(luò)的基本單元，有兩個(gè)輸入端和兩個(gè)輸出端，又分為二功能和四功能兩種。二功能有直通和交換，四功能是增加了上播和下播，如圖 。 圖 交換開關(guān)的四種功能 （ 2）拓?fù)浣Y(jié)構(gòu)：拓?fù)浣Y(jié)構(gòu)是指各級(jí)之間輸入端和輸出端的連接規(guī)則或模式。按照一定的規(guī)則或模式可將各種單級(jí)互連網(wǎng)絡(luò)進(jìn)行組合，從而構(gòu)成具有不同連接特性的多級(jí)互連網(wǎng)絡(luò)。 （ 3）控制方式：根據(jù)互聯(lián)網(wǎng)絡(luò)的結(jié)構(gòu)可有三種控制方式。 ① 級(jí)控：同一級(jí)的所有交換開關(guān)受同一信號(hào)控制，對(duì)于一個(gè) n級(jí)網(wǎng)絡(luò)需要 n個(gè)控制信號(hào)。 ② 單元控制：每個(gè)開關(guān)有一個(gè)單獨(dú)的控制信號(hào)。對(duì)于 n級(jí)網(wǎng)絡(luò)，其輸入與輸出端數(shù) N=2n，故每級(jí)有 N/2個(gè)開關(guān)，共需 nN/2個(gè)控制信號(hào)?？刂茝?fù)雜，但使用靈活。 ③ 部分級(jí)控：對(duì)同一級(jí)開關(guān)分組，在不同級(jí)使用不同數(shù)量的控制信號(hào)。比如第 0級(jí)用 1個(gè)控制信號(hào)，第 1級(jí)用 2個(gè)控制信號(hào)，第 2級(jí)用 3個(gè)控制信號(hào)，即第 i級(jí)用 i+1個(gè)控制信號(hào)，其中 0≤i≤n1， n為級(jí)數(shù)。 如圖 a b開關(guān)模塊和不同的級(jí)間連接模式（ ISC）構(gòu)成的多級(jí)互連網(wǎng)絡(luò)示意圖。不同的多級(jí)互連網(wǎng)絡(luò)的主要區(qū)別表現(xiàn)在上述三個(gè)方面。其中開關(guān)可以根據(jù)需要選用 2 4 4 8 16 1 …… 、64 64等；級(jí)間連接模式可選擇 Exch