第6章 并行處理機(jī)

1、 高性能計算機(jī)發(fā)展歷程自自19641964年以后年以后, ,高性能計算機(jī)經(jīng)歷了三個發(fā)展階段高性能計算機(jī)經(jīng)歷了三個發(fā)展階段: :萌芽階段、向量機(jī)鼎盛階段和大規(guī)模并行處理機(jī)萌芽階段、向量機(jī)鼎盛階段和大規(guī)模并行處理機(jī)（MPPMPP）蓬勃發(fā)展階段。）蓬勃發(fā)展階段。1. 1. 萌芽階段（萌芽階段（1964-19751964-1975） 19641964年誕生的年誕生的CDC6600CDC6600被公認(rèn)為世界上第一臺被公認(rèn)為世界上第一臺巨型計算機(jī)，其運(yùn)算速度為巨型計算機(jī)，其運(yùn)算速度為1Mflops1Mflops。7070年代初研年代初研制成功制成功STAR-100STAR-100向量機(jī)，這是世界上最早的向

2、量向量機(jī)，這是世界上最早的向量機(jī)。隨后于機(jī)。隨后于19741974年，誕生了世界上最早的年，誕生了世界上最早的SIMDSIMD陣陣列計算機(jī)列計算機(jī)-ILLIAC-IV-ILLIAC-IV并行機(jī)。并行機(jī)。 2.2.向量機(jī)鼎盛階段（向量機(jī)鼎盛階段（1976-19901976-1990） 19761976年，年，CRAYCRAY公司推出公司推出CRAY-1CRAY-1向量機(jī)，開始向量機(jī)，開始了向量機(jī)的蓬勃發(fā)展，其峰值速度為了向量機(jī)的蓬勃發(fā)展，其峰值速度為0.1Gflops.0.1Gflops. 1985 1985年，年，CRAY-2CRAY-2，1G flops1G flops 1990 1990年

3、，年，SX-3SX-3，22G flops22G flops 1991 1991年，年，Cray-YMP-C90Cray-YMP-C90，16Gflops16Gflops 向量機(jī)處理對提高計算機(jī)運(yùn)算速度十分有利，向量機(jī)處理對提高計算機(jī)運(yùn)算速度十分有利，有利于流水線的充分利用，有利于多功能部件的有利于流水線的充分利用，有利于多功能部件的充分利用，但由于時鐘周期已接近物理極限，向充分利用，但由于時鐘周期已接近物理極限，向量計算機(jī)的進(jìn)一步發(fā)展已經(jīng)不太可能。量計算機(jī)的進(jìn)一步發(fā)展已經(jīng)不太可能。3. MPP3. MPP（massively parallel processingmassively para

4、llel processing蓬勃發(fā)展階段（蓬勃發(fā)展階段（19901990年至今年至今） 就在傳統(tǒng)向量機(jī)逐漸萎縮的同時，迎來了大就在傳統(tǒng)向量機(jī)逐漸萎縮的同時，迎來了大規(guī)模并行處理規(guī)模并行處理MPPMPP機(jī)蓬勃發(fā)展的時代。各種新技術(shù)層機(jī)蓬勃發(fā)展的時代。各種新技術(shù)層出不窮，大公司也紛紛介入。這一時期的代表機(jī)型出不窮，大公司也紛紛介入。這一時期的代表機(jī)型有：有： 1989 1989年，年，BBNBBN公司的公司的TC2000TC2000 1992 1992年，年，IntelIntel公司的公司的ParagonParagon，TMCTMC公司的公司的CM-5CM-5 1993 1993年，年，Cray

5、Cray公司的公司的T3DT3D 1994 1994年，年，IBMIBM公司的公司的SP2SP2 1996 1996年，年，CrayCray公司的公司的T3ET3E，HitachiHitachi公司的公司的SR2201SR2201，SGISGI公司的公司的Origin2000Origin2000，IntelIntel公司的公司的 ASCE REDASCE RED。其中，。其中，19961996年年1212月宣布的月宣布的ASCI REDASCI RED，運(yùn)，運(yùn)算速度超過了萬億次算速度超過了萬億次/ /秒。秒。銀河銀河-I巨型計算機(jī)巨型計算機(jī) 1983年年12月月銀河銀河-II-II巨型計算機(jī)巨

