《并行計(jì)算機(jī)體系結(jié)構(gòu)》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行計(jì)算機(jī)體系結(jié)構(gòu)（64頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、Title,PCA L5 Chp3.,*,Wu Spring 09 USTC,This is our 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,This is our next 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,Parallel C,omputer Architecture,并行計(jì)算機(jī)體系結(jié)構(gòu),Lecture 5,March 16,2009,Wu,junmin,(),Ove

2、rview,Review of Lec4,間接互連網(wǎng)絡(luò),交換技術(shù),Review of Lec4,性能提高（任務(wù)劃分、分配、調(diào)度）,pcam,任務(wù)劃分的方法,粒度與并發(fā)度,靜態(tài)調(diào)度與動(dòng)態(tài)調(diào)度,互連網(wǎng)絡(luò),系統(tǒng)互連,不同帶寬與距離的互連技術(shù),基本網(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í)鐘：一條鏈路常由同步或異步兩

3、種時(shí)鐘機(jī)制驅(qū)動(dòng)；同步時(shí)鐘是指源和目的操作使用全局相同的時(shí)鐘；異步時(shí)鐘允許兩端使用不同的時(shí)鐘握手,網(wǎng)絡(luò)性能指標(biāo)（,1,）,通信時(shí)延：,從源節(jié)點(diǎn)到目的節(jié)點(diǎn)傳輸一條消息所需的總時(shí)間,在網(wǎng)絡(luò)兩端相應(yīng)收發(fā)消息的軟件開(kāi)銷,由于通道占用導(dǎo)致的通道時(shí)延（即總的消息長(zhǎng)度除以通道帶寬）,沿選路路徑作一系列選路決策期間花費(fèi)在后續(xù)交換開(kāi)關(guān)上的選路時(shí)延,由于網(wǎng)絡(luò)傳輸競(jìng)爭(zhēng)導(dǎo)致的競(jìng)爭(zhēng)時(shí)延,軟件開(kāi)銷主要取決于主機(jī)內(nèi)核，與競(jìng)爭(zhēng)時(shí)延均依賴于程序行為,網(wǎng)絡(luò)時(shí)延：通道時(shí)延和選路時(shí)延之和，完全由網(wǎng)絡(luò)硬件特征決定，（通常,1,微秒左右）大大小于軟件開(kāi)銷和競(jìng)爭(zhēng)時(shí)延（幾十或幾百微秒）,網(wǎng)絡(luò)性能指標(biāo)（,2,）,每端口帶寬：,從任意端口到另外端

4、口每秒鐘傳輸消息的最大位（或字節(jié)）數(shù),如,IBM HPS,每端口帶寬,40MB/s,聚集帶寬：,從一半節(jié)點(diǎn)到另一半節(jié)點(diǎn)，每秒鐘傳輸消息的最大位（或字節(jié)）數(shù),如,IBM HPS,端口數(shù)最多為,512,，聚集帶寬為,512*40/2=10.24GB/s,對(duì)剖寬度：將網(wǎng)絡(luò)分成兩個(gè)相等部分所必須移去的最少邊數(shù)。,對(duì)剖帶寬（,Bisection Bandwidth,）：,每秒鐘內(nèi)，在最小的對(duì)剖平面上通過(guò)所有連線的最大信息位（或字節(jié)）數(shù)。等于對(duì)剖寬度與通道帶寬之積。,靜態(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)的鏈接保持不變；

