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

高性能計(jì)算機(jī)發(fā)展歷程

自1964年以后,高性能計(jì)算機(jī)經(jīng)歷了三個(gè)發(fā)展階段:

萌芽階段、向量機(jī)鼎盛階段和大規(guī)模并行處理機(jī)（MPP）蓬勃發(fā)展階段。

1.萌芽階段（1964-1975）

1964年誕生的CDC6600被公認(rèn)為世界上第一臺(tái)巨型計(jì)算機(jī)，其運(yùn)算速度為1Mflops。70年代初研制成功STAR-100向量機(jī)，這是世界上最早的向量機(jī)。隨后于1974年，誕生了世界上最早的SIMD陣列計(jì)算機(jī)--ILLIAC-IV并行機(jī)。2.向量機(jī)鼎盛階段（1976-1990）

1976年，CRAY公司推出CRAY-1向量機(jī)，開始了向量機(jī)的蓬勃發(fā)展，其峰值速度為0.1Gflops.

1985年，CRAY-2，1Gflops

1990年，SX-3，22Gflops

1991年，Cray-YMP-C90，16Gflops

向量機(jī)處理對(duì)提高計(jì)算機(jī)運(yùn)算速度十分有利，有利于流水線的充分利用，有利于多功能部件的充分利用，但由于時(shí)鐘周期已接近物理極限，向量計(jì)算機(jī)的進(jìn)一步發(fā)展已經(jīng)不太可能。3.MPP（massivelyparallelprocessing

蓬勃發(fā)展階段（1990年至今）

就在傳統(tǒng)向量機(jī)逐漸萎縮的同時(shí)，迎來(lái)了大規(guī)模并行處理MPP機(jī)蓬勃發(fā)展的時(shí)代。各種新技術(shù)層出不窮，大公司也紛紛介入。這一時(shí)期的代表機(jī)型有：

1989年，BBN公司的TC2000

1992年，Intel公司的Paragon，TMC公司的CM-5

1993年，Cray公司的T3D

1994年，IBM公司的SP2

1996年，Cray公司的T3E，Hitachi公司的SR2201，SGI公司的Origin2000，Intel公司的ASCERED。其中，1996年12月宣布的ASCIRED，運(yùn)算速度超過(guò)了萬(wàn)億次/秒。銀河-I巨型計(jì)算機(jī)1983年12月銀河-II巨型計(jì)算機(jī)1992年11月銀河-II主機(jī)為我國(guó)高性能向量中央處理機(jī)共享主存緊耦合系統(tǒng)，基本字長(zhǎng)64位，峰值速度為每秒10億次以上運(yùn)算操作，擁有兩個(gè)獨(dú)立的輸入輸出子系統(tǒng)。各項(xiàng)技術(shù)指標(biāo)達(dá)到了八十年代中后期國(guó)際先進(jìn)水平。銀河-III巨型計(jì)算機(jī)

1997年6月銀河III采用分布共享存儲(chǔ)結(jié)構(gòu)，峰值性能達(dá)到每秒130億浮點(diǎn)運(yùn)算。具有良好的可擴(kuò)展性，銀河III在MPP資源管理與處理機(jī)調(diào)度、并行I/O軟件、高性能優(yōu)化編譯、網(wǎng)絡(luò)軟硬件設(shè)計(jì)等技術(shù)方面均達(dá)到國(guó)內(nèi)領(lǐng)先水平，系統(tǒng)綜合技術(shù)達(dá)到當(dāng)時(shí)國(guó)際先進(jìn)水平。我國(guó)超級(jí)計(jì)算機(jī)的發(fā)展和應(yīng)用

