【正文】 E F G H I J K L 0 1 2 3 4 5 6 7 0級(jí) 0 1 2 3 4 5 6 7 1級(jí) 2級(jí) 開關(guān)組合控制： 級(jí)控制、部分級(jí)控制 STARAN網(wǎng)絡(luò) (交換、移數(shù)功能 )； 單元控制 間接二進(jìn)制 n方體網(wǎng)絡(luò) (更復(fù)雜的功能 )。 DTR MUX 循環(huán) 單個(gè)互連函數(shù)拓?fù)?PE0來 去 PE0 PEN1來 去 PEN1 … DTR MUX 單級(jí)互連函數(shù)拓?fù)浣Y(jié)構(gòu)： ①經(jīng)過循環(huán)能夠?qū)崿F(xiàn)某結(jié)點(diǎn)到任意結(jié)點(diǎn)的互連； ②經(jīng)過循環(huán)能夠改變同時(shí)連接的結(jié)點(diǎn)對(duì)間相互關(guān)系。 網(wǎng)絡(luò)集中控制： 控制器 根據(jù) 同時(shí)通信的所有消息 源、目標(biāo)結(jié)點(diǎn)地址和拓?fù)浣Y(jié)構(gòu)類型，生成 所有開關(guān) 的外部控制信號(hào)； 網(wǎng)絡(luò)分布控制： 當(dāng)前開關(guān) 根據(jù) 當(dāng)前消息 源、目標(biāo)結(jié)點(diǎn)地址和拓?fù)浣Y(jié)構(gòu)類型，生成 當(dāng)前開關(guān) 的 部分通道 的內(nèi)部控制信號(hào)。 直 徑： 兩個(gè)結(jié)點(diǎn)互連的最大步數(shù)。 n/2(縱向 )互連函數(shù)。 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)變換功能。 互連函數(shù)也可稱為單級(jí)互連網(wǎng)絡(luò)。 時(shí)延 發(fā)送方 接收方 發(fā)送方 開銷 傳輸時(shí)間 飛行時(shí)間 接收方 開銷 傳輸時(shí)間 傳輸時(shí)延 互連網(wǎng)絡(luò) 通信時(shí)延 =額外開銷 +飛行時(shí)間 +消息長度 /通道帶寬 額外開銷 — 指收 /發(fā)雙方軟 /硬件開銷，與結(jié)點(diǎn)內(nèi)核及NIC結(jié)構(gòu)有關(guān)； 飛行時(shí)間 — 與結(jié)點(diǎn)間距離 (拓?fù)浣Y(jié)構(gòu) )及通道帶寬有關(guān)； 通道帶寬 — 與鏈路帶寬和通道競爭情況有關(guān)。 集中控制方式 對(duì)拓?fù)浣Y(jié)構(gòu)的要求較高，直接影響并行算法的實(shí)現(xiàn)效果 (同時(shí)連接的結(jié)點(diǎn)對(duì)數(shù)量 )； 分布控制方式 對(duì)拓?fù)浣Y(jié)構(gòu)的要求一般。 消息 包 片 R S D D D D R：導(dǎo)徑信息 S：順序號(hào) D：數(shù)據(jù)片 傳輸方式 — 分為存儲(chǔ) 轉(zhuǎn)發(fā)、蟲孔尋徑兩種。 PE0 … PEN1 ISC(O) ISC(nl) … … PEN1 PE1 PE0 PE1 … … … 交叉 開關(guān) 接收器 緩沖區(qū) 緩沖區(qū) 發(fā)送器 路由、調(diào)度、控制 輸 入 端 口 輸 出 端 口 應(yīng)用： 集中控制適合于 SIMD系統(tǒng)，采用同步并行算法； 分布控制適合于 MIMD系統(tǒng)，采用異步并行算法。 例如： 以基于開關(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è)處理單元。 交叉開關(guān) 由 N2個(gè)交叉點(diǎn)開關(guān)組成，每個(gè)交叉點(diǎn)開關(guān)只有兩個(gè)狀態(tài) (通 /斷 )； 拓?fù)浣Y(jié)構(gòu) — 無。 動(dòng)態(tài)互連網(wǎng)絡(luò) 結(jié)點(diǎn)到結(jié)點(diǎn)的連接由程序動(dòng)態(tài)地改變，包括共享介質(zhì)、非阻塞、基于開關(guān)的三種子類型網(wǎng)絡(luò)。 互連函數(shù)定義： 是入端編碼的排列、組合、移位、取反等操作的結(jié)果。 互連網(wǎng)絡(luò) IN 互連函數(shù)與互連網(wǎng)絡(luò)： 不同的互連函數(shù)可通過互連網(wǎng)絡(luò)不同控制信號(hào)實(shí)現(xiàn)。 PE0 PE1 PEN1 … PEN1 PE0 PE1 … 拓?fù)浣Y(jié)構(gòu)： 包括總線、環(huán)狀結(jié)構(gòu)。 組成： 由鏈路、交換開關(guān) (交換機(jī) )、各級(jí)間拓?fù)浣Y(jié)構(gòu) (ISC)、 NIC組成。 控制方式分集中控制和分布控制兩種。（先尋徑，后傳輸） T N1 N2 N3 N4 消息 1 消息 2 D 說明：本圖傳輸時(shí)忽略了鏈路時(shí)延。 T N1 N2 N3 N4 數(shù)據(jù)包 1 數(shù)據(jù)包 2 D 應(yīng)用 — 包交換只能與分布控制配對(duì)，應(yīng)用于 MIMD系統(tǒng)。 路由算法： 算術(shù)路由、源路由、查表路由、自適應(yīng)路由等。 聚集帶寬： 網(wǎng)絡(luò)的前一半節(jié)點(diǎn) (與結(jié)點(diǎn)不同含義 )與后一半節(jié)點(diǎn)間傳輸?shù)膸挘话阒妇W(wǎng)絡(luò)內(nèi)部帶寬的總和。 應(yīng)用： 2 2交換開關(guān) 可實(shí)現(xiàn)恒等置換與交換置換功能，功能控制可通過外部信號(hào)或內(nèi)部消息譯碼實(shí)現(xiàn)。 應(yīng)用： 單向帶弦環(huán)可實(shí)現(xiàn)移數(shù)置換功能 (內(nèi)弦連接不同實(shí)現(xiàn)的間隔不同 )，雙向帶弦環(huán)可實(shí)現(xiàn)兩個(gè)移數(shù)置換。 結(jié)點(diǎn) NIC組成： 一般有多個(gè)輸入 /輸出通道，其中一對(duì)連接本結(jié)點(diǎn) CPU； 所有通道有外部信號(hào)和內(nèi)部信號(hào)控制兩種控制方式。 與連接度和拓?fù)浣Y(jié)構(gòu)有關(guān)。 PE0 PE1 PEN1 … PE0 PE1 PEN1 … 轉(zhuǎn) 18頁 交叉開關(guān) 互連控制： 可采用集中、分布方式實(shí)現(xiàn)控制； 通過 N2個(gè)交叉開關(guān)組合完成控制。 多級(jí)網(wǎng)絡(luò) — 多級(jí)互連網(wǎng)絡(luò) 組成： 交換開關(guān) +級(jí)間拓?fù)浣Y(jié)構(gòu)。 Cube04組 2元交換； Cube12組 4元交換 +4組 2元交換； Cube21組 8元交換 +2組 4元交換。請(qǐng)畫出互連網(wǎng)絡(luò)結(jié)構(gòu)圖，寫出控制方式及各開關(guān)狀態(tài)。 證明： 對(duì) n=log2N級(jí)網(wǎng)絡(luò)，開關(guān)數(shù) =N/2 n。 網(wǎng)絡(luò)時(shí)延： Tcs(n,d)=dnt/b+n/b≈ n/b，其中 ntn 尋徑阻塞處理： 放棄尋徑消息 nt，等待通道空閑時(shí)重發(fā)。 轉(zhuǎn)上頁 T N1 N2 N3 N4 數(shù)據(jù)包 1 數(shù)據(jù)包 2 D 網(wǎng)絡(luò)時(shí)延： Twh(n’,d)=dnt/b+n’/b≈ n’/b 網(wǎng)絡(luò)狀態(tài)較好時(shí)，蟲孔尋徑與線路交換時(shí)延相當(dāng)； 網(wǎng)絡(luò)狀態(tài)不好時(shí)，蟲孔尋徑不如存儲(chǔ) 轉(zhuǎn)時(shí)延。 （ 1）算術(shù)路由法 各交換開關(guān) 根據(jù)消息中源與目的地址、拓?fù)浣Y(jié)構(gòu)中的 當(dāng)前開關(guān)位置 來計(jì)算到下級(jí)開關(guān)的所選路徑。 回下頁 自適應(yīng)路由算法 一般為確定性路由算法的擴(kuò)展算法，即可根據(jù)網(wǎng)絡(luò)傳輸狀況在幾條路徑中選擇一條。 C4 C1 C3 C2 C4 C1 C3 C2 V3 V4 轉(zhuǎn)上頁 轉(zhuǎn) 49頁 只需在部分通道上設(shè)置虛擬通道，即可打破閉環(huán)。