并行計(jì)算-29中科大教案體系結(jié)構(gòu)lec05interconnect

ParallelComputerArchitecture

并行計(jì)算機(jī)體系結(jié)構(gòu)

Lecture6OverviewReviewofLec5互連網(wǎng)絡(luò)系統(tǒng)互連靜態(tài)互連動(dòng)態(tài)互連機(jī)群中的互連ReviewofLec5Benchmark分類并行Benchmark性能提高（任務(wù)劃分、分配、調(diào)度）任務(wù)劃分的方法粒度與并發(fā)度靜態(tài)調(diào)度與動(dòng)態(tài)調(diào)度OverviewReviewofLec5互連網(wǎng)絡(luò)系統(tǒng)互連靜態(tài)互連動(dòng)態(tài)互連機(jī)群中的互連第三章互連網(wǎng)絡(luò)系統(tǒng)互連不同帶寬與距離的互連技術(shù)局部總線、I/O總線、SAN和LAN基本網(wǎng)絡(luò)部件——鏈路鏈路（link)：傳輸信息的物理介質(zhì)，也稱為通道或電纜不同的物理介質(zhì)：雙絞線(STP)、同軸電纜、光纖可用來(lái)連接兩個(gè)Switch或主機(jī)與Switch長(zhǎng)度:短鏈路在任一時(shí)刻僅包含一個(gè)邏輯信號(hào)；而長(zhǎng)鏈路允許同時(shí)在鏈路上傳輸邏輯信號(hào)寬度:一條窄鏈路只有一位信號(hào)線；一條寬鏈路有多位信號(hào)線。時(shí)鐘：一條鏈路常由同步或異步兩種時(shí)鐘機(jī)制驅(qū)動(dòng)；同步時(shí)鐘是指源和目的操作使用全局相同的時(shí)鐘；異步時(shí)鐘允許兩端使用不同的時(shí)鐘握手基本網(wǎng)絡(luò)部件——交換開關(guān)交換開關(guān)（switch/router)：用于建立交換網(wǎng)絡(luò)。通常包括多個(gè)輸入和輸出端口最基本的功能應(yīng)提供從輸入到輸出的某種映射可能還提供內(nèi)部緩沖、路由、多播等從輸入到輸出的映射可通過(guò)多種機(jī)制實(shí)現(xiàn)：如Crossbar、多端口存儲(chǔ)器、多路選擇器、時(shí)分總線等基本網(wǎng)絡(luò)部件——網(wǎng)絡(luò)接口電路網(wǎng)絡(luò)接口電路（NIC):用來(lái)連接主機(jī)和網(wǎng)絡(luò)包括輸入輸出端口將數(shù)據(jù)輸入輸出到網(wǎng)絡(luò)上有如下功能：數(shù)據(jù)打包/解包、計(jì)算路由信息、輸入/出數(shù)據(jù)緩沖（匹配網(wǎng)絡(luò)和節(jié)點(diǎn)的速度）、糾錯(cuò)等通常包括：處理器、I/O緩沖、控制存儲(chǔ)器和控制邏輯接入位置很重要：I/O總線，Memory總線網(wǎng)絡(luò)性能指標(biāo)（1）通信時(shí)延：從源節(jié)點(diǎn)到目的節(jié)點(diǎn)傳輸一條消息所需的總時(shí)間在網(wǎng)絡(luò)兩端相應(yīng)收發(fā)消息的軟件開銷由于通道占用導(dǎo)致的通道時(shí)延（即總的消息長(zhǎng)度除以通道帶寬）沿選路路徑作一系列選路決策期間花費(fèi)在后續(xù)交換開關(guān)上的選路時(shí)延由于網(wǎng)絡(luò)傳輸競(jìng)爭(zhēng)導(dǎo)致的競(jìng)爭(zhēng)時(shí)延軟件開銷主要取決于主機(jī)內(nèi)核，與競(jìng)爭(zhēng)時(shí)延均依賴于程序行為網(wǎng)絡(luò)時(shí)延：通道時(shí)延和選路時(shí)延之和，完全有網(wǎng)絡(luò)硬件特征決定，（通常1微秒左右）大大小于軟件開銷和競(jìng)爭(zhēng)時(shí)延（幾十或幾百微秒）網(wǎng)絡(luò)性能指標(biāo)（2）每端口帶寬：從任意端口到另外端口每秒鐘傳輸消息的最大位（或字節(jié)）數(shù)如IBMHPS每端口帶寬40MB/s聚集帶寬：從一半節(jié)點(diǎn)到另一半節(jié)點(diǎn)，每秒鐘傳輸消息的最大位（或字節(jié)）數(shù)如IBMHPS端口數(shù)最多為512，聚集帶寬為512*40/2=10.24GB/s對(duì)剖寬度：將網(wǎng)絡(luò)分成兩個(gè)相等部分所必須移去的最少邊數(shù)。對(duì)剖帶寬（BisectionBandwidth）：每秒鐘內(nèi)，在最小的對(duì)剖平面上通過(guò)所有連線的最大信息位（或字節(jié)）數(shù)。等于對(duì)剖寬度與通道帶寬之積。網(wǎng)絡(luò)性能指標(biāo)（3）節(jié)點(diǎn)度（NodeDegree）：射入或射出一個(gè)節(jié)點(diǎn)的邊數(shù)。在單向網(wǎng)絡(luò)中，入射和出射邊之和稱為節(jié)點(diǎn)度。網(wǎng)絡(luò)直徑（NetworkDiameter）：網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)之間的最長(zhǎng)距離，即最大路徑數(shù)。如果從任一節(jié)點(diǎn)觀看網(wǎng)絡(luò)都一樣，則稱網(wǎng)絡(luò)為對(duì)稱的（Symmetry）邊連通度（arcconnectivity)：將網(wǎng)絡(luò)分成兩個(gè)不連通的部分所必須移去的邊數(shù)。代價(jià)（cost）：可以用總邊數(shù)（鏈路數(shù)）來(lái)衡量。OverviewReviewofLec5互連網(wǎng)絡(luò)系統(tǒng)互連靜態(tài)互連動(dòng)態(tài)互連機(jī)群中的互連靜態(tài)互連網(wǎng)絡(luò)與動(dòng)態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)：又稱為直接連接網(wǎng)絡(luò)。處理單元間有著固定連接的一類網(wǎng)絡(luò)，在程序執(zhí)行期間，這種點(diǎn)到點(diǎn)的鏈接保持不變；典型的靜態(tài)網(wǎng)絡(luò)有一維線性陣列、二維網(wǎng)孔、樹連接、超立方網(wǎng)絡(luò)、立方環(huán)等。動(dòng)態(tài)網(wǎng)絡(luò)：又稱為間接連接網(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ò)等。靜態(tài)互連網(wǎng)絡(luò)（1）一維線性陣列（1-DLinearArray）：并行機(jī)中最簡(jiǎn)單、最基本的互連方式，每個(gè)節(jié)點(diǎn)只與其左、右近鄰相連，也叫二近鄰連接，N個(gè)節(jié)點(diǎn)用N-1條邊串接之，內(nèi)節(jié)點(diǎn)度為2，直徑為N-1，對(duì)剖寬度為1當(dāng)首、尾節(jié)點(diǎn)相連時(shí)構(gòu)成環(huán)，環(huán)可以是單向的或雙向的。其節(jié)點(diǎn)度恒為2，直徑或?yàn)椋p向環(huán)）或?yàn)镹-1（單向環(huán)），對(duì)剖寬度為2靜態(tài)互連網(wǎng)絡(luò)（2）