6、型計算機(jī) 19921992年年1111月月銀河銀河-II-II主機(jī)為我國高性能主機(jī)為我國高性能向量向量中央處理機(jī)中央處理機(jī)共享主存緊耦合系統(tǒng)共享主存緊耦合系統(tǒng)，基本字長，基本字長6464位，峰值位，峰值速度為每秒速度為每秒1010億次以上運(yùn)算操作，擁有兩個億次以上運(yùn)算操作，擁有兩個獨(dú)立的輸入輸出子系統(tǒng)。各項技術(shù)指標(biāo)達(dá)到獨(dú)立的輸入輸出子系統(tǒng)。各項技術(shù)指標(biāo)達(dá)到了八十年代中后期國際先進(jìn)水平。了八十年代中后期國際先進(jìn)水平。銀河銀河-III-III巨型計算機(jī)巨型計算機(jī) 1997 1997年年6 6月月銀河銀河IIIIII采用采用分布共享存儲結(jié)構(gòu)分布共享存儲結(jié)構(gòu)，峰值性能達(dá)，峰值性能達(dá)到每秒到每秒1301

7、30億浮點(diǎn)運(yùn)算。具有良好的可擴(kuò)展性，億浮點(diǎn)運(yùn)算。具有良好的可擴(kuò)展性，銀河銀河IIIIII在在MPPMPP資源管理與處理機(jī)調(diào)度、并行資源管理與處理機(jī)調(diào)度、并行I/OI/O軟件、高性能優(yōu)化編譯、網(wǎng)絡(luò)軟硬件設(shè)計軟件、高性能優(yōu)化編譯、網(wǎng)絡(luò)軟硬件設(shè)計等技術(shù)方面均達(dá)到國內(nèi)領(lǐng)先水平，系統(tǒng)綜合等技術(shù)方面均達(dá)到國內(nèi)領(lǐng)先水平，系統(tǒng)綜合技術(shù)達(dá)到當(dāng)時國際先進(jìn)水平。技術(shù)達(dá)到當(dāng)時國際先進(jìn)水平。 我國超級計算機(jī)的發(fā)展和應(yīng)用 曙光一號曙光一號并行計算機(jī)是并行計算機(jī)是 1993 年我國自行研制的第一臺用微處年我國自行研制的第一臺用微處理器芯片（理器芯片（88100 微處理器）構(gòu)成的全對稱緊耦合共享存儲微處理器）構(gòu)成的全對稱緊耦

8、合共享存儲多處理機(jī)系統(tǒng)（多處理機(jī)系統(tǒng)（SMP），最大支持），最大支持 16 個個 CPU（4 CPU 共享共享存儲為一結(jié)點(diǎn)主板，存儲為一結(jié)點(diǎn)主板，4 個主板通過個主板通過 VME總線連接），系統(tǒng)外總線連接），系統(tǒng)外設(shè)采用設(shè)采用 SCSI 設(shè)備，系統(tǒng)峰值定點(diǎn)速度每秒設(shè)備，系統(tǒng)峰值定點(diǎn)速度每秒 6.4億，主存容量億，主存容量最大最大 768 MB。在對稱式體系結(jié)構(gòu)、操作系統(tǒng)核心代碼并行。在對稱式體系結(jié)構(gòu)、操作系統(tǒng)核心代碼并行化和支持細(xì)粒度并行的多線程技術(shù)等方面實現(xiàn)了一系列的技化和支持細(xì)粒度并行的多線程技術(shù)等方面實現(xiàn)了一系列的技術(shù)突破。硬件的技術(shù)突破包括多處理機(jī)共享內(nèi)部總線協(xié)議設(shè)術(shù)突破。硬件的技術(shù)突

9、破包括多處理機(jī)共享內(nèi)部總線協(xié)議設(shè)計、多機(jī)中斷控制器芯片設(shè)計等；軟件包括計、多機(jī)中斷控制器芯片設(shè)計等；軟件包括 SNIX (Symmetric uNIX) 操作系統(tǒng)采用的細(xì)粒度加鎖以及動態(tài)分配操作系統(tǒng)采用的細(xì)粒度加鎖以及動態(tài)分配 I/O 中斷向量以實現(xiàn)多機(jī)系統(tǒng)對稱式處理的方法；在中斷向量以實現(xiàn)多機(jī)系統(tǒng)對稱式處理的方法；在 UNIX 核心中增加共享資源進(jìn)程以及成群調(diào)度核心中增加共享資源進(jìn)程以及成群調(diào)度 ( Gang Scheduling) 策略，策略， 在用戶空間以庫函數(shù)的方式實現(xiàn)線程在用戶空間以庫函數(shù)的方式實現(xiàn)線程 ( Threads) 概念，概念， 支持中微粒度的并行計算等。支持中微粒度的并行