5、典型的靜態(tài)網(wǎng)絡(luò)有一維線性陣列、二維網(wǎng)孔、樹(shù)連接、超立方網(wǎng)絡(luò)、立方環(huán)等。,動(dòng)態(tài)網(wǎng)絡(luò)：又稱為間接連接網(wǎng)絡(luò)。用交換開(kāi)關(guān)構(gòu)成的，可按應(yīng)用程序的要求動(dòng)態(tài)地改變連接組態(tài)；典型的動(dòng)態(tài)網(wǎng)絡(luò)包括總線、交叉開(kāi)關(guān)和多級(jí)互連網(wǎng)絡(luò)等。,靜態(tài)網(wǎng)絡(luò)性能指標(biāo),節(jié)點(diǎn)度（,Node Degree,）：射入或射出一個(gè)節(jié)點(diǎn)的邊數(shù)。在單向網(wǎng)絡(luò)中，入射和出射邊之和稱為節(jié)點(diǎn)度。,網(wǎng)絡(luò)直徑（,Network Diameter,）：網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)之間的最長(zhǎng)距離，即最大路徑數(shù)。,如果從任一節(jié)點(diǎn)觀看網(wǎng)絡(luò)都一樣，則稱網(wǎng)絡(luò)為對(duì)稱的（,Symmetry,）,邊連通度（,arc connectivity),：將網(wǎng)絡(luò)分成兩個(gè)不連通的部分所必須移去的邊數(shù)

6、。,代價(jià)（,cost,）：可以用總邊數(shù)（鏈路數(shù)）來(lái)衡量。,靜態(tài)互連網(wǎng)絡(luò)拓?fù)?大多數(shù)都是正交拓?fù)?網(wǎng)絡(luò)拓?fù)湔坏某湟獥l件是：節(jié)點(diǎn)可以在一個(gè)正交的,n,維空間內(nèi)組織起來(lái)，每條鏈路的安排都要在一維中產(chǎn)生一個(gè)偏移量。,正交拓?fù)淇梢赃M(jìn)一步分為嚴(yán)格正交和弱正交。,嚴(yán)格正交拓?fù)涿總€(gè)節(jié)點(diǎn)至少有一條鏈路通過(guò)每一維。,在弱正交中，某些節(jié)點(diǎn)在某些維上沒(méi)有鏈路，因此不可能從任意節(jié)點(diǎn)穿過(guò)任意維，從給定的節(jié)點(diǎn)到結(jié)定的維首先要轉(zhuǎn)移到其他維。,模型可用圖,G(N,C),表示，其中頂點(diǎn),N,代表處理節(jié)點(diǎn)的集合，邊,C,代表通信信道的集合。,嚴(yán)格正交拓?fù)?路由簡(jiǎn)單，可以用硬件實(shí)現(xiàn)高效路由算法,在嚴(yán)格正交拓?fù)渲校梢杂霉?jié)點(diǎn)在,n,

7、維空間中的坐標(biāo)作為節(jié)點(diǎn)的編號(hào)。,由于每條鏈路都遍歷了一維，而且每一個(gè)節(jié)點(diǎn)在每一維上至少有一條鏈路，兩個(gè)節(jié)點(diǎn)間的距離就可以用每一維的偏移量的和來(lái)計(jì)算。,給定鏈路上的偏移量?jī)H僅影響相應(yīng)維的偏移量。由于從網(wǎng)絡(luò)中的任意節(jié)點(diǎn)可以直接到達(dá)任意維，路由實(shí)現(xiàn)只需在某一維上選擇絕對(duì)偏移量減小的鏈路就可以了。,各維的偏移量可以存儲(chǔ)在報(bào)文頭中，報(bào)文每次成功地經(jīng)過(guò)中間節(jié)點(diǎn)時(shí)將會(huì)更新偏移量（增加或減少一個(gè)單位）,嚴(yán)格正交拓?fù)?n,維網(wǎng)格,最流行的直接網(wǎng)絡(luò)是,n,維網(wǎng)格、,k,元,n,立方或環(huán)網(wǎng)和超立方。它們都是嚴(yán)格正交的。,n,維網(wǎng)格有,K,0,xK,1,xK,n-2,xK,n-1,個(gè)節(jié)點(diǎn)，,K,i,是第,i,維的節(jié)點(diǎn)