二維網(wǎng)孔（2-DMesh）：每個(gè)節(jié)點(diǎn)只與其上、下、左、右的近鄰相連（邊界節(jié)點(diǎn)除外），故也稱四近鄰連接，因而節(jié)點(diǎn)度為4，網(wǎng)絡(luò)直徑為，對(duì)剖寬度為如果在垂直方向上帶環(huán)繞，而水平方向呈蛇狀，則2-D網(wǎng)孔就變成Illiac網(wǎng)孔了，此時(shí)節(jié)點(diǎn)度恒為4，網(wǎng)絡(luò)直徑為，而對(duì)剖寬度為如果2-D網(wǎng)孔的垂直和水平方向均帶環(huán)繞，則它就變成了2-D環(huán)繞（2-DTorus），其節(jié)點(diǎn)度恒為4，網(wǎng)絡(luò)直徑為，對(duì)剖寬度為k-dmeshes:k:維數(shù)，d:每維上的節(jié)點(diǎn)數(shù)一維線性陣列，k=1,d=Hypercude,k=,d=2靜態(tài)互連網(wǎng)絡(luò)（3）樹形連接：二叉樹中除了根節(jié)點(diǎn)和葉節(jié)點(diǎn)之外，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)相連，故稱為三近鄰連接。節(jié)點(diǎn)度為3，對(duì)剖寬度為1，而樹的直徑為，N為樹的總節(jié)點(diǎn)數(shù)。如果盡量增大根節(jié)點(diǎn)度為N-1，其他所有節(jié)點(diǎn)都與它直接相連，則直徑縮小為2，此時(shí)就變成了星形連接，其對(duì)剖寬度為，從某種意義上講類似于基于總線的網(wǎng)絡(luò)。樹的主要問題是根易成為通信瓶頸。1985年Leiserson提出的胖樹（FatTree）可緩解此問題。胖樹節(jié)點(diǎn)間的通路自葉向根逐漸變寬，它更像真實(shí)的樹，連向根部的枝叉變得愈來(lái)愈粗。靜態(tài)互連網(wǎng)絡(luò)（4）超立方（hypercube)：一個(gè)n-立方由個(gè)頂點(diǎn)組成，3-立方如圖(a)所示；4-立方如圖(b)所示，由兩個(gè)3-立方的對(duì)應(yīng)頂點(diǎn)連接而成。n-立方的節(jié)點(diǎn)度為n，網(wǎng)絡(luò)直徑也是n，而對(duì)剖寬度為。由于該網(wǎng)絡(luò)缺乏可擴(kuò)放性和不易構(gòu)成多維超立方，逐漸被其它的網(wǎng)絡(luò)所代替。在超立方上開發(fā)了很多優(yōu)秀的算法，而像二叉樹，網(wǎng)孔和很多其它低維網(wǎng)絡(luò)均能嵌入超立方中，所以超立方具有學(xué)術(shù)研究的意義。如果將3-立方的每個(gè)頂點(diǎn)代之以一個(gè)環(huán)就構(gòu)成了圖(d)所示的3-立方環(huán)，此時(shí)每個(gè)頂點(diǎn)的度為3，而不像超立方那樣節(jié)點(diǎn)度為n。靜態(tài)互連網(wǎng)絡(luò)特性表3.1靜態(tài)互連網(wǎng)絡(luò)特性一覽表網(wǎng)絡(luò)名稱網(wǎng)絡(luò)規(guī)模節(jié)點(diǎn)度網(wǎng)絡(luò)直徑對(duì)剖寬度對(duì)稱鏈路數(shù)線性陣列個(gè)節(jié)點(diǎn)21非環(huán)形個(gè)節(jié)點(diǎn)2