曙光一號(hào)并行計(jì)算機(jī)是1993年我國(guó)自行研制的第一臺(tái)用微處理器芯片（88100微處理器）構(gòu)成的全對(duì)稱緊耦合共享存儲(chǔ)多處理機(jī)系統(tǒng)（SMP），最大支持16個(gè)CPU（4CPU共享存儲(chǔ)為一結(jié)點(diǎn)主板，4個(gè)主板通過(guò)VME總線連接），系統(tǒng)外設(shè)采用SCSI設(shè)備，系統(tǒng)峰值定點(diǎn)速度每秒6.4億，主存容量最大768MB。在對(duì)稱式體系結(jié)構(gòu)、操作系統(tǒng)核心代碼并行化和支持細(xì)粒度并行的多線程技術(shù)等方面實(shí)現(xiàn)了一系列的技術(shù)突破。硬件的技術(shù)突破包括多處理機(jī)共享內(nèi)部總線協(xié)議設(shè)計(jì)、多機(jī)中斷控制器芯片設(shè)計(jì)等；軟件包括SNIX(SymmetricuNIX)操作系統(tǒng)采用的細(xì)粒度加鎖以及動(dòng)態(tài)分配I/O中斷向量以實(shí)現(xiàn)多機(jī)系統(tǒng)對(duì)稱式處理的方法；在UNIX核心中增加共享資源進(jìn)程以及成群調(diào)度(GangScheduling)策略，在用戶空間以庫(kù)函數(shù)的方式實(shí)現(xiàn)線程(Threads)概念，支持中微粒度的并行計(jì)算等?！吧裢本扌陀?jì)算機(jī) 1999年8月“神威”計(jì)算機(jī)有384個(gè)CPU，內(nèi)存總?cè)萘繛?8GB，峰值運(yùn)行速度達(dá)到了每秒3840億次。國(guó)家最高科學(xué)技術(shù)獎(jiǎng)2010年

師昌緒（著名材料科學(xué)家）王振義（血液學(xué)專家）

2009年

谷超豪（著名數(shù)學(xué)家）孫家棟（運(yùn)載火箭與衛(wèi)星技術(shù)專家）

2008年

王忠誠(chéng)（神經(jīng)外科專家）徐光憲（化學(xué)家）

2007年

閔恩澤（石油化工催化劑專家）吳征鎰（著名植物學(xué)家）

2006年

李振聲（遺傳學(xué)家，小麥遠(yuǎn)緣雜交的奠基人）2005年

葉篤正（世界著名氣象學(xué)家），吳孟超（世界著名肝臟外科學(xué)家）2004年空缺2003年

劉東生（著名地球環(huán)境科學(xué)家）王永志（著名航天技術(shù)專家）

2002年金怡濂（高性能計(jì)算機(jī)領(lǐng)域的著名專家）

2001年王選（漢字激光照排系統(tǒng)創(chuàng)始人）黃昆（著名物理學(xué)家）2000年吳文俊（世界著名數(shù)學(xué)家）袁隆平（雜交水稻之父）

2009年6月15日，國(guó)內(nèi)首臺(tái)百萬(wàn)億次超級(jí)計(jì)算機(jī)“魔方”，在上海正式啟用?！澳Х健辈坏莵喼薜谝坏某?jí)計(jì)算機(jī)，也是目前美國(guó)本土之外唯一計(jì)算速度排名進(jìn)入全球前十的超級(jí)計(jì)算機(jī)，表明中國(guó)成為全球第二個(gè)能夠研發(fā)百萬(wàn)億次超級(jí)計(jì)算機(jī)的國(guó)家。2009年10月29日，我國(guó)首臺(tái)千萬(wàn)億次超級(jí)計(jì)算機(jī)系統(tǒng)——“天河一號(hào)”由國(guó)防科學(xué)技術(shù)大學(xué)研制成功。該系統(tǒng)突破了多陣列可配置協(xié)同并行體系結(jié)構(gòu)、高速率可擴(kuò)展互連通信、高效異構(gòu)協(xié)同計(jì)算、基于隔離的安全控制、虛擬化的網(wǎng)絡(luò)計(jì)算支撐、多層次的大規(guī)模系統(tǒng)容錯(cuò)、系統(tǒng)能耗綜合控制等一系列關(guān)鍵技術(shù)，系統(tǒng)峰值性能達(dá)每秒1206萬(wàn)億次雙精度浮點(diǎn)運(yùn)算，內(nèi)存總?cè)萘?8TB，點(diǎn)點(diǎn)通信帶寬每秒40Gb，共享磁盤容量為1PB，具有高性能、高能效、高安全和易使用等顯著特點(diǎn)，綜合技術(shù)水平進(jìn)入世界前列。