8、數(shù)，,K,i,2,且,0=,i,=n,一,1,。每個(gè)節(jié)點(diǎn),X,由,i,維坐標(biāo)（,X,n-1,X,n-2,X,1,X,0,),定義，其中，對(duì)于,0=,X,i,=,K,i,-1,。,X,和,Y,兩個(gè)節(jié)點(diǎn)相鄰的充要條件是：存在,j,使得,y,j,=x,j,+1,或,x,j,-1,，而對(duì)其他的,0=,i,=n-1,，有,y,i,x,i,。,一個(gè)節(jié)點(diǎn)根據(jù)它們?cè)诰W(wǎng)格中的位置，有,n,到,2n,個(gè)相鄰節(jié)點(diǎn)，因此這種拓?fù)浣Y(jié)構(gòu)不是規(guī)整的。,嚴(yán)格正交拓?fù)?k,元,n,立方,在雙向,k,元,n,立方中，所有節(jié)點(diǎn)的相鄰節(jié)點(diǎn)數(shù)目相同。,k,元,n,立方與,n,維網(wǎng)格的定義有所區(qū)別，它所有的,k,i,都等于,k,，并且,

9、X,和,Y,兩個(gè)節(jié)點(diǎn)相鄰的充要條件是：,存在,j,使得,y,j,=(x,j,+1,）,mod k,或,y,j,=(x,j,-1,）,mod k,，而對(duì)于其他任意,0=i2,，所有的節(jié)點(diǎn)都有,2n,個(gè)相鄰節(jié)點(diǎn)。,當(dāng),n=1,時(shí)，,k,元,n,立方變成了具有,k,個(gè)節(jié)點(diǎn)的雙向環(huán)。,嚴(yán)格正交拓?fù)?超立方,超立方是,n,維網(wǎng)格和,k,元,n,立方的特例。,超立方是一個(gè),n,維網(wǎng)格，其中,ki,=2,且,0i=n,一,1,，,2,元,n,立方也叫做二進(jìn)制,n,方。,其他直接互連網(wǎng)絡(luò),樹(shù)形連接：,二叉樹(shù)中除了根節(jié)點(diǎn)和葉節(jié)點(diǎn)之外，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)相連，故稱為三近鄰連接。,節(jié)點(diǎn)度為,3,，對(duì)

10、剖寬度為,1,，而樹(shù)的直徑為 ，,N,為樹(shù)的總節(jié)點(diǎn)數(shù)。,如果盡量增大根節(jié)點(diǎn)度為,N-1,，其他所有節(jié)點(diǎn)都與它直接相連，則直徑縮小為,2,，此時(shí)就變成了星形連接，其對(duì)剖寬度為 ，從某種意義上講類似于基于總線的網(wǎng)絡(luò)。,樹(shù)的主要問(wèn)題是根易成為通信瓶頸。,1985,年,Leiserson,提出的胖樹(shù)（,Fat Tree,）可緩解此問(wèn)題。胖樹(shù)節(jié)點(diǎn)間的通路自葉向根逐漸變寬，它更像真實(shí)的樹(shù)，連向根部的枝叉變得愈來(lái)愈粗。,Overview,Review of Lec4,間接互連網(wǎng)絡(luò),交換技術(shù),動(dòng)態(tài)互連網(wǎng)絡(luò)特性,動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò)沒(méi)有提供節(jié)點(diǎn)間的直接連接，任何兩個(gè)節(jié)點(diǎn)間的通信必須通過(guò)某些交換機(jī)進(jìn)行。,每個(gè)節(jié)點(diǎn)都有一個(gè)

