【文章內(nèi)容簡介】 C ?一個 3立方體可改成帶環(huán) 3立方體 (CCC)。構(gòu)成的辦法是將 3立方體的角結(jié)點(diǎn) (頂角 )用一個結(jié)點(diǎn)環(huán)來代替 ?一般說來， kCCC的網(wǎng)格直徑 2k。 CCC的主要改進(jìn)在其結(jié)點(diǎn)度為常數(shù) 3，與超立方體的維數(shù)無關(guān) ?3CCC的直徑為 6，比原來 3立方體的直徑大一倍 ?一個超立方體有 N=2^n結(jié)點(diǎn)。一個有同樣 N結(jié)點(diǎn)數(shù)的 CCC一定是由低維 k立方體組成，即 2^n=k 2^k，其中 kn ?對應(yīng)于 n=6和 k=4的情況，一個 64結(jié)點(diǎn)的 CCC可用 4結(jié)點(diǎn)的環(huán)取代 4立方體的角結(jié)點(diǎn)組成。 CCC的直徑為 2k=8，比 6立方體的 6要長些。但是， CCC的結(jié)點(diǎn)度為 3，比 6立方體的結(jié)點(diǎn)度 6要小 ?容許一定的時延 ,CCC是一種構(gòu)造可擴(kuò)展系統(tǒng)的較好的結(jié)構(gòu) tiger September 2022 39 (9)帶環(huán)立方體 Y X Z 011 000 010 110 111 101 100 tiger September 2022 40 (10)k元 n立方體網(wǎng)絡(luò) ?環(huán)形、網(wǎng)格形、環(huán)網(wǎng)形、二元 n立方體 (超立方體 )和 W網(wǎng)絡(luò)都是 k元 n立方體網(wǎng)絡(luò)系列的拓?fù)渫瑯?gòu)體 ?參數(shù) n是立方體的維數(shù)， k是基數(shù)或者說是沿每個方向的結(jié)點(diǎn)數(shù) (多重性 )。與網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù) N的關(guān)系 ?k元 n立方體的結(jié)點(diǎn)可用基數(shù)為 k的 n位地址 A=a1a2…an來表示，其中 ai代表第 i維結(jié)點(diǎn)位置 ?為簡單起見，所有鏈路都認(rèn)為是雙向的 ?網(wǎng)絡(luò)中每條線代表兩個通信通道，每個方向一個 )l o gn ,(, k NNkkN nn ???tiger September 2022 41 圖 k=4和 n=3的 k元 n立方體網(wǎng)絡(luò) ?(1)4結(jié)點(diǎn)串成綠色環(huán) ?(2)4綠色環(huán)并排成面，同一列用黃色環(huán)連接 ?(3)4黃色面堆成體，同一行用藍(lán)色環(huán)連接 ?機(jī)器的擺放是否也要相應(yīng)立體格局 ? 如何連接繁雜的接線 ? 1 2 3 tiger September 2022 42 環(huán)網(wǎng) ?(a)傳統(tǒng)環(huán)網(wǎng) (4元 2立方體 ) (b)折疊連接的環(huán)網(wǎng) tiger September 2022 43 2動態(tài)互連網(wǎng)絡(luò) ?動態(tài)互連網(wǎng)絡(luò)設(shè)置有源開關(guān) ?通過控制信號對連接通路重新組合，實現(xiàn)所要求的通信模式 ?包括總線、多級互連網(wǎng)和交叉開關(guān)網(wǎng)絡(luò) tiger September 2022 44 (1)總線 ?總線系統(tǒng)是一組導(dǎo)線和插座用于處理與總線相連接的處理機(jī)、存儲器模塊和外圍設(shè)備間的數(shù)據(jù)業(yè)務(wù) ?總線被稱為多個功能模塊間爭用總線或時分總線 ?總線系統(tǒng)與其它兩種動態(tài)連接網(wǎng)絡(luò)相比，價格較低，帶寬較窄 ?有很多可用的工業(yè)和 IEEE總線標(biāo)準(zhǔn) tiger September 2022 45 (2)開關(guān)模塊 ?一個 a?b開關(guān)模塊有 a個輸入和 b個輸出 ?一個二元開關(guān)則與 a=b=2的 2?2開關(guān)模塊相對應(yīng) ?實際中 a和 b通常選為 a=b=2^k， k=1 ?最常用的二元開關(guān)： a=b=2 ?每個輸入可與一個或多個輸出相連，在輸出端必須避免發(fā)生沖突。容許一對一和一對多映射；不容許多對一映射 ?只容許一對一映射時稱為置換連接，稱為 n n交叉開關(guān) ?具有直通和交換兩種功能的交換開關(guān)稱為二功能開關(guān)，或交換開關(guān)。用一位控制信號控制 ?具有所有四種功能的交換開關(guān)稱為四功能開關(guān)，用兩位控制信號控制 tiger September 2022 46 直通 交換 上播 下播 模塊大小 合法狀態(tài) 交換連接 2 2 4 2 4 4 256 24 8 8 16777216 40320 n n nn n! 交換開關(guān)和合法狀態(tài) tiger September 2022 47 (3)多級網(wǎng)絡(luò) ?互連網(wǎng)絡(luò)的一種基本功能 : 實現(xiàn)結(jié)點(diǎn)到結(jié)點(diǎn)之間的任意互連 ?多級互連網(wǎng)絡(luò)采用多個相同或不同的互連網(wǎng)絡(luò)直接連接起來 ?屬組合邏輯線路，同一個時鐘周期能實現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連 ?多級互連網(wǎng)絡(luò)的關(guān)鍵技術(shù) ?(1) 交換開關(guān) ?(2) 交換開關(guān)之間的拓?fù)溥B接 ?(3) 對交換開關(guān)的不同控制方式 tiger September 2022 48 (3)多級網(wǎng)絡(luò) ?(3a)拓?fù)浣Y(jié)構(gòu) (級間連接 ) ?前一級交換開關(guān)的輸出端與后一級交換開關(guān)的輸入端之間的連接模式稱為拓?fù)浣Y(jié)構(gòu) ?通常采用前面介紹的互連函數(shù)實現(xiàn)拓?fù)浣Y(jié)構(gòu) ?從結(jié)點(diǎn)的輸出到第一級交換開關(guān)的輸入，及從最后一級交換開關(guān)的輸出到結(jié)點(diǎn)的輸入也可采用拓?fù)浣Y(jié)構(gòu)連接 ?(3b)控制方式 ?多級互連網(wǎng)絡(luò)中有多級交換開關(guān)，每一級有多個交換開關(guān) ?(1)級控制：同一級交換開關(guān)使用同一個控制信號控制 ?(2)單元級控制：每個交換開關(guān)分別控制 ?(3)部分級控制：如，第 i級使用 i+1個控制信號控制(0=i=n1) 由粗到細(xì)逐步切換之目的節(jié)點(diǎn) ?同一個多級互連網(wǎng)絡(luò)分別使用三種不同的控制方式，可構(gòu)成三種不同的互連網(wǎng)絡(luò) tiger September 2022 49 圖 一種由 a b開關(guān)模塊和級間連接模式 ISC tiger September 2022 50 ?采用二功能開關(guān)，共需開關(guān) n 2^(n1)個 ?由多個單級立方體網(wǎng)組成，某級開關(guān)處于交換狀態(tài)時 , 各級分別實現(xiàn) E0、 E …En1交換函數(shù) ?所有開關(guān)都直通時，實現(xiàn)恒等變換 ?第 0級 A、 B、 C、 D開關(guān)交換，其余直通實現(xiàn) E0 互連函數(shù) ?第 1級 E、 F、 G、 H開關(guān)交換，其余直通實現(xiàn) E1 互連函數(shù) ?第 2級 I、 J、 K、 L開關(guān)交換，其余直通實現(xiàn) E2 互連函數(shù) ?采用三種不同的控制方式，可構(gòu)成三種不同的互連網(wǎng)絡(luò) ?采用級控制， 構(gòu)成 STARAN交換網(wǎng) ?采用部分級控制，構(gòu)成 STARAN移數(shù)網(wǎng) ?采用單元控制， 構(gòu)成間接二進(jìn)制 n方體網(wǎng) (3c)多級立方體網(wǎng) tiger September 2022 51 (3c)多級立方體網(wǎng) B(2) B(3) S 1 A B C D E F G H I J K L 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 k=0 k = 1 k = 2 tiger September 2022 52 ? B(2) B(3) B(4) S 1 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F 級 k0 k2 k3 k1 tiger September 2022 53 (3d)全排列互連網(wǎng)絡(luò) ?循環(huán)互連網(wǎng)絡(luò)和多級互連網(wǎng)絡(luò)都能實現(xiàn)任意一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的互連，但同時有兩個或兩個以上結(jié)點(diǎn)要求與其他結(jié)點(diǎn)互連時，有可能發(fā)生沖突 ?在上面的多級立方體網(wǎng)中，如果要求同時實現(xiàn) 05和 17的互連，在開關(guān) A發(fā)生沖突 ?全排列互連網(wǎng)絡(luò)能同時實現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連 ?解決方法：采用多個多級互連網(wǎng)絡(luò)連接 ?原理： N個結(jié)點(diǎn)的全排列共有 N！ ?N=2n個結(jié)點(diǎn)的多級互連網(wǎng)絡(luò)有 n級， 二功能開關(guān) n 2n1個，有不同的狀態(tài)種類 )2(!)2(2 2)22(21時當(dāng) ???????nNNNn nn ntiger September 2022 54 (4)Ω網(wǎng)絡(luò) ?16 16Ω網(wǎng)絡(luò)，共需 4級 2 2開關(guān) ?網(wǎng)絡(luò)左側(cè)有 16個輸入，右側(cè)有 16個輸出 ?ISC是對 16個對象的 2路 (組 )均勻洗牌模式 ?一個 n輸入的 Ω網(wǎng)絡(luò)需 log2n級 2 2開關(guān)，每級需 n/2個開關(guān)模塊，網(wǎng)絡(luò)共需 (nlog2n)/2個開關(guān) ?不同開關(guān)狀態(tài)組合可實現(xiàn)各種置換、廣播或從輸入到輸出的其它連接 ?每級的拓?fù)浣Y(jié)構(gòu)相同 ?采用單元控制 ?能實現(xiàn)任意一個輸入端到任意一個輸出端的連接 ?有沖突時不能同時實現(xiàn)多個輸入端到多個輸出端的連接 ?檢查二進(jìn)制目的地址編碼來控制數(shù)據(jù)路徑 ?目的地址編碼從高位開始 ?第 i位為 0時，第 i級的 2 2開關(guān)輸入端與 上 輸出端連接 ?第 i位為 1時，第 i級的 2 2開關(guān)輸入端與 下 輸出端連接 tiger September 2022 55 (4)Ω網(wǎng)絡(luò) 輸入 1可連接到哪個輸出 ? 均勻洗牌置換 tiger September 2022 56 (5)基準(zhǔn)網(wǎng)絡(luò) ?Wu和 Feng研究多級互連網(wǎng)絡(luò)之間的關(guān)系 ?基準(zhǔn)網(wǎng)絡(luò)如圖 (a)所示遞歸生成 ?第 1級為一個 N N模塊 ?第 2級為兩個 (N/2) (N/2)子模塊，以 C0和 C1表示 ?以上構(gòu)成方法遞歸用于子模塊 ?直至得到 2 2的 N/2子模塊為止 ?各小框和最終的子模塊構(gòu)件是 2 2開關(guān) ?每個有兩個合法連接狀態(tài)：兩個輸入和兩個輸出間的直送和交叉連接 tiger September 2022 57 (5)基準(zhǔn)網(wǎng)絡(luò) ? N結(jié)點(diǎn) S 1 ?每個 2 2交換開關(guān)的輸出分成上下兩組，分別連到兩個 N/2 ?遞歸分組的過程是逐步細(xì)化到達(dá)目的結(jié)點(diǎn)的過程 tiger September 2022 58 (5)基準(zhǔn)網(wǎng)絡(luò) ? 1組 16結(jié)點(diǎn) S 1 2組 8結(jié)點(diǎn) S 1 4組 4結(jié)點(diǎn) S 1 遞歸終點(diǎn)為 1個 2x2子模塊，即僅有兩個結(jié)點(diǎn) tiger September 2022 59 (6)交叉開關(guān)網(wǎng)絡(luò) ?全交叉開關(guān)網(wǎng)絡(luò)能夠同時實現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連 ?還能實現(xiàn)廣播和多播 ?帶寬和互連特性最好 ?多處理機(jī)系統(tǒng)中，處理機(jī)、存儲器和 IOP之間用交叉開關(guān)網(wǎng)絡(luò)連接 ?可看作是一個單級開關(guān)網(wǎng)絡(luò) ?象電話交換機(jī)一樣，交叉點(diǎn)開關(guān)能在對偶 (源、目的 )之間形成動態(tài)連接，每個交叉點(diǎn)開關(guān)在對偶間提供一條專用連接通路，開關(guān)可根據(jù)程序的要求動態(tài)地設(shè)置“開”或“關(guān)” ? ? 處理機(jī)１ 處理機(jī) N 處理機(jī)２ 處理機(jī)１ 處理機(jī)２ 處理機(jī)Ｎ tiger September 2022 60 另一種分類 tiger September 2022 61 消息傳遞機(jī)制 ?研究各種尋徑方法，分析它們的通信時延問題 ?引入虛擬通道的概念，用虛擬通道來避免死鎖 ?確定的和自適應(yīng)兩種尋徑算法 ?拓?fù)浣Y(jié)構(gòu)與尋徑策略有一定的關(guān)系 tiger September 2022 62 消息尋徑方式 ?四種尋徑方式 ?線路交換、存儲轉(zhuǎn)發(fā)、虛擬直通、蟲蝕尋徑 ?1. 消息格式 ?消息 ?結(jié)點(diǎn)間通信的邏輯單位 , 由任意數(shù)目的長度固定的包組成 ?包是包含尋徑目的地址的基本單位 ?每個包需要一個序號，以重新組裝消息 ?包可分成固定長度的片 ?尋徑信息和序號形成頭片，其余的片是數(shù)據(jù)片 tiger September 2022 63 ?R：導(dǎo)徑信息 S：序號 D：數(shù)據(jù)片 b：位 消息傳遞網(wǎng)絡(luò)中通信的信息單位：消息、包和片 消息 包 片 D D D D D D S R b b b b b b b b tiger September 2022 64 包 ?采用存儲轉(zhuǎn)發(fā)尋徑方式的多計算機(jī)系統(tǒng)中，包是信息傳送的最小單位 ?采用蟲蝕尋徑網(wǎng)絡(luò)的多計算機(jī)中，包可進(jìn)一步分成片。片的長度受網(wǎng)絡(luò)大小的影響 ?256個結(jié)點(diǎn)的網(wǎng)絡(luò)需要片長為 8位 ?包的長度取決于尋徑方式和網(wǎng)絡(luò)的實現(xiàn)方法 ?典型的包的長度為 64～ 512位 ?序號可能占用 1～ 2個片，取決于消息的長度 ?包和片的大小還與通道頻寬、尋徑器設(shè)計以及網(wǎng)絡(luò)流量密度等有關(guān) tiger September 2022 65 四種尋徑方式 ?兩大類 ?線路交換 ?包交換 (存儲轉(zhuǎn)發(fā)、虛擬直通和蟲蝕尋徑 ) ?(1)線路交換 (circuit