【正文】 N技術(shù)。網(wǎng)絡(luò)能夠避免 8個(gè)處理器同時(shí)進(jìn)行存儲(chǔ)器存取時(shí)的沖突。 ? 交叉開關(guān)一般有兩種使用方式：一種是用于對(duì)稱的多處理機(jī)或多計(jì)算機(jī)機(jī)群中的處理器間的通信；另一種是用于 SMP服務(wù)器或向量超級(jí)計(jì)算機(jī)中處理器和存儲(chǔ)器之間的存取。 ? 環(huán)網(wǎng)可完美嵌入到 2D環(huán)繞網(wǎng)中 ? 超立方網(wǎng)可完美嵌入到 2－ D環(huán)繞網(wǎng)中 國家高性能計(jì)算中心（合肥） 15 2022/2/16 嵌入 （ 2） 1000 1001 1011 10101100 1101 1111 11100100 0101 0111 01100000 0001 0011 0010010101000000 0001011101100010 0011110111001000 1001111111101010 1011國家高性能計(jì)算中心（合肥） 16 2022/2/16 網(wǎng)絡(luò)名稱 網(wǎng)絡(luò)規(guī)模 節(jié)點(diǎn)度 網(wǎng)絡(luò)直徑 對(duì)剖寬度 對(duì)稱 鏈路數(shù) 線性陣列 2 1 非 環(huán)形 2 （雙向） 2 是 2D網(wǎng)孔 4 非 Illiac網(wǎng)孔 4 非 2D環(huán)繞 4 是 二叉樹 3 1 非 星形 2 非 超立方 n n 是 立方環(huán) 3 是 NNNN? ?NN?? ?NN?? ?NN?nN 2?kkN 2??1?N1?N? ?2/N)1(2 ?N1?N? ?2/2 N? ?? ?1log2 ?N? ?2/12 kk ??NN2N2? ?2/N2/N)2/(kN1?NN)(2 NN ?N2N21?N1?N2/nN2/3N靜態(tài)互連網(wǎng)絡(luò)特性比較 國家高性能計(jì)算中心（合肥） 17 2022/2/16 動(dòng)態(tài)互連網(wǎng)絡(luò) (1) ? 總線： PCI、 VME、 Multibus、 Sbus、 MicroChannel ? 多處理機(jī)總線系統(tǒng)的主要問題包括總線仲裁、中斷處理、協(xié)議轉(zhuǎn)換、快速同步、高速緩存一致性協(xié)議、分事務(wù)、總線橋和層次總線擴(kuò)展等 LM IOC本地總線高速緩存CPUIF IFIF存儲(chǔ)器總線存儲(chǔ)器單元IFIFCPU板 存儲(chǔ)器板I/O板 通信板系統(tǒng)總線 (底板上)數(shù)據(jù)總線緩沖CCIOP數(shù)據(jù)總線網(wǎng)絡(luò)(以太網(wǎng)等)磁盤和磁帶部件打印機(jī)或繪圖儀本地外圍設(shè)備(SCSI總線)MCIF緩沖國家高性能計(jì)算中心（合肥） 18 2022/2/16 動(dòng)態(tài)互連網(wǎng)絡(luò) （ 2） ? 交叉開關(guān)（ Crossbar）： ? 單級(jí)交換網(wǎng)絡(luò)，可為每個(gè)端口提供更高的帶寬。 ? 如果將 3立方的每個(gè)頂點(diǎn)代之以一個(gè)環(huán)就構(gòu)成了如圖 (d)所示的 3立方環(huán)，此時(shí)每個(gè)頂點(diǎn)的度為 3，而不像超立方那樣節(jié)點(diǎn)度為 n。 ? ?? ?1log2 ?N? ?2/N(a) 二叉樹 (b) 星形連接(c) 二叉胖樹國家高性能計(jì)算中心（合肥） 13 2022/2/16 靜態(tài)互連網(wǎng)絡(luò)（ 4） ? 超立方 ： ? 一個(gè) n立方由 個(gè)頂點(diǎn)組成， 3立方如圖 (a)所示； 4立方如圖 (b)所示，由兩個(gè) 3立方的對(duì)應(yīng)頂點(diǎn)連接而成。 ? 節(jié)點(diǎn)度為 3，對(duì)剖寬度為 1，而樹的直徑為 ? 如果盡量增大節(jié)點(diǎn)度數(shù)，則直徑縮小為 2，此時(shí)就變成了星形網(wǎng)絡(luò)，其對(duì)剖寬度為 ? 傳統(tǒng)二叉樹的主要問題是根易成為通信瓶頸。 ? 對(duì)剖寬度 （ Bisection Width） ： 對(duì)分網(wǎng)絡(luò)各半所必須移去的最少邊數(shù) ? 對(duì)剖帶寬 （ Bisection Bandwidth） :每秒鐘內(nèi)，在最小的對(duì)剖平面上通過所有連線的最大信息位（或字節(jié)）數(shù) ? 如果從任一節(jié)點(diǎn)觀看網(wǎng)絡(luò)都一樣，則稱網(wǎng)絡(luò)為 對(duì)稱的（ Symmetry） 國家高性能計(jì)算中心（合肥） 9 2022/2/16 靜態(tài)互連網(wǎng)絡(luò) 與動(dòng)態(tài)互連網(wǎng)絡(luò) ? 靜態(tài)互連網(wǎng)絡(luò)： 處理單元間有著固定連接的一類網(wǎng)絡(luò)，在程序執(zhí)行期間，這種點(diǎn)到點(diǎn)的鏈接保持不變；典型的靜態(tài)網(wǎng)絡(luò)有一維線性陣列、二維網(wǎng)孔、樹連接、超立方網(wǎng)絡(luò)、立方環(huán)、洗牌交換網(wǎng)、蝶形網(wǎng)絡(luò)等 ? 動(dòng)態(tài)網(wǎng)絡(luò)： 用交換開關(guān)構(gòu)成的，可按應(yīng)用程序的要求動(dòng)態(tài)地改變連接組態(tài)；典型的動(dòng)態(tài)網(wǎng)絡(luò)包括總線、交叉開關(guān)和多級(jí)互連網(wǎng)絡(luò)等。在單向網(wǎng)絡(luò)中，入射和出射邊之和稱為節(jié)點(diǎn)度。 ? 美國 ASCI計(jì)劃 (1996)：核武器數(shù)值模擬。 ? 需求類型：計(jì)算密集、數(shù)據(jù)密集、網(wǎng)絡(luò)密集。多核并行計(jì)算 Multicore Parallel Computing 主講人 徐 云 國家高性能計(jì)算中心（合肥） 2 2022/2/16 并行計(jì)算 ——結(jié)構(gòu) ?算法 ?編程 ? 第一篇 并行計(jì)算的基礎(chǔ) ? 第一章 并行計(jì)算機(jī)系統(tǒng)及其結(jié)構(gòu)模型 ? 第二章 當(dāng)代并行機(jī)系統(tǒng)： SMP、 MPP和 Cluster ? 第三章 并行計(jì)算性能評(píng)測 國家高性能計(jì)算中心（合肥） 3 2022/2/16 第一章并行計(jì)算機(jī)系統(tǒng)及結(jié)構(gòu)模型 ? 并行計(jì)算 ? 并行計(jì)算與計(jì)算科學(xué) ? 當(dāng)代科學(xué)與工程問題的計(jì)算需求 ? 并行計(jì)算機(jī)系統(tǒng)互連 ? 系統(tǒng)互連 ? 靜態(tài)互聯(lián)網(wǎng)絡(luò) ? 動(dòng)態(tài)互連網(wǎng)絡(luò) ? 標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò) ? 并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) ? 并行計(jì)算機(jī)結(jié)構(gòu)模型 ? 并行計(jì)算機(jī)訪存模型 ? 多核處理器架構(gòu) 國家高性能計(jì)算中心（合肥） 4 2022/2/16 并行計(jì)算、計(jì)算科學(xué)、計(jì)算需求 ? 并行計(jì)算：并行機(jī)上所作的計(jì)算，又稱高性能計(jì)算或超級(jí)計(jì)算。 ? 計(jì)算科學(xué)：計(jì)算物理、計(jì)算化學(xué)、計(jì)算生物等 ? 科學(xué)與工程問題的需求：氣象預(yù)報(bào)、油藏模擬、核武器數(shù)值模擬、航天器設(shè)計(jì)、基因測序等。 ? 美國 HPCC計(jì)劃 (1993)：重大挑戰(zhàn)性課題， 3T性能 ? 美國 Petaflops研究項(xiàng)目： Pflop/s。 國家高性能計(jì)算中心（合肥） 5 2022/2/16 第一章并行計(jì)算機(jī)系統(tǒng)及結(jié)構(gòu)模型 ? 并行計(jì)算 ? 并行計(jì)算與計(jì)算科學(xué) ? 當(dāng)代科學(xué)與工程問題的計(jì)算需求 ? 并行計(jì)算機(jī)系統(tǒng)互連 ? 系統(tǒng)互連 ? 靜態(tài)互聯(lián)網(wǎng)絡(luò) ? 動(dòng)態(tài)互連網(wǎng)絡(luò) ? 標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò) ? 并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) ? 并行計(jì)算機(jī)結(jié)構(gòu)模型 ? 并行計(jì)算機(jī)訪存模型 ? 多核處理器架構(gòu) 國家高性能計(jì)算中心（合肥） 6 2022/2/16 系統(tǒng)互連 ? 不同帶寬與距離的互連技術(shù) : 總線、 SAN、 LAN、 MAN、 WAN 局部總線I/O總線SCIHiPPIMyri千兆位 以太網(wǎng)光纖通道快速以太網(wǎng)以太網(wǎng)10 Base TFDDIATM總線或開關(guān) SAN LAN MAN WAN100Gb/s10Gb/s1Gb/s100Mb/s10Mb/s IsoE網(wǎng)絡(luò)帶寬交叉開關(guān)MIN 或100 Base T國家高性能計(jì)算中心（合肥） 7 2022/2/16 局部總線、 I/O總線、 SAN和 LAN P MI/O橋磁盤SAN()LAN(,FDDI) 系統(tǒng) III/O總線,接口系統(tǒng) I處理器總線局部總線,存儲(chǔ)器總線SCSI節(jié)點(diǎn) 2 節(jié)點(diǎn) N系統(tǒng)總線節(jié)點(diǎn) 1國家高性能計(jì)算中心（合肥） 8 2022/2/16 網(wǎng)絡(luò)性能指標(biāo) ? 節(jié)點(diǎn)度 （ Node Degree）： 射入或射出一個(gè)節(jié)點(diǎn)的邊數(shù)。 ? 網(wǎng)絡(luò)直徑 （ Network Diameter）： 網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)之間的最長距離，即最大路徑數(shù)。 國家高性能計(jì)算中心（合肥） 10 2022/2/16 靜態(tài)互連網(wǎng)絡(luò)（ 1） ? 一維線性陣列（ 1D Linear Array）： ? 并行機(jī)中最簡單、最基本的互連方式， ? 每個(gè)節(jié)點(diǎn)只與其左、右近鄰相連，也叫二近鄰連接， ? N個(gè)節(jié)點(diǎn)用 N1條邊串接之，內(nèi)節(jié)點(diǎn)度為 2，直徑為N1， 對(duì)剖寬度為 1 ? 當(dāng)首、尾節(jié)點(diǎn)相連時(shí)可構(gòu)成循環(huán)移位器，在拓?fù)浣Y(jié)構(gòu)上等同于環(huán)，環(huán)可以是單向的或雙向的，其節(jié)點(diǎn)度恒為 2，直徑或?yàn)? （雙向環(huán)）或?yàn)?N1（ 單向環(huán)），對(duì)剖寬度為 2 ? ?2/N國家高性能計(jì)算中心（合肥） 11 2022/2/16 靜態(tài)互連網(wǎng)絡(luò)（ 2） ? 二維網(wǎng)孔（ 2D Mesh）： ? 每個(gè)節(jié)點(diǎn)只與其上、下、左、右的近鄰相連（邊界節(jié)點(diǎn)除外），節(jié)點(diǎn)度為 4，網(wǎng)絡(luò)直徑為 ，對(duì)剖寬度為 ? 在垂直方向上帶環(huán)繞，水平方向呈蛇狀，就變成 Illiac網(wǎng)孔了，節(jié)點(diǎn)度恒為 4，網(wǎng)絡(luò)直徑為 ，而對(duì)剖寬度為 ? 垂直和水平方向均帶環(huán)繞，則變成了 2D環(huán)繞（ 2D Torus），節(jié)點(diǎn)度恒為 4，網(wǎng)絡(luò)直徑為 ，對(duì)剖寬度為 )1(2 ?N N1?N N2? ?2/2 N N2NN ?(a) 2D 網(wǎng)孔 (b)Illiac網(wǎng)孔 (c) 2D 環(huán)繞國家高性能計(jì)算中心（合肥） 12 2022/2/16 靜態(tài)互連網(wǎng)絡(luò)（ 3） ? 二叉樹： ? 除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)相連。胖樹節(jié)點(diǎn)間的通路自葉向根逐漸變寬。 ? n立方的節(jié)點(diǎn)度為 n， 網(wǎng)絡(luò)直徑也是 n ， 而對(duì)剖寬度為 。 nN 2?2/N(b)4立方(a)3立方(c)頂點(diǎn)代之以環(huán) (d)3立方環(huán)國家高性能計(jì)算中心（合肥） 14 2022/2/16 嵌入 （ 1） ? 將網(wǎng)絡(luò)中的各節(jié)點(diǎn)映射到另一個(gè)網(wǎng)絡(luò)中去 ? 用 膨脹 （ Dilation）系數(shù) 來描述嵌入的質(zhì)量，它是指被嵌入網(wǎng)絡(luò)中的一條鏈路在所要嵌入的網(wǎng)絡(luò)中對(duì)應(yīng)所需的最大鏈路數(shù) ? 如果該系數(shù)為 1，則稱為完美嵌入。象電話交換機(jī)一樣，交叉點(diǎn)開關(guān)可由程序控制動(dòng)態(tài)設(shè)置其處于 “ 開 ” 或 “ 關(guān) ”狀態(tài)，而能提供所有（源、目的）對(duì)之間的動(dòng)態(tài)連接。 國家高性能計(jì)算中心（合肥） 19 2022/2/16 動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò) （ 3） ? 單級(jí)交叉開關(guān)級(jí)聯(lián)起來形