（雙向）2是2-D網(wǎng)孔

個(gè)節(jié)點(diǎn)4非Illiac網(wǎng)孔

個(gè)節(jié)點(diǎn)4非2-D環(huán)繞

個(gè)節(jié)點(diǎn)4是二叉樹個(gè)節(jié)點(diǎn)31非星形個(gè)節(jié)點(diǎn)2非超立方

節(jié)點(diǎn)

nn是立方環(huán)節(jié)點(diǎn)3是OverviewReviewofLec5互連網(wǎng)絡(luò)系統(tǒng)互連靜態(tài)互連動(dòng)態(tài)互連機(jī)群中的互連動(dòng)態(tài)互連網(wǎng)絡(luò)(1)總線：PCI、VME、Multics、Sbus、MicroChannel多處理機(jī)總線系統(tǒng)的主要問題包括總線仲裁、中斷處理、協(xié)議轉(zhuǎn)換、快速同步、高速緩存一致性協(xié)議、分事務(wù)、總線橋和層次總線擴(kuò)展等動(dòng)態(tài)互連網(wǎng)絡(luò)層次總線：IEEEFuturebus動(dòng)態(tài)互連網(wǎng)絡(luò)總線的優(yōu)點(diǎn)在于成本低，不隨處理器數(shù)目的增加而增加總線的缺點(diǎn)在于擴(kuò)展性不好，總線的帶寬固定，隨著處理器數(shù)的增加，每個(gè)處理器帶寬減少?？衫贸绦蛑械木植啃栽頊p少對(duì)總線帶寬的需求交叉開關(guān)（1）交叉開關(guān)（Crossbar）網(wǎng)絡(luò)是單級(jí)交換網(wǎng)絡(luò)，可為每個(gè)端口提供更高的帶寬。象電話交換機(jī)一樣，交叉點(diǎn)開關(guān)可由程序控制動(dòng)態(tài)設(shè)置其處于“開”或“關(guān)”狀態(tài)，而能提供所有（源、目的）對(duì)之間的動(dòng)態(tài)連接。在并行處理中，交叉開關(guān)一般有兩種使用方式：一種是用于對(duì)稱的多處理機(jī)或多計(jì)算機(jī)機(jī)群中的處理器間的通信；另一種是用于SMP服務(wù)器或向量超級(jí)計(jì)算機(jī)中處理器和存儲(chǔ)器之間的存取。交叉開關(guān)（2）千兆開關(guān)/FDDI:一種用于構(gòu)造Alpha工作站和服務(wù)器互連的交叉開關(guān)，帶寬3.6GbpsSunMicrosystem公司在它們的UltraEnterprisel0000（StarFire）SMP服務(wù)器中，將Gigaplane總線升級(jí)成Gigaplane-XB互連交叉開關(guān)（3）處理器和存儲(chǔ)器間的交叉開關(guān)：交叉開關(guān)代替處理器和存儲(chǔ)器間的連接總線提供了多個(gè)處理器模塊并行存取存儲(chǔ)器的可能性每個(gè)時(shí)刻每個(gè)存儲(chǔ)器模塊只能由一個(gè)處理器進(jìn)行訪問交叉開關(guān)（4）交叉開關(guān)具有良好的帶寬特性Non-Blocking:兩個(gè)節(jié)點(diǎn)之間的通信，不會(huì)阻塞其他節(jié)點(diǎn)之間的通信。代價(jià)不可擴(kuò)放，O(P2)多級(jí)互連網(wǎng)絡(luò)（1）交換開關(guān)模塊一個(gè)交換開關(guān)模塊有n個(gè)輸入和n個(gè)輸出，每個(gè)輸入可連接到任意輸出端口，但只允許一對(duì)一或一對(duì)多的映射，不允許多對(duì)一的映射，因?yàn)檫@將發(fā)生輸出沖突級(jí)間互連（InterstageConnection）：每一級(jí)輸入與輸出之間連接，輸出作為交換開關(guān)的輸入連到下一級(jí)均勻洗牌、蝶網(wǎng)、多路均勻洗牌、交叉開關(guān)等n輸入的Ω網(wǎng)絡(luò)需要級(jí)開關(guān)，在Ilinois大學(xué)的Cedar[2]多處理機(jī)系統(tǒng)中采用了Ω網(wǎng)絡(luò)CrayY/MP多級(jí)網(wǎng)絡(luò)，該網(wǎng)絡(luò)用來(lái)支持8個(gè)向量處理器和256個(gè)存儲(chǔ)器模塊之間的數(shù)據(jù)傳輸。網(wǎng)絡(luò)能夠避免8個(gè)處理器同時(shí)進(jìn)行存儲(chǔ)器存取時(shí)的沖突。多級(jí)互連網(wǎng)絡(luò)（2）單級(jí)交叉開關(guān)級(jí)聯(lián)起來(lái)形成多級(jí)互連網(wǎng)絡(luò)MIN（MultistageInterconnectionNetwork）多級(jí)互連網(wǎng)絡(luò)（3）動(dòng)態(tài)互連網(wǎng)絡(luò)比較n,節(jié)點(diǎn)規(guī)模w，數(shù)據(jù)寬度表3.2動(dòng)態(tài)互連網(wǎng)絡(luò)的復(fù)雜度和帶寬性能一覽表網(wǎng)絡(luò)特性總線系統(tǒng)多級(jí)互連網(wǎng)絡(luò)交叉開關(guān)硬件復(fù)雜度每個(gè)處理器帶寬