“魔方”的誕生將中國(guó)的超級(jí)計(jì)算一下子帶入了百萬(wàn)億次計(jì)算時(shí)代，但是應(yīng)用卻仍停留在幾萬(wàn)億次到幾十萬(wàn)億次的水平，中間至少相差了一代。因?yàn)楝F(xiàn)在能夠?qū)懘祟愜浖娜瞬盘^(guò)稀少，硬件跟軟件的關(guān)系就像“修了一條好路，卻沒(méi)有好車”。一、并行處理機(jī)1、概念：并行處理機(jī)是將重復(fù)設(shè)置的N個(gè)處理單元，按一定方式互連組成陣列，在單一控制部件CU控制下，同時(shí)對(duì)處理單元各自分配到的數(shù)據(jù)并行完成同一條指令所規(guī)定的操作。又叫陣列處理機(jī)，是典型的指令操作級(jí)并行的SIMD計(jì)算機(jī)2、特點(diǎn)：特別適于求解向量、陣列類的計(jì)算問(wèn)題陣列處理機(jī)：依靠處理單元的資源重復(fù)設(shè)置，利用的是并行性中的同時(shí)性；實(shí)現(xiàn)的是操作級(jí)的并行解題專用性強(qiáng)，靈活性差，處理單元的時(shí)間利用率低，但提高速度的潛力大向量流水處理機(jī)：依靠的是在系統(tǒng)同一套資源中各個(gè)處理機(jī)、部件、子部件在時(shí)間上的重疊使用，利用的是并行性中的并發(fā)性解題通用性強(qiáng)，靈活性好，流水線各部件的時(shí)間利用率高，提高速度受到限制。3、實(shí)質(zhì)：異構(gòu)型的多處理機(jī)系統(tǒng)專門進(jìn)行向量/數(shù)組運(yùn)算的處理單元陣列專門進(jìn)行標(biāo)量運(yùn)算和處理的控制處理機(jī)CU專門進(jìn)行輸入輸出和運(yùn)行操作系統(tǒng)的管理處理機(jī)SC互連網(wǎng)絡(luò)特別重要，它規(guī)定了處理單元的連接模式，決定了SIMD能適應(yīng)的算法類別4、并行處理機(jī)的構(gòu)形PEM0PEM1PEMN-1PE0PE1PEN-1ICNI/O接口DCUCUMSC分布式存儲(chǔ)器的并行處理機(jī)構(gòu)形:各處理單元的局部存儲(chǔ)器只能被本處理單元直接訪問(wèn)；在CU中有存放程序和數(shù)據(jù)的主存儲(chǔ)器；ILLIACⅥ、MPP、DAP、CM-2、MP-14、并行處理機(jī)的構(gòu)形MM0MM1PEMN-1PE0PE1PEN-1ICNCUSC集中式共享存儲(chǔ)器的并行處理機(jī)構(gòu)形:系統(tǒng)存儲(chǔ)器由N個(gè)存儲(chǔ)體集中組成，經(jīng)互連網(wǎng)絡(luò)ICN為全部N個(gè)處理單元所共享BSPI/O-CHI/OSM5、處理單元陣列結(jié)構(gòu)（以ILLIAC