10、計算等。 “神威神威”巨型計算機(jī)巨型計算機(jī)1999年年8月月“神威神威”計算機(jī)有計算機(jī)有384個個CPU，內(nèi)存總?cè)萘繛?，?nèi)存總?cè)萘繛?8GB，峰值運(yùn)行速度達(dá)，峰值運(yùn)行速度達(dá)到了每秒到了每秒3840億次。億次。國家最高科學(xué)技術(shù)獎國家最高科學(xué)技術(shù)獎2010年年 師昌緒師昌緒 （著名材料科學(xué)家（著名材料科學(xué)家 ）王振義王振義 （血液學(xué)專家（血液學(xué)專家 ）2009年年 谷超豪谷超豪 （著名數(shù)學(xué)家）（著名數(shù)學(xué)家）孫家棟（運(yùn)載火箭與衛(wèi)星技術(shù)專家）孫家棟（運(yùn)載火箭與衛(wèi)星技術(shù)專家）2008年年 王忠誠王忠誠 （神經(jīng)外科專家）（神經(jīng)外科專家）徐光憲（化學(xué)家）徐光憲（化學(xué)家）2007年年 閔恩澤（石油化工催化劑專

11、家）閔恩澤（石油化工催化劑專家）吳征鎰（著名植物學(xué)家）吳征鎰（著名植物學(xué)家）2006年年 李振聲（遺傳學(xué)家，小麥遠(yuǎn)緣雜交的奠基人）李振聲（遺傳學(xué)家，小麥遠(yuǎn)緣雜交的奠基人）2005年年 葉篤正（世界著名氣象學(xué)家），葉篤正（世界著名氣象學(xué)家），吳孟超（世界著名肝臟外科學(xué)家）吳孟超（世界著名肝臟外科學(xué)家）2004年年 空缺空缺2003年年 劉東生（著名地球環(huán)境科學(xué)家）劉東生（著名地球環(huán)境科學(xué)家）王永志（著名航天技術(shù)專家）王永志（著名航天技術(shù)專家）2002年年 金怡濂（高性能計算機(jī)領(lǐng)域的著名專家）金怡濂（高性能計算機(jī)領(lǐng)域的著名專家）2001年年 王選（漢字激光照排系統(tǒng)創(chuàng)始人）王選（漢字激光照排系統(tǒng)創(chuàng)始

12、人）黃昆（著名物理學(xué)家）黃昆（著名物理學(xué)家）2000年年 吳文?。ㄊ澜缰麛?shù)學(xué)家）吳文?。ㄊ澜缰麛?shù)學(xué)家）袁隆平（雜交水稻之父）袁隆平（雜交水稻之父） 2009年年6月月15日，國內(nèi)首臺百萬億次超級計算機(jī)日，國內(nèi)首臺百萬億次超級計算機(jī)“魔方魔方”，在，在上海正式啟用。上海正式啟用?！澳Х侥Х健辈坏莵喼薜谝坏某売嬎銠C(jī)，也是目不但是亞洲第一的超級計算機(jī)，也是目前美國本土之外唯一計算速度排名進(jìn)入全球前十的超級計算機(jī)，前美國本土之外唯一計算速度排名進(jìn)入全球前十的超級計算機(jī)，表明中國成為全球第二個能夠研發(fā)百萬億次超級計算機(jī)的國家。表明中國成為全球第二個能夠研發(fā)百萬億次超級計算機(jī)的國家。 2009年年

