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