Ⅵ為例）PU1PU57PU0PU56PU7PU63PU8PU8PU9PU15PU56PU57PU63PU16PU0PU63PU7PU55PU0PU1PU7任意兩個(gè)處理單元之間的最短距離不會(huì)超過(guò)√N(yùn)-1步閉合螺旋陣列閉合螺旋陣列PU1PU0PU3PU2PU4PU5PU7PU6PU12PU13PU15PU14PU8PU9PU10PU116、SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò)SIMD互連網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)：結(jié)構(gòu)要簡(jiǎn)單，以降低成本；連接要靈活，以滿足算法和應(yīng)用的需要；中轉(zhuǎn)傳送的步數(shù)要少，以提高陣列運(yùn)算速度；規(guī)整性、模塊性要好，以便可以采用基本構(gòu)件來(lái)組合，增強(qiáng)系統(tǒng)的可擴(kuò)充性，也便于大規(guī)模集成?；ミB網(wǎng)絡(luò)的連接規(guī)律可以用互連函數(shù)來(lái)表示，它反映了所有N個(gè)入端同時(shí)存在的入端j連至出端f（j）的函數(shù)關(guān)系。XYZ000001101100111011010110N個(gè)節(jié)點(diǎn)的立方體單級(jí)網(wǎng)絡(luò)共有n=log2N種互連函數(shù)，Cubei(Pn-1…Pi…P1P0)=Pn-1…Pi…P1P0

