《并行算法第一章并行計算性能測評課件》由會員分享，可在線閱讀，更多相關(guān)《并行算法第一章并行計算性能測評課件（118頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、南京林業(yè)大學(xué)南京林業(yè)大學(xué)南京林業(yè)大學(xué)南京林業(yè)大學(xué)-信息學(xué)院信息學(xué)院信息學(xué)院信息學(xué)院并行算法南京林業(yè)大學(xué)-信息學(xué)院2任課教師：章春芳任課教師：章春芳辦公室：辦公室：0250E-mail：2任課教師：章春芳3教材、參考書 教材教材教材教材并行計算并行計算并行計算并行計算-結(jié)構(gòu)結(jié)構(gòu)結(jié)構(gòu)結(jié)構(gòu) 算法算法算法算法 編程編程編程編程 陳國良陳國良陳國良陳國良 高等教育出版社高等教育出版社高等教育出版社高等教育出版社并行算法實踐并行算法實踐并行算法實踐并行算法實踐 陳國良陳國良陳國良陳國良 高等教育出版社高等教育出版社高等教育出版社高等教育出版社 參考書參考書參考書參考書并行處理技術(shù)并行處理技術(shù)并行處理技術(shù)并

2、行處理技術(shù) 張德富張德富張德富張德富 南京大學(xué)南京大學(xué)南京大學(xué)南京大學(xué)出版社出版社出版社出版社面向結(jié)構(gòu)的并行算法設(shè)計與分析面向結(jié)構(gòu)的并行算法設(shè)計與分析面向結(jié)構(gòu)的并行算法設(shè)計與分析面向結(jié)構(gòu)的并行算法設(shè)計與分析 李曉梅李曉梅李曉梅李曉梅 國防科技大學(xué)國防科技大學(xué)國防科技大學(xué)國防科技大學(xué)出版社出版社出版社出版社3教材、參考書 教材主要內(nèi)容 并行處理概論并行處理概論并行處理概論并行處理概論 1 1 并行計算性能測評并行計算性能測評并行計算性能測評并行計算性能測評 2 2 并行算法的一般設(shè)計方法并行算法的一般設(shè)計方法并行算法的一般設(shè)計方法并行算法的一般設(shè)計方法 4 4 并行算法的基本設(shè)計技術(shù)并行算法的基

3、本設(shè)計技術(shù)并行算法的基本設(shè)計技術(shù)并行算法的基本設(shè)計技術(shù) 5 5 非數(shù)值并行算法非數(shù)值并行算法非數(shù)值并行算法非數(shù)值并行算法 6 6 圖論圖論圖論圖論 7 7 矩陣運算矩陣運算矩陣運算矩陣運算 8 8 并行算法的設(shè)計基礎(chǔ)并行算法的設(shè)計基礎(chǔ)并行算法的設(shè)計基礎(chǔ)并行算法的設(shè)計基礎(chǔ) 3 3 并行程序設(shè)計基礎(chǔ)并行程序設(shè)計基礎(chǔ)并行程序設(shè)計基礎(chǔ)并行程序設(shè)計基礎(chǔ) 9 9主要內(nèi)容 并行處理概論 1 并行計算性5第一章并行計算機系統(tǒng)及結(jié)構(gòu)模型1.1 并行計算概論并行計算概論1.2 并行計算機系統(tǒng)互并行計算機系統(tǒng)互連連1.3 并行計算機系統(tǒng)結(jié)并行計算機系統(tǒng)結(jié)構(gòu)構(gòu)5第一章并行計算機系統(tǒng)及結(jié)構(gòu)模型1.1 并行計算概論1.2

4、 1.1 并行計算概論并行處理的定義并行處理的定義并行處理的定義并行處理的定義 并行性的含義并行性的含義并行性的含義并行性的含義并行處理的應(yīng)用并行處理的應(yīng)用并行處理的應(yīng)用并行處理的應(yīng)用并行處理中的幾個難題并行處理中的幾個難題并行處理中的幾個難題并行處理中的幾個難題61.1 并行計算概論并行處理的定義 671.1.1并行處理的含義發(fā)展背景：發(fā)展背景：發(fā)展背景：發(fā)展背景：僅提高電子部件的速度來改善計算機僅提高電子部件的速度來改善計算機僅提高電子部件的速度來改善計算機僅提高電子部件的速度來改善計算機的性能以滿足用戶越來越高的要求是不可能的。的性能以滿足用戶越來越高的要求是不可能的。的性能以滿足用戶越

5、來越高的要求是不可能的。的性能以滿足用戶越來越高的要求是不可能的。計算科學(xué)：計算科學(xué)：計算科學(xué)：計算科學(xué)：計算物理、計算化學(xué)、計算生物等。計算物理、計算化學(xué)、計算生物等。計算物理、計算化學(xué)、計算生物等。計算物理、計算化學(xué)、計算生物等。并行處理：并行處理：并行處理：并行處理：一種有效的強調(diào)開發(fā)計算過程中并行一種有效的強調(diào)開發(fā)計算過程中并行一種有效的強調(diào)開發(fā)計算過程中并行一種有效的強調(diào)開發(fā)計算過程中并行事件的信息處理方式。事件的信息處理方式。事件的信息處理方式。事件的信息處理方式。并行計算：并行計算：并行計算：并行計算：并行機上的計算，又稱高性能計算并行機上的計算，又稱高性能計算并行機上的計算，又

6、稱高性能計算并行機上的計算，又稱高性能計算（HPC)HPC)。并行計算機：并行計算機：并行計算機：并行計算機：為并行處理所設(shè)計的計算機系統(tǒng)。為并行處理所設(shè)計的計算機系統(tǒng)。為并行處理所設(shè)計的計算機系統(tǒng)。為并行處理所設(shè)計的計算機系統(tǒng)。71.1.1并行處理的含義發(fā)展背景：僅提高電子部件的速度來改8并行性的含義同時性：同時性：同時性：同時性：兩個或多個事件在兩個或多個事件在兩個或多個事件在兩個或多個事件在同一時刻同一時刻同一時刻同一時刻發(fā)生在多個發(fā)生在多個發(fā)生在多個發(fā)生在多個資源中資源中資源中資源中并發(fā)性：并發(fā)性：并發(fā)性：并發(fā)性：兩個或多個事件在兩個或多個事件在兩個或多個事件在兩個或多個事件在同一時間

7、間隔內(nèi)同一時間間隔內(nèi)同一時間間隔內(nèi)同一時間間隔內(nèi)發(fā)生發(fā)生發(fā)生發(fā)生在多個資源中在多個資源中在多個資源中在多個資源中流水線：流水線：流水線：流水線：兩個或多個事件發(fā)生在兩個或多個事件發(fā)生在兩個或多個事件發(fā)生在兩個或多個事件發(fā)生在可能重疊的時間可能重疊的時間可能重疊的時間可能重疊的時間內(nèi)內(nèi)內(nèi)內(nèi)模式：模式：模式：模式：以數(shù)值計算為例計算并行性，有以數(shù)值計算為例計算并行性，有以數(shù)值計算為例計算并行性，有以數(shù)值計算為例計算并行性，有表達模式表達模式表達模式表達模式與與與與遞歸模式遞歸模式遞歸模式遞歸模式8并行性的含義同時性：兩個或多個事件在同一時刻發(fā)生在多個資源9并行性的含義 例如：兩個向量的內(nèi)積：例如：

8、兩個向量的內(nèi)積：例如：兩個向量的內(nèi)積：例如：兩個向量的內(nèi)積：表達式形式：表達式形式：表達式形式：表達式形式：9并行性的含義例如：兩個向量的內(nèi)積：10并行性的含義 并行模式：并行模式：并行模式：并行模式：x x1 1Y Y1 1x x2 2Y Y2 2 X Xn-1n-1Y Yn-1n-1x xn nY Yn n R R10并行性的含義并行模式：x1Y1x2Y2Xn-1Yn-111并行性的含義 遞歸模式：遞歸模式：遞歸模式：遞歸模式：流水線模式：流水線模式：流水線模式：流水線模式：*+11并行性的含義遞歸模式：*+121.1.2 并行處理的應(yīng)用高速并行計算主要有三種類型的應(yīng)用需求：高速并行計算主

