計(jì)算機(jī)互連網(wǎng)絡(luò)ppt課件-文庫吧資料
2025-05-09 07:08本頁面
【正文】 C u b e0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5單級(jí)立方體網(wǎng)絡(luò)廣播算法 （順序是 C ub e3 ～ C ube0）2022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 34 選播算法 選播算法的設(shè)計(jì)目標(biāo)有 3種：時(shí)間最少、流量最少、在時(shí)間最少的多個(gè)方案中選取流量最少方案。 如圖 （ 圖中實(shí)線箭頭表示一個(gè)數(shù)據(jù)的一次實(shí)際傳送 ， 虛線指出上一步已有數(shù)據(jù)的結(jié)點(diǎn) ） 。下面舉幾個(gè)具體實(shí)例。向不同方向進(jìn)行的發(fā)送不能同時(shí)進(jìn)行（具有這種能力的互連網(wǎng)不屬于現(xiàn)在的討論范圍）。 研究廣播與選播算法的目的是盡量利用互連網(wǎng)的并行傳輸能力，尋找花費(fèi)時(shí)間最少或者動(dòng)用信道次數(shù)（又稱 流量 或 通道數(shù) ）最少的方案。個(gè)）結(jié)點(diǎn)， 1≤N39。 輸入 第 2 級(jí) 第 1 級(jí) 第 0 級(jí) 輸出 000 00 1 0 1 0 0 11 1 00 1 0 1 11 0 1 11 000 00 1 0 1 0 0 11 1 00 1 0 1 11 0 1 11 2022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 28 傳輸性能計(jì)算 基本傳輸時(shí)間（ P400） 說明：指 相鄰結(jié)點(diǎn)間傳輸 單個(gè)數(shù)據(jù)包 所用時(shí)間，不考慮中間結(jié)點(diǎn)轉(zhuǎn)發(fā)的時(shí)間開銷。 輸入 第 2 級(jí) 第 1 級(jí) 第 0 級(jí) 輸出000 00 000 1 00 10 1 0 0 1 00 11 01 11 00 1 001 0 1 1 0111 0 1 101 11 1 112022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 27 Omega網(wǎng)尋徑?jīng)_突 給定傳輸 101B→ 011B， 二者異或結(jié)果為 110B， 路徑 如下圖 紅線 所示 。 例如給定傳輸 101B→ 011B， 二者異或結(jié)果為 110B， 于是從 101B號(hào)輸入端開始 ， 把它遇到的第 2級(jí)開關(guān)置為 “ 交換 ” ， 第 1級(jí)開關(guān)置為 “ 交換 ” ， 第 0級(jí)開關(guān)置為 “ 直連 ” 。 2022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 26 多級(jí)混洗 — 交換網(wǎng)絡(luò)尋徑算法（路由算法） 目的 ：根據(jù)給定的輸入 /輸出對(duì)應(yīng)關(guān)系 ， 確定各開關(guān)的狀態(tài) 。 如果各級(jí)二元交換開關(guān)都處于 “ 直連 ” 狀態(tài) ， N個(gè)結(jié)點(diǎn)的數(shù)據(jù)通過網(wǎng)絡(luò)僅經(jīng)過 n次混洗操作 ， 排列順序最終 恢復(fù)輸入狀態(tài) （ 混洗函數(shù)性質(zhì) 2） ；如果各級(jí)二元交換開關(guān)都處于 “ 交換 ” 狀態(tài) ， 則 N個(gè)結(jié)點(diǎn)的數(shù)據(jù)在每次混洗之后緊接著一次交換 （ Cube0） ， 也就是地址碼的最低位取反 ， 最后 n位地址均被取反 。 各級(jí)編號(hào)是 n1， …… ， 0， 即按 降序排列 。 多級(jí)混洗 — 交換網(wǎng)絡(luò)結(jié)構(gòu)：它 由 n級(jí)構(gòu)成 ， 每一級(jí)包含 一個(gè)無條件 混洗拓?fù)?線路 和 一列可控的二元 交換開關(guān) ， 前后重復(fù) ， 便于制造 。 級(jí)控方式 就是同一級(jí) （ 即同一列 ） 開關(guān)共用一個(gè)控制信號(hào) ， 動(dòng)作保持一致；部分級(jí)控方式 在第 i級(jí)設(shè)置 i+1個(gè)獨(dú)立的控制信號(hào) ， 每個(gè)信號(hào)管轄若干開關(guān)； 單元控制方式 為每個(gè)開關(guān)獨(dú)自設(shè)置一個(gè)控制信號(hào) ， 各開關(guān)動(dòng)作獨(dú)立 ， 性能比前兩種方式都更靈活 ， 結(jié)構(gòu)也更復(fù)雜 。 二元交換開關(guān)的基本接通狀態(tài)有 “ 直連 ” 、 “ 交換 ” 、 “ 上播 ” 和 “ 下播 ” ， 在進(jìn)行數(shù)據(jù)置換時(shí)只能使用前 2種 。 我們只學(xué)習(xí)多級(jí)混洗 — 交換網(wǎng) 。 通常在 N個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)中 ， 多級(jí) ICN由 n級(jí)構(gòu)成 （ n = log2N） 。 i的功能是對(duì)入端結(jié)點(diǎn)編號(hào)加或減 2i， 然后再作模 N運(yùn)算 PM2+i（ X） = X + 2i mod N PM2i（ X） = X 2i mod N 其中 X = 0 ～ N 1， i = 0 ～ n 1。 單級(jí) PM2I網(wǎng)絡(luò)的直徑是 。 ? 性質(zhì) 1：對(duì)相同的 i值 ， PM2+i 與 PM2i函數(shù)的傳送路徑相同 ， 方向相反 （ 右圖中所有箭頭 反向即為 PM21的拓?fù)湫螤?） ； ? 性質(zhì) 2： PM2+(n1) = PM2(n1)。 單級(jí)加減 2i網(wǎng) （ PM2I網(wǎng)，移數(shù)網(wǎng)， P398倒數(shù)第 2行） 0 01 12 23 34 45 56 67 72022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 22 N = 8的 PM2+i網(wǎng)絡(luò)拓?fù)湫螤钊缦聢D所示，可以看出它包含多個(gè)強(qiáng)連通子圖（即除去若干邊以后仍能保證任何一對(duì)結(jié)點(diǎn)互相可達(dá)），所以這 2n個(gè)函數(shù)并不是實(shí)現(xiàn)互連網(wǎng)的最小集合。 例如：當(dāng) N = 8時(shí) ， PM2+0（ 0） = 0 + 20 = 1， PM2+0（ 1） = 1 + 20 = 2， PM2+0（ 7） = 7 + 20 = 0， PM2+1（ 0） = 0 + 21 = 2。 PM2I函數(shù)定義： PM2177。 1，…… ， PM2 177。 交換置換函數(shù)定義：對(duì)入端結(jié)點(diǎn)編號(hào)二進(jìn)制形式的第 0位取反 0 1 2 3 4 5 6 7 2022/5/31 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 21 該網(wǎng)絡(luò)由 PM2I函數(shù)定義 ， PM2I函數(shù)共有 n對(duì)成員 ， 分別是 PM2 177。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1