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