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