13、10月月29日，我國首臺千萬億次超級計算機(jī)系統(tǒng)日，我國首臺千萬億次超級計算機(jī)系統(tǒng)“天天河一號河一號”由國防科學(xué)技術(shù)大學(xué)研制成功。該系統(tǒng)突破了多陣列可由國防科學(xué)技術(shù)大學(xué)研制成功。該系統(tǒng)突破了多陣列可配置協(xié)同并行體系結(jié)構(gòu)、高速率可擴(kuò)展互連通信、高效異構(gòu)協(xié)同配置協(xié)同并行體系結(jié)構(gòu)、高速率可擴(kuò)展互連通信、高效異構(gòu)協(xié)同計算、基于隔離的安全控制、虛擬化的網(wǎng)絡(luò)計算支撐、多層次的計算、基于隔離的安全控制、虛擬化的網(wǎng)絡(luò)計算支撐、多層次的大規(guī)模系統(tǒng)容錯、系統(tǒng)能耗綜合控制等一系列關(guān)鍵技術(shù)，系統(tǒng)峰大規(guī)模系統(tǒng)容錯、系統(tǒng)能耗綜合控制等一系列關(guān)鍵技術(shù)，系統(tǒng)峰值性能達(dá)每秒值性能達(dá)每秒1206萬億次雙精度浮點(diǎn)運(yùn)算，內(nèi)存總?cè)萘咳f億

14、次雙精度浮點(diǎn)運(yùn)算，內(nèi)存總?cè)萘?8TB，點(diǎn)，點(diǎn)點(diǎn)通信帶寬每秒點(diǎn)通信帶寬每秒40Gb，共享磁盤容量為，共享磁盤容量為1PB，具有高性能、高能，具有高性能、高能效、高安全和易使用等顯著特點(diǎn)，綜合技術(shù)水平進(jìn)入世界前列。效、高安全和易使用等顯著特點(diǎn)，綜合技術(shù)水平進(jìn)入世界前列。 “魔方”的誕生將中國的超級計算一下子帶入了百萬億次計算時代，但是應(yīng)用卻仍停留在幾萬億次到幾十萬億次的水平，中間至少相差了一代。因為現(xiàn)在能夠?qū)懘祟愜浖娜瞬盘^稀少，硬件跟軟件的關(guān)系就像“修了一條好路，卻沒有好車”。一、并行處理機(jī)一、并行處理機(jī)1、概念：、概念： 并行處理機(jī)是將重復(fù)設(shè)置的并行處理機(jī)是將重復(fù)設(shè)置的N個處理單元，按一定個

15、處理單元，按一定方式互連組成陣列，在單一控制部件方式互連組成陣列，在單一控制部件CU控制下，同時對控制下，同時對處理單元各自分配到的數(shù)據(jù)并行完成同一條指令所規(guī)定處理單元各自分配到的數(shù)據(jù)并行完成同一條指令所規(guī)定的操作。又叫陣列處理機(jī)，的操作。又叫陣列處理機(jī)， 是典型的指令操作級并行的是典型的指令操作級并行的SIMD計算機(jī)計算機(jī)2、特點(diǎn)：特別適于求解向量、陣列類的計算問題、特點(diǎn)：特別適于求解向量、陣列類的計算問題陣列處理機(jī)陣列處理機(jī)：依靠處理單元的資源重復(fù)設(shè)置，利用的是：依靠處理單元的資源重復(fù)設(shè)置，利用的是并行性中的同時性；實現(xiàn)的是操作級的并行并行性中的同時性；實現(xiàn)的是操作級的并行解題專用性強(qiáng)，靈

16、活性差，處理單元的時間利用率低，解題專用性強(qiáng)，靈活性差，處理單元的時間利用率低，但提高速度的潛力大但提高速度的潛力大向量流水處理機(jī)向量流水處理機(jī)：依靠的是在系統(tǒng)同一套資源中各個處：依靠的是在系統(tǒng)同一套資源中各個處理機(jī)、部件、子部件在時間上的重疊使用，利用的是并理機(jī)、部件、子部件在時間上的重疊使用，利用的是并行性中的并發(fā)性行性中的并發(fā)性解題通用性強(qiáng)，靈活性好，流水線各部件的時間利用率解題通用性強(qiáng)，靈活性好，流水線各部件的時間利用率高，提高速度受到限制。高，提高速度受到限制。3、實質(zhì)：異構(gòu)型的多處理機(jī)系統(tǒng)、實質(zhì)：異構(gòu)型的多處理機(jī)系統(tǒng)專門進(jìn)行向量專門進(jìn)行向量/數(shù)組運(yùn)算的處理單元陣列數(shù)組運(yùn)算的處理單元

