《《互聯(lián)網絡》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《互聯(lián)網絡》PPT課件.ppt（56頁珍藏版）》請在裝配圖網上搜索。
1、1,第五章 互連網絡,互連網絡是現(xiàn)代計算機系統(tǒng)中的一個核心部分和關鍵部件。對整個計算機系統(tǒng)的性能有著決定性影響。隨著系統(tǒng)規(guī)模、通信要求和線路復雜性的增加,其重要性在不斷增長。已經成為計算機組織和系統(tǒng)結構中獨立的研究內容。,5.3 路由選擇和信息傳遞方式 5.4 流量控制策略和通信模式,5.1 互連網絡的相關概念 5.2 互連網絡的結構,2,5.1 互連網絡的相關概念,一、互連網絡的組成,1、互連網絡(IN)定義 由開關元件按照一定拓撲結構和控制方式構成的網絡，實現(xiàn)多個節(jié)點對之間的相互連接。 互連網絡已成并行計算機系統(tǒng)中重要的核心部件。,根據(jù)需要，有PP及PM的連接形式,3,2、互連網絡(IN)
2、 的特性 *特性1：同時實現(xiàn)多個端口對的互連及通信。,*特性2：具有多種并行端口對的互連方式.,*互連網絡與總線比較： 互連網絡 : 強調多個節(jié)點對之間的互連及通信。 總 線 : 多個設備或單元所共享的公共通道(分時),理論上有N!種端口對互連排列方式,4,2、互連網絡要素：開關元件、互聯(lián)結構、控制方式。 互聯(lián)結構：網絡合理布局關鍵因素，反映系統(tǒng)結構特征。用有向圖或無向圖表示，節(jié)點對應開關元件或處理機。邊對應通信鏈路。 開關元件：網絡中最基本模塊，在不同系統(tǒng)和控制中，開關元件所處的物理位置和工作狀態(tài)不同。 控制方式：網絡中各種開關的控制方法 3 、互連網絡的特征,1) 拓撲結構 靜
3、態(tài) 動態(tài) 2) 控制策略 集中式 分散式 3) 定時方式 同步 異步 4) 交換方法 線路交換 分組交換,5,互連網絡的特征,1) 拓撲結構: 分靜態(tài)和動態(tài)兩種。 靜態(tài)網:各節(jié)點間有專用通信線路（鏈路），運行間不改變或重新組合。又稱直接網絡 (節(jié)點通過鏈路直接連接) 組成：由鏈路、結構及網絡節(jié)點組成。 結構: 線性、環(huán)形、樹形、 立方體等。,6,動態(tài)網: 鏈路可通過設置網絡中開關重新組合。節(jié)點與節(jié)點的連接由程序或控制信號動態(tài)地改變，又稱間接網絡(節(jié)點與交換開關連接)。 組成：由鏈路、結構、開關及節(jié)點組成。 結構: 總線、環(huán)狀、 開關、(單)多級。,動態(tài)網:,7,互連網
4、絡的特征,2)控制策略: 集中控制:全局控制器接收所有通信請求，設置互連網絡的開關連接。 分散控制: 通信請求和開關設置由互連網絡分散地進行。 3)定時方式 ： 同步系統(tǒng)：系統(tǒng)使用一個集中的統(tǒng)一時鐘. 異步系統(tǒng)：無統(tǒng)一時鐘，節(jié)點根據(jù)各自情況獨立工作。 4)交換方法: 線路交換和分組交換。 線路交換：源結點和目的結點間的物理通路在整個數(shù)據(jù)傳送期間一直保持連接。 分組交換：信息分割成組(包)，各組(包)通過多個不同路徑傳分別送入互連網絡。傳送不存在一個實際連接的固定通路。,8,5.1.2 互連網絡的描述,根據(jù)輸入與輸出結點之間的對應關系，有以下表示方法： 函數(shù)表示法 變量x表示輸入，函數(shù)
5、f(x)表示輸出，建立輸入與輸出端的一一對應關系。 自變量和函數(shù)常用二進制、十進制表示?；ミB函數(shù)反映網絡輸入數(shù)組和輸出數(shù)組之間對應的排列關系，也稱排列函數(shù)。 輸入輸出對應表示法 圖形表示法 用圖形表示輸入端 與輸出端之間的一一對應關系 循環(huán)表示法：如(0 4)(1 5)(2 6)(3 7),,9,互連函數(shù) 數(shù)的排列：N個數(shù)的每一種有確定次序的放置方法叫做一個N排列。一般有N！種放置方法。 網絡排列：N輸入、N輸出端網絡中，輸入端和輸出端的放置方法分別為一種排列。 置換：把一個N排列變成另一個N排列的變換叫N階置換。表示輸入端和輸出端的連接關系. 復雜的置換方式可用少量基本的互聯(lián)函數(shù)表示,10
6、,基本的互聯(lián)函數(shù),恒等函數(shù):輸入端與輸出端一一對應,且編號相同。,Xn-1 Xn-2Xk X0是PE的地址（通常為二進制）。n為3時的恒等函數(shù)的連接情形如下：,(0)(1)(2)(3)(4)(5)(6)(7),11,交換函數(shù),交換函數(shù):函數(shù)形式為,主要用于超立方體互聯(lián)網絡中。,超立方體由n個交換函數(shù)組成。 K=1,二進制地址編碼下，,某一位的輸入與輸出端編號相反。,0kn,12,當n=3，結點數(shù)N8時，可得到3立方體互連函數(shù)： 互連函數(shù)變換圖形,交換函數(shù),典型的立方體網絡結構圖,(0 1) (2 3 ) (4 5) (6 7),(0 2)(1 3 ) (4 6) (
7、5 7),(0 4)(1 5) (2 6) (3 7),13,均勻洗牌函數(shù),把輸入端二進制地址循環(huán)左移一位。表示為： 逆均勻洗牌函數(shù): 輸入端二進制地址循環(huán)右移一位。函數(shù)：,(0)(1 2 4)(3 6 5)(7),將輸入端分成數(shù)目相等的兩半，前一半和后一半按序一個隔一個，從頭依次與輸出端相連，類似洗牌方式。,14,均勻洗牌函數(shù),均勻洗牌函數(shù),逆均勻洗牌函數(shù),均勻洗牌與開關多級組合起來可構成Omega網絡,15,蝶式函數(shù),蝶式函數(shù): 輸入二進制地址的最高位和最低位互換位置，定義為： N=8的蝶式函數(shù)變換圖形,均勻洗牌，蝶式函數(shù)不能單獨實現(xiàn)任意結點間互連。它們與交換函數(shù)多級組合是構成復雜多
8、級網絡的基礎,例如 : 均勻洗牌函數(shù)與Cube0的組合,(0)(2)(1 4) (3 6)(5)(7),16,反位序函數(shù),反位序函數(shù): 輸入端二進制地址的位序顛倒過來求得相應輸出端的地址。其互連函數(shù)表示如下： 對于N=8的情況，圖形見圖5.4（b）,17,PM2I移數(shù)函數(shù),移數(shù)函數(shù)的一般形式為： 如k=2 PM2I函數(shù)（加減2i）是一種特殊移數(shù)函數(shù)，將輸入端數(shù)組的十進制編號循環(huán)移動特定的位置向輸出端傳輸。 N個結點的移數(shù)函數(shù)表示為： 如i=1 設 N為結點數(shù)。n=log2 N ； 0 xN1，0in1， 共有2n個互連函數(shù),(0 2 4 6)(1 3 5 7),18
9、,N=8的PM2I函數(shù)的變換圖形。,(a) PM2： (0 1 2 3 4 5 6 7),(b) PM21： (0 2 4 6) (1 3 5 7),(c) PM2+2： (0 4)(1 5)(2 6)(3 7),實質為1,2,4 個環(huán)型網,移數(shù)函數(shù)可構成環(huán)型網(單向環(huán)網、雙向環(huán)網)、方格網、移數(shù)網,19,課堂練習,設PM2I網絡有8個結點，寫出所有PM2I函數(shù)的輸入輸出對表示，畫出PM21、PM22互連網絡的連接圖。,20,【例 】設PM2I網絡有8個結點，寫出所有PM2I函數(shù)的，畫出PM21、PM22互連網絡的連接圖。,解 N=8，則n =3，所以i=0,1,2;j=0,1,,7。
10、 根據(jù)公式 6個PM2I函數(shù)如下： PM2：(0 1 2 3 4 5 6 7) PM2：(7 6 5 4 3 2 1 0) PM21：(0 2 4 6)(1 3 5 7) PM21：(6 4 2 0)(7 5 3 1) PM2 2：(0 4)(1 5)(2 6)(3 7) PM2 2 ：(4 0)(5 1)(6 2)( 7 3),PM2,PM2,21,PM21：(0 2 4 6)(1 3 5 7),PM21互連網絡的連接圖。,22,(c) PM22：(0 4)(1 5)(2 6)(3 7) (4 0)(5 1)(6 2)(7 3),,PM22互連網絡的連接圖,23,【例】Ill
11、iac 陣列計算機：采用PM20和PM2n/2四個移數(shù)網絡構成處理器的連接。16個結點的Illiac 網絡表示,PM22：(0 4)(1 5)(2 6) (3 7) (4 8)(5 9)(6 10)(7 11) (8 12)(9 13)(10 14)(11 15) (0 12)(1 13)(2 14) (3 15),PM2+0:( 0 1 2 15 ) PM2-0:( 15 14 13 0 ),24,5.1.3互連網絡的特性參數(shù),,主要特性參數(shù)有： 網絡規(guī)模: 結點度: 距離 網絡直徑 結點間線長 等分寬度 對稱性,25,網絡規(guī)模：網絡中結點個數(shù)，表示該網絡所能連接的部件多少。 結點度
12、：與結點相連接的邊數(shù)(通道數(shù))。進結點的邊數(shù)叫入度，出結點的邊數(shù)叫出度。 結點度=出度+入度 距離：兩個結點之間相連的最少邊數(shù)。 網絡直徑：網絡中結點間距離的最大值，可用結點間的連接邊數(shù)表示。 結點間線長：結點間連線的長度，用米、公里等表示。,互連網絡的特性參數(shù),26,等分寬度:把N個結點構成的網絡切成結點數(shù)相同（N/2）的兩半，在各種切法中，沿切口邊數(shù)的最小值。反映網絡內部傳輸帶寬。 線等分寬度：傳輸帶寬與通道寬度w(位)的乘積，Bbw。反映網絡最大流量。 對稱性：從任何結點，拓撲結構都相同的網絡稱為對稱網絡。對稱網絡容易編程和實現(xiàn)。結點上的負載量分布均勻。,互連網絡的特性參數(shù),27,5.
13、2.1 靜態(tài)互連網絡 靜態(tài)網絡： 指各節(jié)點（處理單元）間有著固定或專用的連接通路的網絡。在程序執(zhí)行中，節(jié)點到節(jié)點的鏈接保持（或網絡）保持不變。 靜態(tài)網絡中，每個開關元件固定地與一個結點相連，或分散在每個節(jié)點的內部（看不到開關元件），直接實現(xiàn)兩結點之間的通信。 一般是簡單的、通信模式可預測的網絡系統(tǒng)。,5.2 互連網絡的結構,互連網絡可分為靜態(tài)和動態(tài)互連網絡。,28,靜態(tài)互連網絡,從不同的角度對靜態(tài)互連網絡進行分類 1）按通路類型 共享（總線型）通路： 非共享通路： 2) 按拓撲維數(shù) 所謂維數(shù) n ，指網絡畫在n維空間時才能保證各條鏈路不會相交。 3) 按網絡形狀 總線型、線型、 環(huán)型、立方體
14、型、樹型、全連接等。 4) 按度數(shù),29,典型的靜態(tài)網絡,N個結點的線形網（規(guī)模），有N-1條鏈路，距離的最大值為N-1（直徑），度為2，等分寬度為1。 一維，不對稱（？）。 簡單，N很大時，通信效率很低。,1.線形網,30,2.環(huán)形網,N個結點的環(huán)，有雙向環(huán)和單向環(huán)。 雙向環(huán)：鏈路數(shù)為N，直徑N/2，度為2，對稱，等分寬度為2。 單向環(huán)：鏈路數(shù)為N，直徑N-1，度為2，對稱，等分寬度為2。,31,3.帶弦環(huán),圖為（12個結點）帶弦雙向環(huán) 結點度為3：鏈路數(shù)為18，直徑4（紅色結點），度為3，不對稱，等分寬度為2。 結點度為4：鏈路數(shù)為24，直徑3（紅色結點），度為4，對稱，等分寬度為8。,3
15、2,4.全鏈接 全鏈接中的每個結點和其他結點之間都有單一的直接鏈路。帶弦環(huán)的一種特殊情形。 下圖中8個結點的全鏈接：,,,,,,,,,,28條鏈路，直徑1，度為7，對稱，等分寬度16。,,,,,,,,,,,,,,,,,,,,,全連接網絡是最復雜的拓撲結構，每個結點同其他 結點都連接，直徑為1，度數(shù)是(N-1)。,33,5.樹形,4層的二叉樹,K層完全二叉樹有N = 2K - 1個結點，中間層結點的結點度為3，直徑為2（K - 1）。不對稱，等分度為1。樹形網是一種容易擴展的系統(tǒng)結構。 根部結點和連到根部鏈路上的負載量較大，為系統(tǒng)的瓶頸。,34,,,樹形的擴展：,,,,,,,,,,,,,,,,,
16、,,,,,,,,,,,,,帶環(huán)樹,,兩種結構可以緩解根結點的瓶頸問題。,35,6.星形,星形實際上是一種二層樹（如右圖）。 N個結點的星形網絡，有N - 1條鏈路，直徑為2，最大結點度為N - 1，非對稱（？），等分寬度為1。,,36,,,,,,,,,,7.網格,N個結點的rr網格，有2N - 2r條鏈路， 直徑為2（r-1)，結點度為4，非對稱，等分寬度為r。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,二維環(huán)形拓撲結構,37,網格的變形---Illiac 網：,N個結點的rr網格 2N條鏈路（
17、？），直徑為r-1，結點度為4。,--網格結構擴充性好，易在VLSI芯片上實現(xiàn)。,每行尾與下一行的頭，每列尾與下一列的頭相接-網格卷繞。,38,,,,,,,,,,網格的變形---搏動式陣列（Systolic Array）,,,,,,,,,,39,8.超立方體,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,0維-立方體,1維-立方體,2維-立方體,3維-立方體,4維-立方體,n-立方體由N = 2n個結點構成。直徑為n，結點度為n，對稱。結點度隨維數(shù)線性增加。,特點： 相鄰的結點編號只差一位,40,
18、9.帶環(huán)立方體（CCC）,一個帶環(huán)n-立方體，由N = 2n個結點環(huán)構成，每個結點環(huán)是一個有n個結點的環(huán)，結點總數(shù)為n 2n個。直徑通常為2n，結點度為3，對稱。,帶環(huán)3-立方體,41,靜態(tài)網絡特性比較,42,5.2.2 動態(tài)互連網絡,,動態(tài)網絡(dynamic Networks)通常由交換開關構成互聯(lián)網絡的，可按運行程序的要求改變網絡的連接狀態(tài)。 特點： 網絡中開關元件可以控制（有源）。 鏈路可通過設置開關的狀態(tài)來重構。 網絡邊界上的開關元件可與處理機相連。 有總線網絡、多級網絡和交叉開關網絡等。,43,1 總線系統(tǒng),總線是一組公用通信通路，通過導線和插座把各臺處理機、存儲模塊和外圍設備與總
19、線連接起來。總線是一組公用通信通路，通過導線和插座把各臺處理機、存儲模塊和外圍設備與總線連接起來。 組成：處理機、存儲模塊、局部Catch、I/O部件和外圍設備等?？偩€結構在并行處理機系統(tǒng)有重要地位。,44,總線系統(tǒng)一般特點,處理機、存儲模塊和外圍設備均與總線相連，分時工作。價格低。 每臺處理機都能訪問公共總線，有局部catch。 處理機通過請求訪問全局存儲器。多請求下總線仲裁邏輯將總線分配給一個請求。 局部Catch數(shù)據(jù)修改和通信執(zhí)行“一致性協(xié)議” 存在總線和共享存儲器兩大瓶頸。 主要問題：總線仲裁、中斷處理、一致性協(xié)議和總線事務處理（帶寬窄）。 總線復雜性由總線上連接的分接頭數(shù)n與數(shù)據(jù)通路
20、寬度w的和w+n決定.,45,多級網絡,單級網絡：由一級開關和一種連接模式構成的互聯(lián)。 多級網絡則包含多級開關和多級連接模式。,每一級都用多個ab開關，通過動態(tài)設置開關狀態(tài)，改變或建立輸入和輸出對之間的連接。 相鄰級開關間有固定的級間連接（ISC)。 ab開關: a個輸入和b個輸出。a和b常為2的整數(shù)冪 級控制、單元控制、部分級控制 三種控制方式。,46,控制方式指對各個開關模塊進行控制的方法。 (1)級控制 每一級所有開關只用一個控制信號控制，該級所有開關處于同一種狀態(tài)； (2)單元控制 每個開關都有單獨的控制信號，各自可處于不同的狀態(tài)； (3)部分級控制 第i級的所有開關分別用i+1個信號
21、控制，控制信號隨級數(shù)增加而遞加。 級間連接(ISC)模式：均勻洗牌、蝶式、交換 常用開關模塊：22，44，88。,多級互連網絡控制方式,47,【例】Omega網絡,,88 Omega網絡，3級。22開關。級數(shù)一般為logkn 網絡左側有8個輸入，右側有8個輸出。 級間連接(ISC)是對8個對象的均勻洗牌模式。 控制開關狀態(tài)可實現(xiàn)從輸入到輸出的多種連接。 交叉開關復雜性 O((n logkn) w)。w是MIN設計中鏈路寬度。(假設k*k開關為基本構件)。,48,Omega網絡,構造Omega網絡的22開關的四種連接方式：直通、交叉、上播和下播。,開關模塊及狀態(tài)：,上播和下播不能構成置換（允許一
22、個輸入連接兩個輸出）,49,【例4】一個多級立方體網采用二功能開關和交換函數(shù)構成，其拓撲結構如圖所示。使交換開關的設置處于某一種工作狀態(tài)，可以得到的不同的多級互連網絡。 (1)當所有開關都直通時，實現(xiàn)恒等變換； (2)當A、B、C、D四個開關交換，其余直通時實現(xiàn)C； (3)當E、F、G、H四個開關交換，其余直通時實現(xiàn)C1； (4)當I、J、K、L四個開關交換，其余直通時實現(xiàn)C2。,,50,交叉開關網絡,可看作單級開關網絡。帶寬和互連特性最好。交叉點能在(源，目的)之間動態(tài)連接，每個交叉點開關根據(jù)程序要求動態(tài)設置“開”或“關”。如圖是多處理機中處理機-存儲器間的交叉開關網絡。,51,交叉開關網絡
23、,在處理機和存儲模塊間用交叉開關網絡構成一個共享存儲型多處理機，實際是一個存儲器訪問網絡。支持并行(或交叉)存儲器訪問。 每個處理機可同時訪問不同的存儲模塊。同時接通幾個交叉點開關。 每個存儲模塊一次只能滿足一臺處理機的請求。每一列只能接通一個交叉點開關。 在多個請求同時到達同一存儲模塊時，交叉開關要分解所發(fā)生的沖突。 每臺處理機可能會產生一系列地址，同時訪問多個存儲模塊。,52,向量并行處理機(VPP 500),采用大型交叉開關網絡。PE為帶存儲器的處理機，CP代表控制處理機。 網絡中，每行和一列只能接通一個交叉點開關。處理機間的交叉開關實現(xiàn)處理機之間的置換連接（一對一）。 n*n交叉開關網
24、絡一次最多可連通n個(源，目的)處理機對。,53,三種動態(tài)網絡比較,1) 硬件復雜性 總線互連成本低。連線復雜性由數(shù)據(jù)總線和地址總線的寬度決定。地址線可為數(shù)據(jù)總線的一部分。256根數(shù)據(jù)線和64根地址線代表當今總線的設計水平。總線互連開關的硬件復雜性隨分接頭數(shù)n和數(shù)據(jù)通路寬w兩者線性增加。 交叉開關復雜性隨 n*n w乘積而增大，其中n*n 對應交叉開關中的交叉點數(shù)，w是交叉開關中的通路寬度。 多級網絡(MIN)，硬件復雜性函數(shù)為O((nlogkn)w)，復雜性位于總線和交叉開關網絡之間。 總線、多級網絡、交叉開關硬件復雜性呈增加趨勢。,54,2）處理器帶寬,總線系統(tǒng)中n個處理器競爭總線帶寬。假
25、設時鐘頻率為f，則總線的每個處理器帶寬在函數(shù)O(wf/n)和O(wf)范圍內變化。 MIN和交叉開關具有較寬的處理器帶寬，該帶寬隨函數(shù)O(wf)線性變化。 在多級網絡中，數(shù)據(jù)傳輸要經過多級開關，總線和交叉開關只需較少時間(1或2周期)來傳輸單位數(shù)據(jù)。 交叉開關具有最高的處理器帶寬。 總線、多級網絡、交叉開關的處理器帶寬呈增加趨勢。,55,3 聚集帶寬,聚集帶寬物理概念是：在一個給定的網絡中，從一半結點到另一半結點，每秒傳輸信息的最大位數(shù)。 結論：多級網絡（MIN）比總線或交叉開關互連具有更大的聚集帶寬。,56,4.動態(tài)網絡比較,表5.3匯總了構成動態(tài)網絡的總線、多級網絡、交叉開關的主要特性。 表5.3 動態(tài)網絡的復雜性和帶寬性能一覽表,,,,,,
《互聯(lián)網絡》PPT課件.ppt
