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

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

2、量向量機(jī)，這是世界上最早的向量機(jī)。隨后于機(jī)。隨后于19741974年，誕生了世界上最早的年，誕生了世界上最早的SIMDSIMD陣陣列計(jì)算機(jī)列計(jì)算機(jī)-ILLIAC-IV-ILLIAC-IV并行機(jī)。并行機(jī)。 2.2.向量機(jī)鼎盛階段（向量機(jī)鼎盛階段（1976-19901976-1990） 19761976年，年，CRAYCRAY公司推出公司推出CRAY-1CRAY-1向量機(jī)，開(kāi)始向量機(jī)，開(kāi)始了向量機(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ī)處理對(duì)提高計(jì)算機(jī)運(yùn)算速度十分有利，向量機(jī)處理對(duì)提高計(jì)算機(jī)運(yùn)算速度十分有利，有利于流水線的充分利用，有利于多功能部件的有利于流水線的充分利用，有利于多功能部件的充分利用，但由于時(shí)鐘周期已接近物理極限，向充分利用，但由于時(shí)鐘周期已接近物理極限，向量計(jì)算機(jī)的進(jìn)一步發(fā)展已經(jīng)不太可能。量計(jì)算機(jī)的進(jìn)一步發(fā)展已經(jīng)不太可能。3. MPP3. MPP（massively parallel processingmassively para

4、llel processing蓬勃發(fā)展階段（蓬勃發(fā)展階段（19901990年至今年至今） 就在傳統(tǒng)向量機(jī)逐漸萎縮的同時(shí)，迎來(lái)了大就在傳統(tǒng)向量機(jī)逐漸萎縮的同時(shí)，迎來(lái)了大規(guī)模并行處理規(guī)模并行處理MPPMPP機(jī)蓬勃發(fā)展的時(shí)代。各種新技術(shù)層機(jī)蓬勃發(fā)展的時(shí)代。各種新技術(shù)層出不窮，大公司也紛紛介入。這一時(shí)期的代表機(jī)型出不窮，大公司也紛紛介入。這一時(shí)期的代表機(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)算速度超過(guò)了萬(wàn)億次算速度超過(guò)了萬(wàn)億次/ /秒。秒。銀河銀河-I巨型計(jì)算機(jī)巨型計(jì)算機(jī) 1983年年12月月銀河銀河-II-II巨型計(jì)算機(jī)巨

6、型計(jì)算機(jī) 19921992年年1111月月銀河銀河-II-II主機(jī)為我國(guó)高性能主機(jī)為我國(guó)高性能向量向量中央處理機(jī)中央處理機(jī)共享主存緊耦合系統(tǒng)共享主存緊耦合系統(tǒng)，基本字長(zhǎng)，基本字長(zhǎng)6464位，峰值位，峰值速度為每秒速度為每秒1010億次以上運(yùn)算操作，擁有兩個(gè)億次以上運(yùn)算操作，擁有兩個(gè)獨(dú)立的輸入輸出子系統(tǒng)。各項(xiàng)技術(shù)指標(biāo)達(dá)到獨(dú)立的輸入輸出子系統(tǒng)。各項(xiàng)技術(shù)指標(biāo)達(dá)到了八十年代中后期國(guó)際先進(jìn)水平。了八十年代中后期國(guó)際先進(jìn)水平。銀河銀河-III-III巨型計(jì)算機(jī)巨型計(jì)算機(jī) 1997 1997年年6 6月月銀河銀河IIIIII采用采用分布共享存儲(chǔ)結(jié)構(gòu)分布共享存儲(chǔ)結(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è)計(jì)軟件、高性能優(yōu)化編譯、網(wǎng)絡(luò)軟硬件設(shè)計(jì)等技術(shù)方面均達(dá)到國(guó)內(nèi)領(lǐng)先水平，系統(tǒng)綜合等技術(shù)方面均達(dá)到國(guó)內(nèi)領(lǐng)先水平，系統(tǒng)綜合技術(shù)達(dá)到當(dāng)時(shí)國(guó)際先進(jìn)水平。技術(shù)達(dá)到當(dāng)時(shí)國(guó)際先進(jìn)水平。 我國(guó)超級(jí)計(jì)算機(jī)的發(fā)展和應(yīng)用 曙光一號(hào)曙光一號(hào)并行計(jì)算機(jī)是并行計(jì)算機(jī)是 1993 年我國(guó)自行研制的第一臺(tái)用微處年我國(guó)自行研制的第一臺(tái)用微處理器芯片（理器芯片（88100 微處理器）構(gòu)成的全對(duì)稱(chēng)緊耦合共享存儲(chǔ)微處理器）構(gòu)成的全對(duì)稱(chēng)緊耦

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

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

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

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

