計算機互連網(wǎng)絡ppt課件-資料下載頁
2025-05-03 07:08本頁面
【正文】 法，具體操作順序既可以是先短邊后長邊“長樹”，也可以是先長邊后短邊“砍樹” （ 教材 P426圖(c)）。 實現(xiàn)第 3種目標的一種重要算法是貪婪算法（教材 P426圖 (b)）。 不論對何種網(wǎng)絡，貪婪算法總是重復使用一個固定的操作規(guī)則：從當前擁有數(shù)據(jù)的結點出發(fā)，向需要數(shù)據(jù)的結點數(shù)最多的方向并行傳送一步，如此循環(huán)，直至傳遍所有需要數(shù)據(jù)的結點。如果最后發(fā)現(xiàn)某個通道（即一次數(shù)據(jù)發(fā)送操作）不在通往給定目標結點的路徑上，則應將其刪去。 2022/5/31 計算機系統(tǒng)結構 35 (1)單級網(wǎng)格網(wǎng)（ Mash網(wǎng)）貪婪算法 算法： 以教材 P426圖 ，小圖 (a)指出總共有 1個源結點 S和 5個目的結點。小圖 (b)指出從 S出發(fā)，首先應向右鄰結點發(fā)送數(shù)據(jù)，因為 S的左方只有 1個目的結點、上方有 3個目的結點、右方有４個目的結點；第二步從這２個擁有數(shù)據(jù)的結點出發(fā)，可以再向右發(fā)送（有 3個目的結點），也可以改向上發(fā)送（也有 3個目的結點）， …… 。只要每步遵守貪婪算法的規(guī)則，最后形成的不同路徑樹的時間和流量都是相同的。 2022/5/31 計算機系統(tǒng)結構 36 (2)單級立方體網(wǎng)絡貪婪算法 算法： 以教材 P426圖 。 小圖 (a)指出廣播算法的時間是 4， 流量是 15。Cube0 ～ Cuben1的使用順序對廣播算法的時間和流量沒有影響 ， 但對小圖 (b)的選播算法的時間和流量有影響 。 先看一個簡單的例子 （ 下圖 ） ：已知 N=4， 維數(shù) n=2， 源結點是 0， 目的結點是 1和 3。 源結點編號的二進制形式 00在 bit0位與兩個目的結點的二進制形式 0 11 都不相同 ， 而在 bit1位僅與一個目的結點的二進制形式不同 ， 所以應該先傳bit0方向 、 再傳 bit1方向 ， 如右 圖 (a)所示 ， 這 時流量 =2；如果 先傳 bit1方向 、 再傳 bit0方向 ， 如右圖 (b)所示 ， 則流量 =3。 0 0 0 0 Cu b e0 Cu b e1 0 0 01 0 0 1 0 Cu b e1 Cu b e00 0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 (a) 先傳 Cu b e0方向，流量 = 2 (b ) 先傳 C u b e1方向，流量 =3單級立方體網(wǎng)絡貪婪算法的簡單例子2022/5/31 計算機系統(tǒng)結構 37 0 1 0 1 Cu b e3 0 1 0 1 1 1 0 1 Cu b e1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 Cu b e0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 Cu b e2 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 5 1 4 0 7 3 6 2 1 3 9 1 2 8 1 5 1 1 1 4 1 0單級立方體網(wǎng)絡貪婪算法的復雜例子 再看教材 P426圖 (b)的例子。源結點編號的二進制形式 0101在 Cube0 ～Cube3位分別與 5個目的結點的二進制形式不同，所以 Cube2方向應該最后發(fā)送，其它 3個方向的發(fā)送先后順序則沒有限制。教材 P427采用了Cube Cube Cube0、 Cube2的發(fā)送順序，如下圖所示，時間 =4，總流量 =10。 2022/5/31 計算機系統(tǒng)結構 38 本章小結 (1) 通用網(wǎng)的拓撲結構，傳輸協(xié)議，主要參數(shù)，典型代表； (2) 互連函數(shù)（置換，循環(huán)）的 4種表示方式； (3) 單級立方體網(wǎng)（ Cube網(wǎng)）的定義，拓撲形狀，直徑，性質(zhì)，互連函數(shù)族的組成； (4) 單級混洗 交換網(wǎng)的定義，拓撲形狀，直徑，性質(zhì)，互連函數(shù)族的組成； (5) 單級加減 2i網(wǎng)（ PM2I網(wǎng)，移數(shù)網(wǎng)）的定義，拓撲形狀，直徑，性質(zhì)，互連函數(shù)族的組成； (6) 二元交換開關，控制信號的 3種分配方式； (7) 多級混洗 — 交換網(wǎng)絡的結構，尋徑算法（路由算法）。 習題： P446，題 3，題 10，題 26(1)～ (2)，題 27(3)。
教學課件相關推薦
鄂ICP備17016276號-1