17、陣列專門進(jìn)行標(biāo)量運(yùn)算和處理的控制處理機(jī)專門進(jìn)行標(biāo)量運(yùn)算和處理的控制處理機(jī)CU專門進(jìn)行輸入輸出和運(yùn)行操作系統(tǒng)的管理處理機(jī)專門進(jìn)行輸入輸出和運(yùn)行操作系統(tǒng)的管理處理機(jī)SC互連網(wǎng)絡(luò)特別重要，它規(guī)定了處理單元的連接模式，決定互連網(wǎng)絡(luò)特別重要，它規(guī)定了處理單元的連接模式，決定了了SIMD能適應(yīng)的算法類別能適應(yīng)的算法類別4、并行處理機(jī)的構(gòu)形、并行處理機(jī)的構(gòu)形PEM0PEM1PEMN-1PE0PE1PEN-1ICNI/O接口接口DCUCUMSC分布式存儲器的并行處理機(jī)構(gòu)形分布式存儲器的并行處理機(jī)構(gòu)形:各處理單元的局部存儲器只能被本處各處理單元的局部存儲器只能被本處理單元直接訪問；理單元直接訪問；在在CU中有存

18、放程序和數(shù)據(jù)的主存儲器；中有存放程序和數(shù)據(jù)的主存儲器；ILLIAC 、MPP、DAP、CM-2、MP-14、并行處理機(jī)的構(gòu)形、并行處理機(jī)的構(gòu)形MM0MM1PEMN-1PE0PE1PEN-1ICNCUSC集中式共享存儲器的并集中式共享存儲器的并行處理機(jī)構(gòu)形行處理機(jī)構(gòu)形:系統(tǒng)存儲器由系統(tǒng)存儲器由N個存儲個存儲體集中組成，經(jīng)互連網(wǎng)體集中組成，經(jīng)互連網(wǎng)絡(luò)絡(luò)ICN為全部為全部N個處理單個處理單元所共享元所共享BSPI/O-CHI/OSM5、處理單元陣列結(jié)構(gòu)（、處理單元陣列結(jié)構(gòu)（以以ILLIAC 為例為例 ）PU1PU57PU0PU56PU7PU63PU8PU8PU9PU15PU56PU57PU63PU1

19、6PU0PU63PU7PU55PU0PU1PU7任意兩個處理單元之間的最短距離不會超過任意兩個處理單元之間的最短距離不會超過N-1步步閉合螺旋陣列閉合螺旋陣列閉合螺旋陣列閉合螺旋陣列PU1PU0PU3PU2PU4PU5PU7PU6PU12PU13PU15PU14PU8PU9PU10PU116、SIMD計算機(jī)的互連網(wǎng)絡(luò)計算機(jī)的互連網(wǎng)絡(luò)SIMD互連網(wǎng)絡(luò)的互連網(wǎng)絡(luò)的設(shè)計目標(biāo)設(shè)計目標(biāo)：結(jié)構(gòu)要簡單，以降低成本；結(jié)構(gòu)要簡單，以降低成本；連接要靈活，以滿足算法和應(yīng)用的需要；連接要靈活，以滿足算法和應(yīng)用的需要；中轉(zhuǎn)傳送的步數(shù)要少，以提高陣列運(yùn)算速度；中轉(zhuǎn)傳送的步數(shù)要少，以提高陣列運(yùn)算速度；規(guī)整性、模塊性要好，

20、以便可以采用基本構(gòu)件來組合，增規(guī)整性、模塊性要好，以便可以采用基本構(gòu)件來組合，增強(qiáng)系統(tǒng)的可擴(kuò)充性，也便于大規(guī)模集成。強(qiáng)系統(tǒng)的可擴(kuò)充性，也便于大規(guī)模集成?；ミB網(wǎng)絡(luò)的連接規(guī)律可以用互連函數(shù)來表示，它反映了所互連網(wǎng)絡(luò)的連接規(guī)律可以用互連函數(shù)來表示，它反映了所有有N個入端同時存在的入端個入端同時存在的入端j連至出端連至出端f（j）的函數(shù)關(guān)系。）的函數(shù)關(guān)系。XYZ000001101100111011010110N個節(jié)點(diǎn)的立方體單級網(wǎng)個節(jié)點(diǎn)的立方體單級網(wǎng)絡(luò)共有絡(luò)共有n = log 2 N 種互連種互連函數(shù)，函數(shù)，Cube i (P n-1P i P 1P 0 )= P n-1P i P 1P 0 最大距離