12、人）黃昆（著名物理學(xué)家）黃昆（著名物理學(xué)家）2000年年 吳文?。ㄊ澜缰麛?shù)學(xué)家）吳文俊（世界著名數(shù)學(xué)家）袁隆平（雜交水稻之父）袁隆平（雜交水稻之父） 2009年年6月月15日，國(guó)內(nèi)首臺(tái)百萬(wàn)億次超級(jí)計(jì)算機(jī)日，國(guó)內(nèi)首臺(tái)百萬(wàn)億次超級(jí)計(jì)算機(jī)“魔方魔方”，在，在上海正式啟用。上海正式啟用。“魔方魔方”不但是亞洲第一的超級(jí)計(jì)算機(jī)，也是目不但是亞洲第一的超級(jí)計(jì)算機(jī)，也是目前美國(guó)本土之外唯一計(jì)算速度排名進(jìn)入全球前十的超級(jí)計(jì)算機(jī)，前美國(guó)本土之外唯一計(jì)算速度排名進(jìn)入全球前十的超級(jí)計(jì)算機(jī)，表明中國(guó)成為全球第二個(gè)能夠研發(fā)百萬(wàn)億次超級(jí)計(jì)算機(jī)的國(guó)家。表明中國(guó)成為全球第二個(gè)能夠研發(fā)百萬(wàn)億次超級(jí)計(jì)算機(jī)的國(guó)家。 2009年年

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

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

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

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

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

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

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

20、以便可以采用基本構(gòu)件來(lái)組合，增規(guī)整性、模塊性要好，以便可以采用基本構(gòu)件來(lái)組合，增強(qiáng)系統(tǒng)的可擴(kuò)充性，也便于大規(guī)模集成。強(qiáng)系統(tǒng)的可擴(kuò)充性，也便于大規(guī)模集成?；ミB網(wǎng)絡(luò)的連接規(guī)律可以用互連函數(shù)來(lái)表示，它反映了所互連網(wǎng)絡(luò)的連接規(guī)律可以用互連函數(shù)來(lái)表示，它反映了所有有N個(gè)入端同時(shí)存在的入端個(gè)入端同時(shí)存在的入端j連至出端連至出端f（j）的函數(shù)關(guān)系。）的函數(shù)關(guān)系。XYZ000001101100111011010110N個(gè)節(jié)點(diǎn)的立方體單級(jí)網(wǎng)個(gè)節(jié)點(diǎn)的立方體單級(jí)網(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ù)使用單級(jí)網(wǎng)絡(luò)，最多經(jīng)過(guò)用單級(jí)網(wǎng)絡(luò)，最多經(jīng)過(guò)n次傳送就可以實(shí)現(xiàn)任意一次傳送就可以實(shí)現(xiàn)任意一對(duì)入、出端間的連接。對(duì)入、出端間的連接。(1)、立方體單級(jí)網(wǎng)絡(luò)、立方體單級(jí)網(wǎng)絡(luò)基本的單級(jí)互連網(wǎng)絡(luò)基本的單級(jí)互連網(wǎng)絡(luò)(2)、PM2I單級(jí)網(wǎng)絡(luò)單級(jí)網(wǎng)絡(luò)PM2I單級(jí)網(wǎng)絡(luò)是單級(jí)網(wǎng)絡(luò)是“加減加減2 i”（Plus Minus 2 i ）單級(jí)）單級(jí)網(wǎng)絡(luò)的簡(jiǎn)稱(chēng)。能實(shí)現(xiàn)與網(wǎng)絡(luò)的簡(jiǎn)稱(chēng)。能實(shí)現(xiàn)與 j 號(hào)處理單元直接相連的是號(hào)號(hào)處理單元直接相連的是號(hào)為為 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實(shí)際上實(shí)際上PM2I互連網(wǎng)絡(luò)只有互連網(wǎng)絡(luò)只有2n-1種不同的互連函數(shù)。種不同的互連函數(shù)。最大距離：最大距離：n / 2102435670213456702134567PM2 2PM2 +1PM2 +0(3)、混洗交換單級(jí)網(wǎng)絡(luò)、混洗交換單級(jí)網(wǎng)絡(luò)0213456702134567000001010011100101110111000001010011100101110111混洗交換單級(jí)網(wǎng)絡(luò)混洗交換單級(jí)網(wǎng)絡(luò)(Shuffle-Exchange)的連接規(guī)的連接規(guī)律是把全部按編碼順序排列的處理單元從當(dāng)中律是把全部按編碼順序排列的

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

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

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

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

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

28、7ECDB89AF08192A3B4C5D6E7F0123674589EFABCDN=16n =log2N=4每一級(jí)每一級(jí)N/2個(gè)個(gè)二功能交換二功能交換開(kāi)關(guān)開(kāi)關(guān)級(jí)控制信號(hào)（級(jí)控制信號(hào)（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級(jí)相同的網(wǎng)級(jí)相同的網(wǎng)絡(luò)組成，每一級(jí)絡(luò)組成，每一級(jí)都包含一個(gè)全混都包含一個(gè)全混拓?fù)浜碗S后一列拓?fù)浜碗S后一列2 n-1個(gè)四功能交個(gè)四功能交換單元，采用單換單元，采用單元控制方式。元控制方式。0級(jí)級(jí)1級(jí)級(jí)2級(jí)級(jí)多級(jí)混洗交換網(wǎng)絡(luò)多級(jí)混洗交換網(wǎng)絡(luò) omega網(wǎng)絡(luò)網(wǎng)絡(luò)0415263701230A00A01A02A031A10A11A12A132A20A21A22A233A30A31A32A33012340A00A01A02A031A13A10A11A122A21A22A23A203A30A31A3