9、要有三種類型的應(yīng)用需求：高速并行計算主要有三種類型的應(yīng)用需求：高速并行計算主要有三種類型的應(yīng)用需求：121.1.2 并行處理的應(yīng)用高速并行計算主要有三種類型的應(yīng)13并行處理的應(yīng)用主要應(yīng)用領(lǐng)域：主要應(yīng)用領(lǐng)域：主要應(yīng)用領(lǐng)域：主要應(yīng)用領(lǐng)域：氣象、海洋、天體物理氣象、海洋、天體物理氣象、海洋、天體物理氣象、海洋、天體物理 遙測地球資源數(shù)據(jù)處理遙測地球資源數(shù)據(jù)處理遙測地球資源數(shù)據(jù)處理遙測地球資源數(shù)據(jù)處理 石油開采及管理石油開采及管理石油開采及管理石油開采及管理 磁聚變及核反應(yīng)堆磁聚變及核反應(yīng)堆磁聚變及核反應(yīng)堆磁聚變及核反應(yīng)堆 生物及醫(yī)學(xué)生物及醫(yī)學(xué)生物及醫(yī)學(xué)生物及醫(yī)學(xué) 工程計算工程計算工程計算工程計算 社

10、會經(jīng)濟學(xué)及政府部門社會經(jīng)濟學(xué)及政府部門社會經(jīng)濟學(xué)及政府部門社會經(jīng)濟學(xué)及政府部門 國防國防國防國防 13并行處理的應(yīng)用主要應(yīng)用領(lǐng)域：14氣象數(shù)值預(yù)報 將地球由北至南分成將地球由北至南分成將地球由北至南分成將地球由北至南分成2 2度一格，延赤道分成度一格，延赤道分成度一格，延赤道分成度一格，延赤道分成4 4度一格，度一格，度一格，度一格，將大氣層分成將大氣層分成將大氣層分成將大氣層分成2020層，形成一個三維網(wǎng)格。設(shè)每個網(wǎng)格層，形成一個三維網(wǎng)格。設(shè)每個網(wǎng)格層，形成一個三維網(wǎng)格。設(shè)每個網(wǎng)格層，形成一個三維網(wǎng)格。設(shè)每個網(wǎng)格上計算量約為上計算量約為上計算量約為上計算量約為30003000次，若時間步長為

11、次，若時間步長為次，若時間步長為次，若時間步長為2 2分鐘，則當給分鐘，則當給分鐘，則當給分鐘，則當給出出出出一天的氣象預(yù)報一天的氣象預(yù)報一天的氣象預(yù)報一天的氣象預(yù)報時，總計算量為時，總計算量為時，總計算量為時，總計算量為3.5103.5101111次。次。次。次。在在在在Gray1Gray1（GrayGray公司的向量流水機）上進行計算（每公司的向量流水機）上進行計算（每公司的向量流水機）上進行計算（每公司的向量流水機）上進行計算（每秒秒秒秒1 1億次浮點運算，需計算億次浮點運算，需計算億次浮點運算，需計算億次浮點運算，需計算1 1小時小時小時小時左右，若左右，若左右，若左右，若將網(wǎng)格邊長將

12、網(wǎng)格邊長將網(wǎng)格邊長將網(wǎng)格邊長減半減半減半減半，是，是，是，是原來計算量的原來計算量的原來計算量的原來計算量的8 8倍倍倍倍。14氣象數(shù)值預(yù)報將地球由北至南分成2度一格，延赤道分成4度一15海洋學(xué)、天體物理 以以以以1 1。為為為為間間間間隔隔隔隔的的的的類類類類似似似似網(wǎng)網(wǎng)網(wǎng)網(wǎng)格格格格，用用用用Gyber-205Gyber-205（美美美美國國國國數(shù)數(shù)數(shù)數(shù)據(jù)據(jù)據(jù)據(jù)控控控控制制制制公公公公司司司司CDCCDC，19821982，5252位位位位4 4億億億億次次次次每每每每秒秒秒秒，400mflops400mflops的的的的流水線機）對太平洋流水線機）對太平洋流水線機）對太平洋流水線機）對太平

13、洋5050年作一次完整模擬要年作一次完整模擬要年作一次完整模擬要年作一次完整模擬要10001000小時小時小時小時。模模模模擬擬擬擬地地地地球球球球等等等等行行行行星星星星的的的的形形形形成成成成過過過過程程程程，其其其其動動動動態(tài)態(tài)態(tài)態(tài)范范范范圍圍圍圍從從從從毫毫毫毫秒秒秒秒到到到到幾幾幾幾十十十十億億億億，ILLIAC-VILLIAC-V陣陣陣陣 列列列列 處處處處 理理理理 機機機機（美美美美 國國國國 Illinios Illinios uinv,1973,64uinv,1973,64個個個個PEPE主主主主存存存存1313萬萬萬萬字字字字，1.51.5億億億億次次次次每每每每秒秒秒秒

14、的的的的陣陣陣陣列列列列機）曾用于這一方面的研究。機）曾用于這一方面的研究。機）曾用于這一方面的研究。機）曾用于這一方面的研究。15海洋學(xué)、天體物理以1。為間隔的類似網(wǎng)格，用Gyber-216遙測地球資源數(shù)據(jù)處理 大大大大量量量量衛(wèi)衛(wèi)衛(wèi)衛(wèi)星星星星圖圖圖圖像像像像資資資資料料料料處處處處理理理理。陸陸陸陸地地地地探探探探測測測測衛(wèi)衛(wèi)衛(wèi)衛(wèi)星星星星的的的的一一一一張張張張圖圖圖圖像像像像有有有有3 3千千千千萬萬萬萬個個個個字字字字符符符符，覆覆覆覆蓋蓋蓋蓋美美美美國國國國AlabamaAlabama州州州州需需需需要要要要1313幅幅幅幅這這這這樣樣樣樣的的的的圖圖圖圖像像像像，每每每每1515天

15、天天天產(chǎn)產(chǎn)產(chǎn)產(chǎn)生生生生一一一一次次次次新新新新的的的的圖圖圖圖像像像像，計計計計算算算算量量量量很很很很大大大大。美美美美國國國國宇宇宇宇航航航航 局局局局 訂訂訂訂 購購購購 了了了了 并并并并 行行行行 處處處處 理理理理 機機機機 MPPMPP（美美美美 國國國國 Goodyear Goodyear AerospaceAerospace，19791979，128128PES128128PES），最最最最高高高高速速速速度度度度每每每每秒秒秒秒6060億次億次億次億次8 8位整數(shù)運算位整數(shù)運算位整數(shù)運算位整數(shù)運算，能提供實時的情景分析。，能提供實時的情景分析。，能提供實時的情景分析。，能提

16、供實時的情景分析。16遙測地球資源數(shù)據(jù)處理大量衛(wèi)星圖像資料處理。陸地探測衛(wèi)星的17石油開采及管理地震探測地震探測地震探測地震探測 19851985年年年年，我我我我國國國國南南南南海海海海西西西西部部部部石石石石油油油油公公公公司司司司向向向向美美美美國國國國訂訂訂訂購購購購PE3230MPSPE3230MPS并并并并行行行行處處處處理理理理計計計計算算算算機機機機。地地地地震震震震數(shù)數(shù)數(shù)數(shù)據(jù)據(jù)據(jù)據(jù)處處處處理理理理費費費費用用用用占占占占地地地地震震震震探探探探測測測測總總總總費費費費用用用用的的的的10%10%，地地地地震震震震數(shù)數(shù)數(shù)數(shù)據(jù)據(jù)據(jù)據(jù)相相相相當當當當多多多多，僅僅僅僅1979197

17、9年年年年就就就就有有有有10101515位位位位地地地地震震震震數(shù)數(shù)數(shù)數(shù)據(jù)據(jù)據(jù)據(jù)處處處處理理理理。美美美美國國國國休休休休斯斯斯斯頓頓頓頓一一一一家家家家地地地地球球球球物物物物理理理理公公公公司司司司存存存存儲儲儲儲的的的的地地地地球球球球地地地地震震震震數(shù)數(shù)數(shù)數(shù)據(jù)據(jù)據(jù)據(jù)有有有有200200萬個磁帶卷萬個磁帶卷萬個磁帶卷萬個磁帶卷。17石油開采及管理地震探測18石油開采及管理儲油層模型的建立儲油層模型的建立儲油層模型的建立儲油層模型的建立 SOHOSOHO公公公公司司司司用用用用Cyber-203Cyber-203（CDCCDC）建建建建立立立立波波波波羅羅羅羅的的的的海海海海灣灣灣灣油油