21、：最大距離：n，即反復(fù)使，即反復(fù)使用單級網(wǎng)絡(luò)，最多經(jīng)過用單級網(wǎng)絡(luò)，最多經(jīng)過n次傳送就可以實現(xiàn)任意一次傳送就可以實現(xiàn)任意一對入、出端間的連接。對入、出端間的連接。(1)、立方體單級網(wǎng)絡(luò)、立方體單級網(wǎng)絡(luò)基本的單級互連網(wǎng)絡(luò)基本的單級互連網(wǎng)絡(luò)(2)、PM2I單級網(wǎng)絡(luò)單級網(wǎng)絡(luò)PM2I單級網(wǎng)絡(luò)是單級網(wǎng)絡(luò)是“加減加減2 i”（Plus Minus 2 i ）單級）單級網(wǎng)絡(luò)的簡稱。能實現(xiàn)與網(wǎng)絡(luò)的簡稱。能實現(xiàn)與 j 號處理單元直接相連的是號號處理單元直接相連的是號為為 j 2 i 的處理單元。即：的處理單元。即：PM2 +i ( j ) = j + 2 i mod NPM2 -i ( j ) = j - 2 i

22、 mod N式中，式中，0 j N-1， 0 I n-1，n = log 2 N實際上實際上PM2I互連網(wǎng)絡(luò)只有互連網(wǎng)絡(luò)只有2n-1種不同的互連函數(shù)。種不同的互連函數(shù)。最大距離：最大距離：n / 2102435670213456702134567PM2 2PM2 +1PM2 +0(3)、混洗交換單級網(wǎng)絡(luò)、混洗交換單級網(wǎng)絡(luò)0213456702134567000001010011100101110111000001010011100101110111混洗交換單級網(wǎng)絡(luò)混洗交換單級網(wǎng)絡(luò)(Shuffle-Exchange)的連接規(guī)的連接規(guī)律是把全部按編碼順序排列的處理單元從當(dāng)中律是把全部按編碼順序排列的

23、處理單元從當(dāng)中分為數(shù)目相等的兩半，前一半和后一半在連至分為數(shù)目相等的兩半，前一半和后一半在連至出端時正好一一隔開。出端時正好一一隔開。Shuffle(P n-1P i P 1P 0 ) = P n-2P 1P 0 P n-1特性：不可逆；特性：不可逆； 每全混一次，新的最高位就被移至最低每全混一次，新的最高位就被移至最低位；當(dāng)經(jīng)過位；當(dāng)經(jīng)過 n 次全排列后，全部次全排列后，全部N各處理單元各處理單元便又恢復(fù)到最初的排列順序。在多次全混的過便又恢復(fù)到最初的排列順序。在多次全混的過程中，除了編號為全程中，除了編號為全“0”和全和全“1”的處理單元的處理單元外，各個處理單元都遇到了與其他多個處理單外

24、，各個處理單元都遇到了與其他多個處理單元連接的機(jī)會。元連接的機(jī)會。02134567全混交換單級網(wǎng)絡(luò)全混交換單級網(wǎng)絡(luò)在全混的基礎(chǔ)上再增加在全混的基礎(chǔ)上再增加Cube 0交換交換函數(shù)。函數(shù)。在全混交換單級網(wǎng)絡(luò)中，最遠(yuǎn)的兩個入、出端號是全在全混交換單級網(wǎng)絡(luò)中，最遠(yuǎn)的兩個入、出端號是全“0”和和“1”，它們的連接需要，它們的連接需要 n 次交換和次交換和 n-1 次混洗，所以最次混洗，所以最大距離為大距離為2n-1。單級網(wǎng)絡(luò)單級網(wǎng)絡(luò)只有有限的幾種連接，因而在陣列機(jī)中必須經(jīng)過只有有限的幾種連接，因而在陣列機(jī)中必須經(jīng)過多次循環(huán)，才能實現(xiàn)任意兩個處理單元之間的信息傳送。多次循環(huán)，才能實現(xiàn)任意兩個處理單元之間