11、網(wǎng)絡(luò)適配器連接在網(wǎng)絡(luò)開(kāi)關(guān)上。,每個(gè)開(kāi)關(guān)都有一組端口，每個(gè)端口包括一條輸入和一條輸出鏈路。每個(gè)開(kāi)關(guān)的端口或連接到處理器，或者懸空，或者連接到其他開(kāi)關(guān)的端口上，以實(shí)現(xiàn)處理器間的連接。這些開(kāi)關(guān)的互連方式?jīng)Q定了不同的網(wǎng)絡(luò)拓?fù)洹?間接網(wǎng)絡(luò)的模型也可以用圖,G(N,C),表示，其中,N,是開(kāi)關(guān)的集合，,C,是開(kāi)關(guān)之間的單向或雙向鏈路集合。,從一個(gè)節(jié)點(diǎn)向另一個(gè)節(jié)點(diǎn)發(fā)送消息時(shí)，需要經(jīng)過(guò)源節(jié)點(diǎn)和它連接的開(kāi)關(guān)之間的鏈路及傳輸路徑中最后一個(gè)開(kāi)關(guān)和目的節(jié)點(diǎn)之間的鏈路。因此兩個(gè)節(jié)點(diǎn)間的距離要在直接連接兩個(gè)節(jié)點(diǎn)的開(kāi)關(guān)之間的距離上再加上兩個(gè)單位。類似地，網(wǎng)絡(luò)直徑等于連接到節(jié)點(diǎn)的開(kāi)關(guān)之間的最大距離加上兩個(gè)單位。,動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò)

12、類型,與直接網(wǎng)絡(luò)相似，間接網(wǎng)絡(luò)的主要屬性由三個(gè)要素來(lái)描述：拓?fù)洹⒙酚珊徒粨Q。,拓?fù)涠x了開(kāi)關(guān)是如何通過(guò)通道互連的，可以圖建模。,對(duì)于具有,N,個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，理想環(huán)境是使用一個(gè),NxN,的開(kāi)關(guān)連接它們，這種開(kāi)關(guān)就是交叉開(kāi)關(guān)。,使用一個(gè),NxN,的交叉開(kāi)關(guān)比使用全連接的直接網(wǎng)絡(luò)拓?fù)洌ㄓ?N,個(gè)路由器，每個(gè)路由器都有一個(gè),NxN,內(nèi)部交叉開(kāi)關(guān)）便宜，但是交叉開(kāi)關(guān)的成本仍然限制了它在大型網(wǎng)絡(luò)中的使用。,于是，又提出其他的拓?fù)浣Y(jié)構(gòu)。在這些拓?fù)渲?，消息到達(dá)目的節(jié)點(diǎn)之前要經(jīng)過(guò)多個(gè)開(kāi)關(guān)。規(guī)整網(wǎng)絡(luò)中的開(kāi)關(guān)通常都是相同的，傳統(tǒng)上采用多級(jí)結(jié)構(gòu)。,除了輸人輸出級(jí)以外，每一級(jí)使用規(guī)整連接與前一級(jí)和下一級(jí)相連。輸人輸出級(jí)

13、既連接節(jié)點(diǎn)，又連接了網(wǎng)絡(luò)中的其他級(jí)，這種網(wǎng)絡(luò)稱作多級(jí)互連網(wǎng)絡(luò)。,交叉開(kāi)關(guān),交叉開(kāi)關(guān)（,Crossbar,）網(wǎng)絡(luò)是單級(jí)交換網(wǎng)絡(luò)，可為每個(gè)端口提供更高的帶寬。象電話交換機(jī)一樣，交叉點(diǎn)開(kāi)關(guān)可由程序控制動(dòng)態(tài)設(shè)置其處于“開(kāi)”或“關(guān)”狀態(tài)，而能提供所有（源、目的）對(duì)之間的動(dòng)態(tài)連接。,在并行處理中，交叉開(kāi)關(guān)一般有兩種使用方式：一種是用于對(duì)稱的多處理機(jī)或多計(jì)算機(jī)機(jī)群中的處理器間的通信；另一種是用于,SMP,服務(wù)器或向量超級(jí)計(jì)算機(jī)中處理器和存儲(chǔ)器之間的存取。,交叉開(kāi)關(guān)點(diǎn)的狀態(tài),a,中該行輸入允許訪問(wèn)相應(yīng)的輸出，而從上面發(fā)出的對(duì)同一輸出的訪問(wèn)被阻塞。,b,中上面發(fā)出的輸入允許訪問(wèn)輸出，通過(guò)開(kāi)關(guān)點(diǎn)的行輸入不請(qǐng)求同一