18、油油田田田田數(shù)數(shù)數(shù)數(shù)值值值值模模模模擬擬擬擬器器器器，包包包包括括括括10001000個個個個油油油油井井井井，一一一一個個個個需需需需一一一一年年年年模模模模擬擬擬擬實實實實驗驗驗驗的的的的工工工工作作作作量量量量，在在在在Cyber-203Cyber-203僅僅僅僅用用用用3333分鐘分鐘分鐘分鐘即可完成。即可完成。即可完成。即可完成。18石油開采及管理儲油層模型的建立19工程計算 水水水水壩壩壩壩、橋橋橋橋梁梁梁梁、船船船船只只只只、超超超超音音音音速速速速飛飛飛飛機機機機、高高高高層層層層建建建建筑筑筑筑、太太太太空空空空飛飛飛飛行行行行器器器器設(shè)設(shè)設(shè)設(shè)計計計計需需需需解解解解大大大大

19、型型型型偏偏偏偏微微微微分分分分方方方方程程程程組組組組和和和和代代代代數(shù)數(shù)數(shù)數(shù)方方方方程程程程組組組組，可可可可以以以以用用用用并并并并行處理機提高設(shè)計效率行處理機提高設(shè)計效率行處理機提高設(shè)計效率行處理機提高設(shè)計效率。在在在在空空空空氣氣氣氣動動動動力力力力學(xué)學(xué)學(xué)學(xué)計計計計算算算算中中中中美美美美國國國國航航航航天天天天局局局局AmesAmes研研研研究究究究中中中中心心心心用用用用超超超超級級級級計算機作風(fēng)洞實驗三級模擬計算機作風(fēng)洞實驗三級模擬計算機作風(fēng)洞實驗三級模擬計算機作風(fēng)洞實驗三級模擬。由由由由BurroughsBurroughs公公公公司司司司及及及及CDCCDC公公公公司司司司推

20、推推推出出出出“數(shù)數(shù)數(shù)數(shù)值值值值航航航航空空空空動動動動力力力力學(xué)學(xué)學(xué)學(xué)模模模模擬擬擬擬設(shè)設(shè)設(shè)設(shè)備備備備“（NAFSNAFS）的的的的兩兩兩兩臺臺臺臺1010億億億億次次次次超超超超級級級級計計計計算算算算機機機機可可可可以以以以模模模模擬完整的飛機設(shè)計。擬完整的飛機設(shè)計。擬完整的飛機設(shè)計。擬完整的飛機設(shè)計。19工程計算水壩、橋梁、船只、超音速飛機、高層建筑、太空飛行20社會經(jīng)濟學(xué)及政府部門 計計計計量量量量經(jīng)經(jīng)經(jīng)經(jīng)濟濟濟濟學(xué)學(xué)學(xué)學(xué)、社社社社會會會會工工工工程程程程、政政政政府府府府人人人人口口口口普普普普查查查查、犯犯犯犯罪罪罪罪控控控控制制制制20002000年世界經(jīng)濟模型構(gòu)造等計算的計算

21、量大，需并行計算。年世界經(jīng)濟模型構(gòu)造等計算的計算量大，需并行計算。年世界經(jīng)濟模型構(gòu)造等計算的計算量大，需并行計算。年世界經(jīng)濟模型構(gòu)造等計算的計算量大，需并行計算。諾諾諾諾貝貝貝貝爾爾爾爾獎獎獎獎學(xué)學(xué)學(xué)學(xué)金金金金獲獲獲獲得得得得者者者者W.W.Leontief W.W.Leontief 19801980年年年年提提提提出出出出一一一一個個個個世世世世界界界界經(jīng)經(jīng)經(jīng)經(jīng)濟濟濟濟輸輸輸輸入入入入/輸輸輸輸出出出出模模模模型型型型，在在在在CDCCDC科科科科學(xué)學(xué)學(xué)學(xué)計計計計算算算算機機機機上上上上運運運運算算算算，認認認認為為為為一一一一個個個個以以以以部部部部分分分分裁裁裁裁軍軍軍軍為為為為特特特特

22、征征征征的的的的國國國國際際際際性性性性經(jīng)經(jīng)經(jīng)經(jīng)濟濟濟濟關(guān)關(guān)關(guān)關(guān)系系系系系系系系統(tǒng)統(tǒng)統(tǒng)統(tǒng)，可可可可以以以以縮小貧富國家的差距，該項目受到聯(lián)合國支持?？s小貧富國家的差距，該項目受到聯(lián)合國支持?？s小貧富國家的差距，該項目受到聯(lián)合國支持。縮小貧富國家的差距，該項目受到聯(lián)合國支持。美美美美國國國國使使使使用用用用大大大大型型型型計計計計算算算算機機機機控控控控制制制制犯犯犯犯罪罪罪罪、收收收收稅稅稅稅與與與與審審審審計計計計，進進進進行行行行人人人人口口口口普普普普查查查查及及及及民民民民意意意意測測測測驗驗驗驗。過過過過去去去去美美美美國國國國制制制制造造造造的的的的大大大大型型型型計計計計算算算算

23、機機機機57%57%由由由由政政政政府使用。府使用。府使用。府使用。20社會經(jīng)濟學(xué)及政府部門計量經(jīng)濟學(xué)、社會工程、政府人口普查、21國防、人工智能、基礎(chǔ)研究國防國防國防國防軍軍軍軍事事事事部部部部門門門門使使使使用用用用現(xiàn)現(xiàn)現(xiàn)現(xiàn)存存存存的的的的大大大大部部部部分分分分超超超超級級級級計計計計算算算算機機機機，如如如如Cray-1Cray-1多用于彈頭核武器設(shè)計。多用于彈頭核武器設(shè)計。多用于彈頭核武器設(shè)計。多用于彈頭核武器設(shè)計。在在在在關(guān)關(guān)關(guān)關(guān)聯(lián)聯(lián)聯(lián)聯(lián)處處處處理理理理機機機機上上上上為為為為反反反反彈彈彈彈道道道道導(dǎo)導(dǎo)導(dǎo)導(dǎo)彈彈彈彈程程程程序序序序處處處處理理理理雷雷雷雷達達達達信信信信號號號號，

24、用用用用S-1S-1多處理機做反潛艇海洋監(jiān)視。多處理機做反潛艇海洋監(jiān)視。多處理機做反潛艇海洋監(jiān)視。多處理機做反潛艇海洋監(jiān)視。21國防、人工智能、基礎(chǔ)研究國防22國防、人工智能、基礎(chǔ)研究人工智能人工智能人工智能人工智能 圖像處理圖像處理圖像處理圖像處理 模式識別模式識別模式識別模式識別 計算機視覺計算機視覺計算機視覺計算機視覺 自然語言理解自然語言理解自然語言理解自然語言理解 機器推理機器推理機器推理機器推理 智能機器人智能機器人智能機器人智能機器人 專家系統(tǒng)專家系統(tǒng)專家系統(tǒng)專家系統(tǒng) 知識工程知識工程知識工程知識工程基礎(chǔ)研究基礎(chǔ)研究基礎(chǔ)研究基礎(chǔ)研究 計算化學(xué)計算化學(xué)計算化學(xué)計算化學(xué) 計算物理計算

25、物理計算物理計算物理 計算幾何計算幾何計算幾何計算幾何 VLSIVLSI輔助設(shè)計輔助設(shè)計輔助設(shè)計輔助設(shè)計22國防、人工智能、基礎(chǔ)研究人工智能23當代科學(xué)與工程問題的計算需求評測計算機性能的指標評測計算機性能的指標評測計算機性能的指標評測計算機性能的指標7070年代年代年代年代Mflops 10Mflops 106 6 百萬百萬百萬百萬現(xiàn)在現(xiàn)在現(xiàn)在現(xiàn)在Pflops 10Pflops 101515 千萬億次千萬億次千萬億次千萬億次9090年代年代年代年代Tflops 10Tflops 101212 萬億萬億萬億萬億8080年代年代年代年代Gflops 10Gflops 109 9 十億十億十億十億

26、世界上第一臺峰值速度世界上第一臺峰值速度超過超過1Tflops1Tflops的高性能計的高性能計算機是由算機是由IntelIntel公司于公司于19961996年年1212月研制成功的。月研制成功的。23當代科學(xué)與工程問題的計算需求評測計算機性能的指標70年代24當代科學(xué)與工程問題的計算需求美美美美 國國國國 HPCCHPCC計計計計 劃劃劃劃（High High Performance Performance Computing&CommunicationComputing&Communication）為為為為了了了了保保保保持持持持美美美美國國國國的的的的世世世世界界界界領(lǐng)領(lǐng)領(lǐng)領(lǐng)先先先先地

