計算機(jī)互連網(wǎng)絡(luò)ppt課件(完整版)
【正文】 Cube0 ～ Cuben1各一次 ， 每一步都從當(dāng)前擁有數(shù)據(jù)的所有結(jié)點同時發(fā)往等量的無數(shù)據(jù)結(jié)點 ， 也就是將網(wǎng)絡(luò)中擁有數(shù)據(jù)的結(jié)點數(shù)加倍 。 總時間 = 發(fā)送前準(zhǔn)備時間 + 首位路途時間 + 首位至末位通過時間 + 接收后處理時間 其中：首位至末位通過時間 = 數(shù)據(jù)包總位數(shù) / 傳輸頻率（即單位時間傳輸?shù)奈粩?shù)） 2022/5/31 計算機(jī)系統(tǒng)結(jié)構(gòu) 29 四種尋徑方式對應(yīng)的總時間（ P415） (1)線路交換 T = ( Lt / B ) D + L / B 其中： Lt是為建立路徑所需的小信息包的長度， (2)存儲轉(zhuǎn)發(fā) T = ( L / B ) D + L / B = ( D + 1 ) L / B (3)虛擬直通 T = ( Lh / B ) D + L / B = ( Lh D + L ) / B 其中： Lh是消息的尋徑頭部的長度， (4)蟲蝕尋徑 T = Tf D + L / B = ( Lf / B ) D + L / B = ( Lf D + L ) / B 其中： Lf是片的長度， 2022/5/31 計算機(jī)系統(tǒng)結(jié)構(gòu) 30 廣播與選播算法（ P425） 廣播是將一個結(jié)點的數(shù)據(jù)復(fù)制到全部 N個結(jié)點；選播是將一個結(jié)點的數(shù)據(jù)復(fù)制到多個（ N39。 程序員根據(jù)數(shù)據(jù)置換或復(fù)制的需要 ， 可以靈活地設(shè)置各開關(guān)的狀態(tài) 。 各開關(guān)的控制信號可采用 3種分配方式之一： 級控方式 、 部分級控方式 和 單元控制方式 。 ? ?2/n i=1 i=207 1i=06 25 342022/5/31 計算機(jī)系統(tǒng)結(jié)構(gòu) 23 各種互連函數(shù)總結(jié) E(Xn1Xn2… X1X0)=Xn1Xn2… X1X0， 其中 0≤ i≤n 1 交換置換函數(shù)定義 Cubei(Xn1… Xi+1XiXi1… X0)=Xn1… Xi+1XiXi1… X0， 其中 0≤ i≤n 1 立方體函數(shù)定義： Cubei的功能是對入端結(jié)點編號二進(jìn)制形式的第 i位取反 均勻洗牌 shuffle（ Xn1Xn2…… X0） = Xn2…… X0Xn1（ 循環(huán)左移 ） PM2I函數(shù)定義： PM2177。 i的功能是對入端結(jié)點編號加或減 2i， 然后再作模 N運(yùn)算 PM2+i（ j） = j + 2i mod N PM2i（ j） = j 2i mod N 其中 j = 0 ～ N 1， i = 0 ～ n 1。 ? 性質(zhì) 1： shuffle（ Xn1Xn2…… X0） = Xn2…… X0Xn1（ 循環(huán)左移） ? 性質(zhì) 2： shufflen（ j） = j n=3的 混洗 網(wǎng)絡(luò)拓?fù)湫螤钊缦聢D 綠線 所示 ， 可以看出它不是一個 連通圖 ， 所以還需要增加一個 交換函數(shù) （ 圖中 紅線 所示 ） ， 才能構(gòu)成完整的單級混洗 — 交換網(wǎng)絡(luò) 。 立方體 函數(shù) 定義： Cubei的功能 是對 入端結(jié)點編號二進(jìn)制形式的第 i位取反 Cubei(Xn1… Xi+1XiXi1… X0)=Xn1… Xi+1XiXi1… X0， 其中 0≤ i≤n 1 例如： Cube0(0)=1， Cube3(7)=15。 (1) 互連函數(shù) N個輸入到 N個輸出的一種對應(yīng)狀態(tài)可以用一個映射函數(shù)表示，稱為互連函數(shù)。然而，其時延隨網(wǎng)絡(luò)的級數(shù)而上升。 對小型系統(tǒng)來說性能價格比較高。 雙向環(huán)的直徑為 N/2，單向環(huán)的直徑是 N。 基本概念 2022/5/31 計算機(jī)系統(tǒng)結(jié)構(gòu) 4 (1)通用網(wǎng) /專用網(wǎng) 通用網(wǎng) （原用于計算機(jī)之間交換信息的普通網(wǎng)絡(luò)） ， 專用網(wǎng) （專用于并行計算系統(tǒng)各處理單元之間并行交換數(shù)據(jù)的特殊網(wǎng)絡(luò)） ； 通用網(wǎng)包括以太網(wǎng)、電話撥號網(wǎng)等，專用網(wǎng)在后面介紹。在單向通道的情況下，進(jìn)入結(jié)點的通道數(shù)叫做 入度 ，而從結(jié)點出來的通道數(shù)則稱為 出度 。 ?互連網(wǎng)絡(luò)是一種由 開關(guān)元件 按照一定的拓樸結(jié)構(gòu)和控制方式 構(gòu)成的網(wǎng)絡(luò)，用來實現(xiàn)多處理機(jī)、多計算機(jī)之間或多個功能 部件之間的連接，是多處理機(jī)、多計算機(jī)系統(tǒng)的核心。 輸入端 IC N 輸出端 輸入端 IC N 輸出端(a ) 處理單元 / 處理單元的連接 (b ) 處理單元 / 存儲單元 的連接0 0（開關(guān)網(wǎng)絡(luò)）N 1 N 10 0（開關(guān)網(wǎng)絡(luò)）N 1 N 1處理單元 0處理單元 N 1存儲單元 0存儲單元 N 1處理單元 0處理單元 N 12022/5/31 計算機(jī)系統(tǒng)結(jié)構(gòu) 3 (1) 網(wǎng)絡(luò)規(guī)模 一般說來，網(wǎng)絡(luò)用圖來表示。 (5) 等分寬度 當(dāng)某一網(wǎng)絡(luò)被切成相等的兩半時，沿切口的最小邊數(shù) (通道 )稱為通道等分寬度。 下面介紹幾種常用的靜態(tài)網(wǎng)絡(luò)。 通常，這類交叉開關(guān)網(wǎng)絡(luò)需要使用 n m個交叉點開關(guān)。如果網(wǎng)絡(luò)的規(guī)模較小，它是一種理想的倍選擇。 (3) 主要參數(shù) (P399)： 直徑，中剖寬度，結(jié)點的度，最長邊。 f( j入 ) = j出 ， 0≤ j≤N 1 在互連函數(shù)中，記： N ── 結(jié)點數(shù) n = log2N ── 維數(shù) j= Xn1…… X0 ─ ─ 結(jié)點 編號的二進(jìn)制形式，位數(shù)為 n。 單級立方體網(wǎng) （ Cube網(wǎng)， P396第 1行 / P405第 4行） 2 30 1 6 74 52022/5/31 計算機(jī)系統(tǒng)結(jié)構(gòu) 19
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1