【正文】 =01175。 圖 Cube交換互連示意圖 按照 Cube函數(shù)的連接示意如圖 。其表達(dá)式為： I(x)=I(bn1bn2…b1b0)=bn1bn2…b1b0 其示意如圖 ，左邊表示輸入端，右邊表示輸出端。 則 f(x)因函數(shù)的不同，而有不同的表達(dá)式，例如： 交換互連函數(shù) f(x)=f(bn1bn2…b1b0)= bn1bn2…b1b175。設(shè)用 x表示具有 N個(gè)輸入端的網(wǎng)絡(luò)輸入序號(hào)，則輸出端的序號(hào)用函數(shù) f(x)表示。在動(dòng)態(tài)拓?fù)渲兄饕譃閱渭?jí)循環(huán)網(wǎng)絡(luò)和各種多級(jí)互連網(wǎng)絡(luò)，其連接形式與互連函數(shù)密切相關(guān)。靜態(tài)拓?fù)涫窃诰W(wǎng)絡(luò)運(yùn)行中其結(jié)構(gòu)不能改變；而在動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)中設(shè)有有源開關(guān)，在網(wǎng)絡(luò)運(yùn)行中可借助于控制信號(hào)對(duì)連接通路重新組合。 SIMD計(jì)算機(jī)一般采用線路交換， MIMD多處理機(jī)多采用分組交換方式。線路交換是在傳送過程中，在源 /目標(biāo)結(jié)點(diǎn)間建立固定的物理通路，適合于成批數(shù)據(jù)傳送。 一般 SIMD計(jì)算機(jī)采用的是集中控制和同步傳送方式。 （ 2）控制策略 是控制互連開關(guān)構(gòu)成信息通路的方式，可分為集中控制和分散控制兩種。所謂同步方式，是在數(shù)據(jù)傳送的過程中采用統(tǒng)一的時(shí)鐘信號(hào)。 在設(shè)計(jì)互連網(wǎng)絡(luò)時(shí)，所考慮的主要因素有以下 4個(gè)方面。 （ 7）成本：構(gòu)建互連網(wǎng)絡(luò)所花的費(fèi)用。 （ 6）誤碼率：是傳輸信息時(shí)出現(xiàn)錯(cuò)誤的概率，等于錯(cuò)誤碼的位數(shù)除以總碼長。 （ 4）傳輸延時(shí)：傳輸延時(shí)等于飛行時(shí)間與傳輸時(shí)間之和，是消息通過互連網(wǎng)絡(luò)的時(shí)間，但不包括網(wǎng)絡(luò)兩端硬件設(shè)備發(fā)送和接收的時(shí)間。 （ 2）傳輸時(shí)間：是指信息通過網(wǎng)絡(luò)所用的時(shí)間，等于信息長度除以帶寬。 例如 HPS是一個(gè)對(duì)稱式網(wǎng)絡(luò)，包含 512個(gè)結(jié)點(diǎn)，每個(gè)端口的帶寬為40MBps，可計(jì)算出聚集帶寬為 512/2 40MBps=10GBps。所謂聚集帶寬是在網(wǎng)絡(luò)中，從一半結(jié)點(diǎn)到另一半結(jié)點(diǎn)，每秒鐘傳送信息的最大位數(shù)或字節(jié)數(shù) .。不同的網(wǎng)絡(luò)結(jié)構(gòu)有著不同的數(shù)據(jù)尋徑功能，常見的有一到一、一到多 (廣播 )、散射、匯合 /聚集、歸約 (多到一 )、循環(huán)移位、掃描和全交換等。 （ 8）數(shù)據(jù)尋徑功能：表示互連網(wǎng)絡(luò)把數(shù)據(jù)從網(wǎng)絡(luò)的一端傳送到另一端的方式和能力，分為靜態(tài)和動(dòng)態(tài)兩種。 （ 7）對(duì)稱性：從任何一個(gè)結(jié)點(diǎn)來看，若網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)都一樣，則稱為對(duì)稱網(wǎng)絡(luò)。把網(wǎng)絡(luò)切成相等的兩半，沿切口的最小邊（通道）數(shù)稱為通道等分寬度，可用 k表示；若用 w表示通道寬度（用位表示），則 B=k w稱為線等分寬度。從數(shù)據(jù)傳送的角度來看，網(wǎng)絡(luò)直徑越小越好。 （ 3）結(jié)點(diǎn)距離：結(jié)點(diǎn)距離是從一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)所經(jīng)過的最少邊數(shù)。 （ 2）連接度：也稱為結(jié)點(diǎn)度，是指與該結(jié)點(diǎn)連接的邊數(shù)，也就是直接連接到該結(jié)點(diǎn)的其它結(jié)點(diǎn)數(shù)，常用 d表示。 主要是指網(wǎng)絡(luò)規(guī)模、連接度、結(jié)點(diǎn)距離、網(wǎng)絡(luò)直徑、帶寬、可靠性和成本。 圖 互連網(wǎng)絡(luò)示意圖 概括起來，互連網(wǎng)絡(luò)的主要功能有以下兩點(diǎn)： ① 連接各個(gè)結(jié)點(diǎn)，構(gòu)成信息通路，傳送數(shù)據(jù)或者控制命令； ② 通過路徑選擇，實(shí)現(xiàn)有目的的信息交換，其中包括一到一和一到多的選擇與交換。如果再配以軟件，還可實(shí)現(xiàn)數(shù)據(jù)格式的定義、轉(zhuǎn)換、打包、幀識(shí)別、發(fā)送與接收控制以及誤碼檢測(cè)等功能。第 6章 互連網(wǎng)絡(luò) 互連網(wǎng)絡(luò)的基本概念 靜態(tài)互連網(wǎng)絡(luò) 動(dòng)態(tài)互連網(wǎng)絡(luò) 消息傳送與控制 互連網(wǎng)絡(luò)的基本概念 互連網(wǎng)絡(luò)的功能與特征 互連函數(shù) 互連網(wǎng)絡(luò)的功能與特征 互連網(wǎng)絡(luò)是一種由開關(guān)元件按一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)，用來實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多處理機(jī)或多功能部件之間的相互連接。它通過硬件線路，實(shí)現(xiàn)設(shè)備之間的連接；通過開關(guān)選擇，構(gòu)成一對(duì)一或者一對(duì)多的信息通路。這里主要從硬件的角度討論互連網(wǎng)絡(luò)的功能與特征，如圖 。 隨著互聯(lián)網(wǎng)的發(fā)展，越來越多的并行計(jì)算機(jī)系統(tǒng)直接使用臺(tái)式計(jì)算機(jī)作為結(jié)點(diǎn)機(jī)，通過互聯(lián)網(wǎng)連接，構(gòu)成并行計(jì)算機(jī)系統(tǒng)，這也使互連網(wǎng)絡(luò)由專用型發(fā)展成為通用型。 （ 1）網(wǎng)絡(luò)規(guī)模：是指網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)，它體現(xiàn)網(wǎng)絡(luò)所能連接的部件數(shù)，隨著設(shè)備的增加而擴(kuò)大。如果一個(gè)結(jié)點(diǎn)直接連接的其它結(jié)點(diǎn)越多，則該網(wǎng)絡(luò)的連接度也就越高。 （ 4）網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)直徑是指網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間的最大距離，常用 D表示。 （ 5）等分寬度：分為通道等分寬度和線等分寬度。 （ 6）結(jié)點(diǎn)間線長：是指兩結(jié)點(diǎn)之間的線路長度，它影響信號(hào)傳輸中的延時(shí)、扭曲和需要的功率。對(duì)于這種網(wǎng)絡(luò)，容易設(shè)計(jì)和編程。靜態(tài)數(shù)據(jù)尋徑網(wǎng)絡(luò)是指其結(jié)構(gòu)不能用程序改變；而動(dòng)態(tài)數(shù)據(jù)尋徑網(wǎng)絡(luò)的結(jié)構(gòu)可用程序改變。 （ 1）帶寬 是指網(wǎng)絡(luò)傳送信息的速率，常用 Mbps或 MBps表示，又分為聚集帶寬和等分帶寬。而等分帶寬是指每秒鐘從最小線等分寬度 (線 )上通過信息的最大位數(shù)或字節(jié)數(shù)。 若用 r表示線等分寬度中每條線上傳送信息的速率，則等分帶寬可表示為P=kwr。 （ 3）飛行時(shí)間：是指消息的第一位數(shù)據(jù)通過網(wǎng)絡(luò)到達(dá)接收端所用的時(shí)間。 （ 5）總延時(shí)：包括上述傳輸延時(shí)和網(wǎng)絡(luò)兩端的發(fā)送與接收時(shí)間。顯然，誤碼率越低越好。在保證功能要求的基礎(chǔ)上，越低越好。 （ 1）傳送方式 傳送方式分為同步和異步兩種。 異步方式則不需要統(tǒng)一的時(shí)鐘信號(hào)在各處理機(jī)（或單元）之間進(jìn)行同步，各處理機(jī)（或單元）根據(jù)自身需要相互建立動(dòng)態(tài)連接。所謂集中控制，是由統(tǒng)一的控制器對(duì)各個(gè)互連開關(guān)實(shí)施控制；而分散控制，是由各個(gè)開關(guān)自身實(shí)施控制。 （ 3）交換方式 是指數(shù)據(jù)傳送管理方式，分為線路交換和分組交換。分組交換是對(duì)數(shù)據(jù)進(jìn)行分組，分別送入互連網(wǎng)絡(luò)，各分組可通過不同的路由到達(dá)目標(biāo)結(jié)點(diǎn)，適合于短數(shù)據(jù)報(bào)文傳送。 （ 4）拓?fù)浣Y(jié)構(gòu) 是指互連網(wǎng)絡(luò)中各結(jié)點(diǎn)之間的連接關(guān)系，可分為靜態(tài)拓?fù)浜蛣?dòng)態(tài)拓?fù)洹? 一維靜態(tài)拓?fù)溆芯€性結(jié)構(gòu)，二維有圓型、星型、樹狀和網(wǎng)格型等結(jié)構(gòu)，三維及以上有超立方體結(jié)構(gòu)等。 為反映互連網(wǎng)絡(luò)的連接特征，常用函數(shù)的形式進(jìn)行描述，稱為互連函數(shù)，它反映的是從輸入端到輸出端的映象關(guān)系。 設(shè) x是一個(gè) n位的二進(jìn)制數(shù)，即 x=bn1bn2…b1b0，其中 n=log2N。0 全混洗互連函數(shù) f(x)=f(bn1bn2…b1b0)=bn2…b1b0bn1 互連函數(shù) 也稱為直通互連函數(shù)，是指輸出端與相同序號(hào)的輸入端對(duì)應(yīng)連接。 圖 恒等互連示意圖 交換互連函數(shù)（ Exchange）實(shí)現(xiàn)輸入端與地址中某一位取反的輸出端連接： Exchange(bn1bn2…b1b0)= bn1bn2…b1b0 擴(kuò)展交換互連函數(shù)是把地址中的任一位變反，其表達(dá)式為： Exchange(bn1bn2…bk…b1b0)k= bn1bn2…bk …b1b0 圖 立方體結(jié)構(gòu)圖 如果設(shè) N=8，則 n=log2N=3，其互連關(guān)系在空間表示一個(gè)立方體，如圖 ，因此也稱為立方體（ Cube）互連函數(shù)： Cube0(b2b1b0)=b2b1b0 Cube1(b2b1b0)=b2b1b0 Cube2(b2b1b0)=b2b1b0 按照 Cube函數(shù)的連接示 意如圖 。 【 例 】 設(shè)有 64個(gè)處理器，其編號(hào)依次是 0， 1， 2， …， 63，按照互連函數(shù) Exchange()4連接時(shí)，第 21號(hào)處理器與哪一個(gè)處理器連接。0101 =000101 全混洗互連函數(shù) (Shuffle)也稱為均勻混洗互連函數(shù)，它 實(shí)現(xiàn)輸入端與地址中最高位循環(huán)移位到最低位的輸出端連接： Shuffle(bn1bn2…b1b0)=bn2…b1b0bn1 其示意如圖 ，猶如把一沓撲克牌對(duì)分后均勻洗牌的結(jié)果，因此稱為全混洗互連函數(shù)。 圖 全混洗互連示意 此外，還有逆全混洗和擴(kuò)展全混洗互連函數(shù)。 2i的輸出端連接： PM2I+i(j )=(j+2 i) mod N