27、地地地位位位位，19931993年年年年，美美美美國國國國科科科科學(xué)學(xué)學(xué)學(xué)、工工工工程程程程、技技技技術(shù)術(shù)術(shù)術(shù)聯(lián)聯(lián)聯(lián)聯(lián)邦邦邦邦協(xié)協(xié)協(xié)協(xié)調(diào)調(diào)調(diào)調(diào)理理理理事事事事會會會會的的的的國國國國會會會會提提提提出出出出了了了了題題題題為為為為“重重重重大大大大挑挑挑挑戰(zhàn)戰(zhàn)戰(zhàn)戰(zhàn)項項項項目目目目：高高高高性性性性能能能能計計計計算算算算與與與與通通通通信信信信”的報告，簡稱的報告，簡稱的報告，簡稱的報告，簡稱HPCCHPCC計劃計劃計劃計劃3T3T性能目標性能目標性能目標性能目標 TflopsTflops計算能力、計算能力、計算能力、計算能力、1TB1TB主存容量、主存容量、主存容量、主存容量、1TB/s1T

28、B/s的的的的I/OI/O帶寬帶寬帶寬帶寬24當代科學(xué)與工程問題的計算需求美國HPCC計劃（High 25HPCC應(yīng)用領(lǐng)域高速民航高速民航高速民航高速民航用計算流體動力學(xué)來研制超音速噴氣發(fā)動機用計算流體動力學(xué)來研制超音速噴氣發(fā)動機用計算流體動力學(xué)來研制超音速噴氣發(fā)動機用計算流體動力學(xué)來研制超音速噴氣發(fā)動機新藥設(shè)計新藥設(shè)計新藥設(shè)計新藥設(shè)計研制癌癥和艾滋病的藥物研制癌癥和艾滋病的藥物研制癌癥和艾滋病的藥物研制癌癥和艾滋病的藥物催化作用催化作用催化作用催化作用仿生催化劑計算機建模，分析合成過程中酶的作用仿生催化劑計算機建模，分析合成過程中酶的作用仿生催化劑計算機建模，分析合成過程中酶的作用仿生催化劑

29、計算機建模，分析合成過程中酶的作用燃料燃燒燃料燃燒燃料燃燒燃料燃燒通過化學(xué)動力學(xué)，揭示流體力學(xué)的作用，設(shè)計新型發(fā)動通過化學(xué)動力學(xué)，揭示流體力學(xué)的作用，設(shè)計新型發(fā)動通過化學(xué)動力學(xué)，揭示流體力學(xué)的作用，設(shè)計新型發(fā)動通過化學(xué)動力學(xué)，揭示流體力學(xué)的作用，設(shè)計新型發(fā)動機機機機海洋建模海洋建模海洋建模海洋建模對海洋活動與大氣流的熱交換進行整體海洋模擬對海洋活動與大氣流的熱交換進行整體海洋模擬對海洋活動與大氣流的熱交換進行整體海洋模擬對海洋活動與大氣流的熱交換進行整體海洋模擬大氣污染大氣污染大氣污染大氣污染對大氣質(zhì)量模型進行模擬研究，揭示其物理和化學(xué)機理對大氣質(zhì)量模型進行模擬研究，揭示其物理和化學(xué)機理對大氣

30、質(zhì)量模型進行模擬研究，揭示其物理和化學(xué)機理對大氣質(zhì)量模型進行模擬研究，揭示其物理和化學(xué)機理蛋白質(zhì)結(jié)構(gòu)設(shè)計蛋白質(zhì)結(jié)構(gòu)設(shè)計蛋白質(zhì)結(jié)構(gòu)設(shè)計蛋白質(zhì)結(jié)構(gòu)設(shè)計使用計算機模擬，對蛋白質(zhì)組成的三維結(jié)構(gòu)進行研究使用計算機模擬，對蛋白質(zhì)組成的三維結(jié)構(gòu)進行研究使用計算機模擬，對蛋白質(zhì)組成的三維結(jié)構(gòu)進行研究使用計算機模擬，對蛋白質(zhì)組成的三維結(jié)構(gòu)進行研究圖像理解圖像理解圖像理解圖像理解實時繪制圖像或動畫實時繪制圖像或動畫實時繪制圖像或動畫實時繪制圖像或動畫密碼破譯密碼破譯密碼破譯密碼破譯破譯由長位數(shù)組成的密碼，求找該數(shù)的兩個乘積因子破譯由長位數(shù)組成的密碼，求找該數(shù)的兩個乘積因子破譯由長位數(shù)組成的密碼，求找該數(shù)的兩個乘積

31、因子破譯由長位數(shù)組成的密碼，求找該數(shù)的兩個乘積因子19941994年年4 4月月2626日，美國宣日，美國宣布破譯了世界上最長的布破譯了世界上最長的RSA129RSA129密碼，在因特網(wǎng)上密碼，在因特網(wǎng)上使用使用16001600臺計算機，臺計算機，600600多人工作多人工作8 8個月個月，破譯了，破譯了129129位數(shù)字組成的密碼位數(shù)字組成的密碼25HPCC應(yīng)用領(lǐng)域高速民航用計算流體動力學(xué)來研制超音速噴氣26科學(xué)計算的需要26科學(xué)計算的需要27當代科學(xué)與工程問題的計算需求美美美美 國國國國 ASCIASCI計計計計 劃劃劃劃（Accelerated Accelerated Strategic

32、 Strategic Computing InitiativeComputing Initiative）全全全全面面面面禁禁禁禁止止止止核核核核實實實實驗驗驗驗條條條條約約約約簽簽簽簽訂訂訂訂后后后后，19961996年年年年6 6月月月月能能能能源源源源部部部部聯(lián)聯(lián)聯(lián)聯(lián)合合合合美美美美國國國國三三三三大大大大武武武武器器器器實實實實驗驗驗驗室室室室共共共共同同同同提提提提出出出出了了了了“加加加加速速速速戰(zhàn)戰(zhàn)戰(zhàn)戰(zhàn)略略略略計劃創(chuàng)新計劃創(chuàng)新計劃創(chuàng)新計劃創(chuàng)新”，簡稱為，簡稱為，簡稱為，簡稱為ASCIASCI計劃計劃計劃計劃27當代科學(xué)與工程問題的計算需求美國ASCI計劃（Accel28美國美國AS

33、CI計劃劃 目的目的目的目的 通通通通過過過過數(shù)數(shù)數(shù)數(shù)值值值值模模模模擬擬擬擬，評評評評估估估估核核核核武武武武器器器器的的的的性性性性能能能能、安安安安全全全全性性性性、可可可可靠靠靠靠性性性性等等等等，達達達達到到到到高高高高分分分分辨辨辨辨率率率率、高高高高逼逼逼逼真真真真度度度度、三三三三維維維維、全全全全物物物物理理理理、全全全全系系系系統(tǒng)統(tǒng)統(tǒng)統(tǒng)的的的的規(guī)規(guī)規(guī)規(guī)模模模模和和和和能能能能力力力力，該該該該計計計計劃劃劃劃被被被被認認認認為為為為是是是是與與與與當當當當年年年年曼曼曼曼哈哈哈哈頓頓頓頓計計計計劃劃劃劃等等等等同同同同的的的的一一一一個個個個巨巨巨巨大的挑戰(zhàn)。大的挑戰(zhàn)。大的

34、挑戰(zhàn)。大的挑戰(zhàn)。平臺平臺平臺平臺 三三三三 大大大大 核核核核 武武武武 器器器器 實實實實 驗驗驗驗 室室室室 向向向向 三三三三 大大大大 公公公公 司司司司（IntelIntel，IBMIBM和和和和SGI/CraySGI/Cray）預(yù)預(yù)預(yù)預(yù)訂訂訂訂了了了了峰峰峰峰值值值值超超超超過過過過1Tflops1Tflops的的的的并并并并行行行行計計計計算算算算機機機機，預(yù)預(yù)預(yù)預(yù)計計計計20032003年年年年使使使使用用用用運運運運算算算算100Tflops100Tflops，50TB50TB存存存存儲儲儲儲容容容容量量量量，I/OI/O傳傳傳傳輸輸輸輸速率為速率為速率為速率為5000GB/

