南京林業(yè)大學(xué)南京林業(yè)大學(xué)南京林業(yè)大學(xué)南京林業(yè)大學(xué)-信息學(xué)院信息學(xué)院信息學(xué)院信息學(xué)院并行算法南京林業(yè)大學(xué)-信息學(xué)院2任課教師：章春芳任課教師：章春芳辦公室：辦公室：0250E-mail：2任課教師：章春芳3教材、參考書 教材教材教材教材并行計(jì)算并行計(jì)算并行計(jì)算并行計(jì)算-結(jié)構(gòu)結(jié)構(gòu)結(jié)構(gòu)結(jié)構(gòu) 算法算法算法算法 編程編程編程編程 陳國(guó)良陳國(guó)良陳國(guó)良陳國(guó)良 高等教育出版社高等教育出版社高等教育出版社高等教育出版社并行算法實(shí)踐并行算法實(shí)踐并行算法實(shí)踐并行算法實(shí)踐 陳國(guó)良陳國(guó)良陳國(guó)良陳國(guó)良 高等教育出版社高等教育出版社高等教育出版社高等教育出版社 參考書參考書參考書參考書并行處理技術(shù)并行處理技術(shù)并行處理技術(shù)并行處理技術(shù) 張德富張德富張德富張德富 南京大學(xué)南京大學(xué)南京大學(xué)南京大學(xué)出版社出版社出版社出版社面向結(jié)構(gòu)的并行算法設(shè)計(jì)與分析面向結(jié)構(gòu)的并行算法設(shè)計(jì)與分析面向結(jié)構(gòu)的并行算法設(shè)計(jì)與分析面向結(jié)構(gòu)的并行算法設(shè)計(jì)與分析 李曉梅李曉梅李曉梅李曉梅 國(guó)防科技大學(xué)國(guó)防科技大學(xué)國(guó)防科技大學(xué)國(guó)防科技大學(xué)出版社出版社出版社出版社3教材、參考書 教材主要內(nèi)容 并行處理概論并行處理概論并行處理概論并行處理概論 1 1 并行計(jì)算性能測(cè)評(píng)并行計(jì)算性能測(cè)評(píng)并行計(jì)算性能測(cè)評(píng)并行計(jì)算性能測(cè)評(píng) 2 2 并行算法的一般設(shè)計(jì)方法并行算法的一般設(shè)計(jì)方法并行算法的一般設(shè)計(jì)方法并行算法的一般設(shè)計(jì)方法 4 4 并行算法的基本設(shè)計(jì)技術(shù)并行算法的基本設(shè)計(jì)技術(shù)并行算法的基本設(shè)計(jì)技術(shù)并行算法的基本設(shè)計(jì)技術(shù) 5 5 非數(shù)值并行算法非數(shù)值并行算法非數(shù)值并行算法非數(shù)值并行算法 6 6 圖論圖論圖論圖論 7 7 矩陣運(yùn)算矩陣運(yùn)算矩陣運(yùn)算矩陣運(yùn)算 8 8 并行算法的設(shè)計(jì)基礎(chǔ)并行算法的設(shè)計(jì)基礎(chǔ)并行算法的設(shè)計(jì)基礎(chǔ)并行算法的設(shè)計(jì)基礎(chǔ) 3 3 并行程序設(shè)計(jì)基礎(chǔ)并行程序設(shè)計(jì)基礎(chǔ)并行程序設(shè)計(jì)基礎(chǔ)并行程序設(shè)計(jì)基礎(chǔ) 9 9主要內(nèi)容 并行處理概論 1 并行計(jì)算性5第一章并行計(jì)算機(jī)系統(tǒng)及結(jié)構(gòu)模型1.1 并行計(jì)算概論并行計(jì)算概論1.2 并行計(jì)算機(jī)系統(tǒng)互并行計(jì)算機(jī)系統(tǒng)互連連1.3 并行計(jì)算機(jī)系統(tǒng)結(jié)并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)構(gòu)5第一章并行計(jì)算機(jī)系統(tǒng)及結(jié)構(gòu)模型1.1 并行計(jì)算概論1.2 1.1 并行計(jì)算概論并行處理的定義并行處理的定義并行處理的定義并行處理的定義 并行性的含義并行性的含義并行性的含義并行性的含義并行處理的應(yīng)用并行處理的應(yīng)用并行處理的應(yīng)用并行處理的應(yīng)用并行處理中的幾個(gè)難題并行處理中的幾個(gè)難題并行處理中的幾個(gè)難題并行處理中的幾個(gè)難題61.1 并行計(jì)算概論并行處理的定義 671.1.1并行處理的含義發(fā)展背景：發(fā)展背景：發(fā)展背景：發(fā)展背景：僅提高電子部件的速度來(lái)改善計(jì)算機(jī)僅提高電子部件的速度來(lái)改善計(jì)算機(jī)僅提高電子部件的速度來(lái)改善計(jì)算機(jī)僅提高電子部件的速度來(lái)改善計(jì)算機(jī)的性能以滿足用戶越來(lái)越高的要求是不可能的。的性能以滿足用戶越來(lái)越高的要求是不可能的。的性能以滿足用戶越來(lái)越高的要求是不可能的。的性能以滿足用戶越來(lái)越高的要求是不可能的。計(jì)算科學(xué)：計(jì)算科學(xué)：計(jì)算科學(xué)：計(jì)算科學(xué)：計(jì)算物理、計(jì)算化學(xué)、計(jì)算生物等。計(jì)算物理、計(jì)算化學(xué)、計(jì)算生物等。計(jì)算物理、計(jì)算化學(xué)、計(jì)算生物等。計(jì)算物理、計(jì)算化學(xué)、計(jì)算生物等。并行處理：并行處理：并行處理：并行處理：一種有效的強(qiáng)調(diào)開發(fā)計(jì)算過(guò)程中并行一種有效的強(qiáng)調(diào)開發(fā)計(jì)算過(guò)程中并行一種有效的強(qiáng)調(diào)開發(fā)計(jì)算過(guò)程中并行一種有效的強(qiáng)調(diào)開發(fā)計(jì)算過(guò)程中并行事件的信息處理方式。事件的信息處理方式。事件的信息處理方式。事件的信息處理方式。并行計(jì)算：并行計(jì)算：并行計(jì)算：并行計(jì)算：并行機(jī)上的計(jì)算，又稱高性能計(jì)算并行機(jī)上的計(jì)算，又稱高性能計(jì)算并行機(jī)上的計(jì)算，又稱高性能計(jì)算并行機(jī)上的計(jì)算，又稱高性能計(jì)算（HPC)HPC)。并行計(jì)算機(jī)：并行計(jì)算機(jī)：并行計(jì)算機(jī)：并行計(jì)算機(jī)：為并行處理所設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)。為并行處理所設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)。為并行處理所設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)。為并行處理所設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)。71.1.1并行處理的含義發(fā)展背景：僅提高電子部件的速度來(lái)改8并行性的含義同時(shí)性：同時(shí)性：同時(shí)性：同時(shí)性：兩個(gè)或多個(gè)事件在兩個(gè)或多個(gè)事件在兩個(gè)或多個(gè)事件在兩個(gè)或多個(gè)事件在同一時(shí)刻同一時(shí)刻同一時(shí)刻同一時(shí)刻發(fā)生在多個(gè)發(fā)生在多個(gè)發(fā)生在多個(gè)發(fā)生在多個(gè)資源中資源中資源中資源中并發(fā)性：并發(fā)性：并發(fā)性：并發(fā)性：兩個(gè)或多個(gè)事件在兩個(gè)或多個(gè)事件在兩個(gè)或多個(gè)事件在兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)同一時(shí)間間隔內(nèi)同一時(shí)間間隔內(nèi)同一時(shí)間間隔內(nèi)發(fā)生發(fā)生發(fā)生發(fā)生在多個(gè)資源中在多個(gè)資源中在多個(gè)資源中在多個(gè)資源中流水線：流水線：流水線：流水線：兩個(gè)或多個(gè)事件發(fā)生在兩個(gè)或多個(gè)事件發(fā)生在兩個(gè)或多個(gè)事件發(fā)生在兩個(gè)或多個(gè)事件發(fā)生在可能重疊的時(shí)間可能重疊的時(shí)間可能重疊的時(shí)間可能重疊的時(shí)間內(nèi)內(nèi)內(nèi)內(nèi)模式：模式：模式：模式：以數(shù)值計(jì)算為例計(jì)算并行性，有以數(shù)值計(jì)算為例計(jì)算并行性，有以數(shù)值計(jì)算為例計(jì)算并行性，有以數(shù)值計(jì)算為例計(jì)算并行性，有表達(dá)模式表達(dá)模式表達(dá)模式表達(dá)模式與與與與遞歸模式遞歸模式遞歸模式遞歸模式8并行性的含義同時(shí)性：兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生在多個(gè)資源9并行性的含義 例如：兩個(gè)向量的內(nèi)積：例如：兩個(gè)向量的內(nèi)積：例如：兩個(gè)向量的內(nèi)積：例如：兩個(gè)向量的內(nèi)積：表達(dá)式形式：表達(dá)式形式：表達(dá)式形式：表達(dá)式形式：9并行性的含義例如：兩個(gè)向量的內(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)用高速并行計(jì)算主要有三種類型的應(yīng)用需求：高速并行計(jì)算主要有三種類型的應(yīng)用需求：高速并行計(jì)算主要有三種類型的應(yīng)用需求：高速并行計(jì)算主要有三種類型的應(yīng)用需求：121.1.2 并行處理的應(yīng)用高速并行計(jì)算主要有三種類型的應(yīng)13并行處理的應(yīng)用主要應(yīng)用領(lǐng)域：主要應(yīng)用領(lǐng)域：主要應(yīng)用領(lǐng)域：主要應(yīng)用領(lǐng)域：氣象、海洋、天體物理氣象、海洋、天體物理氣象、海洋、天體物理氣象、海洋、天體物理 遙測(cè)地球資源數(shù)據(jù)處理遙測(cè)地球資源數(shù)據(jù)處理遙測(cè)地球資源數(shù)據(jù)處理遙測(cè)地球資源數(shù)據(jù)處理 石油開采及管理石油開采及管理石油開采及管理石油開采及管理 磁聚變及核反應(yīng)堆磁聚變及核反應(yīng)堆磁聚變及核反應(yīng)堆磁聚變及核反應(yīng)堆 生物及醫(yī)學(xué)生物及醫(yī)學(xué)生物及醫(yī)學(xué)生物及醫(yī)學(xué) 工程計(jì)算工程計(jì)算工程計(jì)算工程計(jì)算 社會(huì)經(jīng)濟(jì)學(xué)及政府部門社會(huì)經(jīng)濟(jì)學(xué)及政府部門社會(huì)經(jīng)濟(jì)學(xué)及政府部門社會(huì)經(jīng)濟(jì)學(xué)及政府部門 國(guó)防國(guó)防國(guó)防國(guó)防 13并行處理的應(yīng)用主要應(yīng)用領(lǐng)域：14氣象數(shù)值預(yù)報(bào) 將地球由北至南分成將地球由北至南分成將地球由北至南分成將地球由北至南分成2 2度一格，延赤道分成度一格，延赤道分成度一格，延赤道分成度一格，延赤道分成4 4度一格，度一格，度一格，度一格，將大氣層分成將大氣層分成將大氣層分成將大氣層分成2020層，形成一個(gè)三維網(wǎng)格。設(shè)每個(gè)網(wǎng)格層，形成一個(gè)三維網(wǎng)格。設(shè)每個(gè)網(wǎng)格層，形成一個(gè)三維網(wǎng)格。設(shè)每個(gè)網(wǎng)格層，形成一個(gè)三維網(wǎng)格。設(shè)每個(gè)網(wǎng)格上計(jì)算量約為上計(jì)算量約為上計(jì)算量約為上計(jì)算量約為30003000次，若時(shí)間步長(zhǎng)為次，若時(shí)間步長(zhǎng)為次，若時(shí)間步長(zhǎng)為次，若時(shí)間步長(zhǎng)為2 2分鐘，則當(dāng)給分鐘，則當(dāng)給分鐘，則當(dāng)給分鐘，則當(dāng)給出出出出一天的氣象預(yù)報(bào)一天的氣象預(yù)報(bào)一天的氣象預(yù)報(bào)一天的氣象預(yù)報(bào)時(shí)，總計(jì)算量為時(shí)，總計(jì)算量為時(shí)，總計(jì)算量為時(shí)，總計(jì)算量為3.5103.5101111次。次。次。次。在在在在Gray1Gray1（GrayGray公司的向量流水機(jī)）上進(jìn)行計(jì)算（每公司的向量流水機(jī)）上進(jìn)行計(jì)算（每公司的向量流水機(jī)）上進(jìn)行計(jì)算（每公司的向量流水機(jī)）上進(jìn)行計(jì)算（每秒秒秒秒1 1億次浮點(diǎn)運(yùn)算，需計(jì)算億次浮點(diǎn)運(yùn)算，需計(jì)算億次浮點(diǎn)運(yùn)算，需計(jì)算億次浮點(diǎn)運(yùn)算，需計(jì)算1 1小時(shí)小時(shí)小時(shí)小時(shí)左右，若左右，若左右，若左右，若將網(wǎng)格邊長(zhǎng)將網(wǎng)格邊長(zhǎng)將網(wǎng)格邊長(zhǎng)將網(wǎng)格邊長(zhǎng)減半減半減半減半，是，是，是，是原來(lái)計(jì)算量的原來(lái)計(jì)算量的原來(lái)計(jì)算量的原來(lái)計(jì)算量的8 8倍倍倍倍。14氣象數(shù)值預(yù)報(bào)將地球由北至南分成2度一格，延赤道分成4度一15海洋學(xué)、天體物理 以以以以1 1。為為為為間間間間隔隔隔隔的的的的類類類類似似似似網(wǎng)網(wǎng)網(wǎng)網(wǎng)格格格格，用用用用Gyber-205Gyber-205（美美美美國(guó)國(guó)國(guó)國(guó)數(shù)數(shù)數(shù)數(shù)據(jù)據(jù)據(jù)據(jù)控控控控制制制制公公公公司司司司CDCCDC，19821982，5252位位位位4 4億億億億次次次次每每每每秒秒秒秒，400mflops400mflops的的的的流水線機(jī)）對(duì)太平洋流水線機(jī)）對(duì)太平洋流水線機(jī)）對(duì)太平洋流水線機(jī)）對(duì)太平洋5050年作一次完整模擬要年作一次完整模擬要年作一次完整模擬要年作一次完整模擬要10001000小時(shí)小時(shí)小時(shí)小時(shí)。模模模模擬擬擬擬地地地地球球球球等等等等行行行行星星星星的的的的形形形形成成成成過(guò)過(guò)過(guò)過(guò)程程程程，其其其其動(dòng)動(dòng)動(dòng)動(dòng)態(tài)態(tài)態(tài)態(tài)范范范范圍圍圍圍從從從從毫毫毫毫秒秒秒秒到到到到幾幾幾幾十十十十億億億億，ILLIAC-VILLIAC-V陣陣陣陣 列列列列 處處處處 理理理理 機(jī)機(jī)機(jī)機(jī)（美美美美 國(guó)國(guó)國(guó)國(guó) Illinios Illinios uinv,1973,64uinv,1973,64個(gè)個(gè)個(gè)個(gè)PEPE主主主主存存存存1313萬(wàn)萬(wàn)萬(wàn)萬(wàn)字字字字，1.51.5億億億億次次次次每每每每秒秒秒秒的的的的陣陣陣陣列列列列機(jī)）曾用于這一方面的研究。機(jī)）曾用于這一方面的研究。機(jī)）曾用于這一方面的研究。機(jī)）曾用于這一方面的研究。15海洋學(xué)、天體物理以1。為間隔的類似網(wǎng)格，用Gyber-216遙測(cè)地球資源數(shù)據(jù)處理 大大大大量量量量衛(wèi)衛(wèi)衛(wèi)衛(wèi)星星星星圖圖圖圖像像像像資資資資料料料料處處處處理理理理。陸陸陸陸地地地地探探探探測(cè)測(cè)測(cè)測(cè)衛(wèi)衛(wèi)衛(wèi)衛(wèi)星星星星的的的的一一一一張張張張圖圖圖圖像像像像有有有有3 3千千千千萬(wàn)萬(wàn)萬(wàn)萬(wàn)個(gè)個(gè)個(gè)個(gè)字字字字符符符符，覆覆覆覆蓋蓋蓋蓋美美美美國(guó)國(guó)國(guó)國(guó)AlabamaAlabama州州州州需需需需要要要要1313幅幅幅幅這這這這樣樣樣樣的的的的圖圖圖圖像像像像，每每每每1515天天天天產(chǎn)產(chǎn)產(chǎn)產(chǎn)生生生生一一一一次次次次新新新新的的的的圖圖圖圖像像像像，計(jì)計(jì)計(jì)計(jì)算算算算量量量量很很很很大大大大。美美美美國(guó)國(guó)國(guó)國(guó)宇宇宇宇航航航航 局局局局 訂訂訂訂 購(gòu)購(gòu)購(gòu)購(gòu) 了了了了 并并并并 行行行行 處處處處 理理理理 機(jī)機(jī)機(jī)機(jī) MPPMPP（美美美美 國(guó)國(guó)國(guó)國(guó) Goodyear Goodyear AerospaceAerospace，19791979，128128PES128128PES），最最最最高高高高速速速速度度度度每每每每秒秒秒秒6060億次億次億次億次8 8位整數(shù)運(yùn)算位整數(shù)運(yùn)算位整數(shù)運(yùn)算位整數(shù)運(yùn)算，能提供實(shí)時(shí)的情景分析。，能提供實(shí)時(shí)的情景分析。，能提供實(shí)時(shí)的情景分析。，能提供實(shí)時(shí)的情景分析。16遙測(cè)地球資源數(shù)據(jù)處理大量衛(wèi)星圖像資料處理。陸地探測(cè)衛(wèi)星的17石油開采及管理地震探測(cè)地震探測(cè)地震探測(cè)地震探測(cè) 19851985年年年年，我我我我國(guó)國(guó)國(guó)國(guó)南南南南海海海海西西西西部部部部石石石石油油油油公公公公司司司司向向向向美美美美國(guó)國(guó)國(guó)國(guó)訂訂訂訂購(gòu)購(gòu)購(gòu)購(gòu)PE3230MPSPE3230MPS并并并并行行行行處處處處理理理理計(jì)計(jì)計(jì)計(jì)算算算算機(jī)機(jī)機(jī)機(jī)。地地地地震震震震數(shù)數(shù)數(shù)數(shù)據(jù)據(jù)據(jù)據(jù)處處處處理理理理費(fèi)費(fèi)費(fèi)費(fèi)用用用用占占占占地地地地震震震震探探探探測(cè)測(cè)測(cè)測(cè)總總總總費(fèi)費(fèi)費(fèi)費(fèi)用用用用的的的的10%10%，地地地地震震震震數(shù)數(shù)數(shù)數(shù)據(jù)據(jù)據(jù)據(jù)相相相相當(dāng)當(dāng)當(dāng)當(dāng)多多多多，僅僅僅僅19791979年年年年就就就就有有有有10101515位位位位地地地地震震震震數(shù)數(shù)數(shù)數(shù)據(jù)據(jù)據(jù)據(jù)處處處處理理理理。美美美美國(guó)國(guó)國(guó)國(guó)休休休休斯斯斯斯頓頓頓頓一一一一家家家家地地地地球球球球物物物物理理理理公公公公司司司司存存存存儲(chǔ)儲(chǔ)儲(chǔ)儲(chǔ)的的的的地地地地球球球球地地地地震震震震數(shù)數(shù)數(shù)數(shù)據(jù)據(jù)據(jù)據(jù)有有有有200200萬(wàn)個(gè)磁帶卷萬(wàn)個(gè)磁帶卷萬(wàn)個(gè)磁帶卷萬(wàn)個(gè)磁帶卷。17石油開采及管理地震探測(cè)18石油開采及管理儲(chǔ)油層模型的建立儲(chǔ)油層模型的建立儲(chǔ)油層模型的建立儲(chǔ)油層模型的建立 SOHOSOHO公公公公司司司司用用用用Cyber-203Cyber-203（CDCCDC）建建建建立立立立波波波波羅羅羅羅的的的的海海海海灣灣灣灣油油油油田田田田數(shù)數(shù)數(shù)數(shù)值值值值模模模模擬擬擬擬器器器器，包包包包括括括括10001000個(gè)個(gè)個(gè)個(gè)油油油油井井井井，一一一一個(gè)個(gè)個(gè)個(gè)需需需需一一一一年年年年模模模模擬擬擬擬實(shí)實(shí)實(shí)實(shí)驗(yàn)驗(yàn)驗(yàn)驗(yàn)的的的的工工工工作作作作量量量量，在在在在Cyber-203Cyber-203僅僅僅僅用用用用3333分鐘分鐘分鐘分鐘即可完成。即可完成。即可完成。即可完成。18石油開采及管理儲(chǔ)油層模型的建立19工程計(jì)算 水水水水壩壩壩壩、橋橋橋橋梁梁梁梁、船船船船只只只只、超超超超音音音音速速速速飛飛飛飛機(jī)機(jī)機(jī)機(jī)、高高高高層層層層建建建建筑筑筑筑、太太太太空空空空飛飛飛飛行行行行器器器器設(shè)設(shè)設(shè)設(shè)計(jì)計(jì)計(jì)計(jì)需需需需解解解解大大大大型型型型偏偏偏偏微微微微分分分分方方方方程程程程組組組組和和和和代代代代數(shù)數(shù)數(shù)數(shù)方方方方程程程程組組組組，可可可可以以以以用用用用并并并并行處理機(jī)提高設(shè)計(jì)效率行處理機(jī)提高設(shè)計(jì)效率行處理機(jī)提高設(shè)計(jì)效率行處理機(jī)提高設(shè)計(jì)效率。在在在在空空空空氣氣氣氣動(dòng)動(dòng)動(dòng)動(dòng)力力力力學(xué)學(xué)學(xué)學(xué)計(jì)計(jì)計(jì)計(jì)算算算算中中中中美美美美國(guó)國(guó)國(guó)國(guó)航航航航天天天天局局局局AmesAmes研研研研究究究究中中中中心心心心用用用用超超超超級(jí)級(jí)級(jí)級(jí)計(jì)算機(jī)作風(fēng)洞實(shí)驗(yàn)三級(jí)模擬計(jì)算機(jī)作風(fēng)洞實(shí)驗(yàn)三級(jí)模擬計(jì)算機(jī)作風(fēng)洞實(shí)驗(yàn)三級(jí)模擬計(jì)算機(jī)作風(fēng)洞實(shí)驗(yàn)三級(jí)模擬。由由由由BurroughsBurroughs公公公公司司司司及及及及CDCCDC公公公公司司司司推推推推出出出出“數(shù)數(shù)數(shù)數(shù)值值值值航航航航空空空空動(dòng)動(dòng)動(dòng)動(dòng)力力力力學(xué)學(xué)學(xué)學(xué)模模模模擬擬擬擬設(shè)設(shè)設(shè)設(shè)備備備備“（NAFSNAFS）的的的的兩兩兩兩臺(tái)臺(tái)臺(tái)臺(tái)1010億億億億次次次次超超超超級(jí)級(jí)級(jí)級(jí)計(jì)計(jì)計(jì)計(jì)算算算算機(jī)機(jī)機(jī)機(jī)可可可可以以以以模模模模擬完整的飛機(jī)設(shè)計(jì)。擬完整的飛機(jī)設(shè)計(jì)。擬完整的飛機(jī)設(shè)計(jì)。擬完整的飛機(jī)設(shè)計(jì)。19工程計(jì)算水壩、橋梁、船只、超音速飛機(jī)、高層建筑、太空飛行20社會(huì)經(jīng)濟(jì)學(xué)及政府部門 計(jì)計(jì)計(jì)計(jì)量量量量經(jīng)經(jīng)經(jīng)經(jīng)濟(jì)濟(jì)濟(jì)濟(jì)學(xué)學(xué)學(xué)學(xué)、社社社社會(huì)會(huì)會(huì)會(huì)工工工工程程程程、政政政政府府府府人人人人口口口口普普普普查查查查、犯犯犯犯罪罪罪罪控控控控制制制制20002000年世界經(jīng)濟(jì)模型構(gòu)造等計(jì)算的計(jì)算量大，需并行計(jì)算。年世界經(jīng)濟(jì)模型構(gòu)造等計(jì)算的計(jì)算量大，需并行計(jì)算。年世界經(jīng)濟(jì)模型構(gòu)造等計(jì)算的計(jì)算量大，需并行計(jì)算。年世界經(jīng)濟(jì)模型構(gòu)造等計(jì)算的計(jì)算量大，需并行計(jì)算。諾諾諾諾貝貝貝貝爾爾爾爾獎(jiǎng)獎(jiǎng)獎(jiǎng)獎(jiǎng)學(xué)學(xué)學(xué)學(xué)金金金金獲獲獲獲得得得得者者者者W.W.Leontief W.W.Leontief 19801980年年年年提提提提出出出出一一一一個(gè)個(gè)個(gè)個(gè)世世世世界界界界經(jīng)經(jīng)經(jīng)經(jīng)濟(jì)濟(jì)濟(jì)濟(jì)輸輸輸輸入入入入/輸輸輸輸出出出出模模模模型型型型，在在在在CDCCDC科科科科學(xué)學(xué)學(xué)學(xué)計(jì)計(jì)計(jì)計(jì)算算算算機(jī)機(jī)機(jī)機(jī)上上上上運(yùn)運(yùn)運(yùn)運(yùn)算算算算，認(rèn)認(rèn)認(rèn)認(rèn)為為為為一一一一個(gè)個(gè)個(gè)個(gè)以以以以部部部部分分分分裁裁裁裁軍軍軍軍為為為為特特特特征征征征的的的的國(guó)國(guó)國(guó)國(guó)際際際際性性性性經(jīng)經(jīng)經(jīng)經(jīng)濟(jì)濟(jì)濟(jì)濟(jì)關(guān)關(guān)關(guān)關(guān)系系系系系系系系統(tǒng)統(tǒng)統(tǒng)統(tǒng)，可可可可以以以以縮小貧富國(guó)家的差距，該項(xiàng)目受到聯(lián)合國(guó)支持?？s小貧富國(guó)家的差距，該項(xiàng)目受到聯(lián)合國(guó)支持?？s小貧富國(guó)家的差距，該項(xiàng)目受到聯(lián)合國(guó)支持?？s小貧富國(guó)家的差距，該項(xiàng)目受到聯(lián)合國(guó)支持。美美美美國(guó)國(guó)國(guó)國(guó)使使使使用用用用大大大大型型型型計(jì)計(jì)計(jì)計(jì)算算算算機(jī)機(jī)機(jī)機(jī)控控控控制制制制犯犯犯犯罪罪罪罪、收收收收稅稅稅稅與與與與審審審審計(jì)計(jì)計(jì)計(jì)，進(jìn)進(jìn)進(jìn)進(jìn)行行行行人人人人口口口口普普普普查查查查及及及及民民民民意意意意測(cè)測(cè)測(cè)測(cè)驗(yàn)驗(yàn)驗(yàn)驗(yàn)。過(guò)過(guò)過(guò)過(guò)去去去去美美美美國(guó)國(guó)國(guó)國(guó)制制制制造造造造的的的的大大大大型型型型計(jì)計(jì)計(jì)計(jì)算算算算機(jī)機(jī)機(jī)機(jī)57%57%由由由由政政政政府使用。府使用。府使用。府使用。20社會(huì)經(jīng)濟(jì)學(xué)及政府部門計(jì)量經(jīng)濟(jì)學(xué)、社會(huì)工程、政府人口普查、21國(guó)防、人工智能、基礎(chǔ)研究國(guó)防國(guó)防國(guó)防國(guó)防軍軍軍軍事事事事部部部部門門門門使使使使用用用用現(xiàn)現(xiàn)現(xiàn)現(xiàn)存存存存的的的的大大大大部部部部分分分分超超超超級(jí)級(jí)級(jí)級(jí)計(jì)計(jì)計(jì)計(jì)算算算算機(jī)機(jī)機(jī)機(jī)，如如如如Cray-1Cray-1多用于彈頭核武器設(shè)計(jì)。多用于彈頭核武器設(shè)計(jì)。多用于彈頭核武器設(shè)計(jì)。多用于彈頭核武器設(shè)計(jì)。在在在在關(guān)關(guān)關(guān)關(guān)聯(lián)聯(lián)聯(lián)聯(lián)處處處處理理理理機(jī)機(jī)機(jī)機(jī)上上上上為為為為反反反反彈彈彈彈道道道道導(dǎo)導(dǎo)導(dǎo)導(dǎo)彈彈彈彈程程程程序序序序處處處處理理理理雷雷雷雷達(dá)達(dá)達(dá)達(dá)信信信信號(hào)號(hào)號(hào)號(hào)，用用用用S-1S-1多處理機(jī)做反潛艇海洋監(jiān)視。多處理機(jī)做反潛艇海洋監(jiān)視。多處理機(jī)做反潛艇海洋監(jiān)視。多處理機(jī)做反潛艇海洋監(jiān)視。21國(guó)防、人工智能、基礎(chǔ)研究國(guó)防22國(guó)防、人工智能、基礎(chǔ)研究人工智能人工智能人工智能人工智能 圖像處理圖像處理圖像處理圖像處理 模式識(shí)別模式識(shí)別模式識(shí)別模式識(shí)別 計(jì)算機(jī)視覺(jué)計(jì)算機(jī)視覺(jué)計(jì)算機(jī)視覺(jué)計(jì)算機(jī)視覺(jué) 自然語(yǔ)言理解自然語(yǔ)言理解自然語(yǔ)言理解自然語(yǔ)言理解 機(jī)器推理機(jī)器推理機(jī)器推理機(jī)器推理 智能機(jī)器人智能機(jī)器人智能機(jī)器人智能機(jī)器人 專家系統(tǒng)專家系統(tǒng)專家系統(tǒng)專家系統(tǒng) 知識(shí)工程知識(shí)工程知識(shí)工程知識(shí)工程基礎(chǔ)研究基礎(chǔ)研究基礎(chǔ)研究基礎(chǔ)研究 計(jì)算化學(xué)計(jì)算化學(xué)計(jì)算化學(xué)計(jì)算化學(xué) 計(jì)算物理計(jì)算物理計(jì)算物理計(jì)算物理 計(jì)算幾何計(jì)算幾何計(jì)算幾何計(jì)算幾何 VLSIVLSI輔助設(shè)計(jì)輔助設(shè)計(jì)輔助設(shè)計(jì)輔助設(shè)計(jì)22國(guó)防、人工智能、基礎(chǔ)研究人工智能23當(dāng)代科學(xué)與工程問(wèn)題的計(jì)算需求評(píng)測(cè)計(jì)算機(jī)性能的指標(biāo)評(píng)測(cè)計(jì)算機(jī)性能的指標(biāo)評(píng)測(cè)計(jì)算機(jī)性能的指標(biāo)評(píng)測(cè)計(jì)算機(jī)性能的指標(biāo)7070年代年代年代年代Mflops 10Mflops 106 6 百萬(wàn)百萬(wàn)百萬(wàn)百萬(wàn)現(xiàn)在現(xiàn)在現(xiàn)在現(xiàn)在Pflops 10Pflops 101515 千萬(wàn)億次千萬(wàn)億次千萬(wàn)億次千萬(wàn)億次9090年代年代年代年代Tflops 10Tflops 101212 萬(wàn)億萬(wàn)億萬(wàn)億萬(wàn)億8080年代年代年代年代Gflops 10Gflops 109 9 十億十億十億十億世界上第一臺(tái)峰值速度世界上第一臺(tái)峰值速度超過(guò)超過(guò)1Tflops1Tflops的高性能計(jì)的高性能計(jì)算機(jī)是由算機(jī)是由IntelIntel公司于公司于19961996年年1212月研制成功的。月研制成功的。23當(dāng)代科學(xué)與工程問(wèn)題的計(jì)算需求評(píng)測(cè)計(jì)算機(jī)性能的指標(biāo)70年代24當(dāng)代科學(xué)與工程問(wèn)題的計(jì)算需求美美美美 國(guó)國(guó)國(guó)國(guó) HPCCHPCC計(jì)計(jì)計(jì)計(jì) 劃劃劃劃（High High Performance Performance Computing&CommunicationComputing&Communication）為為為為了了了了保保保保持持持持美美美美國(guó)國(guó)國(guó)國(guó)的的的的世世世世界界界界領(lǐng)領(lǐng)領(lǐng)領(lǐng)先先先先地地地地位位位位，19931993年年年年，美美美美國(guó)國(guó)國(guó)國(guó)科科科科學(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)理理理理事事事事會(huì)會(huì)會(huì)會(huì)的的的的國(guó)國(guó)國(guó)國(guó)會(huì)會(huì)會(huì)會(huì)提提提提出出出出了了了了題題題題為為為為“重重重重大大大大挑挑挑挑戰(zhàn)戰(zhàn)戰(zhàn)戰(zhàn)項(xiàng)項(xiàng)項(xiàng)項(xiàng)目目目目：高高高高性性性性能能能能計(jì)計(jì)計(jì)計(jì)算算算算與與與與通通通通信信信信”的報(bào)告，簡(jiǎn)稱的報(bào)告，簡(jiǎn)稱的報(bào)告，簡(jiǎn)稱的報(bào)告，簡(jiǎn)稱HPCCHPCC計(jì)劃計(jì)劃計(jì)劃計(jì)劃3T3T性能目標(biāo)性能目標(biāo)性能目標(biāo)性能目標(biāo) TflopsTflops計(jì)算能力、計(jì)算能力、計(jì)算能力、計(jì)算能力、1TB1TB主存容量、主存容量、主存容量、主存容量、1TB/s1TB/s的的的的I/OI/O帶寬帶寬帶寬帶寬24當(dāng)代科學(xué)與工程問(wèn)題的計(jì)算需求美國(guó)HPCC計(jì)劃（High 25HPCC應(yīng)用領(lǐng)域高速民航高速民航高速民航高速民航用計(jì)算流體動(dòng)力學(xué)來(lái)研制超音速噴氣發(fā)動(dòng)機(jī)用計(jì)算流體動(dòng)力學(xué)來(lái)研制超音速噴氣發(fā)動(dòng)機(jī)用計(jì)算流體動(dòng)力學(xué)來(lái)研制超音速噴氣發(fā)動(dòng)機(jī)用計(jì)算流體動(dòng)力學(xué)來(lái)研制超音速噴氣發(fā)動(dòng)機(jī)新藥設(shè)計(jì)新藥設(shè)計(jì)新藥設(shè)計(jì)新藥設(shè)計(jì)研制癌癥和艾滋病的藥物研制癌癥和艾滋病的藥物研制癌癥和艾滋病的藥物研制癌癥和艾滋病的藥物催化作用催化作用催化作用催化作用仿生催化劑計(jì)算機(jī)建模，分析合成過(guò)程中酶的作用仿生催化劑計(jì)算機(jī)建模，分析合成過(guò)程中酶的作用仿生催化劑計(jì)算機(jī)建模，分析合成過(guò)程中酶的作用仿生催化劑計(jì)算機(jī)建模，分析合成過(guò)程中酶的作用燃料燃燒燃料燃燒燃料燃燒燃料燃燒通過(guò)化學(xué)動(dòng)力學(xué)，揭示流體力學(xué)的作用，設(shè)計(jì)新型發(fā)動(dòng)通過(guò)化學(xué)動(dòng)力學(xué)，揭示流體力學(xué)的作用，設(shè)計(jì)新型發(fā)動(dòng)通過(guò)化學(xué)動(dòng)力學(xué)，揭示流體力學(xué)的作用，設(shè)計(jì)新型發(fā)動(dòng)通過(guò)化學(xué)動(dòng)力學(xué)，揭示流體力學(xué)的作用，設(shè)計(jì)新型發(fā)動(dòng)機(jī)機(jī)機(jī)機(jī)海洋建模海洋建模海洋建模海洋建模對(duì)海洋活動(dòng)與大氣流的熱交換進(jìn)行整體海洋模擬對(duì)海洋活動(dòng)與大氣流的熱交換進(jìn)行整體海洋模擬對(duì)海洋活動(dòng)與大氣流的熱交換進(jìn)行整體海洋模擬對(duì)海洋活動(dòng)與大氣流的熱交換進(jìn)行整體海洋模擬大氣污染大氣污染大氣污染大氣污染對(duì)大氣質(zhì)量模型進(jìn)行模擬研究，揭示其物理和化學(xué)機(jī)理對(duì)大氣質(zhì)量模型進(jìn)行模擬研究，揭示其物理和化學(xué)機(jī)理對(duì)大氣質(zhì)量模型進(jìn)行模擬研究，揭示其物理和化學(xué)機(jī)理對(duì)大氣質(zhì)量模型進(jìn)行模擬研究，揭示其物理和化學(xué)機(jī)理蛋白質(zhì)結(jié)構(gòu)設(shè)計(jì)蛋白質(zhì)結(jié)構(gòu)設(shè)計(jì)蛋白質(zhì)結(jié)構(gòu)設(shè)計(jì)蛋白質(zhì)結(jié)構(gòu)設(shè)計(jì)使用計(jì)算機(jī)模擬，對(duì)蛋白質(zhì)組成的三維結(jié)構(gòu)進(jìn)行研究使用計(jì)算機(jī)模擬，對(duì)蛋白質(zhì)組成的三維結(jié)構(gòu)進(jìn)行研究使用計(jì)算機(jī)模擬，對(duì)蛋白質(zhì)組成的三維結(jié)構(gòu)進(jìn)行研究使用計(jì)算機(jī)模擬，對(duì)蛋白質(zhì)組成的三維結(jié)構(gòu)進(jìn)行研究圖像理解圖像理解圖像理解圖像理解實(shí)時(shí)繪制圖像或動(dòng)畫實(shí)時(shí)繪制圖像或動(dòng)畫實(shí)時(shí)繪制圖像或動(dòng)畫實(shí)時(shí)繪制圖像或動(dòng)畫密碼破譯密碼破譯密碼破譯密碼破譯破譯由長(zhǎng)位數(shù)組成的密碼，求找該數(shù)的兩個(gè)乘積因子破譯由長(zhǎng)位數(shù)組成的密碼，求找該數(shù)的兩個(gè)乘積因子破譯由長(zhǎng)位數(shù)組成的密碼，求找該數(shù)的兩個(gè)乘積因子破譯由長(zhǎng)位數(shù)組成的密碼，求找該數(shù)的兩個(gè)乘積因子19941994年年4 4月月2626日，美國(guó)宣日，美國(guó)宣布破譯了世界上最長(zhǎng)的布破譯了世界上最長(zhǎng)的RSA129RSA129密碼，在因特網(wǎng)上密碼，在因特網(wǎng)上使用使用16001600臺(tái)計(jì)算機(jī)，臺(tái)計(jì)算機(jī)，600600多人工作多人工作8 8個(gè)月個(gè)月，破譯了，破譯了129129位數(shù)字組成的密碼位數(shù)字組成的密碼25HPCC應(yīng)用領(lǐng)域高速民航用計(jì)算流體動(dòng)力學(xué)來(lái)研制超音速噴氣26科學(xué)計(jì)算的需要26科學(xué)計(jì)算的需要27當(dāng)代科學(xué)與工程問(wèn)題的計(jì)算需求美美美美 國(guó)國(guó)國(guó)國(guó) ASCIASCI計(jì)計(jì)計(jì)計(jì) 劃劃劃劃（Accelerated Accelerated Strategic Strategic Computing InitiativeComputing Initiative）全全全全面面面面禁禁禁禁止止止止核核核核實(shí)實(shí)實(shí)實(shí)驗(yàn)驗(yàn)驗(yàn)驗(yàn)條條條條約約約約簽簽簽簽訂訂訂訂后后后后，19961996年年年年6 6月月月月能能能能源源源源部部部部聯(lián)聯(lián)聯(lián)聯(lián)合合合合美美美美國(guó)國(guó)國(guó)國(guó)三三三三大大大大武武武武器器器器實(shí)實(shí)實(shí)實(shí)驗(yàn)驗(yàn)驗(yàn)驗(yàn)室室室室共共共共同同同同提提提提出出出出了了了了“加加加加速速速速戰(zhàn)戰(zhàn)戰(zhàn)戰(zhàn)略略略略計(jì)劃創(chuàng)新計(jì)劃創(chuàng)新計(jì)劃創(chuàng)新計(jì)劃創(chuàng)新”，簡(jiǎn)稱為，簡(jiǎn)稱為，簡(jiǎn)稱為，簡(jiǎn)稱為ASCIASCI計(jì)劃計(jì)劃計(jì)劃計(jì)劃27當(dāng)代科學(xué)與工程問(wèn)題的計(jì)算需求美國(guó)ASCI計(jì)劃（Accel28美國(guó)美國(guó)ASCI計(jì)劃劃 目的目的目的目的 通通通通過(guò)過(guò)過(guò)過(guò)數(shù)數(shù)數(shù)數(shù)值值值值模模模模擬擬擬擬，評(píng)評(píng)評(píng)評(píng)估估估估核核核核武武武武器器器器的的的的性性性性能能能能、安安安安全全全全性性性性、可可可可靠靠靠靠性性性性等等等等，達(dá)達(dá)達(dá)達(dá)到到到到高高高高分分分分辨辨辨辨率率率率、高高高高逼逼逼逼真真真真度度度度、三三三三維維維維、全全全全物物物物理理理理、全全全全系系系系統(tǒng)統(tǒng)統(tǒng)統(tǒng)的的的的規(guī)規(guī)規(guī)規(guī)模模模模和和和和能能能能力力力力，該該該該計(jì)計(jì)計(jì)計(jì)劃劃劃劃被被被被認(rèn)認(rèn)認(rèn)認(rèn)為為為為是是是是與與與與當(dāng)當(dāng)當(dāng)當(dāng)年年年年曼曼曼曼哈哈哈哈頓頓頓頓計(jì)計(jì)計(jì)計(jì)劃劃劃劃等等等等同同同同的的的的一一一一個(gè)個(gè)個(gè)個(gè)巨巨巨巨大的挑戰(zhàn)。大的挑戰(zhàn)。大的挑戰(zhàn)。大的挑戰(zhàn)。平臺(tái)平臺(tái)平臺(tái)平臺(tái) 三三三三 大大大大 核核核核 武武武武 器器器器 實(shí)實(shí)實(shí)實(shí) 驗(yàn)驗(yàn)驗(yàn)驗(yàn) 室室室室 向向向向 三三三三 大大大大 公公公公 司司司司（IntelIntel，IBMIBM和和和和SGI/CraySGI/Cray）預(yù)預(yù)預(yù)預(yù)訂訂訂訂了了了了峰峰峰峰值值值值超超超超過(guò)過(guò)過(guò)過(guò)1Tflops1Tflops的的的的并并并并行行行行計(jì)計(jì)計(jì)計(jì)算算算算機(jī)機(jī)機(jī)機(jī)，預(yù)預(yù)預(yù)預(yù)計(jì)計(jì)計(jì)計(jì)20032003年年年年使使使使用用用用運(yùn)運(yùn)運(yùn)運(yùn)算算算算100Tflops100Tflops，50TB50TB存存存存儲(chǔ)儲(chǔ)儲(chǔ)儲(chǔ)容容容容量量量量，I/OI/O傳傳傳傳輸輸輸輸速率為速率為速率為速率為5000GB/s5000GB/s的并行機(jī)的并行機(jī)的并行機(jī)的并行機(jī)28美國(guó)ASCI計(jì)劃29并行處理中的幾個(gè)難題任務(wù)分配非常困難任務(wù)分配非常困難任務(wù)分配非常困難任務(wù)分配非常困難 考慮時(shí)空復(fù)雜度，還需考慮模塊之間的通信量考慮時(shí)空復(fù)雜度，還需考慮模塊之間的通信量考慮時(shí)空復(fù)雜度，還需考慮模塊之間的通信量考慮時(shí)空復(fù)雜度，還需考慮模塊之間的通信量 很難擺脫串行處理方式的約束很難擺脫串行處理方式的約束很難擺脫串行處理方式的約束很難擺脫串行處理方式的約束 軟件和算法大都是按照串行結(jié)構(gòu)設(shè)計(jì)的軟件和算法大都是按照串行結(jié)構(gòu)設(shè)計(jì)的軟件和算法大都是按照串行結(jié)構(gòu)設(shè)計(jì)的軟件和算法大都是按照串行結(jié)構(gòu)設(shè)計(jì)的 現(xiàn)有的算法語(yǔ)言對(duì)并行性限制很大現(xiàn)有的算法語(yǔ)言對(duì)并行性限制很大現(xiàn)有的算法語(yǔ)言對(duì)并行性限制很大現(xiàn)有的算法語(yǔ)言對(duì)并行性限制很大 現(xiàn)有語(yǔ)言以現(xiàn)有語(yǔ)言以現(xiàn)有語(yǔ)言以現(xiàn)有語(yǔ)言以Von NeumannVon Neumann方式為基礎(chǔ)，對(duì)并行性限方式為基礎(chǔ)，對(duì)并行性限方式為基礎(chǔ)，對(duì)并行性限方式為基礎(chǔ)，對(duì)并行性限 制嚴(yán)重：制嚴(yán)重：制嚴(yán)重：制嚴(yán)重：l l 語(yǔ)句執(zhí)行結(jié)果、執(zhí)行順序與前面結(jié)果和狀態(tài)相關(guān)語(yǔ)句執(zhí)行結(jié)果、執(zhí)行順序與前面結(jié)果和狀態(tài)相關(guān)語(yǔ)句執(zhí)行結(jié)果、執(zhí)行順序與前面結(jié)果和狀態(tài)相關(guān)語(yǔ)句執(zhí)行結(jié)果、執(zhí)行順序與前面結(jié)果和狀態(tài)相關(guān)l l 大量賦值語(yǔ)句使得處理器與存儲(chǔ)器頻繁交換信息，大量賦值語(yǔ)句使得處理器與存儲(chǔ)器頻繁交換信息，大量賦值語(yǔ)句使得處理器與存儲(chǔ)器頻繁交換信息，大量賦值語(yǔ)句使得處理器與存儲(chǔ)器頻繁交換信息，降低系統(tǒng)效率降低系統(tǒng)效率降低系統(tǒng)效率降低系統(tǒng)效率29并行處理中的幾個(gè)難題任務(wù)分配非常困難30并行處理中的幾個(gè)難題Von NeumannVon Neumann模式一直伴隨著并行機(jī)模式一直伴隨著并行機(jī)模式一直伴隨著并行機(jī)模式一直伴隨著并行機(jī) 未擺脫以未擺脫以未擺脫以未擺脫以指令流指令流指令流指令流為主導(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)，使并行受到制約處理機(jī)間的通訊開銷使并行處理技術(shù)可能得不償失處理機(jī)間的通訊開銷使并行處理技術(shù)可能得不償失處理機(jī)間的通訊開銷使并行處理技術(shù)可能得不償失處理機(jī)間的通訊開銷使并行處理技術(shù)可能得不償失 并行處理技術(shù)的主要難點(diǎn)在于軟件并行處理技術(shù)的主要難點(diǎn)在于軟件并行處理技術(shù)的主要難點(diǎn)在于軟件并行處理技術(shù)的主要難點(diǎn)在于軟件 串行機(jī)中軟件好壞對(duì)于工作性能影響串行機(jī)中軟件好壞對(duì)于工作性能影響串行機(jī)中軟件好壞對(duì)于工作性能影響串行機(jī)中軟件好壞對(duì)于工作性能影響2-32-3倍，并行計(jì)算倍，并行計(jì)算倍，并行計(jì)算倍，并行計(jì)算機(jī)中卻是機(jī)中卻是機(jī)中卻是機(jī)中卻是50-10050-100倍，而且最困難的在于并行編譯程序倍，而且最困難的在于并行編譯程序倍，而且最困難的在于并行編譯程序倍，而且最困難的在于并行編譯程序30并行處理中的幾個(gè)難題Von Neumann模式一直伴隨著傳統(tǒng)Von Neumann結(jié)構(gòu)及其存在構(gòu)及其存在問(wèn)題 存儲(chǔ)程序控制方式存儲(chǔ)程序控制方式存儲(chǔ)程序控制方式存儲(chǔ)程序控制方式31存儲(chǔ)器指令寄存器、計(jì)數(shù)器存儲(chǔ)器指令數(shù)據(jù)指令流驅(qū)動(dòng)傳統(tǒng)Von Neumann結(jié)構(gòu)及其存在問(wèn)題存儲(chǔ)程序控制方式332研究并行處理應(yīng)考慮的幾個(gè)問(wèn)題算法、體系結(jié)構(gòu)、高級(jí)語(yǔ)言三者之間的關(guān)系應(yīng)考慮：算法、體系結(jié)構(gòu)、高級(jí)語(yǔ)言三者之間的關(guān)系應(yīng)考慮：算法、體系結(jié)構(gòu)、高級(jí)語(yǔ)言三者之間的關(guān)系應(yīng)考慮：算法、體系結(jié)構(gòu)、高級(jí)語(yǔ)言三者之間的關(guān)系應(yīng)考慮：對(duì)于一些特定的計(jì)算機(jī)對(duì)于一些特定的計(jì)算機(jī)對(duì)于一些特定的計(jì)算機(jī)對(duì)于一些特定的計(jì)算機(jī)如何設(shè)計(jì)軟件如何設(shè)計(jì)軟件如何設(shè)計(jì)軟件如何設(shè)計(jì)軟件 對(duì)于一個(gè)給定的程序?qū)τ谝粋€(gè)給定的程序?qū)τ谝粋€(gè)給定的程序?qū)τ谝粋€(gè)給定的程序如何使之結(jié)構(gòu)化以便在給定的計(jì)算如何使之結(jié)構(gòu)化以便在給定的計(jì)算如何使之結(jié)構(gòu)化以便在給定的計(jì)算如何使之結(jié)構(gòu)化以便在給定的計(jì)算機(jī)上處理機(jī)上處理機(jī)上處理機(jī)上處理 對(duì)于一個(gè)給定的計(jì)算機(jī)和一組應(yīng)用軟件對(duì)于一個(gè)給定的計(jì)算機(jī)和一組應(yīng)用軟件對(duì)于一個(gè)給定的計(jì)算機(jī)和一組應(yīng)用軟件對(duì)于一個(gè)給定的計(jì)算機(jī)和一組應(yīng)用軟件怎樣設(shè)計(jì)語(yǔ)言及怎樣設(shè)計(jì)語(yǔ)言及怎樣設(shè)計(jì)語(yǔ)言及怎樣設(shè)計(jì)語(yǔ)言及編譯系統(tǒng)編譯系統(tǒng)編譯系統(tǒng)編譯系統(tǒng) 對(duì)于給定的計(jì)算機(jī)、語(yǔ)言及編譯系統(tǒng)對(duì)于給定的計(jì)算機(jī)、語(yǔ)言及編譯系統(tǒng)對(duì)于給定的計(jì)算機(jī)、語(yǔ)言及編譯系統(tǒng)對(duì)于給定的計(jì)算機(jī)、語(yǔ)言及編譯系統(tǒng)如何設(shè)計(jì)算法與程如何設(shè)計(jì)算法與程如何設(shè)計(jì)算法與程如何設(shè)計(jì)算法與程序序序序32研究并行處理應(yīng)考慮的幾個(gè)問(wèn)題算法、體系結(jié)構(gòu)、高級(jí)語(yǔ)言三者33并行處理機(jī)系統(tǒng)的優(yōu)點(diǎn)具有很高的性能價(jià)格比具有很高的性能價(jià)格比具有很高的性能價(jià)格比具有很高的性能價(jià)格比由于系統(tǒng)的模塊性，使之便于維護(hù)由于系統(tǒng)的模塊性，使之便于維護(hù)由于系統(tǒng)的模塊性，使之便于維護(hù)由于系統(tǒng)的模塊性，使之便于維護(hù)具有較高的可靠性具有較高的可靠性具有較高的可靠性具有較高的可靠性具有較高的處理速度具有較高的處理速度具有較高的處理速度具有較高的處理速度結(jié)構(gòu)的靈活性結(jié)構(gòu)的靈活性結(jié)構(gòu)的靈活性結(jié)構(gòu)的靈活性便于便于便于便于VLSIVLSI實(shí)現(xiàn)實(shí)現(xiàn)實(shí)現(xiàn)實(shí)現(xiàn)33并行處理機(jī)系統(tǒng)的優(yōu)點(diǎn)具有很高的性能價(jià)格比341.1.3 并行處理機(jī)的分類1 13 34 42 2341.1.3 并行處理機(jī)的分類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í)際不存在）（實(shí)際不存在）（實(shí)際不存在）（實(shí)際不存在）多多多多指令流指令流指令流指令流多多多多數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流MIMDMIMD35Flynn分類法單指令流單數(shù)據(jù)流SISD36SISDCUCUPUPUMMMMISISDSDSISISCUCU：控制單元：控制單元：控制單元：控制單元 PUPU：處理單元：處理單元：處理單元：處理單元 MMMM：存儲(chǔ)器：存儲(chǔ)器：存儲(chǔ)器：存儲(chǔ)器 IS IS：指令流：指令流：指令流：指令流 DSDS：數(shù)據(jù)流：數(shù)據(jù)流：數(shù)據(jù)流：數(shù)據(jù)流36SISDCUPUMMISDSISCU：控制單元 PU37SIMDCUCUPUPU1 1ISISPUPU2 2PUPUn n MMMM1 1MMMM2 2MMMMn n DSDS1 1DSDS2 2DSDSn nISIS37SIMDCUPU1ISPU2PUnMM1MM2MMn38MIMDPUPU1 1PUPU2 2PUPUn n MMMM1 1MMMM2 2MMMMn n DSDS1 1DSDS2 2DSDSn nISIS1 1ISIS2 2ISISn nCUCU1 1CUCU2 2CUCUn n ISIS1 1ISIS2 2ISISn n38MIMDPU1PU2PUnMM1MM2MMnDS1D39Handler分類法 19771977年，年，年，年，HandlerHandler根據(jù)計(jì)算機(jī)系統(tǒng)中流水線和并行度根據(jù)計(jì)算機(jī)系統(tǒng)中流水線和并行度根據(jù)計(jì)算機(jī)系統(tǒng)中流水線和并行度根據(jù)計(jì)算機(jī)系統(tǒng)中流水線和并行度出現(xiàn)的級(jí)別，將一臺(tái)計(jì)算機(jī)表示為三對(duì)整數(shù)：出現(xiàn)的級(jí)別，將一臺(tái)計(jì)算機(jī)表示為三對(duì)整數(shù)：出現(xiàn)的級(jí)別，將一臺(tái)計(jì)算機(jī)表示為三對(duì)整數(shù)：出現(xiàn)的級(jí)別，將一臺(tái)計(jì)算機(jī)表示為三對(duì)整數(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ù)計(jì)算機(jī)40按體系結(jié)構(gòu)分類 同步系統(tǒng)同步系統(tǒng)同步系統(tǒng)同步系統(tǒng) 向量向量向量向量流水機(jī)流水機(jī)流水機(jī)流水機(jī) 陣列陣列陣列陣列處理機(jī)：（含心動(dòng)陣列）處理機(jī)：（含心動(dòng)陣列）處理機(jī)：（含心動(dòng)陣列）處理機(jī)：（含心動(dòng)陣列）SIMDSIMD 關(guān)聯(lián)關(guān)聯(lián)關(guān)聯(lián)關(guān)聯(lián)處理機(jī)：具有聯(lián)想存儲(chǔ)、按內(nèi)容存取、邏輯操作等處理機(jī)：具有聯(lián)想存儲(chǔ)、按內(nèi)容存取、邏輯操作等處理機(jī)：具有聯(lián)想存儲(chǔ)、按內(nèi)容存取、邏輯操作等處理機(jī)：具有聯(lián)想存儲(chǔ)、按內(nèi)容存取、邏輯操作等 多處理機(jī)系統(tǒng)多處理機(jī)系統(tǒng)多處理機(jī)系統(tǒng)多處理機(jī)系統(tǒng)MIMD:MIMD:由獨(dú)立執(zhí)行指令的處理器由獨(dú)立執(zhí)行指令的處理器由獨(dú)立執(zhí)行指令的處理器由獨(dú)立執(zhí)行指令的處理器構(gòu)成構(gòu)成構(gòu)成構(gòu)成 分布分布分布分布存儲(chǔ)系統(tǒng)：每個(gè)結(jié)點(diǎn)有獨(dú)立的存儲(chǔ)單元存儲(chǔ)系統(tǒng)：每個(gè)結(jié)點(diǎn)有獨(dú)立的存儲(chǔ)單元存儲(chǔ)系統(tǒng)：每個(gè)結(jié)點(diǎn)有獨(dú)立的存儲(chǔ)單元存儲(chǔ)系統(tǒng)：每個(gè)結(jié)點(diǎn)有獨(dú)立的存儲(chǔ)單元 共享共享共享共享存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng) MIMDMIMD變體變體變體變體（MIMD/SIMDMIMD/SIMD混合型）混合型）混合型）混合型）40按體系結(jié)構(gòu)分類同步系統(tǒng)41現(xiàn)代并行機(jī)結(jié)構(gòu)分類 SIMDSIMD PVPPVP并行向量處理機(jī)并行向量處理機(jī)并行向量處理機(jī)并行向量處理機(jī) SMPSMP對(duì)稱多處理機(jī)對(duì)稱多處理機(jī)對(duì)稱多處理機(jī)對(duì)稱多處理機(jī) MPPMPP大規(guī)模并行處理機(jī)大規(guī)模并行處理機(jī)大規(guī)模并行處理機(jī)大規(guī)模并行處理機(jī) DSMDSM分布式共享存儲(chǔ)多處理機(jī)分布式共享存儲(chǔ)多處理機(jī)分布式共享存儲(chǔ)多處理機(jī)分布式共享存儲(chǔ)多處理機(jī) COWCOW工作站機(jī)群工作站機(jī)群工作站機(jī)群工作站機(jī)群Gray C-90Gray C-90Gray T-90Gray T-90銀河銀河1 1號(hào)號(hào)41現(xiàn)代并行機(jī)結(jié)構(gòu)分類SIMDGray C-9042對(duì)稱多處理機(jī)SMPIBM R50IBM R50、SGI Power ChakengeSGI Power Chakenge、曙光、曙光、曙光、曙光1 1號(hào)號(hào)號(hào)號(hào)使用商用微處理的芯片，由高速總線連向共享使用商用微處理的芯片，由高速總線連向共享使用商用微處理的芯片，由高速總線連向共享使用商用微處理的芯片，由高速總線連向共享存儲(chǔ)器，對(duì)稱性存儲(chǔ)器，對(duì)稱性存儲(chǔ)器，對(duì)稱性存儲(chǔ)器，對(duì)稱性共享存儲(chǔ)共享存儲(chǔ)共享存儲(chǔ)共享存儲(chǔ)，PEPE個(gè)數(shù)不能太多個(gè)數(shù)不能太多個(gè)數(shù)不能太多個(gè)數(shù)不能太多。系統(tǒng)是系統(tǒng)是系統(tǒng)是系統(tǒng)是對(duì)稱對(duì)稱對(duì)稱對(duì)稱的，每個(gè)處理器可的，每個(gè)處理器可的，每個(gè)處理器可的，每個(gè)處理器可等同的訪問(wèn)共享等同的訪問(wèn)共享等同的訪問(wèn)共享等同的訪問(wèn)共享存儲(chǔ)存儲(chǔ)存儲(chǔ)存儲(chǔ)，I/OI/O設(shè)備。設(shè)備。設(shè)備。設(shè)備。42對(duì)稱多處理機(jī)SMPIBM R50、SGI Power 43大規(guī)模并行處理機(jī)MPP 經(jīng)典機(jī)型：經(jīng)典機(jī)型：經(jīng)典機(jī)型：經(jīng)典機(jī)型：IBM SP2IBM SP2、Intel ParagonIntel Paragon、Intel Intel TFLOPSTFLOPS、曙光、曙光、曙光、曙光10001000等。等。等。等。特性：特性：特性：特性：節(jié)點(diǎn)為微處理器節(jié)點(diǎn)為微處理器節(jié)點(diǎn)為微處理器節(jié)點(diǎn)為微處理器物理上的物理上的物理上的物理上的分布存儲(chǔ)分布存儲(chǔ)分布存儲(chǔ)分布存儲(chǔ)高帶寬、低延遲的網(wǎng)絡(luò)高帶寬、低延遲的網(wǎng)絡(luò)高帶寬、低延遲的網(wǎng)絡(luò)高帶寬、低延遲的網(wǎng)絡(luò)成百上千個(gè)成百上千個(gè)成百上千個(gè)成百上千個(gè)PEPE異步異步異步異步MIMDMIMD，程序由多個(gè)進(jìn)程組成，每個(gè)進(jìn)程有私，程序由多個(gè)進(jìn)程組成，每個(gè)進(jìn)程有私，程序由多個(gè)進(jìn)程組成，每個(gè)進(jìn)程有私，程序由多個(gè)進(jìn)程組成，每個(gè)進(jìn)程有私有空間，進(jìn)程間采用有空間，進(jìn)程間采用有空間，進(jìn)程間采用有空間，進(jìn)程間采用消息傳遞消息傳遞消息傳遞消息傳遞的方式的方式的方式的方式43大規(guī)模并行處理機(jī)MPP經(jīng)典機(jī)型：IBM SP2、Inte44分布式共享存儲(chǔ)多處理機(jī)DSM經(jīng)典機(jī)型：經(jīng)典機(jī)型：經(jīng)典機(jī)型：經(jīng)典機(jī)型：Cray T3DCray T3D、SGI/Gray Origin 2000SGI/Gray Origin 2000特點(diǎn)：特點(diǎn)：特點(diǎn)：特點(diǎn)：分布在各個(gè)節(jié)點(diǎn)上的局存形成了一個(gè)共享的存儲(chǔ)器分布在各個(gè)節(jié)點(diǎn)上的局存形成了一個(gè)共享的存儲(chǔ)器分布在各個(gè)節(jié)點(diǎn)上的局存形成了一個(gè)共享的存儲(chǔ)器分布在各個(gè)節(jié)點(diǎn)上的局存形成了一個(gè)共享的存儲(chǔ)器與與與與SIMDSIMD相相相相同同同同，在在在在物物物物理理理理上上上上有有有有分分分分布布布布在在在在各各各各點(diǎn)點(diǎn)點(diǎn)點(diǎn)的的的的共共共共享享享享主主主主存存存存，但采用但采用但采用但采用單一地址空間單一地址空間單一地址空間單一地址空間，與，與，與，與MPPMPP相比，相比，相比，相比，易于編程易于編程易于編程易于編程44分布式共享存儲(chǔ)多處理機(jī)DSM經(jīng)典機(jī)型：Cray T3D、45工作站機(jī)群COW 經(jīng)典機(jī)型：經(jīng)典機(jī)型：經(jīng)典機(jī)型：經(jīng)典機(jī)型：Berkeley NowBerkeley Now、DigitalDigital、TouclusterToucluster等等等等 特點(diǎn)：特點(diǎn)：特點(diǎn)：特點(diǎn)：每個(gè)節(jié)點(diǎn)都是一個(gè)工作站、每個(gè)節(jié)點(diǎn)都是一個(gè)工作站、每個(gè)節(jié)點(diǎn)都是一個(gè)工作站、每個(gè)節(jié)點(diǎn)都是一個(gè)工作站、PCPC機(jī)或機(jī)或機(jī)或機(jī)或SMPSMP 各節(jié)點(diǎn)各節(jié)點(diǎn)各節(jié)點(diǎn)各節(jié)點(diǎn)由低成本網(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)、（商品網(wǎng)絡(luò)、以太網(wǎng)、FDDIFDDI等）等）等）等）各節(jié)點(diǎn)有本地磁盤各節(jié)點(diǎn)有本地磁盤各節(jié)點(diǎn)有本地磁盤各節(jié)點(diǎn)有本地磁盤 各節(jié)點(diǎn)有一完整的各節(jié)點(diǎn)有一完整的各節(jié)點(diǎn)有一完整的各節(jié)點(diǎn)有一完整的OSOS（MPPMPP中只有一個(gè)微核），整個(gè)系統(tǒng)中只有一個(gè)微核），整個(gè)系統(tǒng)中只有一個(gè)微核），整個(gè)系統(tǒng)中只有一個(gè)微核），整個(gè)系統(tǒng)是工作站是工作站是工作站是工作站UnixUnix45工作站機(jī)群COW經(jīng)典機(jī)型：Berkeley Now、Di461.2 并行計(jì)算機(jī)系統(tǒng)互連靜態(tài)互連網(wǎng)絡(luò)：靜態(tài)互連網(wǎng)絡(luò)：靜態(tài)互連網(wǎng)絡(luò)：靜態(tài)互連網(wǎng)絡(luò)：處理單元間有著處理單元間有著處理單元間有著處理單元間有著固定連接固定連接固定連接固定連接的一類網(wǎng)絡(luò)，在程序執(zhí)的一類網(wǎng)絡(luò)，在程序執(zhí)的一類網(wǎng)絡(luò)，在程序執(zhí)的一類網(wǎng)絡(luò)，在程序執(zhí)行期間，這種行期間，這種行期間，這種行期間，這種點(diǎn)到點(diǎn)的連接保持不變點(diǎn)到點(diǎn)的連接保持不變點(diǎn)到點(diǎn)的連接保持不變點(diǎn)到點(diǎn)的連接保持不變動(dòng)態(tài)網(wǎng)絡(luò)：動(dòng)態(tài)網(wǎng)絡(luò)：動(dòng)態(tài)網(wǎng)絡(luò)：動(dòng)態(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)用程序的要求動(dòng)態(tài)地動(dòng)態(tài)地動(dòng)態(tài)地動(dòng)態(tài)地改變連接組成改變連接組成改變連接組成改變連接組成 461.2 并行計(jì)算機(jī)系統(tǒng)互連靜態(tài)互連網(wǎng)絡(luò)：47靜態(tài)互連網(wǎng)絡(luò)一維線性陣列一維線性陣列一維線性陣列一維線性陣列二維網(wǎng)孔二維網(wǎng)孔二維網(wǎng)孔二維網(wǎng)孔樹形連接樹形連接樹形連接樹形連接超立方網(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動(dòng)態(tài)連接總線總線總線總線交叉開關(guān)交叉開關(guān)交叉開關(guān)交叉開關(guān)多級(jí)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)48動(dòng)態(tài)連接總線49網(wǎng)絡(luò)性能指標(biāo)網(wǎng)絡(luò)網(wǎng)絡(luò)網(wǎng)絡(luò)網(wǎng)絡(luò)直徑直徑直徑直徑對(duì)剖對(duì)剖對(duì)剖對(duì)剖寬度寬度寬度寬度49網(wǎng)絡(luò)性能指標(biāo)網(wǎng)絡(luò)直徑對(duì)剖寬度50網(wǎng)絡(luò)性能指標(biāo) 節(jié)節(jié)節(jié)節(jié)點(diǎn)點(diǎn)點(diǎn)點(diǎn)：用用用用圖圖圖圖表表表表示示示示網(wǎng)網(wǎng)網(wǎng)網(wǎng)絡(luò)絡(luò)絡(luò)絡(luò)，則則則則處處處處理理理理機(jī)機(jī)機(jī)機(jī)或或或或存存存存儲(chǔ)儲(chǔ)儲(chǔ)儲(chǔ)器器器器為為為為節(jié)節(jié)節(jié)節(jié)點(diǎn)點(diǎn)點(diǎn)點(diǎn)，連連連連接接接接為邊為邊為邊為邊 節(jié)節(jié)節(jié)節(jié)點(diǎn)點(diǎn)點(diǎn)點(diǎn)度度度度（Node Node DegreeDegree）：射射射射入入入入或或或或射射射射出出出出一一一一個(gè)個(gè)個(gè)個(gè)節(jié)節(jié)節(jié)節(jié)點(diǎn)點(diǎn)點(diǎn)點(diǎn)的的的的邊邊邊邊數(shù)數(shù)數(shù)數(shù)。在單向網(wǎng)絡(luò)中，射入和射出邊之和稱為節(jié)點(diǎn)度在單向網(wǎng)絡(luò)中，射入和射出邊之和稱為節(jié)點(diǎn)度在單向網(wǎng)絡(luò)中，射入和射出邊之和稱為節(jié)點(diǎn)度在單向網(wǎng)絡(luò)中，射入和射出邊之和稱為節(jié)點(diǎn)度 網(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ò)中中中中任任任任何何何何兩兩兩兩個(gè)個(gè)個(gè)個(gè)節(jié)節(jié)節(jié)節(jié)點(diǎn)之間的點(diǎn)之間的點(diǎn)之間的點(diǎn)之間的最長(zhǎng)距離最長(zhǎng)距離最長(zhǎng)距離最長(zhǎng)距離，即最大路徑數(shù)，即最大路徑數(shù)，即最大路徑數(shù)，即最大路徑數(shù) 對(duì)對(duì)對(duì)對(duì)剖剖剖剖寬寬寬寬度度度度（Bisection Bisection WidthWidth）：將將將將網(wǎng)網(wǎng)網(wǎng)網(wǎng)絡(luò)絡(luò)絡(luò)絡(luò)分分分分成成成成兩兩兩兩部部部部分分分分必必必必須移去的最少邊數(shù)須移去的最少邊數(shù)須移去的最少邊數(shù)須移去的最少邊數(shù) 如如如如果果果果從從從從任任任任一一一一節(jié)節(jié)節(jié)節(jié)點(diǎn)點(diǎn)點(diǎn)點(diǎn)觀觀觀觀看看看看網(wǎng)網(wǎng)網(wǎng)網(wǎng)絡(luò)絡(luò)絡(luò)絡(luò)都都都都一一一一樣樣樣樣，則則則則稱稱稱稱網(wǎng)網(wǎng)網(wǎng)網(wǎng)絡(luò)絡(luò)絡(luò)絡(luò)為為為為對(duì)對(duì)對(duì)對(duì)稱稱稱稱的的的的（SymmetrySymmetry）50網(wǎng)絡(luò)性能指標(biāo)節(jié)點(diǎn)：用圖表示網(wǎng)絡(luò)，則處理機(jī)或存儲(chǔ)器為節(jié)點(diǎn)，51靜態(tài)互連網(wǎng)絡(luò)（1）一維線性陣列（一維線性陣列（一維線性陣列（一維線性陣列（1-1-D Linear ArrayD Linear Array）：）：）：）：并行機(jī)中最簡(jiǎn)單、最基本的互連方式并行機(jī)中最簡(jiǎn)單、最基本的互連方式并行機(jī)中最簡(jiǎn)單、最基本的互連方式并行機(jī)中最簡(jiǎn)單、最基本的互連方式每個(gè)節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)只與其左、右近鄰只與其左、右近鄰只與其左、右近鄰只與其左、右近鄰相連，也叫二近相連，也叫二近相連，也叫二近相連，也叫二近鄰連接鄰連接鄰連接鄰連接節(jié)點(diǎn)度為節(jié)點(diǎn)度為節(jié)點(diǎn)度為節(jié)點(diǎn)度為直徑為直徑為直徑為直徑為對(duì)剖寬度為對(duì)剖寬度為對(duì)剖寬度為對(duì)剖寬度為2 21 1N-1N-151靜態(tài)互連網(wǎng)絡(luò)（1）一維線性陣列（1-D Linear A52一一維線性性陣列列線性連接函數(shù)：線性連接函數(shù)：線性連接函數(shù)：線性連接函數(shù)：52一維線性陣列線性連接函數(shù)：53一維線性陣列 當(dāng)首、尾節(jié)點(diǎn)相連時(shí)可構(gòu)成循環(huán)移位器，在拓?fù)浣Y(jié)當(dāng)首、尾節(jié)點(diǎn)相連時(shí)可構(gòu)成循環(huán)移位器，在拓?fù)浣Y(jié)當(dāng)首、尾節(jié)點(diǎn)相連時(shí)可構(gòu)成循環(huán)移位器，在拓?fù)浣Y(jié)當(dāng)首、尾節(jié)點(diǎn)相連時(shí)可構(gòu)成循環(huán)移位器，在拓?fù)浣Y(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é)點(diǎn)度節(jié)點(diǎn)度節(jié)點(diǎn)度節(jié)點(diǎn)度直徑直徑直徑直徑對(duì)剖寬度對(duì)剖寬度對(duì)剖寬度對(duì)剖寬度單向環(huán)單向環(huán)單向環(huán)單向環(huán)雙向環(huán)雙向環(huán)雙向環(huán)雙向環(huán)2 22 22 2N-1N-12 2雙向環(huán)雙向環(huán)單向環(huán)單向環(huán)53一維線性陣列當(dāng)首、尾節(jié)點(diǎn)相連時(shí)可構(gòu)成循環(huán)移位器，在拓?fù)浣Y(jié)54二二維網(wǎng)孔網(wǎng)孔四近鄰連接：四近鄰連接：四近鄰連接：四近鄰連接：每個(gè)節(jié)點(diǎn)只與其每個(gè)節(jié)點(diǎn)只與其每個(gè)節(jié)點(diǎn)只與其每個(gè)節(jié)點(diǎn)只與其上、下、左、右上、下、左、右上、下、左、右上、下、左、右的近的近的近的近鄰相連鄰相連鄰相連鄰相連54二維網(wǎng)孔四近鄰連接：每個(gè)節(jié)點(diǎn)只與其上、下、左、右的近鄰相55二二維網(wǎng)孔網(wǎng)孔IlliacIlliac網(wǎng)孔：網(wǎng)孔：網(wǎng)孔：網(wǎng)孔：簡(jiǎn)記為簡(jiǎn)記為簡(jiǎn)記為簡(jiǎn)記為MCMC2 2，在在在在垂直方向上帶環(huán)垂直方向上帶環(huán)垂直方向上帶環(huán)垂直方向上帶環(huán)繞繞繞繞，水平方向呈蛇狀水平方向呈蛇狀水平方向呈蛇狀水平方向呈蛇狀55二維網(wǎng)孔Illiac網(wǎng)孔：簡(jiǎn)記為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é)點(diǎn)度節(jié)點(diǎn)度節(jié)點(diǎn)度節(jié)點(diǎn)度直徑直徑直徑直徑對(duì)剖寬度對(duì)剖寬度對(duì)剖寬度對(duì)剖寬度四近鄰連接四近鄰連接四近鄰連接四近鄰連接IlliacIlliac網(wǎng)孔網(wǎng)孔2-2-D D環(huán)繞環(huán)繞4 44 457二維網(wǎng)孔4互連網(wǎng)絡(luò)節(jié)點(diǎn)度直徑對(duì)剖寬度四近鄰連接Illia58網(wǎng)孔連接 網(wǎng)孔中的網(wǎng)孔中的網(wǎng)孔中的網(wǎng)孔中的PEPE節(jié)點(diǎn)編號(hào)是按行為主順序，編號(hào)為節(jié)點(diǎn)編號(hào)是按行為主順序，編號(hào)為節(jié)點(diǎn)編號(hào)是按行為主順序，編號(hào)為節(jié)點(diǎn)編號(hào)是按行為主順序，編號(hào)為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é)點(diǎn)編號(hào)是按行為主順序，編號(hào)為0N59網(wǎng)孔連接例：例：例：例：n=16n=16時(shí)的網(wǎng)孔時(shí)的網(wǎng)孔時(shí)的網(wǎng)孔時(shí)的網(wǎng)孔0 01 12 23 34 45 56 67 78 89 910101111121213131414151559網(wǎng)孔連接例：n=16時(shí)的網(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通信功能較通信功能較通信功能較通信功能較差，在最壞情況下，任意兩個(gè)差，在最壞情況下，任意兩個(gè)差，在最壞情況下，任意兩個(gè)差，在最壞情況下，任意兩個(gè)PEPE間信息交換至少要間信息交換至少要間信息交換至少要間信息交換至少要 步。步。步。步。如如如如N=64N=64時(shí)時(shí)時(shí)時(shí) P P6363-P-P1010：P P9 9-P-P4545：63-7-8-9-1063-7-8-9-109-1-57-56-48-47-46-45網(wǎng)孔連接在MC2上61樹形連接 二叉樹連接（簡(jiǎn)記為二叉樹連接（簡(jiǎn)記為二叉樹連接（簡(jiǎn)記為二叉樹連接（簡(jiǎn)記為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樹形連接二叉樹連接（簡(jiǎn)記為TC）：P1P8P2P3P4P62樹形連接除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)相連和兩個(gè)子節(jié)點(diǎn)相連和兩個(gè)子節(jié)點(diǎn)相連和兩個(gè)子節(jié)點(diǎn)相連設(shè)二叉樹有設(shè)二叉樹有設(shè)二叉樹有設(shè)二叉樹有d d d d層，層號(hào)由根至葉子為層，層號(hào)由根至葉子為層，層號(hào)由根至葉子為層，層號(hào)由根至葉子為1d1d1d1d，則，則，則，則共有共有共有共有 個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)節(jié)點(diǎn)度為：節(jié)點(diǎn)度為：節(jié)點(diǎn)度為：節(jié)點(diǎn)度為：對(duì)剖寬度為：對(duì)剖寬度為：對(duì)剖寬度為：對(duì)剖寬度為：直徑為：直徑為：直徑為：直徑為：2 2 2 2d d d d-1-1-1-13162樹形連接除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)樹形連接的典型用法P P1 1P P8 8P P2 2P P3 3P P4 4P P5 5P P6 6P P7 7P P9 9P P1010P P1111P P1212P P1313P P1414P P1515根根根根及及及及葉葉葉葉子子子子節(jié)節(jié)節(jié)節(jié)點(diǎn)點(diǎn)點(diǎn)點(diǎn)具具具具有有有有I/OI/O功功功功能能能能，且且且且葉葉葉葉子子子子節(jié)節(jié)節(jié)節(jié)點(diǎn)點(diǎn)點(diǎn)點(diǎn)執(zhí)執(zhí)執(zhí)執(zhí)行行行行并并并并行行行行計(jì)計(jì)計(jì)計(jì)算算算算，內(nèi)節(jié)點(diǎn)內(nèi)節(jié)點(diǎn)內(nèi)節(jié)點(diǎn)內(nèi)節(jié)點(diǎn)負(fù)責(zé)負(fù)責(zé)負(fù)責(zé)負(fù)責(zé)節(jié)點(diǎn)間的通信節(jié)點(diǎn)間的通信節(jié)點(diǎn)間的通信節(jié)點(diǎn)間的通信樹樹樹樹型型型型連連連連接接接接的的的的最最最最長(zhǎng)長(zhǎng)長(zhǎng)長(zhǎng)通通通通信信信信路路路路徑徑徑徑與與與與樹樹樹樹高高高高相相相相關(guān)關(guān)關(guān)關(guān)，顯顯顯顯然然然然根根根根為為為為通通通通信信信信瓶瓶瓶瓶頸頸頸頸，因因因因此此此此使使使使用用用用X-X-樹樹樹樹，形形形形成成成成樹樹樹樹網(wǎng)網(wǎng)網(wǎng)網(wǎng)連連連連接接接接，可可可可使使使使同同同同級(jí)級(jí)級(jí)級(jí)兄兄兄兄弟弟弟弟之之之之間間間間彼此相連彼此相連彼此相連彼此相連樹形連接的典型用法P1P8P2P3P4P5P6P7P9P1064超立方體連接 一個(gè)一個(gè)一個(gè)一個(gè)n-n-立方由立方由立方由立方由 個(gè)頂點(diǎn)組成，個(gè)頂點(diǎn)組成，個(gè)頂點(diǎn)組成，個(gè)頂點(diǎn)組成，3-