25、的信息傳送。多級網(wǎng)絡(luò)多級網(wǎng)絡(luò)則是由多個單級網(wǎng)絡(luò)組合而成，以實現(xiàn)任意兩個則是由多個單級網(wǎng)絡(luò)組合而成，以實現(xiàn)任意兩個處理單元之間的連接。處理單元之間的連接。不同的多級網(wǎng)絡(luò)表現(xiàn)在不同的多級網(wǎng)絡(luò)表現(xiàn)在交換開關(guān)的功能交換開關(guān)的功能、拓?fù)浣Y(jié)構(gòu)拓?fù)浣Y(jié)構(gòu)和所用和所用的的開關(guān)控制方式開關(guān)控制方式上的不同。上的不同。交換開關(guān)交換開關(guān)：具有兩個入端和兩個出端的交換單元，用作各種多級互連：具有兩個入端和兩個出端的交換單元，用作各種多級互連網(wǎng)絡(luò)的基本構(gòu)件。網(wǎng)絡(luò)的基本構(gòu)件。拓?fù)浣Y(jié)構(gòu)：拓?fù)浣Y(jié)構(gòu)：指的是各級交換開關(guān)之間的連接模式，可以有立方體、混指的是各級交換開關(guān)之間的連接模式，可以有立方體、混洗、洗、PM2I或它們的組合或

26、它們的組合控制方式：控制方式：指的是對各個交換開關(guān)進(jìn)行轉(zhuǎn)切控制的方式。常分為三種：指的是對各個交換開關(guān)進(jìn)行轉(zhuǎn)切控制的方式。常分為三種：級控制、單元控制、部分級控制；級控制、單元控制、部分級控制；多級互連網(wǎng)絡(luò)多級互連網(wǎng)絡(luò)交換開關(guān)只有直連和交換兩種功能的稱為二功能交換交換開關(guān)只有直連和交換兩種功能的稱為二功能交換單元單元;交換開關(guān)可以有直連、交換、上播和下播等四種功能交換開關(guān)可以有直連、交換、上播和下播等四種功能的稱為四功能交換單元的稱為四功能交換單元;i入入j入入i出出j出出直連直連i 入連入連 i 出出, j 入連入連 j 出出交換交換i 入連入連 j 出出, j 入連入連 i 出出上播上播i

27、 入連入連i 出和出和 j 出出, j 入空入空下播下播j 入連入連i 出和出和 j 出出, i 入空入空多級立方體網(wǎng)絡(luò)多級立方體網(wǎng)絡(luò)ABCDEFGHIJKL01234567012345670213465702134657041526370123456704152637STARAN網(wǎng)絡(luò)網(wǎng)絡(luò)：第第 i 級交換單元級交換單元處于交換狀態(tài)時，處于交換狀態(tài)時，實現(xiàn)的是實現(xiàn)的是Cube i 互連函數(shù)，且都互連函數(shù)，且都采用二功能交換采用二功能交換單元，和級控制單元，和級控制方式。方式。0級級1級級2級級0級級1級級2級級3級級0123456789ABCDEF98AB54671023DCEF6453012

28、7ECDB89AF08192A3B4C5D6E7F0123674589EFABCDN=16n =log2N=4每一級每一級N/2個個二功能交換二功能交換開關(guān)開關(guān)級控制信號（級控制信號（K3K2K1K0）101011001011輸輸入入端端0 (0000)1 (0001)2 (0010)3 (0011)4 (0100)5 (0101)6 (0110)7 (0111)8 (1000)9 (1001)A (1010)B (1011)C (1100)D (1101)E (1110)F (1111)AB89EF (1111)C (1100)D (1101)2 (0010)3 (0011)0 (0000)

29、1 (0001)674 (0100)55 (0101)B (1011)A (1010)9 (1001)8 (1000)F (1111)E (1110)D (1101)C (1100)321076544組組4元元3210，7654，BA98，F(xiàn)EDC;2組組8元元45670123，CDEF89AB;1組組16元元BA98FEDC32107654ABCDEFGHIJKL01234567024613570123456701234567omega網(wǎng)絡(luò)：網(wǎng)絡(luò)：由由n級相同的網(wǎng)級相同的網(wǎng)絡(luò)組成，每一級絡(luò)組成，每一級都包含一個全混都包含一個全混拓?fù)浜碗S后一列拓?fù)浜碗S后一列2 n-1個四功能交個四功能交換單元，采用單換單元，采用單元控制方式。元控制方式。0級級1級級2級級多級混洗交換網(wǎng)絡(luò)多級混洗交換網(wǎng)絡(luò) omega網(wǎng)絡(luò)網(wǎng)絡(luò)0415263701230A00A01A02A031A10A11A12A132A20A21A22A233A30A31A32A33012340A00A01A02A031A13A10A11A122A21A22A23A203A30A31A3