35、s5000GB/s的并行機的并行機的并行機的并行機28美國ASCI計劃29并行處理中的幾個難題任務(wù)分配非常困難任務(wù)分配非常困難任務(wù)分配非常困難任務(wù)分配非常困難 考慮時空復(fù)雜度，還需考慮模塊之間的通信量考慮時空復(fù)雜度，還需考慮模塊之間的通信量考慮時空復(fù)雜度，還需考慮模塊之間的通信量考慮時空復(fù)雜度，還需考慮模塊之間的通信量 很難擺脫串行處理方式的約束很難擺脫串行處理方式的約束很難擺脫串行處理方式的約束很難擺脫串行處理方式的約束 軟件和算法大都是按照串行結(jié)構(gòu)設(shè)計的軟件和算法大都是按照串行結(jié)構(gòu)設(shè)計的軟件和算法大都是按照串行結(jié)構(gòu)設(shè)計的軟件和算法大都是按照串行結(jié)構(gòu)設(shè)計的 現(xiàn)有的算法語言對并行性限制很大現(xiàn)有

36、的算法語言對并行性限制很大現(xiàn)有的算法語言對并行性限制很大現(xiàn)有的算法語言對并行性限制很大 現(xiàn)有語言以現(xiàn)有語言以現(xiàn)有語言以現(xiàn)有語言以Von NeumannVon Neumann方式為基礎(chǔ)，對并行性限方式為基礎(chǔ)，對并行性限方式為基礎(chǔ)，對并行性限方式為基礎(chǔ)，對并行性限 制嚴重：制嚴重：制嚴重：制嚴重：l l 語句執(zhí)行結(jié)果、執(zhí)行順序與前面結(jié)果和狀態(tài)相關(guān)語句執(zhí)行結(jié)果、執(zhí)行順序與前面結(jié)果和狀態(tài)相關(guān)語句執(zhí)行結(jié)果、執(zhí)行順序與前面結(jié)果和狀態(tài)相關(guān)語句執(zhí)行結(jié)果、執(zhí)行順序與前面結(jié)果和狀態(tài)相關(guān)l l 大量賦值語句使得處理器與存儲器頻繁交換信息，大量賦值語句使得處理器與存儲器頻繁交換信息，大量賦值語句使得處理器與存儲器頻繁

37、交換信息，大量賦值語句使得處理器與存儲器頻繁交換信息，降低系統(tǒng)效率降低系統(tǒng)效率降低系統(tǒng)效率降低系統(tǒng)效率29并行處理中的幾個難題任務(wù)分配非常困難30并行處理中的幾個難題Von NeumannVon Neumann模式一直伴隨著并行機模式一直伴隨著并行機模式一直伴隨著并行機模式一直伴隨著并行機 未擺脫以未擺脫以未擺脫以未擺脫以指令流指令流指令流指令流為主導(dǎo)的為主導(dǎo)的為主導(dǎo)的為主導(dǎo)的Von NeumannVon Neumann模式，由于指模式，由于指模式，由于指模式，由于指令相關(guān)及地址空間相關(guān)，使并行受到制約令相關(guān)及地址空間相關(guān)，使并行受到制約令相關(guān)及地址空間相關(guān)，使并行受到制約令相關(guān)及地址空間相關(guān)

38、，使并行受到制約處理機間的通訊開銷使并行處理技術(shù)可能得不償失處理機間的通訊開銷使并行處理技術(shù)可能得不償失處理機間的通訊開銷使并行處理技術(shù)可能得不償失處理機間的通訊開銷使并行處理技術(shù)可能得不償失 并行處理技術(shù)的主要難點在于軟件并行處理技術(shù)的主要難點在于軟件并行處理技術(shù)的主要難點在于軟件并行處理技術(shù)的主要難點在于軟件 串行機中軟件好壞對于工作性能影響串行機中軟件好壞對于工作性能影響串行機中軟件好壞對于工作性能影響串行機中軟件好壞對于工作性能影響2-32-3倍，并行計算倍，并行計算倍，并行計算倍，并行計算機中卻是機中卻是機中卻是機中卻是50-10050-100倍，而且最困難的在于并行編譯程序倍，而且

39、最困難的在于并行編譯程序倍，而且最困難的在于并行編譯程序倍，而且最困難的在于并行編譯程序30并行處理中的幾個難題Von Neumann模式一直伴隨著傳統(tǒng)Von Neumann結(jié)構(gòu)及其存在構(gòu)及其存在問題 存儲程序控制方式存儲程序控制方式存儲程序控制方式存儲程序控制方式31存儲器指令寄存器、計數(shù)器存儲器指令數(shù)據(jù)指令流驅(qū)動傳統(tǒng)Von Neumann結(jié)構(gòu)及其存在問題存儲程序控制方式332研究并行處理應(yīng)考慮的幾個問題算法、體系結(jié)構(gòu)、高級語言三者之間的關(guān)系應(yīng)考慮：算法、體系結(jié)構(gòu)、高級語言三者之間的關(guān)系應(yīng)考慮：算法、體系結(jié)構(gòu)、高級語言三者之間的關(guān)系應(yīng)考慮：算法、體系結(jié)構(gòu)、高級語言三者之間的關(guān)系應(yīng)考慮：對于一

40、些特定的計算機對于一些特定的計算機對于一些特定的計算機對于一些特定的計算機如何設(shè)計軟件如何設(shè)計軟件如何設(shè)計軟件如何設(shè)計軟件 對于一個給定的程序?qū)τ谝粋€給定的程序?qū)τ谝粋€給定的程序?qū)τ谝粋€給定的程序如何使之結(jié)構(gòu)化以便在給定的計算如何使之結(jié)構(gòu)化以便在給定的計算如何使之結(jié)構(gòu)化以便在給定的計算如何使之結(jié)構(gòu)化以便在給定的計算機上處理機上處理機上處理機上處理 對于一個給定的計算機和一組應(yīng)用軟件對于一個給定的計算機和一組應(yīng)用軟件對于一個給定的計算機和一組應(yīng)用軟件對于一個給定的計算機和一組應(yīng)用軟件怎樣設(shè)計語言及怎樣設(shè)計語言及怎樣設(shè)計語言及怎樣設(shè)計語言及編譯系統(tǒng)編譯系統(tǒng)編譯系統(tǒng)編譯系統(tǒng) 對于給定的計算機、語言及

41、編譯系統(tǒng)對于給定的計算機、語言及編譯系統(tǒng)對于給定的計算機、語言及編譯系統(tǒng)對于給定的計算機、語言及編譯系統(tǒng)如何設(shè)計算法與程如何設(shè)計算法與程如何設(shè)計算法與程如何設(shè)計算法與程序序序序32研究并行處理應(yīng)考慮的幾個問題算法、體系結(jié)構(gòu)、高級語言三者33并行處理機系統(tǒng)的優(yōu)點具有很高的性能價格比具有很高的性能價格比具有很高的性能價格比具有很高的性能價格比由于系統(tǒng)的模塊性，使之便于維護由于系統(tǒng)的模塊性，使之便于維護由于系統(tǒng)的模塊性，使之便于維護由于系統(tǒng)的模塊性，使之便于維護具有較高的可靠性具有較高的可靠性具有較高的可靠性具有較高的可靠性具有較高的處理速度具有較高的處理速度具有較高的處理速度具有較高的處理速度結(jié)構(gòu)

42、的靈活性結(jié)構(gòu)的靈活性結(jié)構(gòu)的靈活性結(jié)構(gòu)的靈活性便于便于便于便于VLSIVLSI實現(xiàn)實現(xiàn)實現(xiàn)實現(xiàn)33并行處理機系統(tǒng)的優(yōu)點具有很高的性能價格比341.1.3 并行處理機的分類1 13 34 42 2341.1.3 并行處理機的分類134235Flynn分類法單單單單指令流指令流指令流指令流單單單單數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流SISDSISD單單單單指令流指令流指令流指令流多多多多數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流SIMDSIMD多多多多指令流指令流指令流指令流單單單單數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流MISDMISD（實際不存在）（實際不存在）（實際不存在）（實際不存在）多多多多指令流指令流指令流指令流多多多多數(shù)據(jù)流數(shù)據(jù)流

43、數(shù)據(jù)流數(shù)據(jù)流MIMDMIMD35Flynn分類法單指令流單數(shù)據(jù)流SISD36SISDCUCUPUPUMMMMISISDSDSISISCUCU：控制單元：控制單元：控制單元：控制單元 PUPU：處理單元：處理單元：處理單元：處理單元 MMMM：存儲器：存儲器：存儲器：存儲器 IS IS：指令流：指令流：指令流：指令流 DSDS：數(shù)據(jù)流：數(shù)據(jù)流：數(shù)據(jù)流：數(shù)據(jù)流36SISDCUPUMMISDSISCU：控制單元 PU37SIMDCUCUPUPU1 1ISISPUPU2 2PUPUn n MMMM1 1MMMM2 2MMMMn n DSDS1 1DSDS2 2DSDSn nISIS37SIMDCUPU