最大距離：n，即反復(fù)使用單級(jí)網(wǎng)絡(luò)，最多經(jīng)過(guò)n次傳送就可以實(shí)現(xiàn)任意一對(duì)入、出端間的連接。(1)、立方體單級(jí)網(wǎng)絡(luò)基本的單級(jí)互連網(wǎng)絡(luò)(2)、PM2I單級(jí)網(wǎng)絡(luò)PM2I單級(jí)網(wǎng)絡(luò)是“加減2i”（Plus–Minus2i）單級(jí)網(wǎng)絡(luò)的簡(jiǎn)稱。能實(shí)現(xiàn)與j號(hào)處理單元直接相連的是號(hào)為j±2i的處理單元。即：PM2+i(j)=j+2imodNPM2-i(j)=j-2imodN式中，0≤j≤N-1，0≤I≤n-1，n=log2N實(shí)際上PM2I互連網(wǎng)絡(luò)只有2n-1種不同的互連函數(shù)。最大距離：「n/2」102435670213456702134567PM2±2PM2+1PM2+0(3)、混洗交換單級(jí)網(wǎng)絡(luò)0213456702134567000001010011100101110111000001010011100101110111混洗交換單級(jí)網(wǎng)絡(luò)(Shuffle-Exchange)的連接規(guī)律是把全部按編碼順序排列的處理單元從當(dāng)中分為數(shù)目相等的兩半，前一半和后一半在連至出端時(shí)正好一一隔開。Shuffle(Pn-1…Pi…P1P0)=Pn-2…P1P0Pn-1特性：不可逆；每全混一次，新的最高位就被移至最低位；當(dāng)經(jīng)過(guò)n次全排列后，全部N各處理單元便又恢復(fù)到最初的排列順序。在多次全混的過(guò)程中，除了編號(hào)為全“0”和全“1”的處理單元外，各個(gè)處理單元都遇到了與其他多個(gè)處理單元連接的機(jī)會(huì)。02134567全混交換單級(jí)網(wǎng)絡(luò)——在全混的基礎(chǔ)上再增加Cube0交換函數(shù)。在全混交換單級(jí)網(wǎng)絡(luò)中，最遠(yuǎn)的兩個(gè)入、出端號(hào)是全“0”和“1”，它們的連接需要n次交換和n-1次混洗，所以最大距離為2n-1。單級(jí)網(wǎng)絡(luò)只有有限的幾種連接，因而在陣列機(jī)中必須經(jīng)過(guò)多次循環(huán)，才能實(shí)現(xiàn)任意兩個(gè)處理單元之間的信息傳送。多級(jí)網(wǎng)絡(luò)則是由多個(gè)單級(jí)網(wǎng)絡(luò)組合而成，以實(shí)現(xiàn)任意兩個(gè)處理單元之間的連接。不同的多級(jí)網(wǎng)絡(luò)表現(xiàn)在交換開關(guān)的功能、拓?fù)浣Y(jié)構(gòu)和所用的開關(guān)控制方式上的不同。交換開關(guān)：具有兩個(gè)入端和兩個(gè)出端的交換單元，用作各種多級(jí)互連網(wǎng)絡(luò)的基本構(gòu)件。拓?fù)浣Y(jié)構(gòu)：指的是各級(jí)交換開關(guān)之間的連接模式，可以有立方體、混洗、PM2I或它們的組合控制方式：指的是對(duì)各個(gè)交換開關(guān)進(jìn)行轉(zhuǎn)切控制的方式。常分為三種：級(jí)控制、單元控制、部分級(jí)控制；多級(jí)互連網(wǎng)絡(luò)交換開關(guān)只有直連和交換兩種功能的稱為二功能交換單元;交換開關(guān)可以有直連、交換、上播和下播等四種功能的稱為四功能交換單元;i入j入i出j出直連——i入連i出,j入連j出交換——i入連j出,j入連i出上播——i入連i出和j出,j入空下播——j入連i出和j出,i入空多級(jí)立方體網(wǎng)絡(luò)ABCDEFGHIJKL01234567012345670213465702134657041526370123456704152637STARAN網(wǎng)絡(luò)：第i級(jí)交換單元處于交換狀態(tài)時(shí)，實(shí)現(xiàn)的是Cubei互連函數(shù)，且都采用二功能交換單元，和級(jí)控制方式。0級(jí)1級(jí)2級(jí)0級(jí)1級(jí)2級(jí)3級(jí)0123456789ABCDEF98AB54671023DCEF64530127ECDB89AF08192A3B4C5D6E7F0123674589EFABCDN=16n=log2N=4每一級(jí)N/2個(gè)二功能交換開關(guān)級(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)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ò)：由n級(jí)相同的網(wǎng)絡(luò)組成，每一級(jí)都包含一個(gè)全混拓?fù)浜碗S后一列2n-1個(gè)四功能交換單元，采用單元控制方式。0級(jí)1級(jí)2級(jí)多級(jí)混洗交換網(wǎng)絡(luò)omega網(wǎng)絡(luò)0415263701230A00A01A02A031A10A11A12A132A20A21A22A233A30A31A32A33012340A00A01A02A031A13A10A11A122A21A22A23A203A30A31A32A337、并行存儲(chǔ)器的無(wú)沖突訪問(wèn)（以二維數(shù)組為例）要求：對(duì)于二維數(shù)組的行、列、主對(duì)角線、次對(duì)角線都能夠?qū)崿F(xiàn)無(wú)沖突訪問(wèn)。實(shí)現(xiàn)：同一行兩個(gè)相鄰元素在并行存儲(chǔ)器中錯(cuò)開的距離為1；同一列兩個(gè)相鄰元素在并行存儲(chǔ)器中錯(cuò)開的距離為2p；并行存儲(chǔ)體的分體數(shù)m為：22p+1存儲(chǔ)器PE存儲(chǔ)器PEPEPEPEPEPE

脈動(dòng)陣列機(jī)脈動(dòng)結(jié)構(gòu)是由一組處理單元PE構(gòu)成的陣列。每個(gè)PE的內(nèi)部結(jié)構(gòu)相同，功能比較簡(jiǎn)單。陣列內(nèi)所有處理單元的數(shù)據(jù)鎖存器都受同一個(gè)時(shí)鐘控制。運(yùn)算時(shí)，數(shù)據(jù)在陣列結(jié)構(gòu)的各個(gè)處理單元間沿各自的方向，同步地向前推進(jìn)。陣列內(nèi)部的各個(gè)單元只接收前一