第7章-互聯(lián)網(wǎng)絡(luò)-展示頁(yè)
2024-08-31 01:02本頁(yè)面
【正文】 110 111 互連特性： 互連函數(shù)不可逆 (全 0、全 1編碼的結(jié)點(diǎ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)變換功能。 交換置換 互連函數(shù)： Exchange(b2b1b0)=(b2b1b0) 000 001 010 011 100 101 110 111 N=8交換置換 000 001 010 011 100 101 110 111 互連特性： 互連函數(shù)可逆；只有一種變換功能。 互連函數(shù)也可稱為單級(jí)互連網(wǎng)絡(luò)。 回 28頁(yè) 回 30頁(yè) 第二節(jié) 互連網(wǎng)絡(luò)與拓?fù)浣Y(jié)構(gòu) 一、互連函數(shù)與拓?fù)浣Y(jié)構(gòu) 互連函數(shù)是并行算法與硬件互連的結(jié)合點(diǎn)。 等分帶寬 (對(duì)剖帶寬 )： 將網(wǎng)絡(luò)按結(jié)點(diǎn)均勻切成兩個(gè)子網(wǎng)，子網(wǎng)間的通信帶寬。 端口帶寬： 結(jié)點(diǎn)或交換機(jī)每個(gè)端口 (輸入和輸出 )的帶寬。 時(shí)延 發(fā)送方 接收方 發(fā)送方 開(kāi)銷 傳輸時(shí)間 飛行時(shí)間 接收方 開(kāi)銷 傳輸時(shí)間 傳輸時(shí)延 互連網(wǎng)絡(luò) 通信時(shí)延 =額外開(kāi)銷 +飛行時(shí)間 +消息長(zhǎng)度 /通道帶寬 額外開(kāi)銷 — 指收 /發(fā)雙方軟 /硬件開(kāi)銷，與結(jié)點(diǎn)內(nèi)核及NIC結(jié)構(gòu)有關(guān)； 飛行時(shí)間 — 與結(jié)點(diǎn)間距離 (拓?fù)浣Y(jié)構(gòu) )及通道帶寬有關(guān)； 通道帶寬 — 與鏈路帶寬和通道競(jìng)爭(zhēng)情況有關(guān)。 流控機(jī)制層次： 有鏈路級(jí)流控、端到端流控兩個(gè)層次。 路由算法目標(biāo)： 避免死鎖、維持低時(shí)延、均勻分布負(fù)載、容錯(cuò)等。 采用分布控制的互連網(wǎng)絡(luò)才涉及到路由問(wèn)題。 集中控制方式 對(duì)拓?fù)浣Y(jié)構(gòu)的要求較高，直接影響并行算法的實(shí)現(xiàn)效果 (同時(shí)連接的結(jié)點(diǎn)對(duì)數(shù)量 )； 分布控制方式 對(duì)拓?fù)浣Y(jié)構(gòu)的要求一般。 如： 高維拓?fù)浣Y(jié)構(gòu)實(shí)現(xiàn)移位函數(shù)效率總比低維結(jié)構(gòu)好； 又如： 對(duì)稱拓?fù)浣Y(jié)構(gòu)實(shí)現(xiàn)交換函數(shù)效率總比非對(duì)稱結(jié)構(gòu)好。 轉(zhuǎn)上二頁(yè) 回 17頁(yè) 拓?fù)浣Y(jié)構(gòu) 是實(shí)現(xiàn)互連功能的主要機(jī)構(gòu)，反映互連函數(shù)實(shí)現(xiàn)的復(fù)雜度。 R T N1 N2 N3 N4 數(shù)據(jù)包 1 數(shù)據(jù)包 2 D 蟲(chóng)孔尋徑 — 傳輸單位為數(shù)據(jù)片，尋徑、傳輸流水進(jìn)行，中間節(jié)點(diǎn)需緩沖數(shù)據(jù)片。 消息 包 片 R S D D D D R：導(dǎo)徑信息 S：順序號(hào) D：數(shù)據(jù)片 傳輸方式 — 分為存儲(chǔ) 轉(zhuǎn)發(fā)、蟲(chóng)孔尋徑兩種。（邊尋徑，邊傳輸） 消息格式 — 消息由數(shù)據(jù)包組成，數(shù)據(jù)包由數(shù)據(jù)片組成。 應(yīng)用： 線路交換一般與集中控制配對(duì)，應(yīng)用于 SIMD系統(tǒng)； 線路交換也可與分布控制配對(duì)，應(yīng)用于 MIMD系統(tǒng)，如面向連接的通信。 （ 1）線路交換 程序在源和目的結(jié)點(diǎn)間建立一條路徑，直到傳輸完成 (消息全部通過(guò) )為止。 PE0 … PEN1 ISC(O) ISC(nl) … … PEN1 PE1 PE0 PE1 … … … 交叉 開(kāi)關(guān) 接收器 緩沖區(qū) 緩沖區(qū) 發(fā)送器 路由、調(diào)度、控制 輸 入 端 口 輸 出 端 口 應(yīng)用： 集中控制適合于 SIMD系統(tǒng)，采用同步并行算法； 分布控制適合于 MIMD系統(tǒng)，采用異步并行算法。 指令譯碼器 IN控制器 ALU控制器 PE0 … PEN1 ISC(O) ISC(nl) … … PEN1 PE1 PE0 PE1 … … … 分布控制： 消息 在網(wǎng)絡(luò)內(nèi)部 分時(shí)控制 相關(guān) NIC尋徑器或交換開(kāi)關(guān)狀態(tài)，直到消息通過(guò)或傳輸完成為止。 集中控制： 程序 在網(wǎng)絡(luò)外部 同時(shí)控制 所有 NIC尋徑器或交換開(kāi)關(guān)狀態(tài)，直到再次控制為止。 控制方式 控制方式用于實(shí)現(xiàn)網(wǎng)絡(luò)互連時(shí)間特性 (同時(shí)或分時(shí) )。 例如： 以基于開(kāi)關(guān)的超立方體網(wǎng)絡(luò)為主干網(wǎng)； 主干網(wǎng)中每個(gè)結(jié)點(diǎn)為一個(gè)靜態(tài)網(wǎng)格網(wǎng)絡(luò)； 網(wǎng)格網(wǎng)絡(luò)中每個(gè)結(jié)點(diǎn)為一個(gè)共享介質(zhì)的總線； 總線上有 2~4個(gè)處理單元。 混合互連網(wǎng)絡(luò) 為靜態(tài)互連網(wǎng)絡(luò)和動(dòng)態(tài)互連網(wǎng)絡(luò)的混合體，即網(wǎng)絡(luò)中包含了多種網(wǎng)絡(luò)。 NIC0 … NICN1 ISC(O) ISC(nl) … … NICN1 NIC1 NIC0 NIC1 … … … 思考： 為什么要用多級(jí)拓?fù)浣Y(jié)構(gòu)？ 拓?fù)浣Y(jié)構(gòu)： 可為靜態(tài)網(wǎng)絡(luò)的各種結(jié)構(gòu)。 （ 3）基于開(kāi)關(guān)的網(wǎng)絡(luò) 結(jié)點(diǎn)到結(jié)點(diǎn)通過(guò)交換開(kāi)關(guān)進(jìn)行連接 (無(wú)直接相連通道 )，即結(jié)點(diǎn)只與交換開(kāi)關(guān)連接，又稱間接網(wǎng)絡(luò)。 交叉開(kāi)關(guān) 由 N2個(gè)交叉點(diǎn)開(kāi)關(guān)組成，每個(gè)交叉點(diǎn)開(kāi)關(guān)只有兩個(gè)狀態(tài) (通 /斷 )； 拓?fù)浣Y(jié)構(gòu) — 無(wú)。 （ 2）非阻塞網(wǎng)絡(luò) 同時(shí)允許所有結(jié)點(diǎn)對(duì)連接，即所有結(jié)點(diǎn)對(duì)可同時(shí)互連，又稱交叉開(kāi)關(guān)網(wǎng)絡(luò)。 互連功能實(shí)現(xiàn)： 互連空間特性通過(guò) NIC的地址判別實(shí)現(xiàn)； 互連時(shí)間特性是分時(shí)互連。 組成： 由鏈路、拓?fù)浣Y(jié)構(gòu)及 NIC組成。 動(dòng)態(tài)互連網(wǎng)絡(luò) 結(jié)點(diǎn)到結(jié)點(diǎn)的連接由程序動(dòng)態(tài)地改變，包括共享介質(zhì)、非阻塞、基于開(kāi)關(guān)的三種子類型網(wǎng)絡(luò)。 PE100 PE100 PE100 PE111 PE000 PE001 PE010 PE011 M NIC P MB 結(jié)點(diǎn) C M NIC P MB 結(jié)點(diǎn) C Bridge I/OB 拓?fù)浣Y(jié)構(gòu)： 有線性陣列、網(wǎng)格、立方體等多種結(jié)構(gòu)。 二、互連網(wǎng)絡(luò)種類 靜態(tài)互連網(wǎng)絡(luò) 結(jié)點(diǎn)到結(jié)點(diǎn)的連接在運(yùn)行期間不改變，又稱直接網(wǎng)絡(luò)。 并行算法與互連函數(shù)： 并行算法 在不同時(shí)刻按照不同規(guī)則實(shí)現(xiàn)不同結(jié)點(diǎn)間的連接與通信； 互連函數(shù) — 可表示并行算法的連接規(guī)則； 并行算法的連接規(guī)則可通過(guò)一組互連函數(shù)表示。 互連函數(shù)定義： 是入端編碼的排列、組合、移位、取反等操作的結(jié)果。 互連網(wǎng)絡(luò)與總線比較： 互連網(wǎng)絡(luò)同時(shí)有多個(gè)不相關(guān)通道存在； 互連網(wǎng)絡(luò)的通
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1