44、1ISPU2PUnMM1MM2MMn38MIMDPUPU1 1PUPU2 2PUPUn n MMMM1 1MMMM2 2MMMMn n DSDS1 1DSDS2 2DSDSn nISIS1 1ISIS2 2ISISn nCUCU1 1CUCU2 2CUCUn n ISIS1 1ISIS2 2ISISn n38MIMDPU1PU2PUnMM1MM2MMnDS1D39Handler分類法 19771977年，年，年，年，HandlerHandler根據(jù)計算機系統(tǒng)中流水線和并行度根據(jù)計算機系統(tǒng)中流水線和并行度根據(jù)計算機系統(tǒng)中流水線和并行度根據(jù)計算機系統(tǒng)中流水線和并行度出現(xiàn)的級別，將一臺計算機表示為三

45、對整數(shù)：出現(xiàn)的級別，將一臺計算機表示為三對整數(shù)：出現(xiàn)的級別，將一臺計算機表示為三對整數(shù)：出現(xiàn)的級別，將一臺計算機表示為三對整數(shù)：CPUCPU數(shù)目數(shù)目能執(zhí)行流水線的能執(zhí)行流水線的CPUCPU數(shù)目數(shù)目 CPU CPU所控制的所控制的ALUALU數(shù)目數(shù)目 能執(zhí)行流水線的能執(zhí)行流水線的ALUALU數(shù)目數(shù)目ALUALU或或PEPE中的位數(shù)中的位數(shù)ALUALU或或PEPE中流水線的位數(shù)中流水線的位數(shù)39Handler分類法1977年，Handler根據(jù)計算機40按體系結(jié)構(gòu)分類 同步系統(tǒng)同步系統(tǒng)同步系統(tǒng)同步系統(tǒng) 向量向量向量向量流水機流水機流水機流水機 陣列陣列陣列陣列處理機：（含心動陣列）處理機：（含心動

46、陣列）處理機：（含心動陣列）處理機：（含心動陣列）SIMDSIMD 關(guān)聯(lián)關(guān)聯(lián)關(guān)聯(lián)關(guān)聯(lián)處理機：具有聯(lián)想存儲、按內(nèi)容存取、邏輯操作等處理機：具有聯(lián)想存儲、按內(nèi)容存取、邏輯操作等處理機：具有聯(lián)想存儲、按內(nèi)容存取、邏輯操作等處理機：具有聯(lián)想存儲、按內(nèi)容存取、邏輯操作等 多處理機系統(tǒng)多處理機系統(tǒng)多處理機系統(tǒng)多處理機系統(tǒng)MIMD:MIMD:由獨立執(zhí)行指令的處理器由獨立執(zhí)行指令的處理器由獨立執(zhí)行指令的處理器由獨立執(zhí)行指令的處理器構(gòu)成構(gòu)成構(gòu)成構(gòu)成 分布分布分布分布存儲系統(tǒng)：每個結(jié)點有獨立的存儲單元存儲系統(tǒng)：每個結(jié)點有獨立的存儲單元存儲系統(tǒng)：每個結(jié)點有獨立的存儲單元存儲系統(tǒng)：每個結(jié)點有獨立的存儲單元 共享共享共

47、享共享存儲系統(tǒng)存儲系統(tǒng)存儲系統(tǒng)存儲系統(tǒng) MIMDMIMD變體變體變體變體（MIMD/SIMDMIMD/SIMD混合型）混合型）混合型）混合型）40按體系結(jié)構(gòu)分類同步系統(tǒng)41現(xiàn)代并行機結(jié)構(gòu)分類 SIMDSIMD PVPPVP并行向量處理機并行向量處理機并行向量處理機并行向量處理機 SMPSMP對稱多處理機對稱多處理機對稱多處理機對稱多處理機 MPPMPP大規(guī)模并行處理機大規(guī)模并行處理機大規(guī)模并行處理機大規(guī)模并行處理機 DSMDSM分布式共享存儲多處理機分布式共享存儲多處理機分布式共享存儲多處理機分布式共享存儲多處理機 COWCOW工作站機群工作站機群工作站機群工作站機群Gray C-90Gray

48、 C-90Gray T-90Gray T-90銀河銀河1 1號號41現(xiàn)代并行機結(jié)構(gòu)分類SIMDGray C-9042對稱多處理機SMPIBM R50IBM R50、SGI Power ChakengeSGI Power Chakenge、曙光、曙光、曙光、曙光1 1號號號號使用商用微處理的芯片，由高速總線連向共享使用商用微處理的芯片，由高速總線連向共享使用商用微處理的芯片，由高速總線連向共享使用商用微處理的芯片，由高速總線連向共享存儲器，對稱性存儲器，對稱性存儲器，對稱性存儲器，對稱性共享存儲共享存儲共享存儲共享存儲，PEPE個數(shù)不能太多個數(shù)不能太多個數(shù)不能太多個數(shù)不能太多。系統(tǒng)是系統(tǒng)是系統(tǒng)是

49、系統(tǒng)是對稱對稱對稱對稱的，每個處理器可的，每個處理器可的，每個處理器可的，每個處理器可等同的訪問共享等同的訪問共享等同的訪問共享等同的訪問共享存儲存儲存儲存儲，I/OI/O設(shè)備。設(shè)備。設(shè)備。設(shè)備。42對稱多處理機SMPIBM R50、SGI Power 43大規(guī)模并行處理機MPP 經(jīng)典機型：經(jīng)典機型：經(jīng)典機型：經(jīng)典機型：IBM SP2IBM SP2、Intel ParagonIntel Paragon、Intel Intel TFLOPSTFLOPS、曙光、曙光、曙光、曙光10001000等。等。等。等。特性：特性：特性：特性：節(jié)點為微處理器節(jié)點為微處理器節(jié)點為微處理器節(jié)點為微處理器物理上的物

50、理上的物理上的物理上的分布存儲分布存儲分布存儲分布存儲高帶寬、低延遲的網(wǎng)絡(luò)高帶寬、低延遲的網(wǎng)絡(luò)高帶寬、低延遲的網(wǎng)絡(luò)高帶寬、低延遲的網(wǎng)絡(luò)成百上千個成百上千個成百上千個成百上千個PEPE異步異步異步異步MIMDMIMD，程序由多個進程組成，每個進程有私，程序由多個進程組成，每個進程有私，程序由多個進程組成，每個進程有私，程序由多個進程組成，每個進程有私有空間，進程間采用有空間，進程間采用有空間，進程間采用有空間，進程間采用消息傳遞消息傳遞消息傳遞消息傳遞的方式的方式的方式的方式43大規(guī)模并行處理機MPP經(jīng)典機型：IBM SP2、Inte44分布式共享存儲多處理機DSM經(jīng)典機型：經(jīng)典機型：經(jīng)典機型：

51、經(jīng)典機型：Cray T3DCray T3D、SGI/Gray Origin 2000SGI/Gray Origin 2000特點：特點：特點：特點：分布在各個節(jié)點上的局存形成了一個共享的存儲器分布在各個節(jié)點上的局存形成了一個共享的存儲器分布在各個節(jié)點上的局存形成了一個共享的存儲器分布在各個節(jié)點上的局存形成了一個共享的存儲器與與與與SIMDSIMD相相相相同同同同，在在在在物物物物理理理理上上上上有有有有分分分分布布布布在在在在各各各各點點點點的的的的共共共共享享享享主主主主存存存存，但采用但采用但采用但采用單一地址空間單一地址空間單一地址空間單一地址空間，與，與，與，與MPPMPP相比，相比，

52、相比，相比，易于編程易于編程易于編程易于編程44分布式共享存儲多處理機DSM經(jīng)典機型：Cray T3D、45工作站機群COW 經(jīng)典機型：經(jīng)典機型：經(jīng)典機型：經(jīng)典機型：Berkeley NowBerkeley Now、DigitalDigital、TouclusterToucluster等等等等 特點：特點：特點：特點：每個節(jié)點都是一個工作站、每個節(jié)點都是一個工作站、每個節(jié)點都是一個工作站、每個節(jié)點都是一個工作站、PCPC機或機或機或機或SMPSMP 各節(jié)點各節(jié)點各節(jié)點各節(jié)點由低成本網(wǎng)絡(luò)相連由低成本網(wǎng)絡(luò)相連由低成本網(wǎng)絡(luò)相連由低成本網(wǎng)絡(luò)相連（商品網(wǎng)絡(luò)、以太網(wǎng)、（商品網(wǎng)絡(luò)、以太網(wǎng)、（商品網(wǎng)絡(luò)、以太網(wǎng)

