計(jì)算機(jī)互連網(wǎng)絡(luò)ppt課件-在線瀏覽
2025-06-20 07:08本頁面
【正文】 ，而從結(jié)點(diǎn)出來的通道數(shù)則稱為 出度 。 (3) 距離 兩結(jié)點(diǎn)之間相連的最少邊數(shù)。網(wǎng)絡(luò)直徑應(yīng)當(dāng)盡可能地小。 (6) 路由 在網(wǎng)絡(luò)通信中對路徑的選擇與指定。 基本概念 2022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 4 (1)通用網(wǎng) /專用網(wǎng) 通用網(wǎng) （原用于計(jì)算機(jī)之間交換信息的普通網(wǎng)絡(luò)） ， 專用網(wǎng) （專用于并行計(jì)算系統(tǒng)各處理單元之間并行交換數(shù)據(jù)的特殊網(wǎng)絡(luò)） ； 通用網(wǎng)包括以太網(wǎng)、電話撥號網(wǎng)等，專用網(wǎng)在后面介紹。 (3)同步網(wǎng) /異步網(wǎng)（并行網(wǎng)再細(xì)分） 同步網(wǎng) （多個結(jié)點(diǎn)必須朝同一方向、以同一距離、同時開始發(fā)送） ， 異步網(wǎng)（多個結(jié)點(diǎn)可以朝不同方向、以不同距離、不同時開始發(fā)送，可能沖突） ； (4)靜態(tài)網(wǎng) /動態(tài)網(wǎng)（ P402和 P408） 靜態(tài)網(wǎng) （結(jié)點(diǎn)之間有 固定連接 ） ， 動態(tài)網(wǎng) （結(jié)點(diǎn)之間的連接 關(guān)系不固定，須通過開關(guān)導(dǎo)向或地址識別來確定當(dāng)前的目的結(jié)點(diǎn) ） ； 互連網(wǎng)絡(luò)的分類 2022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 5 靜態(tài)網(wǎng)絡(luò)使用直接鏈路，它一旦構(gòu)成后就固定不變。由于直徑隨 N線性增大，因此當(dāng) N比較大時，就不應(yīng)使用了。 2022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 6 環(huán)可以單向工作，也可以雙向工作。 雙向環(huán)的直徑為 N/2，單向環(huán)的直徑是 N。 按照價格和性能增加的順序，動態(tài)連接網(wǎng)絡(luò)的排隊(duì)次序?yàn)榭偩€系統(tǒng)、多級互連網(wǎng)絡(luò) (MIN)和交叉開關(guān)網(wǎng)絡(luò)。 2022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 13 交叉開關(guān)網(wǎng)絡(luò)是單級網(wǎng)絡(luò)，它由交叉點(diǎn)上的一元開關(guān)構(gòu)成。正方形交叉開關(guān)網(wǎng)絡(luò) (n＝ m)可以無阻塞地實(shí)現(xiàn) n!種置換。 對小型系統(tǒng)來說性能價格比較高。 2022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 14 總線的造價最低，但其缺點(diǎn)是可用的帶寬較窄，容易產(chǎn)生故障。但是，交叉開關(guān)的帶寬和路由性能最好。 多級網(wǎng)絡(luò)則是兩個極端之間的折衷。然而，其時延隨網(wǎng)絡(luò)的級數(shù)而上升。 總線、多級網(wǎng)絡(luò)、交叉開關(guān)的對比 2022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 15 特點(diǎn)：成本低，并行性差。 (2) 傳輸協(xié)議 (使用規(guī)則，軟件， P427P435)： 碰撞爭用，令牌協(xié)議，劍橋環(huán)。 示例： (4) 典型代表：以太網(wǎng)，令牌網(wǎng)（環(huán)或直線）。 (1) 互連函數(shù) N個輸入到 N個輸出的一種對應(yīng)狀態(tài)可以用一個映射函數(shù)表示，稱為互連函數(shù)。 互連函數(shù)有多種表示方式，如下例所示： f(0)=1 0 0 f(1)=2 1 1 f= 0 1 2 3 f=(0,1,2)(3) f(2)=0 2 2 1 2 0 3 f(3)=3 3 3 一個網(wǎng)絡(luò)通過開關(guān)切換可以形成多個映射關(guān)系，所以要用“ 互連函數(shù)族 ”來定義一個網(wǎng)絡(luò)。 開關(guān)的每種接通組合方式可用一個互連函數(shù)表示。 互連函數(shù)族的組成必須使網(wǎng)絡(luò)成為 連通圖 。 立方體 函數(shù) 定義： Cubei的功能 是對 入端結(jié)點(diǎn)編號二進(jìn)制形式的第 i位取反 Cubei(Xn1… Xi+1XiXi1… X0)=Xn1… Xi+1XiXi1… X0， 其中 0≤ i≤n 1 例如： Cube0(0)=1， Cube3(7)=15。 最壞情況下的傳輸需 對輸入結(jié)點(diǎn)編號的全部 n位取反 。 立方體 函數(shù) 性質(zhì) ： 結(jié)合律 、 交換律 以及 自反 律 （ Cubei重復(fù)使用 2次的結(jié)果與原始自變量相 同 ） 。 ? 混洗函數(shù) 定義： 2j mod（ N1） ， 當(dāng) j N1 shuffle（ j） = N1 ， 當(dāng) j = N1 例如：當(dāng) N=8時 ， shuffle（ 0） = 0， shuffle（ 1） = 2， shuffle（ 7） = 7。 ? 性質(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ò) 。 單級混洗 交換網(wǎng) （ P396倒數(shù)第 8行 ） 0 1 2 3 4 5 6 72022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 20 交換置換（ P395） E(Xn1Xn2… X1X0)=Xn1Xn2… X1X0， 其中 0≤ i≤n 1 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 n=3的交換置換形狀如 右 圖所示。 0， PM2 177。 (n1)。 i的功能是對入端結(jié)點(diǎn)編號加或減 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。 N = 8的 PM2+1（ j） 函數(shù)開關(guān)狀態(tài)如右圖 所示 ， 其連接規(guī)律是把各入端結(jié)點(diǎn)編號加上 相同的增量 21（ mod N） ， 獲得出端結(jié)點(diǎn)編號 。實(shí)際應(yīng)用中為了降低造價，人們往往取它們的一個子集來構(gòu)造互連網(wǎng)。 根據(jù)性質(zhì) 2， 我們知道 單級 PM2I網(wǎng)絡(luò)實(shí)際上只能 實(shí)現(xiàn) 2n1種不同的置換 。 ? ?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… X1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1