～報(bào)道的聚集帶寬SunFire服務(wù)器中的Gigaplane總線：2.67GB/sIBMSP2中的512節(jié)點(diǎn)的HPS：10.24GB/sDigital的千兆開關(guān)：3.4GB/sOverviewReviewofLec5互連網(wǎng)絡(luò)系統(tǒng)互連靜態(tài)互連動(dòng)態(tài)互連機(jī)群中的互連機(jī)群中的互連技術(shù)（Myrinet)Myrinet:Myrinet是由公司設(shè)計(jì)的千兆位包交換網(wǎng)絡(luò)，其目的是為了構(gòu)筑計(jì)算機(jī)機(jī)群，使系統(tǒng)互連成為一種商業(yè)產(chǎn)品。Myrinet是基于加州理工學(xué)院開發(fā)的多計(jì)算機(jī)和VLSI技術(shù)以及在南加州大學(xué)開發(fā)的ATOMIC/LAN技術(shù)。Myrinet能假設(shè)任意拓?fù)浣Y(jié)構(gòu)，不必限定為開關(guān)網(wǎng)孔或任何規(guī)則的結(jié)構(gòu)。Myrinet在數(shù)據(jù)鏈路層具有可變長(zhǎng)的包格式，對(duì)每條鏈路施行流控制和錯(cuò)誤控制，并使用切通選路法以及定制的可編程的主機(jī)接口。在物理層上，Myrinet網(wǎng)使用全雙工SAN鏈路，最長(zhǎng)可達(dá)3米，峰值速率為（1.28＋1.28）Gbps（目前有2.56+2.56)Myrinet交換開關(guān):8,12,16端口Myrinet主機(jī)接口:32位的稱作LANai芯片的用戶定制的VLSI處理器，它帶有Myrinet接口、包接口、DMA引擎和快速靜態(tài)隨機(jī)存取存儲(chǔ)器SRAM。SRAM用來(lái)存儲(chǔ)Myrinet控制程序MCP（MyrinetControlProgram）和包緩沖PCI接口。目前200MHzRISCand8MMemory的PCI接口。140oftheNovember2002TOP500useMyrinet,including15ofthetop100Myrinet連接的LAN/Cluster機(jī)群中的互連技術(shù)（HiPPI)高性能并行接口（HiPPI）LosAlamos國(guó)家實(shí)驗(yàn)室于1987年提出的一個(gè)標(biāo)準(zhǔn)，其目的是試圖統(tǒng)一來(lái)自不同產(chǎn)商生產(chǎn)的所有大型機(jī)和超級(jí)計(jì)算機(jī)的接口。在大型機(jī)和超級(jí)計(jì)算機(jī)工業(yè)界，HiPPI作為短距離的系統(tǒng)到系統(tǒng)以及系統(tǒng)到外設(shè)連接的高速I/O通道。1993年，ANSIX3T9.3委員會(huì)認(rèn)可了HiPPI標(biāo)準(zhǔn)，它覆蓋了物理和數(shù)據(jù)鏈路層，但在這兩層之上的任何規(guī)定卻取決于用戶。HiPPI是單工的點(diǎn)到點(diǎn)的數(shù)據(jù)傳輸接口，其速率可達(dá)800Mbps到1.6Gbps。開發(fā)成功了一種能提供潛在的6.4Gbps速率，比HiPPI快8倍且有很低時(shí)延的超級(jí)HiPPI技術(shù)，SGI公司和LosAlamos國(guó)家實(shí)驗(yàn)室都開發(fā)了用來(lái)構(gòu)筑速率高達(dá)25.6Gbps的HiPPI交換開關(guān)的HiPPI技術(shù)。HiPPI通道和HiPPI交換開關(guān)被用在SGIPowerChallenge服務(wù)器、IBM390主機(jī)、CrayY/MP、C90和T3D/T3E等系統(tǒng)使用HiPPI通道和開關(guān)構(gòu)筑的LAN主干網(wǎng)光纖通道和FDDI環(huán)光纖通道FC（FiberChannel）:通道和網(wǎng)絡(luò)標(biāo)準(zhǔn)的集成光纖通道既可以是共享介質(zhì)，也可以是一種交換技術(shù)光纖通道操作速度范圍可從100到133、200、400和800Mbps。FCSI廠商也正在推出未來(lái)具有更高速度（1、2或4Gbps）的光纖通道光纖通道的價(jià)值已被現(xiàn)在的某些千兆位局域網(wǎng)所證實(shí)，這些局域網(wǎng)就是基于光纖通道技術(shù)的連網(wǎng)拓?fù)浣Y(jié)構(gòu)的靈活性是光纖通道的主要財(cái)富，它支持點(diǎn)到點(diǎn)、仲裁環(huán)及交換光纖連接FDDI:光纖分布式數(shù)據(jù)接口FDDI（FiberDistributedDataInterface）FDDI采用雙向光纖令牌環(huán)可提供100-200Mbps的數(shù)據(jù)傳輸速率FDDI具有互連大量設(shè)備的能力傳統(tǒng)的FDDI僅以異步方式操作雙向FDDI環(huán)作為主干網(wǎng)異步傳輸模式ATMATM（AsynchronousTransferMode）:由成立于