53、、（商品網(wǎng)絡(luò)、以太網(wǎng)、FDDIFDDI等）等）等）等）各節(jié)點有本地磁盤各節(jié)點有本地磁盤各節(jié)點有本地磁盤各節(jié)點有本地磁盤 各節(jié)點有一完整的各節(jié)點有一完整的各節(jié)點有一完整的各節(jié)點有一完整的OSOS（MPPMPP中只有一個微核），整個系統(tǒng)中只有一個微核），整個系統(tǒng)中只有一個微核），整個系統(tǒng)中只有一個微核），整個系統(tǒng)是工作站是工作站是工作站是工作站UnixUnix45工作站機群COW經(jīng)典機型：Berkeley Now、Di461.2 并行計算機系統(tǒng)互連靜態(tài)互連網(wǎng)絡(luò)：靜態(tài)互連網(wǎng)絡(luò)：靜態(tài)互連網(wǎng)絡(luò)：靜態(tài)互連網(wǎng)絡(luò)：處理單元間有著處理單元間有著處理單元間有著處理單元間有著固定連接固定連接固定連接固定連接的一類網(wǎng)

54、絡(luò)，在程序執(zhí)的一類網(wǎng)絡(luò)，在程序執(zhí)的一類網(wǎng)絡(luò)，在程序執(zhí)的一類網(wǎng)絡(luò)，在程序執(zhí)行期間，這種行期間，這種行期間，這種行期間，這種點到點的連接保持不變點到點的連接保持不變點到點的連接保持不變點到點的連接保持不變動態(tài)網(wǎng)絡(luò)：動態(tài)網(wǎng)絡(luò)：動態(tài)網(wǎng)絡(luò)：動態(tài)網(wǎng)絡(luò)：用用用用交換開關(guān)構(gòu)成交換開關(guān)構(gòu)成交換開關(guān)構(gòu)成交換開關(guān)構(gòu)成的，可按應(yīng)用程序的要求的，可按應(yīng)用程序的要求的，可按應(yīng)用程序的要求的，可按應(yīng)用程序的要求動態(tài)地動態(tài)地動態(tài)地動態(tài)地改變連接組成改變連接組成改變連接組成改變連接組成 461.2 并行計算機系統(tǒng)互連靜態(tài)互連網(wǎng)絡(luò)：47靜態(tài)互連網(wǎng)絡(luò)一維線性陣列一維線性陣列一維線性陣列一維線性陣列二維網(wǎng)孔二維網(wǎng)孔二維網(wǎng)孔二維網(wǎng)孔樹

55、形連接樹形連接樹形連接樹形連接超立方網(wǎng)絡(luò)超立方網(wǎng)絡(luò)超立方網(wǎng)絡(luò)超立方網(wǎng)絡(luò)立方環(huán)立方環(huán)立方環(huán)立方環(huán)洗牌交換網(wǎng)洗牌交換網(wǎng)洗牌交換網(wǎng)洗牌交換網(wǎng)蝶形網(wǎng)絡(luò)蝶形網(wǎng)絡(luò)蝶形網(wǎng)絡(luò)蝶形網(wǎng)絡(luò) 47靜態(tài)互連網(wǎng)絡(luò)一維線性陣列48動態(tài)連接總線總線總線總線交叉開關(guān)交叉開關(guān)交叉開關(guān)交叉開關(guān)多級互連網(wǎng)絡(luò)多級互連網(wǎng)絡(luò)多級互連網(wǎng)絡(luò)多級互連網(wǎng)絡(luò)48動態(tài)連接總線49網(wǎng)絡(luò)性能指標網(wǎng)絡(luò)網(wǎng)絡(luò)網(wǎng)絡(luò)網(wǎng)絡(luò)直徑直徑直徑直徑對剖對剖對剖對剖寬度寬度寬度寬度49網(wǎng)絡(luò)性能指標網(wǎng)絡(luò)直徑對剖寬度50網(wǎng)絡(luò)性能指標 節(jié)節(jié)節(jié)節(jié)點點點點：用用用用圖圖圖圖表表表表示示示示網(wǎng)網(wǎng)網(wǎng)網(wǎng)絡(luò)絡(luò)絡(luò)絡(luò)，則則則則處處處處理理理理機機機機或或或或存存存存儲儲儲儲器器器器為為為為節(jié)節(jié)節(jié)節(jié)點

56、點點點，連連連連接接接接為邊為邊為邊為邊 節(jié)節(jié)節(jié)節(jié)點點點點度度度度（Node Node DegreeDegree）：射射射射入入入入或或或或射射射射出出出出一一一一個個個個節(jié)節(jié)節(jié)節(jié)點點點點的的的的邊邊邊邊數(shù)數(shù)數(shù)數(shù)。在單向網(wǎng)絡(luò)中，射入和射出邊之和稱為節(jié)點度在單向網(wǎng)絡(luò)中，射入和射出邊之和稱為節(jié)點度在單向網(wǎng)絡(luò)中，射入和射出邊之和稱為節(jié)點度在單向網(wǎng)絡(luò)中，射入和射出邊之和稱為節(jié)點度 網(wǎng)網(wǎng)網(wǎng)網(wǎng)絡(luò)絡(luò)絡(luò)絡(luò)直直直直徑徑徑徑（Network Network DiameterDiameter）：網(wǎng)網(wǎng)網(wǎng)網(wǎng)絡(luò)絡(luò)絡(luò)絡(luò)中中中中任任任任何何何何兩兩兩兩個個個個節(jié)節(jié)節(jié)節(jié)點之間的點之間的點之間的點之間的最長距離最長距離最長距離最

57、長距離，即最大路徑數(shù)，即最大路徑數(shù)，即最大路徑數(shù)，即最大路徑數(shù) 對對對對剖剖剖剖寬寬寬寬度度度度（Bisection Bisection WidthWidth）：將將將將網(wǎng)網(wǎng)網(wǎng)網(wǎng)絡(luò)絡(luò)絡(luò)絡(luò)分分分分成成成成兩兩兩兩部部部部分分分分必必必必須移去的最少邊數(shù)須移去的最少邊數(shù)須移去的最少邊數(shù)須移去的最少邊數(shù) 如如如如果果果果從從從從任任任任一一一一節(jié)節(jié)節(jié)節(jié)點點點點觀觀觀觀看看看看網(wǎng)網(wǎng)網(wǎng)網(wǎng)絡(luò)絡(luò)絡(luò)絡(luò)都都都都一一一一樣樣樣樣，則則則則稱稱稱稱網(wǎng)網(wǎng)網(wǎng)網(wǎng)絡(luò)絡(luò)絡(luò)絡(luò)為為為為對對對對稱稱稱稱的的的的（SymmetrySymmetry）50網(wǎng)絡(luò)性能指標節(jié)點：用圖表示網(wǎng)絡(luò)，則處理機或存儲器為節(jié)點，51靜態(tài)互連網(wǎng)絡(luò)（1）一維

58、線性陣列（一維線性陣列（一維線性陣列（一維線性陣列（1-1-D Linear ArrayD Linear Array）：）：）：）：并行機中最簡單、最基本的互連方式并行機中最簡單、最基本的互連方式并行機中最簡單、最基本的互連方式并行機中最簡單、最基本的互連方式每個節(jié)點每個節(jié)點每個節(jié)點每個節(jié)點只與其左、右近鄰只與其左、右近鄰只與其左、右近鄰只與其左、右近鄰相連，也叫二近相連，也叫二近相連，也叫二近相連，也叫二近鄰連接鄰連接鄰連接鄰連接節(jié)點度為節(jié)點度為節(jié)點度為節(jié)點度為直徑為直徑為直徑為直徑為對剖寬度為對剖寬度為對剖寬度為對剖寬度為2 21 1N-1N-151靜態(tài)互連網(wǎng)絡(luò)（1）一維線性陣列（1-D

