《并行計算機體系結(jié)構(gòu)》由會員分享，可在線閱讀，更多相關(guān)《并行計算機體系結(jié)構(gòu)（64頁珍藏版）》請在裝配圖網(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,并行計算機體系結(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)度與動態(tài)調(diào)度,互連網(wǎng)絡(luò),系統(tǒng)互連,不同帶寬與距離的互連技術(shù),基本網(wǎng)絡(luò)部件,鏈路,鏈路（,link),：傳輸信息的物理介質(zhì)，也稱為通道或電纜,不同的物理介質(zhì)：雙絞線,(STP),、同軸電纜、光纖,可用來連接兩個,Switch,或主機與,Switch,長度,:,短鏈路在任一時刻僅包含一個邏輯信號；而長鏈路允許同時在鏈路上傳輸邏輯信號,寬度,:,一條窄鏈路只有一位信號線；一條寬鏈路有多位信號線。,時鐘：一條鏈路常由同步或異步兩

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

4、口每秒鐘傳輸消息的最大位（或字節(jié)）數(shù),如,IBM HPS,每端口帶寬,40MB/s,聚集帶寬：,從一半節(jié)點到另一半節(jié)點，每秒鐘傳輸消息的最大位（或字節(jié)）數(shù),如,IBM HPS,端口數(shù)最多為,512,，聚集帶寬為,512*40/2=10.24GB/s,對剖寬度：將網(wǎng)絡(luò)分成兩個相等部分所必須移去的最少邊數(shù)。,對剖帶寬（,Bisection Bandwidth,）：,每秒鐘內(nèi)，在最小的對剖平面上通過所有連線的最大信息位（或字節(jié)）數(shù)。等于對剖寬度與通道帶寬之積。,靜態(tài)互連網(wǎng)絡(luò) 與動態(tài)互連網(wǎng)絡(luò),靜態(tài)互連網(wǎng)絡(luò)：又稱為直接連接網(wǎng)絡(luò)。處理單元間有著固定連接的一類網(wǎng)絡(luò)，在程序執(zhí)行期間，這種點到點的鏈接保持不變；

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

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

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

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

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

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

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

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

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

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

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

16、了每一級輸入與上一級輸出之間連接方式,如果網(wǎng)絡(luò)具有,N=,k,n,個端口，令,X=x,n-1,x,n-2,x,1,x,0,表示任意一個端口號，其中,0=X,i,=k-1,，如,k=2,Generalized MIN Arch,典型的級間互聯(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,）,典型的級間互聯(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,所示）,典型的級間互連,蝶形連接,:,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,個蝶形排列交換索引中的第,0,和第,i,個數(shù),典型的級間互連,立方體排列,:,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,個立方體排列將索引中的第,i,位求反,典