第6章并行處理機

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

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

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

1.萌芽階段（1964-1975）

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

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

1985年，CRAY-2，1Gflops

1990年，SX-3，22Gflops

1991年，Cray-YMP-C90，16Gflops

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

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

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

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，運算速度超過了萬億次/秒。銀河-I巨型計算機1983年12月銀河-II巨型計算機1992年11月銀河-II主機為我國高性能向量中央處理機共享主存緊耦合系統(tǒng)，基本字長64位，峰值速度為每秒10億次以上運算操作，擁有兩個獨立的輸入輸出子系統(tǒng)。各項技術(shù)指標達到了八十年代中后期國際先進水平。銀河-III巨型計算機

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

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

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

2009年

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

2008年

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

2007年

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

2006年

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

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

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

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

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

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

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

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

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

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