14、輸出并可以傳向其他開(kāi)關(guān)。,c,中從上面發(fā)出的輸入允許訪問(wèn)輸出，但是通過(guò)開(kāi)關(guān)點(diǎn)的行輸入也請(qǐng)求同一輸出，被阻塞。,d,中狀態(tài)只用于要求交叉開(kāi)關(guān)支持多播的情形。,交叉開(kāi)關(guān)應(yīng)用,千兆開(kāi)關(guān),/FDDI:,一種用于構(gòu)造,Alpha,工作站和服務(wù)器互連的交叉開(kāi)關(guān)，帶寬,3.6Gbps,Sun,Microsystem,公司在它們的,Ultra Enterprise l0000,（,StarFire,）,SMP,服務(wù)器中，將,Gigaplane,總線升級(jí)成,Gigaplane,-XB,互連,交叉開(kāi)關(guān)應(yīng)用,處理器和存儲(chǔ)器間的交叉開(kāi)關(guān)：,交叉開(kāi)關(guān)代替處理器和存儲(chǔ)器間的連接總線,提供了多個(gè)處理器模塊并行存取存儲(chǔ)器的可

15、能性,每個(gè)時(shí)刻每個(gè)存儲(chǔ)器模塊只能由一個(gè)處理器進(jìn)行訪問(wèn),交叉開(kāi)關(guān)特性,交叉開(kāi)關(guān)具有良好的帶寬特性,Non-Blocking:,兩個(gè)節(jié)點(diǎn)之間的通信，不會(huì)阻塞其他節(jié)點(diǎn)之間的通信。,代價(jià)不可擴(kuò)放，,O(P,2,),多級(jí)互連網(wǎng)絡(luò),交換開(kāi)關(guān)模塊,一個(gè)交換開(kāi)關(guān)模塊有,a,個(gè)輸入和,b,個(gè)輸出，每個(gè)輸入可連接到任意輸出端口，但只允許一對(duì)一或一對(duì)多的映射，不允許多對(duì)一的映射，因?yàn)檫@將發(fā)生輸出沖突,第,i,級(jí)開(kāi)關(guān),Gi,，有,w,i,個(gè),a,i,j,*,b,i,j,開(kāi)關(guān)，,Gi,級(jí)共有,pi,個(gè)輸入和,qi,個(gè)輸出。,通常實(shí)現(xiàn)中所有開(kāi)關(guān)都是相同的。,級(jí)間互連（,Interstage,Connection,）：定義

16、了每一級(jí)輸入與上一級(jí)輸出之間連接方式,如果網(wǎng)絡(luò)具有,N=,k,n,個(gè)端口，令,X=x,n-1,x,n-2,x,1,x,0,表示任意一個(gè)端口號(hào)，其中,0=X,i,=k-1,，如,k=2,Generalized MIN Arch,典型的級(jí)間互聯(lián)模式,完全混洗排列,:C(x,n-1,x,n-2,x,1,x,0,)=x,n-2,x,1,x,0,x,n-1,把,X,中的數(shù)循環(huán)左移一位（圖,a),逆完全混洗正好相反,(,圖,b,）,典型的級(jí)間互聯(lián)模式,數(shù)字反轉(zhuǎn)排列,:C(x,n-1,x,n-2,x,1,x,0,)=x,0,x,1,x,n-2,x,n-1,通常稱為位反轉(zhuǎn)排列（圖,c,所示）,典型的級(jí)間互連,蝶形連接,:,Ci(x,n-1,x,i+1,x,i,x,i-1,x,1,x,0,)=x,n-1,x,i+1,x,0,x,i-1,x,1,x,i,第,i,個(gè)蝶形排列交換索引中的第,0,和第,i,個(gè)數(shù),典型的級(jí)間互連,立方體排列,:,Ci(x,n-1,x,i+1,x,i,x,i-1,x,1,x,0,)=x,n-1,x,i+1,x,i,x,i-1,x,0,第,i,個(gè)立方體排列將索引中的第,i,位求反,典