59、Linear A52一一維線性性陣列列線性連接函數(shù)：線性連接函數(shù)：線性連接函數(shù)：線性連接函數(shù)：52一維線性陣列線性連接函數(shù)：53一維線性陣列 當首、尾節(jié)點相連時可構(gòu)成循環(huán)移位器，在拓撲結(jié)當首、尾節(jié)點相連時可構(gòu)成循環(huán)移位器，在拓撲結(jié)當首、尾節(jié)點相連時可構(gòu)成循環(huán)移位器，在拓撲結(jié)當首、尾節(jié)點相連時可構(gòu)成循環(huán)移位器，在拓撲結(jié)構(gòu)上等同于環(huán)，環(huán)可以是構(gòu)上等同于環(huán)，環(huán)可以是構(gòu)上等同于環(huán)，環(huán)可以是構(gòu)上等同于環(huán)，環(huán)可以是雙向的雙向的雙向的雙向的或或或或單向的單向的單向的單向的互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)節(jié)點度節(jié)點度節(jié)點度節(jié)點度直徑直徑直徑直徑對剖寬度對剖寬度對剖寬度對剖寬度單向環(huán)單向環(huán)單向環(huán)單向環(huán)雙向環(huán)雙向

60、環(huán)雙向環(huán)雙向環(huán)2 22 22 2N-1N-12 2雙向環(huán)雙向環(huán)單向環(huán)單向環(huán)53一維線性陣列當首、尾節(jié)點相連時可構(gòu)成循環(huán)移位器，在拓撲結(jié)54二二維網(wǎng)孔網(wǎng)孔四近鄰連接：四近鄰連接：四近鄰連接：四近鄰連接：每個節(jié)點只與其每個節(jié)點只與其每個節(jié)點只與其每個節(jié)點只與其上、下、左、右上、下、左、右上、下、左、右上、下、左、右的近的近的近的近鄰相連鄰相連鄰相連鄰相連54二維網(wǎng)孔四近鄰連接：每個節(jié)點只與其上、下、左、右的近鄰相55二二維網(wǎng)孔網(wǎng)孔IlliacIlliac網(wǎng)孔：網(wǎng)孔：網(wǎng)孔：網(wǎng)孔：簡記為簡記為簡記為簡記為MCMC2 2，在在在在垂直方向上帶環(huán)垂直方向上帶環(huán)垂直方向上帶環(huán)垂直方向上帶環(huán)繞繞繞繞，水平方向

61、呈蛇狀水平方向呈蛇狀水平方向呈蛇狀水平方向呈蛇狀55二維網(wǎng)孔Illiac網(wǎng)孔：簡記為MC2，在垂直方向上帶環(huán)56二二維網(wǎng)孔網(wǎng)孔2-2-D D環(huán)繞：環(huán)繞：環(huán)繞：環(huán)繞：垂直和水平方向垂直和水平方向垂直和水平方向垂直和水平方向均帶環(huán)繞均帶環(huán)繞均帶環(huán)繞均帶環(huán)繞56二維網(wǎng)孔2-D環(huán)繞：垂直和水平方向均帶環(huán)繞57二二維網(wǎng)孔網(wǎng)孔4 4互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)節(jié)點度節(jié)點度節(jié)點度節(jié)點度直徑直徑直徑直徑對剖寬度對剖寬度對剖寬度對剖寬度四近鄰連接四近鄰連接四近鄰連接四近鄰連接IlliacIlliac網(wǎng)孔網(wǎng)孔2-2-D D環(huán)繞環(huán)繞4 44 457二維網(wǎng)孔4互連網(wǎng)絡(luò)節(jié)點度直徑對剖寬度四近鄰連接Illia58網(wǎng)孔

62、連接 網(wǎng)孔中的網(wǎng)孔中的網(wǎng)孔中的網(wǎng)孔中的PEPE節(jié)點編號是按行為主順序，編號為節(jié)點編號是按行為主順序，編號為節(jié)點編號是按行為主順序，編號為節(jié)點編號是按行為主順序，編號為0 0N-1N-1 連接函數(shù)：連接函數(shù)：連接函數(shù)：連接函數(shù)：0 01 12 23 34 45 56 67 78 89 910101111121213131414151558網(wǎng)孔連接網(wǎng)孔中的PE節(jié)點編號是按行為主順序，編號為0N59網(wǎng)孔連接例：例：例：例：n=16n=16時的網(wǎng)孔時的網(wǎng)孔時的網(wǎng)孔時的網(wǎng)孔0 01 12 23 34 45 56 67 78 89 910101111121213131414151559網(wǎng)孔連接例：n=16

63、時的網(wǎng)孔012345678910119-1-57-56-48-47-46-459-1-57-56-48-47-46-45網(wǎng)孔連接 在在在在MCMC2 2上已經(jīng)有許多有效的并行算法，但上已經(jīng)有許多有效的并行算法，但上已經(jīng)有許多有效的并行算法，但上已經(jīng)有許多有效的并行算法，但MCMC2 2通信功能較通信功能較通信功能較通信功能較差，在最壞情況下，任意兩個差，在最壞情況下，任意兩個差，在最壞情況下，任意兩個差，在最壞情況下，任意兩個PEPE間信息交換至少要間信息交換至少要間信息交換至少要間信息交換至少要 步。步。步。步。如如如如N=64N=64時時時時 P P6363-P-P1010：P P9 9-

64、P-P4545：63-7-8-9-1063-7-8-9-109-1-57-56-48-47-46-45網(wǎng)孔連接在MC2上61樹形連接 二叉樹連接（簡記為二叉樹連接（簡記為二叉樹連接（簡記為二叉樹連接（簡記為TCTC）：）：）：）：P P1 1P P8 8P P2 2P P3 3P P4 4P P5 5P P6 6P P7 7P P9 9P P1010P P1111P P1212P P1313P P1414P P151561樹形連接二叉樹連接（簡記為TC）：P1P8P2P3P4P62樹形連接除了根、葉節(jié)點，每個內(nèi)節(jié)點只與其父節(jié)點除了根、葉節(jié)點，每個內(nèi)節(jié)點只與其父節(jié)點除了根、葉節(jié)點，每個內(nèi)節(jié)點只與

65、其父節(jié)點除了根、葉節(jié)點，每個內(nèi)節(jié)點只與其父節(jié)點和兩個子節(jié)點相連和兩個子節(jié)點相連和兩個子節(jié)點相連和兩個子節(jié)點相連設(shè)二叉樹有設(shè)二叉樹有設(shè)二叉樹有設(shè)二叉樹有d d d d層，層號由根至葉子為層，層號由根至葉子為層，層號由根至葉子為層，層號由根至葉子為1d1d1d1d，則，則，則，則共有共有共有共有 個節(jié)點個節(jié)點個節(jié)點個節(jié)點節(jié)點度為：節(jié)點度為：節(jié)點度為：節(jié)點度為：對剖寬度為：對剖寬度為：對剖寬度為：對剖寬度為：直徑為：直徑為：直徑為：直徑為：2 2 2 2d d d d-1-1-1-13162樹形連接除了根、葉節(jié)點，每個內(nèi)節(jié)點只與其父節(jié)點和兩個子節(jié)樹形連接的典型用法P P1 1P P8 8P P2 2

66、P P3 3P P4 4P P5 5P P6 6P P7 7P P9 9P P1010P P1111P P1212P P1313P P1414P P1515根根根根及及及及葉葉葉葉子子子子節(jié)節(jié)節(jié)節(jié)點點點點具具具具有有有有I/OI/O功功功功能能能能，且且且且葉葉葉葉子子子子節(jié)節(jié)節(jié)節(jié)點點點點執(zhí)執(zhí)執(zhí)執(zhí)行行行行并并并并行行行行計計計計算算算算，內(nèi)節(jié)點內(nèi)節(jié)點內(nèi)節(jié)點內(nèi)節(jié)點負責(zé)負責(zé)負責(zé)負責(zé)節(jié)點間的通信節(jié)點間的通信節(jié)點間的通信節(jié)點間的通信樹樹樹樹型型型型連連連連接接接接的的的的最最最最長長長長通通通通信信信信路路路路徑徑徑徑與與與與樹樹樹樹高高高高相相相相關(guān)關(guān)關(guān)關(guān)，顯顯顯顯然然然然根根根根為為為為通通通通信信信信瓶瓶瓶瓶頸頸頸頸，因因因因此此此此使使使使用用用用X-X-樹樹樹樹，形形形形成成成成樹樹樹樹網(wǎng)網(wǎng)網(wǎng)網(wǎng)連連連連接接接接，可可可可使使使使同同同同級級級級兄兄兄兄弟弟弟弟之之之之間間間間彼此相連彼此相連彼此相連彼此相連樹形連接的典型用法P1P8P2P3P4P5P6P7P9P1064超立方體連接 一個一個一個一個n-n-立方由立方由立方由立方由 個頂點組成，個頂點組成，個頂點組成，個頂點組成，3-