第7章-互聯(lián)網(wǎng)絡(luò)-文庫吧
2025-08-01 01:02 本頁面
【正文】 徑信息 S：順序號 D：數(shù)據(jù)片 傳輸方式 — 分為存儲 轉(zhuǎn)發(fā)、蟲孔尋徑兩種。 存儲 轉(zhuǎn)發(fā) — 傳輸單位為數(shù)據(jù)包，尋徑、傳輸串行進行，中間節(jié)點需緩沖整個數(shù)據(jù)包。 R T N1 N2 N3 N4 數(shù)據(jù)包 1 數(shù)據(jù)包 2 D 蟲孔尋徑 — 傳輸單位為數(shù)據(jù)片，尋徑、傳輸流水進行，中間節(jié)點需緩沖數(shù)據(jù)片。 T N1 N2 N3 N4 數(shù)據(jù)包 1 數(shù)據(jù)包 2 D 應(yīng)用 — 包交換只能與分布控制配對，應(yīng)用于 MIMD系統(tǒng)。 轉(zhuǎn)上二頁 回 17頁 拓撲結(jié)構(gòu) 是實現(xiàn)互連功能的主要機構(gòu)，反映互連函數(shù)實現(xiàn)的復(fù)雜度。 拓撲結(jié)構(gòu)與互連函數(shù)： 網(wǎng)絡(luò)拓撲結(jié)構(gòu)不同，實現(xiàn)互連函數(shù)的效率不同。 如： 高維拓撲結(jié)構(gòu)實現(xiàn)移位函數(shù)效率總比低維結(jié)構(gòu)好； 又如： 對稱拓撲結(jié)構(gòu)實現(xiàn)交換函數(shù)效率總比非對稱結(jié)構(gòu)好。 互連函數(shù)與并行算法： 不同的并行算法需要不同的互連函數(shù)支持； 同一系統(tǒng)的應(yīng)用需要支持多種并行算法。 集中控制方式 對拓撲結(jié)構(gòu)的要求較高，直接影響并行算法的實現(xiàn)效果 (同時連接的結(jié)點對數(shù)量 )； 分布控制方式 對拓撲結(jié)構(gòu)的要求一般。 路由算法 決定消息在網(wǎng)絡(luò)圖中如何移動 (選擇路徑 )的算法。 采用分布控制的互連網(wǎng)絡(luò)才涉及到路由問題。 路由算法： 算術(shù)路由、源路由、查表路由、自適應(yīng)路由等。 路由算法目標： 避免死鎖、維持低時延、均勻分布負載、容錯等。 流控機制 在資源使用沖突時控制各通道流量 (帶寬 )的機制。 流控機制層次： 有鏈路級流控、端到端流控兩個層次。 四、互連網(wǎng)絡(luò)基本性能 時延和帶寬是評價互連網(wǎng)絡(luò)性能的兩個基本指標。 時延 發(fā)送方 接收方 發(fā)送方 開銷 傳輸時間 飛行時間 接收方 開銷 傳輸時間 傳輸時延 互連網(wǎng)絡(luò) 通信時延 =額外開銷 +飛行時間 +消息長度 /通道帶寬 額外開銷 — 指收 /發(fā)雙方軟 /硬件開銷，與結(jié)點內(nèi)核及NIC結(jié)構(gòu)有關(guān)； 飛行時間 — 與結(jié)點間距離 (拓撲結(jié)構(gòu) )及通道帶寬有關(guān)； 通道帶寬 — 與鏈路帶寬和通道競爭情況有關(guān)。 帶寬 可通過端口帶寬、聚集帶寬和等分帶寬表示網(wǎng)絡(luò)帶寬特性。 端口帶寬： 結(jié)點或交換機每個端口 (輸入和輸出 )的帶寬。 聚集帶寬： 網(wǎng)絡(luò)的前一半節(jié)點 (與結(jié)點不同含義 )與后一半節(jié)點間傳輸?shù)膸?，一般指網(wǎng)絡(luò)內(nèi)部帶寬的總和。 等分帶寬 (對剖帶寬 )： 將網(wǎng)絡(luò)按結(jié)點均勻切成兩個子網(wǎng)，子網(wǎng)間的通信帶寬。 … … … 結(jié)點 0 … 結(jié)點 N/21 結(jié)點 N/2 結(jié)點 N1 … 結(jié)點 0 … 結(jié)點 N/21 結(jié)點 N/2 結(jié)點 N1 … 輸出帶寬 +輸入帶寬 =端口帶寬 b 等分帶寬 B=lwb/2 聚集帶寬 l’wb/2 節(jié)點 (交換開關(guān) ) … 說明： l、 l’為穿過 剖面鏈路數(shù)； w為每條鏈路連線數(shù)。 回 28頁 回 30頁 第二節(jié) 互連網(wǎng)絡(luò)與拓撲結(jié)構(gòu) 一、互連函數(shù)與拓撲結(jié)構(gòu) 互連函數(shù)是并行算法與硬件互連的結(jié)合點。 拓撲結(jié)構(gòu)是硬件互連實現(xiàn)互連函數(shù)的有效機構(gòu)。 互連函數(shù)也可稱為單級互連網(wǎng)絡(luò)。 恒等置換 互連函數(shù)： I(b2b1b0)=(b2b1b0) 000 001 010 011 100 101 110 111 N=8恒等置換 000 001 010 011 100 101 110 111 互連特性： 互連函數(shù)可逆；只有一種變換功能。 交換置換 互連函數(shù)： Exchange(b2b1b0)=(b2b1b0) 000 001 010 011 100 101 110 111 N=8交換置換 000 001 010 011 100 101 110 111 互連特性： 互連函數(shù)可逆；只有一種變換功能。 應(yīng)用： 2 2交換開關(guān) 可實現(xiàn)恒等置換與交換置換功能，功能控制可通過外部信號或內(nèi)部消息譯碼實現(xiàn)。 恒等 交換 上播 下播 立方體置換 互連函數(shù)： Cubek(bn1… bk… b0)=(bn1… bk… b0) 000 001 010 011 100 101 110 111 N=8 Cube0置換 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 N=8 Cube1置換 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 N=8 Cube2置換 000 001 010 011 100 101 110 111 互連特性： 互連函數(shù)可逆； n位編碼有 n種 (Cube0， … ， Cuben1)變換功能。 應(yīng)用： n立方體結(jié)構(gòu) 可實現(xiàn) n種立方體變換，功能控制可通過各端點的外部信號或內(nèi)部消息譯碼實現(xiàn)。 z y x 010 011 110 111 000 001 101 100 混洗置換 互連函數(shù)： Shuffle(bn1bn2… b1b0)=(bn2… b1b0bn1)； 000 001 010 011 100 101 110 111 N=8 混洗置換 000 001 010 011 100 101 110 111 互連特性： 互連函數(shù)不可逆 (全 0、全 1編碼的結(jié)點除外 )； 只有一種變換功能。 應(yīng)用： 混洗變換與交換變換的多次組合，可實現(xiàn)某結(jié)點到任意結(jié)點的連接。 0 1 2 3 4 5 6 7 回 32頁 蝶式置換 互連函數(shù)： β (bn1bn2… b1b0)=(b0bn2… b1bn1)； 000 001 010 011 100 101 110 111 N=8蝶式 置換 000 001 010 011 100 101 110 111 子蝶式和超蝶式置換： β (k)(bn1… bk+1bkbk1… b0)=(bn1… bk+1b0bk1… b1bk)； β (k)(bn1… bnkbnk1bnk2… b0)=(bnk1bn2… bnkbn1bnk2… b0)； 000 001 010 011 100 101 110 111 N=8 β(1)子 蝶式 置換 000 001 010 011 100 101 110 111 互連特性： 互連函數(shù)可逆； n位編碼有 2n2種 (子、超各為 n1)變換功能。 應(yīng)用： 蝶式與子蝶式變換實現(xiàn)分組功能，加上交換變換，可實現(xiàn)某結(jié)點到任意結(jié)點的連接。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1