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

張德富

南京大學(xué)出版社面向結(jié)構(gòu)的并行算法設(shè)計(jì)與分析李曉梅

國(guó)防科技大學(xué)出版社3教材、參考書—教材主要內(nèi)容

并行處理概論

1

并行計(jì)算性能測(cè)評(píng)

2

并行算法的一般設(shè)計(jì)方法

4

并行算法的基本設(shè)計(jì)技術(shù)5非數(shù)值并行算法

6圖論

7矩陣運(yùn)算

8

并行算法的設(shè)計(jì)基礎(chǔ)

3并行程序設(shè)計(jì)基礎(chǔ)

9主要內(nèi)容并行處理概論1并行計(jì)算性5第一章并行計(jì)算機(jī)系統(tǒng)及結(jié)構(gòu)模型1.1并行計(jì)算概論1.2并行計(jì)算機(jī)系統(tǒng)互連1.3并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)5第一章并行計(jì)算機(jī)系統(tǒng)及結(jié)構(gòu)模型1.1并行計(jì)算概論1.21.1并行計(jì)算概論并行處理的定義并行性的含義并行處理的應(yīng)用并行處理中的幾個(gè)難題61.1并行計(jì)算概論并行處理的定義671.1.1并行處理的含義發(fā)展背景：僅提高電子部件的速度來改善計(jì)算機(jī)的性能以滿足用戶越來越高的要求是不可能的。計(jì)算科學(xué)：計(jì)算物理、計(jì)算化學(xué)、計(jì)算生物等。并行處理：一種有效的強(qiáng)調(diào)開發(fā)計(jì)算過程中并行事件的信息處理方式。并行計(jì)算：并行機(jī)上的計(jì)算，又稱高性能計(jì)算（HPC)。并行計(jì)算機(jī)：為并行處理所設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)。71.1.1并行處理的含義發(fā)展背景：僅提高電子部件的速度來改8并行性的含義同時(shí)性：兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生在多個(gè)資源中并發(fā)性：兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生在多個(gè)資源中流水線：兩個(gè)或多個(gè)事件發(fā)生在可能重疊的時(shí)間內(nèi)模式：以數(shù)值計(jì)算為例計(jì)算并行性，有表達(dá)模式與遞歸模式8并行性的含義同時(shí)性：兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生在多個(gè)資源9并行性的含義例如：兩個(gè)向量的內(nèi)積：表達(dá)式形式：

9并行性的含義例如：兩個(gè)向量的內(nèi)積：10并行性的含義并行模式：x1Y1x2Y2…Xn-1Yn-1xnYn………R10并行性的含義并行模式：x1Y1x2Y2…Xn-1Yn-111并行性的含義遞歸模式：流水線模式：

*+11并行性的含義遞歸模式：*+121.1.2并行處理的應(yīng)用高速并行計(jì)算主要有三種類型的應(yīng)用需求：121.1.2并行處理的應(yīng)用高速并行計(jì)算主要有三種類型的應(yīng)13并行處理的應(yīng)用主要應(yīng)用領(lǐng)域：氣象、海洋、天體物理遙測(cè)地球資源數(shù)據(jù)處理

石油開采及管理磁聚變及核反應(yīng)堆生物及醫(yī)學(xué)工程計(jì)算社會(huì)經(jīng)濟(jì)學(xué)及政府部門國(guó)防

…13并行處理的應(yīng)用主要應(yīng)用領(lǐng)域：14氣象數(shù)值預(yù)報(bào)將地球由北至南分成2度一格，延赤道分成4度一格，將大氣層分成20層，形成一個(gè)三維網(wǎng)格。設(shè)每個(gè)網(wǎng)格上計(jì)算量約為3000次，若時(shí)間步長(zhǎng)為2分鐘，則當(dāng)給出一天的氣象預(yù)報(bào)時(shí)，總計(jì)算量為3.5×1011次。在Gray1（Gray公司的向量流水機(jī)）上進(jìn)行計(jì)算（每秒1億次浮點(diǎn)運(yùn)算，需計(jì)算1小時(shí)左右，若將網(wǎng)格邊長(zhǎng)減半，是原來計(jì)算量的8倍。14氣象數(shù)值預(yù)報(bào)將地球由北至南分成2度一格，延赤道分成4度一15海洋學(xué)、天體物理以1。為間隔的類似網(wǎng)格，用Gyber-205（美國(guó)數(shù)據(jù)控制公司CDC，1982，52位4億次每秒，400mflops的流水線機(jī)）對(duì)太平洋50年作一次完整模擬要1000小時(shí)。模擬地球等行星的形成過程，其動(dòng)態(tài)范圍從毫秒到幾十億，ILLIAC-V陣列處理機(jī)（美國(guó)Illiniosuinv,1973,64個(gè)PE主存13萬字，1.5億次每秒的陣列機(jī)）曾用于這一方面的研究。15海洋學(xué)、天體物理以1。為間隔的類似網(wǎng)格，用Gyber-216遙測(cè)地球資源數(shù)據(jù)處理大量衛(wèi)星圖像資料處理。陸地探測(cè)衛(wèi)星的一張圖像有3千萬個(gè)字符，覆蓋美國(guó)Alabama州需要13幅這樣的圖像，每15天產(chǎn)生一次新的圖像，計(jì)算量很大。美國(guó)宇航局訂購了并行處理機(jī)MPP（美國(guó)GoodyearAerospace，1979，128×128PES），最高速度每秒60億次8位整數(shù)運(yùn)算，能提供實(shí)時(shí)的情景分析。16遙測(cè)地球資源數(shù)據(jù)處理大量衛(wèi)星圖像資料處理。陸地探測(cè)衛(wèi)星的17石油開采及管理地震探測(cè)

1985年，我國(guó)南海西部石油公司向美國(guó)訂購PE3230MPS并行處理計(jì)算機(jī)。地震數(shù)據(jù)處理費(fèi)用占地震探測(cè)總費(fèi)用的10%，地震數(shù)據(jù)相當(dāng)多，僅1979年就有1015位地震數(shù)據(jù)處理。美國(guó)休斯頓一家地球物理公司存儲(chǔ)的地球地震數(shù)據(jù)有200萬個(gè)磁帶卷。17石油開采及管理地震探測(cè)18石油開采及管理儲(chǔ)油層模型的建立

SOHO公司用Cyber-203（CDC）建立波羅的海灣油田數(shù)值模擬器，包括1000個(gè)油井，一個(gè)需一年模擬實(shí)驗(yàn)的工作量，在Cyber-203僅用33分鐘即可完成。18石油開采及管理儲(chǔ)油層模型的建立19工程計(jì)算水壩、橋梁、船只、超音速飛機(jī)、高層建筑、太空飛行器設(shè)計(jì)需解大型偏微分方程組和代數(shù)方程組，可以用并行處理機(jī)提高設(shè)計(jì)效率。在空氣動(dòng)力學(xué)計(jì)算中美國(guó)航天局Ames研究中心用超級(jí)計(jì)算機(jī)作風(fēng)洞實(shí)驗(yàn)三級(jí)模擬。由Burroughs公司及CDC公司推出“數(shù)值航空動(dòng)力學(xué)模擬設(shè)備“（NAFS）的兩臺(tái)10億次超級(jí)計(jì)算機(jī)可以模擬完整的飛機(jī)設(shè)計(jì)。19工程計(jì)算水壩、橋梁、船只、超音速飛機(jī)、高層建筑、太空飛行20社會(huì)經(jīng)濟(jì)學(xué)及政府部門計(jì)量經(jīng)濟(jì)學(xué)、社會(huì)工程、政府人口普查、犯罪控制2000年世界經(jīng)濟(jì)模型構(gòu)造等計(jì)算的計(jì)算量大，需并行計(jì)算。諾貝爾獎(jiǎng)學(xué)金獲得者W.W.Leontief1980年提出一個(gè)世界經(jīng)濟(jì)輸入/輸出模型，在CDC科學(xué)計(jì)算機(jī)上運(yùn)算，認(rèn)為一個(gè)以部分裁軍為特征的國(guó)際性經(jīng)濟(jì)關(guān)系系統(tǒng)，可以縮小貧富國(guó)家的差距，該項(xiàng)目受到聯(lián)合國(guó)支持。美國(guó)使用大型計(jì)算機(jī)控制犯罪、收稅與審計(jì)，進(jìn)行人口普查及民意測(cè)驗(yàn)。過去美國(guó)制造的大型計(jì)算機(jī)57%由政府使用。20社會(huì)經(jīng)濟(jì)學(xué)及政府部門計(jì)量經(jīng)濟(jì)學(xué)、社會(huì)工程、政府人口普查、21國(guó)防、人工智能、基礎(chǔ)研究國(guó)防軍事部門使用現(xiàn)存的大部分超級(jí)計(jì)算機(jī)，如Cray-1多用于彈頭核武器設(shè)計(jì)。在關(guān)聯(lián)處理機(jī)上為反彈道導(dǎo)彈程序處理雷達(dá)信號(hào)，用S-1多處理機(jī)做反潛艇海洋監(jiān)視。21國(guó)防、人工智能、基礎(chǔ)研究國(guó)防22國(guó)防、人工智能、基礎(chǔ)研究人工智能圖像處理模式識(shí)別計(jì)算機(jī)視覺自然語言理解機(jī)器推理智能機(jī)器人專家系統(tǒng)知識(shí)工程基礎(chǔ)研究計(jì)算化學(xué)計(jì)算物理計(jì)算幾何VLSI輔助設(shè)計(jì)22國(guó)防、人工智能、基礎(chǔ)研究人工智能23當(dāng)代科學(xué)與工程問題的計(jì)算需求評(píng)測(cè)計(jì)算機(jī)性能的指標(biāo)70年代Mflops106

百萬現(xiàn)在Pflops1015

千萬億次90年代Tflops1012

萬億80年代Gflops109

十億世界上第一臺(tái)峰值速度超過1Tflops的高性能計(jì)算機(jī)是由Intel公司于1996年12月研制成功的。23當(dāng)代科學(xué)與工程問題的計(jì)算需求評(píng)測(cè)計(jì)算機(jī)性能的指標(biāo)70年代24當(dāng)代科學(xué)與工程問題的計(jì)算需求美國(guó)HPCC計(jì)劃（HighPerformanceComputing&Communication）為了保持美國(guó)的世界領(lǐng)先地位，1993年，美國(guó)科學(xué)、工程、技術(shù)聯(lián)邦協(xié)調(diào)理事會(huì)的國(guó)會(huì)提出了題為“重大挑戰(zhàn)項(xiàng)目：高性能計(jì)算與通信”的報(bào)告，簡(jiǎn)稱HPCC計(jì)劃3T性能目標(biāo)

Tflops計(jì)算能力、1TB主存容量、1TB/s的I/O帶寬24當(dāng)代科學(xué)與工程問題的計(jì)算需求美國(guó)HPCC計(jì)劃（High25HPCC應(yīng)用領(lǐng)域高速民航用計(jì)算流體動(dòng)力學(xué)來研制超音速噴氣發(fā)動(dòng)機(jī)新藥設(shè)計(jì)研制癌癥和艾滋病的藥物催化作用仿生催化劑計(jì)算機(jī)建模，分析合成過程中酶的作用燃料燃燒通過化學(xué)動(dòng)力學(xué)，揭示流體力學(xué)的作用，設(shè)計(jì)新型發(fā)動(dòng)機(jī)海洋建模對(duì)海洋活動(dòng)與大氣流的熱交換進(jìn)行整體海洋模擬大氣污染對(duì)大氣質(zhì)量模型進(jìn)行模擬研究，揭示其物理和化學(xué)機(jī)理蛋白質(zhì)結(jié)構(gòu)設(shè)計(jì)使用計(jì)算機(jī)模擬，對(duì)蛋白質(zhì)組成的三維結(jié)構(gòu)進(jìn)行研究圖像理解實(shí)時(shí)繪制圖像或動(dòng)畫密碼破譯破譯由長(zhǎng)位數(shù)組成的密碼，求找該數(shù)的兩個(gè)乘積因子1994年4月26日，美國(guó)宣布破譯了世界上最長(zhǎng)的RSA129密碼，在因特網(wǎng)上使用1600臺(tái)計(jì)算機(jī)，600多人工作8個(gè)月，破譯了129位數(shù)字組成的密碼25HPCC應(yīng)用領(lǐng)域高速民航用計(jì)算流體動(dòng)力學(xué)來研制超音速噴氣26科學(xué)計(jì)算的需要26科學(xué)計(jì)算的需要27當(dāng)代科學(xué)與工程問題的計(jì)算需求美國(guó)ASCI計(jì)劃（AcceleratedStrategicComputingInitiative）全面禁止核實(shí)驗(yàn)條約簽訂后，1996年6月能源部聯(lián)合美國(guó)三大武器實(shí)驗(yàn)室共同提出了“加速戰(zhàn)略計(jì)劃創(chuàng)新”，簡(jiǎn)稱為ASCI計(jì)劃27當(dāng)代科學(xué)與工程問題的計(jì)算需求美國(guó)ASCI計(jì)劃（Accel28美國(guó)ASCI計(jì)劃目的通過數(shù)值模擬，評(píng)估核武器的性能、安全性、可靠性等，達(dá)到高分辨率、高逼真度、三維、全物理、全系統(tǒng)的規(guī)模和能力，該計(jì)劃被認(rèn)為是與當(dāng)年曼哈頓計(jì)劃等同的一個(gè)巨大的挑戰(zhàn)。平臺(tái)三大核武器實(shí)驗(yàn)室向三大公司（Intel，IBM和SGI/Cray）預(yù)訂了峰值超過1Tflops的并行計(jì)算機(jī)，預(yù)計(jì)2003年使用運(yùn)算100Tflops，50TB存儲(chǔ)容量，I/O傳輸速率為5000GB/s的并行機(jī)28美國(guó)ASCI計(jì)劃29并行處理中的幾個(gè)難題任務(wù)分配非常困難考慮時(shí)空復(fù)雜度，還需考慮模塊之間的通信量很難擺脫串行處理方式的約束軟件和算法大都是按照串行結(jié)構(gòu)設(shè)計(jì)的現(xiàn)有的算法語言對(duì)并行性限制很大現(xiàn)有語言以VonNeumann方式為基礎(chǔ)，對(duì)并行性限

制嚴(yán)重：語句執(zhí)行結(jié)果、執(zhí)行順序與前面結(jié)果和狀態(tài)相關(guān)大量賦值語句使得處理器與存儲(chǔ)器頻繁交換信息，

降低系統(tǒng)效率29并行處理中的幾個(gè)難題任務(wù)分配非常困難30并行處理中的幾個(gè)難題VonNeumann模式一直伴隨著并行機(jī)未擺脫以指令流為主導(dǎo)的VonNeumann模式，由于指令相關(guān)及地址空間相關(guān)，使并行受到制約處理機(jī)間的通訊開銷使并行處理技術(shù)可能得不償失

并行處理技術(shù)的主要難點(diǎn)在于軟件串行機(jī)中軟件好壞對(duì)于工作性能影響2-3倍，并行計(jì)算機(jī)中卻是50-100倍，而且最困難的在于并行編譯程序30并行處理中的幾個(gè)難題VonNeumann模式一直伴隨著傳統(tǒng)VonNeumann結(jié)構(gòu)及其存在問題存儲(chǔ)程序控制方式31存儲(chǔ)器指令寄存器、計(jì)數(shù)器存儲(chǔ)器指令數(shù)據(jù)指令流驅(qū)動(dòng)傳統(tǒng)VonNeumann結(jié)構(gòu)及其存在問題存儲(chǔ)程序控制方式332研究并行處理應(yīng)考慮的幾個(gè)問題算法、體系結(jié)構(gòu)、高級(jí)語言三者之間的關(guān)系應(yīng)考慮：對(duì)于一些特定的計(jì)算機(jī)如何設(shè)計(jì)軟件對(duì)于一個(gè)給定的程序如何使之結(jié)構(gòu)化以便在給定的計(jì)算機(jī)上處理對(duì)于一個(gè)給定的計(jì)算機(jī)和一組應(yīng)用軟件怎樣設(shè)計(jì)語言及編譯系統(tǒng)對(duì)于給定的計(jì)算機(jī)、語言及編譯系統(tǒng)如何設(shè)計(jì)算法與程序32研究并行處理應(yīng)考慮的幾個(gè)問題算法、體系結(jié)構(gòu)、高級(jí)語言三者33并行處理機(jī)系統(tǒng)的優(yōu)點(diǎn)具有很高的性能價(jià)格比由于系統(tǒng)的模塊性，使之便于維護(hù)具有較高的可靠性具有較高的處理速度結(jié)構(gòu)的靈活性便于VLSI實(shí)現(xiàn)33并行處理機(jī)系統(tǒng)的優(yōu)點(diǎn)具有很高的性能價(jià)格比341.1.3并行處理機(jī)的分類1342341.1.3并行處理機(jī)的分類134235Flynn分類法單指令流單數(shù)據(jù)流SISD單指令流多數(shù)據(jù)流SIMD多指令流單數(shù)據(jù)流MISD（實(shí)際不存在）多指令流多數(shù)據(jù)流MIMD35Flynn分類法單指令流單數(shù)據(jù)流SISD36SISDCUPUMMISDSISCU：控制單元PU：處理單元MM：存儲(chǔ)器IS：指令流DS：數(shù)據(jù)流36SISDCUPUMMISDSISCU：控制單元PU37SIMDCUPU1ISPU2PUn…MM1MM2MMn…DS1DS2DSnIS37SIMDCUPU1ISPU2PUn…MM1MM2MMn…38MIMDPU1PU2PUn…MM1MM2MMn…DS1DS2DSnIS1IS2ISnCU1CU2CUn…IS1IS2ISn38MIMDPU1PU2PUn…MM1MM2MMn…DS1D39Handler分類法1977年，Handler根據(jù)計(jì)算機(jī)系統(tǒng)中流水線和并行度出現(xiàn)的級(jí)別，將一臺(tái)計(jì)算機(jī)表示為三對(duì)整數(shù)：

CPU數(shù)目能執(zhí)行流水線的CPU數(shù)目CPU所控制的ALU數(shù)目

能執(zhí)行流水線的ALU數(shù)目ALU或PE中的位數(shù)ALU或PE中流水線的位數(shù)39Handler分類法1977年，Handler根據(jù)計(jì)算機(jī)40按體系結(jié)構(gòu)分類同步系統(tǒng)向量流水機(jī)陣列處理機(jī)：（含心動(dòng)陣列）SIMD關(guān)聯(lián)處理機(jī)：具有聯(lián)想存儲(chǔ)、按內(nèi)容存取、邏輯操作等多處理機(jī)系統(tǒng)MIMD:由獨(dú)立執(zhí)行指令的處理器構(gòu)成分布存儲(chǔ)系統(tǒng)：每個(gè)結(jié)點(diǎn)有獨(dú)立的存儲(chǔ)單元共享存儲(chǔ)系統(tǒng)MIMD變體（MIMD/SIMD混合型）40按體系結(jié)構(gòu)分類同步系統(tǒng)41現(xiàn)代并行機(jī)結(jié)構(gòu)分類SIMDPVP并行向量處理機(jī)SMP對(duì)稱多處理機(jī)MPP大規(guī)模并行處理機(jī)DSM分布式共享存儲(chǔ)多處理機(jī)COW工作站機(jī)群GrayC-90GrayT-90銀河1號(hào)41現(xiàn)代并行機(jī)結(jié)構(gòu)分類SIMDGrayC-9042對(duì)稱多處理機(jī)SMPIBMR50、SGIPowerChakenge、曙光1號(hào)使用商用微處理的芯片，由高速總線連向共享存儲(chǔ)器，對(duì)稱性共享存儲(chǔ)，PE個(gè)數(shù)不能太多。系統(tǒng)是對(duì)稱的，每個(gè)處理器可等同的訪問共享存儲(chǔ)，I/O設(shè)備。42對(duì)稱多處理機(jī)SMPIBMR50、SGIPower43大規(guī)模并行處理機(jī)MPP經(jīng)典機(jī)型：IBMSP2、IntelParagon、IntelTFLOPS、曙光1000等。特性：節(jié)點(diǎn)為微處理器物理上的分布存儲(chǔ)高帶寬、低延遲的網(wǎng)絡(luò)成百上千個(gè)PE異步MIMD，程序由多個(gè)進(jìn)程組成，每個(gè)進(jìn)程有私有空間，進(jìn)程間采用消息傳遞的方式43大規(guī)模并行處理機(jī)MPP經(jīng)典機(jī)型：IBMSP2、Inte44分布式共享存儲(chǔ)多處理機(jī)DSM經(jīng)典機(jī)型：CrayT3D、SGI/GrayOrigin2000特點(diǎn)：分布在各個(gè)節(jié)點(diǎn)上的局存形成了一個(gè)共享的存儲(chǔ)器與SIMD相同，在物理上有分布在各點(diǎn)的共享主存，但采用單一地址空間，與MPP相比，易于編程44分布式共享存儲(chǔ)多處理機(jī)DSM經(jīng)典機(jī)型：CrayT3D、45工作站機(jī)群COW經(jīng)典機(jī)型：BerkeleyNow、Digital、Toucluster等特點(diǎn)：每個(gè)節(jié)點(diǎn)都是一個(gè)工作站、PC機(jī)或SMP各節(jié)點(diǎn)由低成本網(wǎng)絡(luò)相連（商品網(wǎng)絡(luò)、以太網(wǎng)、FDDI等）各節(jié)點(diǎn)有本地磁盤各節(jié)點(diǎn)有一完整的OS（MPP中只有一個(gè)微核），整個(gè)系統(tǒng)是工作站Unix45工作站機(jī)群COW經(jīng)典機(jī)型：BerkeleyNow、Di461.2并行計(jì)算機(jī)系統(tǒng)互連靜態(tài)互連網(wǎng)絡(luò)：處理單元間有著固定連接的一類網(wǎng)絡(luò)，在程序執(zhí)行期間，這種點(diǎn)到點(diǎn)的連接保持不變動(dòng)態(tài)網(wǎng)絡(luò)：用交換開關(guān)構(gòu)成的，可按應(yīng)用程序的要求動(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)絡(luò)立方環(huán)洗牌交換網(wǎng)蝶形網(wǎng)絡(luò)…47靜態(tài)互連網(wǎng)絡(luò)一維線性陣列48動(dòng)態(tài)連接總線交叉開關(guān)多級(jí)互連網(wǎng)絡(luò)…48動(dòng)態(tài)連接總線49網(wǎng)絡(luò)性能指標(biāo)網(wǎng)絡(luò)直徑對(duì)剖寬度49網(wǎng)絡(luò)性能指標(biāo)網(wǎng)絡(luò)直徑對(duì)剖寬度50網(wǎng)絡(luò)性能指標(biāo)節(jié)點(diǎn)：用圖表示網(wǎng)絡(luò)，則處理機(jī)或存儲(chǔ)器為節(jié)點(diǎn)，連接為邊節(jié)點(diǎn)度（NodeDegree）：射入或射出一個(gè)節(jié)點(diǎn)的邊數(shù)。在單向網(wǎng)絡(luò)中，射入和射出邊之和稱為節(jié)點(diǎn)度網(wǎng)絡(luò)直徑（NetworkDiameter）：

網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)之間的最長(zhǎng)距離，即最大路徑數(shù)對(duì)剖寬度（BisectionWidth）：將網(wǎng)絡(luò)分成兩部分必須移去的最少邊數(shù)如果從任一節(jié)點(diǎn)觀看網(wǎng)絡(luò)都一樣，則稱網(wǎng)絡(luò)為對(duì)稱的（Symmetry）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-DLinearArray）：并行機(jī)中最簡(jiǎn)單、最基本的互連方式每個(gè)節(jié)點(diǎn)只與其左、右近鄰相連，也叫二近鄰連接節(jié)點(diǎn)度為直徑為對(duì)剖寬度為21N-151靜態(tài)互連網(wǎng)絡(luò)（1）一維線性陣列（1-DLinearA52一維線性陣列線性連接函數(shù)：52一維線性陣列線性連接函數(shù)：53一維線性陣列當(dāng)首、尾節(jié)點(diǎn)相連時(shí)可構(gòu)成循環(huán)移位器，在拓?fù)浣Y(jié)構(gòu)上等同于環(huán)，環(huán)可以是雙向的或單向的互連網(wǎng)絡(luò)節(jié)點(diǎn)度直徑對(duì)剖寬度單向環(huán)雙向環(huán)222N-12雙向環(huán)單向環(huán)53一維線性陣列當(dāng)首、尾節(jié)點(diǎn)相連時(shí)可構(gòu)成循環(huán)移位器，在拓?fù)浣Y(jié)54二維網(wǎng)孔四近鄰連接：每個(gè)節(jié)點(diǎn)只與其上、下、左、右的近鄰相連54二維網(wǎng)孔四近鄰連接：每個(gè)節(jié)點(diǎn)只與其上、下、左、右的近鄰相55二維網(wǎng)孔Illiac網(wǎng)孔：簡(jiǎn)記為MC2，在垂直方向上帶環(huán)繞，水平方向呈蛇狀55二維網(wǎng)孔Illiac網(wǎng)孔：簡(jiǎn)記為MC2，在垂直方向上帶環(huán)56二維網(wǎng)孔2-D環(huán)繞：垂直和水平方向均帶環(huán)繞56二維網(wǎng)孔2-D環(huán)繞：垂直和水平方向均帶環(huán)繞57二維網(wǎng)孔4互連網(wǎng)絡(luò)節(jié)點(diǎn)度直徑對(duì)剖寬度四近鄰連接Illiac網(wǎng)孔2-D環(huán)繞4457二維網(wǎng)孔4互連網(wǎng)絡(luò)節(jié)點(diǎn)度直徑對(duì)剖寬度四近鄰連接Illia58網(wǎng)孔連接網(wǎng)孔中的PE節(jié)點(diǎn)編號(hào)是按行為主順序，編號(hào)為0～N-1連接函數(shù)：012345678910111213141558網(wǎng)孔連接網(wǎng)孔中的PE節(jié)點(diǎn)編號(hào)是按行為主順序，編號(hào)為0～N59網(wǎng)孔連接例：n=16時(shí)的網(wǎng)孔012345678910111213141559網(wǎng)孔連接例：n=16時(shí)的網(wǎng)孔012345678910119-1-57-56-48-47-46-45網(wǎng)孔連接在MC2上已經(jīng)有許多有效的并行算法，但MC2通信功能較差，在最壞情況下，任意兩個(gè)PE間信息交換至少要步。如N=64時(shí)P63-P10：P9-P45：63-7-8-9-109-1-57-56-48-47-46-45網(wǎng)孔連接在MC2上61樹形連接二叉樹連接（簡(jiǎn)記為TC）：P1P8P2P3P4P5P6P7P9P10P11P12P13P14P1561樹形連接二叉樹連接（簡(jiǎn)記為TC）：P1P8P2P3P4P62樹形連接除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)相連設(shè)二叉樹有d層，層號(hào)由根至葉子為1~d，則共有個(gè)節(jié)點(diǎn)節(jié)點(diǎn)度為：對(duì)剖寬度為：直徑為：2d-13162樹形連接除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)樹形連接的典型用法P1P8P2P3P4P5P6P7P9P10P11P12P13P14P15根及葉子節(jié)點(diǎn)具有I/O功能，且葉子節(jié)點(diǎn)執(zhí)行并行計(jì)算，內(nèi)節(jié)點(diǎn)負(fù)責(zé)節(jié)點(diǎn)間的通信樹型連接的最長(zhǎng)通信路徑與樹高相關(guān)，顯然根為通信瓶頸，因此使用X-樹，形成樹網(wǎng)連接，可使同級(jí)兄弟之間彼此相連樹形連接的典型用法P1P8P2P3P4P5P6P7P9P1064超立方體連接一個(gè)n-立方由個(gè)頂點(diǎn)組成，3-立方如圖(a)所示；4-立方如圖(b)所示，由兩個(gè)3-立方的對(duì)應(yīng)頂點(diǎn)連接而成。n-立方的節(jié)點(diǎn)度為，網(wǎng)絡(luò)直徑也是

，而對(duì)剖寬度為nn64超立方體連接一個(gè)n-立方由個(gè)頂點(diǎn)組成，365超立方體連接如果將3-立方的每個(gè)頂點(diǎn)代之以一個(gè)環(huán)就構(gòu)成了如圖(d)所示的3-立方環(huán)，此時(shí)每個(gè)頂點(diǎn)的度為3，而不像超立方那樣節(jié)點(diǎn)度為n。65超立方體連接如果將3-立方的每個(gè)頂點(diǎn)代之以一個(gè)環(huán)就構(gòu)成了66立方環(huán)連接（環(huán)型嵌入超立方體）BRGC編碼（二進(jìn)制反射格雷碼）在2n個(gè)數(shù)中，相鄰兩數(shù)只有一位二進(jìn)制代碼不同n=1:01n=2:00011110即0132n=3:000001011010110111101100i01234567G(i)01326754環(huán)上號(hào)為i的處理機(jī)對(duì)應(yīng)立方環(huán)上號(hào)為G(i)的處理機(jī)66立方環(huán)連接（環(huán)型嵌入超立方體）BRGC編碼（二進(jìn)制反射格67立方環(huán)連接12345670i01234567G(i)0132675467立方環(huán)連接12345670i01234567G(i)0168二進(jìn)制碼與格雷碼二進(jìn)制編碼B=bmbm-1…b2b1格雷碼G=gmgm-1…g2g1二進(jìn)制碼轉(zhuǎn)換成格雷碼：

格雷碼轉(zhuǎn)換成二進(jìn)制碼：68二進(jìn)制碼與格雷碼二進(jìn)制編碼B=bmbm-1…b2b169二進(jìn)制編碼與格雷編碼十進(jìn)制數(shù)二進(jìn)制格雷碼00000000010001000120010001130011001040100011050101011160110010170111010081000110091001110110101011111110111110121100101013110110111411101001151111100069二進(jìn)制編碼與格雷編碼十進(jìn)制數(shù)二進(jìn)制格雷碼0000000070立方環(huán)連接1981年由Preparato等人提出立方環(huán)連接，簡(jiǎn)記為CCC，將立方體的每一個(gè)頂點(diǎn)由一個(gè)環(huán)代之，使每個(gè)頂點(diǎn)的度不大于3。例如以四個(gè)結(jié)點(diǎn)組成的一個(gè)環(huán)，此時(shí)立方環(huán)中有32個(gè)結(jié)點(diǎn)，n=32,q=5,r=2。頂點(diǎn)號(hào)一般表示為(k,i)，其中k為三位二進(jìn)制數(shù)，決定環(huán)號(hào)，i為兩位二進(jìn)制數(shù)，決定向外的連接。與頂點(diǎn)(k,i)相連的另一頂點(diǎn)為(k(i),i)。70立方環(huán)連接1981年由Preparato等人提出立方環(huán)連71立方環(huán)連接例1：編號(hào)為30的處理機(jī)

30=（11110）2

k=111i=10

k(i)=011

30是環(huán)號(hào)為7上的第2個(gè)頂點(diǎn)，連向第3個(gè)環(huán)的第2個(gè)頂點(diǎn)1471立方環(huán)連接例1：編號(hào)為30的處理機(jī)72立方環(huán)連接例2：編號(hào)為25的處理機(jī)

25=（11001）2

k=110i=01

k(i)=100

25是環(huán)號(hào)為6上的第1個(gè)頂點(diǎn)，連向第4個(gè)環(huán)的第1個(gè)頂

17例3：編號(hào)為27的處理機(jī)

27=（11011）2

k=110i=11

k(i)不存在

27是環(huán)號(hào)為6上的第3個(gè)頂點(diǎn)，無連接頂點(diǎn)72立方環(huán)連接例2：編號(hào)為25的處理機(jī)73網(wǎng)絡(luò)名稱網(wǎng)絡(luò)規(guī)模節(jié)點(diǎn)度網(wǎng)絡(luò)直徑對(duì)剖寬度對(duì)稱鏈路數(shù)線性陣列21非環(huán)形2（雙向）2是2-D網(wǎng)孔

4非Illiac網(wǎng)孔

4非2-D環(huán)繞4是二叉樹31非星形2非超立方

nn是立方環(huán)3是靜態(tài)互連網(wǎng)絡(luò)特性比較73網(wǎng)絡(luò)名稱網(wǎng)絡(luò)規(guī)模節(jié)點(diǎn)度網(wǎng)絡(luò)直徑對(duì)剖寬度對(duì)稱鏈路數(shù)線性陣列74洗牌交換網(wǎng)絡(luò)洗牌網(wǎng)絡(luò)：

SH(Pm-1Pm-2…P1P0)=Pm-2Pm-3…P0Pm-1例對(duì)8個(gè)對(duì)象的洗牌連接：

0134526701345267循環(huán)左移1位74洗牌交換網(wǎng)絡(luò)洗牌網(wǎng)絡(luò)：0134526701345267循75交換網(wǎng)絡(luò)洗牌網(wǎng)絡(luò)往往不夠充分，因此常與交換連接一起使用EX(Pm-1Pm-2…P1P0)=Pm-1Pm-2…P1P’0例對(duì)8個(gè)對(duì)象的交換連接：013452670134526775交換網(wǎng)絡(luò)洗牌網(wǎng)絡(luò)往往不夠充分，因此常與交換連接一起使用0洗牌交換網(wǎng)絡(luò)12345670當(dāng)n=8時(shí)SH(p)=(0)(1,2,4)(3,6,5)(7)EX(p(=(0,1)(2,3)(4,5)(6,7)洗牌交換網(wǎng)絡(luò)1234567077逆洗牌交換網(wǎng)絡(luò)UNSH(Pm-1Pm-2…P1P0)=P0Pm-1…P2P1例對(duì)8個(gè)對(duì)象的逆洗牌連接：013452670134526777逆洗牌交換網(wǎng)絡(luò)UNSH(Pm-1Pm-2…P1P0)=78逆洗牌交換網(wǎng)絡(luò)12345670例對(duì)8個(gè)對(duì)象的逆洗牌交換連接：78逆洗牌交換網(wǎng)絡(luò)12345670動(dòng)態(tài)互連網(wǎng)絡(luò)公共總線交叉開關(guān)多級(jí)互連網(wǎng)絡(luò)79互連網(wǎng)絡(luò)中最簡(jiǎn)單的一種連接動(dòng)態(tài)互連網(wǎng)絡(luò)公共總線79互連網(wǎng)絡(luò)中最簡(jiǎn)單的一種連接80公共總線總線是連接處理器、存儲(chǔ)模塊和I/O設(shè)備的一組導(dǎo)線和插座，實(shí)現(xiàn)它們之間的數(shù)據(jù)傳輸公共總線：所有PE及存儲(chǔ)模塊排在同一總線上，彼此以均等競(jìng)爭(zhēng)的方式使用總線，會(huì)出現(xiàn)沖突現(xiàn)象改進(jìn)：多總線、多級(jí)總線、多維總線、分時(shí)總線等PcachePcachePcacheMMM80公共總線總線是連接處理器、存儲(chǔ)模塊和I/O設(shè)備的一組導(dǎo)線81交叉開關(guān)（Croosbar）一種高帶寬網(wǎng)絡(luò)，是互連結(jié)構(gòu)中功能最強(qiáng)的連接方式單級(jí)交換網(wǎng)絡(luò)，可為每個(gè)端口提供更高的帶寬。象電話交換機(jī)一樣，交叉點(diǎn)開關(guān)可由程序控制動(dòng)態(tài)設(shè)置其處于“開”或“關(guān)”狀態(tài)，而能提供所有（源、目的）對(duì)之間的動(dòng)態(tài)連接。P0P1MMSSSS81交叉開關(guān)（Croosbar）一種高帶寬網(wǎng)絡(luò)，是互連結(jié)構(gòu)中82交叉開關(guān)（Croosbar）交叉開關(guān)一般有兩種使用方式：一種是用于對(duì)稱的多處理機(jī)或多計(jì)算機(jī)機(jī)群中的處理器間的通信另一種是用于SMP服務(wù)器或向量超級(jí)計(jì)算機(jī)中處理器和存儲(chǔ)器之間的存取P0P1MMSSSS每一列只能接通一個(gè)交叉點(diǎn)開關(guān)82交叉開關(guān)（Croosbar）交叉開關(guān)一般有兩種使用方式：83多級(jí)互連網(wǎng)絡(luò)單級(jí)互連網(wǎng)絡(luò)的局限性:只能實(shí)現(xiàn)有限幾種連接，并不能實(shí)現(xiàn)任意處理機(jī)之間的連接。完全交叉開關(guān)網(wǎng)絡(luò)雖然可以實(shí)現(xiàn)，但結(jié)構(gòu)復(fù)雜，價(jià)格昂貴，適用于處理器數(shù)目不多的系統(tǒng)。解決辦法:多級(jí)互連網(wǎng)絡(luò)

83多級(jí)互連網(wǎng)絡(luò)單級(jí)互連網(wǎng)絡(luò)的局限性:84多級(jí)互連網(wǎng)絡(luò)單級(jí)交叉開關(guān)級(jí)聯(lián)起來形成多級(jí)互連網(wǎng)絡(luò)MIN（MultistageInterconnectionNetwork）優(yōu)點(diǎn)：速度快，靈活性好，傳輸率低于完全開關(guān)網(wǎng)絡(luò)，適用于PE較多的情形84多級(jí)互連網(wǎng)絡(luò)單級(jí)交叉開關(guān)級(jí)聯(lián)起來形成多級(jí)互連網(wǎng)絡(luò)MIN（85多級(jí)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)的性能反映在三個(gè)方面：交換開關(guān)拓?fù)浣Y(jié)構(gòu)控制方式85多級(jí)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)的性能反映在三個(gè)方面：86多級(jí)互連網(wǎng)絡(luò)-交換開關(guān)交換開關(guān)：由2×2的交叉開關(guān)構(gòu)成，具有兩個(gè)輸入和兩個(gè)輸出的交換單元四種關(guān)聯(lián)狀態(tài)：直連、交換、下播和上播

兩功能單元:僅包含直連和交換功能四功能單元:包含全部四種功能86多級(jí)互連網(wǎng)絡(luò)-交換開關(guān)交換開關(guān)：由2×2的交叉開關(guān)構(gòu)成，87多級(jí)互連網(wǎng)絡(luò)-拓?fù)浣Y(jié)構(gòu)若N為輸入端數(shù)，則多級(jí)網(wǎng)絡(luò)一般有l(wèi)og2N級(jí)，每一級(jí)使用N/2個(gè)開關(guān)單元。拓?fù)浣Y(jié)構(gòu)：網(wǎng)絡(luò)中每級(jí)的輸出與下一級(jí)的輸入之間如何連接87多級(jí)互連網(wǎng)絡(luò)-拓?fù)浣Y(jié)構(gòu)若N為輸入端數(shù)，則多級(jí)網(wǎng)絡(luò)一般有l(wèi)88多級(jí)互連網(wǎng)絡(luò)-控制方式幾個(gè)互連函數(shù)：設(shè)C=(bn…,bk+1,bk,bk-1,…b2,b1)蝶形排列：(k)(C)=(bn…,bk+1,b1,bk-1,…b2,bk)混洗：(k)(C)=(bn…,bk+1,bk-1,…b2,b1,bk)交換：E(k)(C)=(bn…,bk+1,b’k,bk-1,…b2,b1)88多級(jí)互連網(wǎng)絡(luò)-控制方式幾個(gè)互連函數(shù)：89多級(jí)互連網(wǎng)絡(luò)例對(duì)8個(gè)對(duì)象的多級(jí)互連—E(2)連接：013452670134526789多級(jí)互連網(wǎng)絡(luò)例對(duì)8個(gè)對(duì)象的多級(jí)互連—E(2)連接：0190多級(jí)互連網(wǎng)絡(luò)例對(duì)8個(gè)對(duì)象的多級(jí)互連—(2)連接：013452670134526790多級(jí)互連網(wǎng)絡(luò)例對(duì)8個(gè)對(duì)象的多級(jí)互連—(2)連接：0191多級(jí)互連網(wǎng)絡(luò)例對(duì)8個(gè)對(duì)象的多級(jí)互連—(3)連接：013452670134526791多級(jí)互連網(wǎng)絡(luò)例對(duì)8個(gè)對(duì)象的多級(jí)互連—(3)連接：01思考題0134526701345267E(1)E(1)E(1)(2)(3)-101345267021345670213456707415026307415263思考題0134526701345267E(1)E(1)E(1931.3并行處理機(jī)的系統(tǒng)結(jié)構(gòu)并行計(jì)算機(jī)結(jié)構(gòu)SIMDPVPSMPMPPDSMCOW并行計(jì)算機(jī)訪存模型UMANUMACOMACC-NUMANORMA931.3并行處理機(jī)的系統(tǒng)結(jié)構(gòu)并行計(jì)算機(jī)結(jié)構(gòu)SIMD并行計(jì)941.3.1并行向量處理機(jī)PVPParallelVectorProcessor，典型的并行向量處理機(jī)的結(jié)構(gòu)如圖：無cache，使用大量的向量寄存器及指令緩沖器系統(tǒng)中使用了高帶寬的交叉開關(guān)網(wǎng)絡(luò)，存儲(chǔ)器可達(dá)每秒兆字節(jié)的速度VPVPVPSMSMSM交叉開關(guān)941.3.1并行向量處理機(jī)PVPParallelVect95對(duì)稱多處理機(jī)SMPSymmetricMultiprocessor其結(jié)構(gòu)如圖：對(duì)稱性：每個(gè)處理器可等同地訪問SM、I/O等共享存儲(chǔ)：系統(tǒng)中的PE一般少于64個(gè)，總線與交叉開關(guān)一旦作成，難以擴(kuò)展P/CP/CP/CSMSMSM總線或交叉開關(guān)95對(duì)稱多處理機(jī)SMPSymmetricMultiproc96大規(guī)模并行處理機(jī)MPPMassivelyParallelProcessor其結(jié)構(gòu)如圖：分布式：每個(gè)處理器都有局部存儲(chǔ)空間是異步的MIMD機(jī)器，程序有多個(gè)進(jìn)程構(gòu)成，每個(gè)都有其私有空間，由進(jìn)程傳遞消息NIC定制網(wǎng)絡(luò)LMP/CMB…NICLMP/CMB96大規(guī)模并行處理機(jī)MPPMassivelyParalle97分布共享存儲(chǔ)多處理機(jī)DSM高速緩存目錄DIR用于支持分布高速緩存的一致性與SMP的主要差異：DSM在物理上有分布在各節(jié)點(diǎn)的LM從而形成一個(gè)共享的存儲(chǔ)器，對(duì)用戶而言，形成了一個(gè)單地址的編址空間NIC定制網(wǎng)絡(luò)LMP/CMB…DIRNICLMP/CMBDIR97分布共享存儲(chǔ)多處理機(jī)DSMNIC定制網(wǎng)絡(luò)LMP/CMB…工作站機(jī)群COW每個(gè)節(jié)點(diǎn)可以是一臺(tái)PC或SMP各節(jié)點(diǎn)通過低成本的商品網(wǎng)絡(luò)互連NIC商品網(wǎng)絡(luò)（以太網(wǎng)、ATM等）MP/CMB…BridgeIOBLDNICMP/CMBBridgeIOBLD工作站機(jī)群COW每個(gè)節(jié)點(diǎn)可以是一臺(tái)PC或SMPNIC商品網(wǎng)絡(luò)99公用結(jié)構(gòu)SMP、MPP、DSM等并行機(jī)結(jié)構(gòu)漸趨一致，DSM是SMP與MPP的自然結(jié)合，MPP與COW的界限逐漸不清，它們最終趨于一致，形成當(dāng)代并行機(jī)的公用結(jié)構(gòu)。其三種不同的結(jié)構(gòu)如下圖所示：節(jié)點(diǎn)NNIC互連網(wǎng)絡(luò)…shellNICPCMD節(jié)點(diǎn)1（a）無共享結(jié)構(gòu)99公用結(jié)構(gòu)節(jié)點(diǎn)NNIC互連網(wǎng)絡(luò)…shellNICPCMD節(jié)100shell結(jié)構(gòu)系統(tǒng)中大量的節(jié)點(diǎn)通過高速網(wǎng)絡(luò)連接，節(jié)點(diǎn)通常遵循shell結(jié)構(gòu)（ShellArchitecture），是其中一個(gè)專門設(shè)計(jì)定制的電路。shell結(jié)構(gòu)將商品微處理器及其余的節(jié)點(diǎn)，包括cache、局存、NIC及磁盤連接起來。一個(gè)節(jié)點(diǎn)內(nèi)可有多個(gè)處理器。shell結(jié)構(gòu)的優(yōu)點(diǎn)：當(dāng)處理器芯片更新?lián)Q代時(shí)，只要改變shell結(jié)構(gòu)。100shell結(jié)構(gòu)系統(tǒng)中大量的節(jié)點(diǎn)通過高速網(wǎng)絡(luò)連接，節(jié)點(diǎn)通101公用結(jié)構(gòu)將無共享結(jié)構(gòu)圖(a)中節(jié)點(diǎn)內(nèi)的磁盤D移出來構(gòu)成共享磁盤的結(jié)構(gòu)盤(b):NIC互連網(wǎng)絡(luò)…shellNICPCM節(jié)點(diǎn)1節(jié)點(diǎn)N共享磁盤（b）共享磁盤101公用結(jié)構(gòu)將無共享結(jié)構(gòu)圖(a)中節(jié)點(diǎn)內(nèi)的磁盤D移出102公用結(jié)構(gòu)把圖(b)中主存(M)移出來就變成了共享存儲(chǔ)結(jié)構(gòu)圖(c):互連網(wǎng)絡(luò)shellPC共享存儲(chǔ)器（c）共享存儲(chǔ)結(jié)構(gòu)shellPC共享磁盤102公用結(jié)構(gòu)把圖(b)中主存(M)移出來就變成了共享103小結(jié)結(jié)構(gòu)類型：皆為MIMD處理器類型：PVP為專用定制，其余為商用互連網(wǎng)絡(luò)：PVP：定制交叉開關(guān)SMP：總線交叉開關(guān)MPP：定制網(wǎng)絡(luò)DSM：定制網(wǎng)絡(luò)COW：商用網(wǎng)絡(luò)（以太網(wǎng)或ATM）通信機(jī)制：PVP、SMP、DSM：共享變量MPP、COW：消息傳遞103小結(jié)結(jié)構(gòu)類型：皆為MIMD1041.3.2并行計(jì)算機(jī)訪存模型均勻存儲(chǔ)訪問模型UMA非均勻存儲(chǔ)訪問模型NUMA全高速緩存存儲(chǔ)訪問模型COMA高速緩存一致性非均勻存儲(chǔ)訪問模型CC-NUMA非遠(yuǎn)程存儲(chǔ)訪問模型NORMA1041.3.2并行計(jì)算機(jī)訪存模型均勻存儲(chǔ)訪問模型UMA105均勻存儲(chǔ)訪問模型UMAUMA：UniformMemoryAccess特點(diǎn)：物理存儲(chǔ)器被所有處理器均勻共享所有處理器訪問存儲(chǔ)器的時(shí)間相同每臺(tái)處理器可帶有高速緩存cache外設(shè)也可以一定形式共享P1P2PnI/OSM1SMn系統(tǒng)互連……105均勻存儲(chǔ)訪問模型UMAUMA：UniformMemo106非均勻存儲(chǔ)訪問模型NUMANUMA：NonuniformMemoryAccess特點(diǎn)：被共享的存儲(chǔ)器在物理上是分布在所有的處理機(jī)中的,所有的本地存儲(chǔ)器的集合就組成了全局地址空間處理器訪問時(shí)間不一樣每個(gè)處理器可以帶cache，外設(shè)也可以某種形式共享P2互連網(wǎng)絡(luò)…P1PnLM1LM2LMn…106非均勻存儲(chǔ)訪問模型NUMANUMA：Nonunifor107全高速緩存存儲(chǔ)訪問模型COMACOMA：Cache-onlyMemoryAccessNUMA的一種特例C互連網(wǎng)絡(luò)DPCDPCDP…高速緩存目錄107全高速緩存存儲(chǔ)訪問模型COMACOMA：Cache-o108全高速緩存存儲(chǔ)訪問模型COMA特點(diǎn)：各處理器中無存儲(chǔ)層次結(jié)構(gòu)，全部高速緩存構(gòu)成了全局地址空間利用分布的高速緩存目錄D進(jìn)行遠(yuǎn)程高速緩存的訪問COMA中的高速緩存容量一般都大于二級(jí)高速緩存的容量使用COMA時(shí)，數(shù)據(jù)開始時(shí)可任意分配，因?yàn)樵谶\(yùn)行時(shí)它最終被遷移到要用到它的地方108全高速緩存存儲(chǔ)訪問模型COMA特點(diǎn)：高速緩存一致性非均勻存儲(chǔ)訪問模型CC-NUMA：Coherent-CacheNonuniformMemoryAccess將一些SMP機(jī)器作為一個(gè)單節(jié)點(diǎn)而彼此連接起來所形成的較大系統(tǒng)系統(tǒng)互連網(wǎng)絡(luò)NIC,DIR總線或交叉開關(guān)I/OP/C…P/CM節(jié)點(diǎn)1NIC,DIR總線或交叉開關(guān)I/OP/C…P/CM節(jié)點(diǎn)N…高速緩存一致性非均勻存儲(chǔ)訪問模型CC-NUMA：Cohere110高速緩存一致性非均勻存儲(chǔ)訪問模型特點(diǎn)：絕大多數(shù)商用CC-NUMA多處理機(jī)系統(tǒng)都使用基于目錄的高速緩存的一致性協(xié)議它保留SMP結(jié)構(gòu)易于編程的優(yōu)點(diǎn)的同時(shí)，也改善了SMP可擴(kuò)放性問題最顯著的優(yōu)點(diǎn)：程序員無需明確地在節(jié)點(diǎn)上分配數(shù)據(jù)，系統(tǒng)的軟、硬件會(huì)自動(dòng)地將數(shù)據(jù)移至它被使用的地方110高速緩存一致性非均勻存儲(chǔ)訪問模型特點(diǎn)：111高速緩存一致性非均勻存儲(chǔ)訪問模型例：某個(gè)程序有P和Q兩個(gè)進(jìn)程，執(zhí)行如下訪問數(shù)組A和B的代碼段：

PQ第一步：use(A)use(B)第二步：use(B)use(A)

PQABBA111高速緩存一致性非均勻存儲(chǔ)訪問模型例：某個(gè)程序有P和Q兩112非遠(yuǎn)程存儲(chǔ)訪問模型NORMAP消息傳遞互連網(wǎng)絡(luò)（網(wǎng)絡(luò)、超立方、立方環(huán)等）…MPMPMMP…MPPM…PMMPMPMPNORMA：No-RemoteMemoryAccess112非遠(yuǎn)程存儲(chǔ)訪問模型NORMAP消息傳遞互連網(wǎng)絡(luò)…MPM非遠(yuǎn)程存儲(chǔ)訪問模型NORMA特點(diǎn)：所有存儲(chǔ)器皆為私有絕大多數(shù)NORMA不支持遠(yuǎn)程M的訪問系統(tǒng)中的多個(gè)計(jì)算節(jié)點(diǎn)通過消息傳遞互連成網(wǎng)絡(luò)

非遠(yuǎn)程存儲(chǔ)訪問模型NORMA特點(diǎn)：小結(jié)注意：（1）物理上分布的存儲(chǔ)器從編程的觀點(diǎn)看可以是共享的，也可以非共享的（2）共享存儲(chǔ)結(jié)構(gòu)多處理機(jī)可以同時(shí)支持共享存儲(chǔ)及消息傳遞編程模型（3）共享存儲(chǔ)的編程模型可同時(shí)執(zhí)行于共享存儲(chǔ)結(jié)構(gòu)和分布存儲(chǔ)結(jié)構(gòu)的計(jì)算機(jī)上114小結(jié)注意：114115小結(jié)屬性PVPSMPMPPDSMCOW結(jié)構(gòu)類型處理器類型互連網(wǎng)絡(luò)通信機(jī)制地址空間系統(tǒng)存儲(chǔ)器訪存模型MIMDMIMDMIMDMIMDMIMD專用定制商用商用商用商用定制交叉

開關(guān)總線交叉開關(guān)定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)商用網(wǎng)絡(luò)共享變量共享變量共享變量消息傳遞消息傳遞單地址單地址單地址多地址多地址集中共享集中共享分布不共享分布不共享分布共享UMAUMANORMANUMANORMA115小結(jié)屬性PVPSMPMPPDSMCOW結(jié)構(gòu)類型處理器類練習(xí)測(cè)評(píng)并行計(jì)算機(jī)運(yùn)行速度的性能指標(biāo)是每秒鐘執(zhí)行的指令條數(shù)，若單位是pflops時(shí)表示的數(shù)量級(jí)是10的________次方。DSM結(jié)構(gòu)的并行機(jī)的訪存模型是________，SMP結(jié)構(gòu)的并行機(jī)的訪存模型是________。在含有N個(gè)節(jié)點(diǎn)的2-D環(huán)繞互連結(jié)構(gòu)中，節(jié)點(diǎn)的度為________，網(wǎng)絡(luò)直徑為________，對(duì)剖寬度為________。11615NUMAUMA4練習(xí)測(cè)評(píng)并行計(jì)算機(jī)運(yùn)行速度的性能指標(biāo)是每秒鐘執(zhí)行的指令條數(shù)，練習(xí)117請(qǐng)?jiān)诒砀竦膯卧裰刑钊胂鄳?yīng)的編碼二進(jìn)制編碼格雷碼1111110001100010110110000110011111001001練習(xí)117請(qǐng)?jiān)诒砀竦膯卧裰刑钊胂鄳?yīng)的編碼二進(jìn)制編碼格雷碼1練習(xí)美國(guó)的HPCC計(jì)劃是在全面禁止核試驗(yàn)條約簽訂后提出的，該計(jì)劃的目的是利用并行機(jī)在實(shí)驗(yàn)室進(jìn)行核武器的數(shù)值模擬。

（）我國(guó)的并行機(jī)銀河1號(hào)屬于SMP結(jié)構(gòu)。（）采用全高速緩存存儲(chǔ)訪問模型COMA的處理器沒有存儲(chǔ)層次結(jié)構(gòu)，全部高速緩存構(gòu)成了全局地址空間。（）MPP結(jié)構(gòu)的并行機(jī)采用的是消息傳遞機(jī)制，而SMP結(jié)構(gòu)的并行機(jī)采用的是共享變量通信機(jī)制。（）118×√√×練習(xí)美國(guó)的HPCC計(jì)劃是在全面禁止核試驗(yàn)條約簽訂后提出的，該并行算法南京林業(yè)大學(xué)-信息學(xué)院并行算法南京林業(yè)大學(xué)-信息學(xué)院120任課教師：章春芳辦公室：0250E-mail：cfzhang1982@2任課教師：章春芳121教材、參考書—教材并行計(jì)算-結(jié)構(gòu)·算法·編程陳國(guó)良高等教育出版社并行算法實(shí)踐陳國(guó)良高等教育出版社—參考書并行處理技術(shù)

張德富

南京大學(xué)出版社面向結(jié)構(gòu)的并行算法設(shè)計(jì)與分析李曉梅

國(guó)防科技大學(xué)出版社3教材、參考書—教材主要內(nèi)容

并行處理概論

1

并行計(jì)算性能測(cè)評(píng)

2

并行算法的一般設(shè)計(jì)方法

4

并行算法的基本設(shè)計(jì)技術(shù)5非數(shù)值并行算法

6圖論

7矩陣運(yùn)算

8

并行算法的設(shè)計(jì)基礎(chǔ)

3并行程序設(shè)計(jì)基礎(chǔ)

9主要內(nèi)容并行處理概論1并行計(jì)算性123第一章并行計(jì)算機(jī)系統(tǒng)及結(jié)構(gòu)模型1.1并行計(jì)算概論1.2并行計(jì)算機(jī)系統(tǒng)互連1.3并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)5第一章并行計(jì)算機(jī)系統(tǒng)及結(jié)構(gòu)模型1.1并行計(jì)算概論1.21.1并行計(jì)算概論并行處理的定義并行性的含義并行處理的應(yīng)用并行處理中的幾個(gè)難題1241.1并行計(jì)算概論并行處理的定義61251.1.1并行處理的含義發(fā)展背景：僅提高電子部件的速度來改善計(jì)算機(jī)的性能以滿足用戶越來越高的要求是不可能的。計(jì)算科學(xué)：計(jì)算物理、計(jì)算化學(xué)、計(jì)算生物等。并行處理：一種有效的強(qiáng)調(diào)開發(fā)計(jì)算過程中并行事件的信息處理方式。并行計(jì)算：并行機(jī)上的計(jì)算，又稱高性能計(jì)算（HPC)。并行計(jì)算機(jī)：為并行處理所設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)。71.1.1并行處理的含義發(fā)展背景：僅提高電子部件的速度來改126并行性的含義同時(shí)性：兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生在多個(gè)資源中并發(fā)性：兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生在多個(gè)資源中流水線：兩個(gè)或多個(gè)事件發(fā)生在可能重疊的時(shí)間內(nèi)模式：以數(shù)值計(jì)算為例計(jì)算并行性，有表達(dá)模式與遞歸模式8并行性的含義同時(shí)性：兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生在多個(gè)資源127并行性的含義例如：兩個(gè)向量的內(nèi)積：表達(dá)式形式：

9并行性的含義例如：兩個(gè)向量的內(nèi)積：128并行性的含義并行模式：x1Y1x2Y2…Xn-1Yn-1xnYn………R10并行性的含義并行模式：x1Y1x2Y2…Xn-1Yn-1129并行性的含義遞歸模式：流水線模式：

*+11并行性的含義遞歸模式：*+1301.1.2并行處理的應(yīng)用高速并行計(jì)算主要有三種類型的應(yīng)用需求：121.1.2并行處理的應(yīng)用高速并行計(jì)算主要有三種類型的應(yīng)131并行處理的應(yīng)用主要應(yīng)用領(lǐng)域：氣象、海洋、天體物理遙測(cè)地球資源數(shù)據(jù)處理

石油開采及管理磁聚變及核反應(yīng)堆生物及醫(yī)學(xué)工程計(jì)算社會(huì)經(jīng)濟(jì)學(xué)及政府部門國(guó)防

…13并行處理的應(yīng)用主要應(yīng)用領(lǐng)域：132氣象數(shù)值預(yù)報(bào)將地球由北至南分成2度一格，延赤道分成4度一格，將大氣層分成20層，形成一個(gè)三維網(wǎng)格。設(shè)每個(gè)網(wǎng)格上計(jì)算量約為3000次，若時(shí)間步長(zhǎng)為2分鐘，則當(dāng)給出一天的氣象預(yù)報(bào)時(shí)，總計(jì)算量為3.5×1011次。在Gray1（Gray公司的向量流水機(jī)）上進(jìn)行計(jì)算（每秒1億次浮點(diǎn)運(yùn)算，需計(jì)算1小時(shí)左右，若將網(wǎng)格邊長(zhǎng)減半，是原來計(jì)算量的8倍。14氣象數(shù)值預(yù)報(bào)將地球由北至南分成2度一格，延赤道分成4度一133海洋學(xué)、天體物理以1。為間隔的類似網(wǎng)格，用Gyber-205（美國(guó)數(shù)據(jù)控制公司CDC，1982，52位4億次每秒，400mflops的流水線機(jī)）對(duì)太平洋50年作一次完整模擬要1000小時(shí)。模擬地球等行星的形成過程，其動(dòng)態(tài)范圍從毫秒到幾十億，ILLIAC-V陣列處理機(jī)（美國(guó)Illiniosuinv,1973,64個(gè)PE主存13萬字，1.5億次每秒的陣列機(jī)）曾用于這一方面的研究。15海洋學(xué)、天體物理以1。為間隔的類似網(wǎng)格，用Gyber-2134遙測(cè)地球資源數(shù)據(jù)處理大量衛(wèi)星圖像資料處理。陸地探測(cè)衛(wèi)星的一張圖像有3千萬個(gè)字符，覆蓋美國(guó)Alabama州需要13幅這樣的圖像，每15天產(chǎn)生一次新的圖像，計(jì)算量很大。美國(guó)宇航局訂購了并行處理機(jī)MPP（美國(guó)GoodyearAerospace，1979，128×128PES），最高速度每秒60億次8位整數(shù)運(yùn)算，能提供實(shí)時(shí)的情景分析。16遙測(cè)地球資源數(shù)據(jù)處理大量衛(wèi)星圖像資料處理。陸地探測(cè)衛(wèi)星的135石油開采及管理地震探測(cè)

1985年，我國(guó)南海西部石油公司向美國(guó)訂購PE3230MPS并行處理計(jì)算機(jī)。地震數(shù)據(jù)處理費(fèi)用占地震探測(cè)總費(fèi)用的10%，地震數(shù)據(jù)相當(dāng)多，僅1979年就有1015位地震數(shù)據(jù)處理。美國(guó)休斯頓一家地球物理公司存儲(chǔ)的地球地震數(shù)據(jù)有200萬個(gè)磁帶卷。17石油開采及管理地震探測(cè)136石油開采及管理儲(chǔ)油層模型的建立

SOHO公司用Cyber-203（CDC）建立波羅的海灣油田數(shù)值模擬器，包括1000個(gè)油井，一個(gè)需一年模擬實(shí)驗(yàn)的工作量，在Cyber-203僅用33分鐘即可完成。18石油開采及管理儲(chǔ)油層模型的建立137工程計(jì)算水壩、橋梁、船只、超音速飛機(jī)、高層建筑、太空飛行器設(shè)計(jì)需解大型偏微分方程組和代數(shù)方程組，可以用并行處理機(jī)提高設(shè)計(jì)效率。在空氣動(dòng)力學(xué)計(jì)算中美國(guó)航天局Ames研究中心用超級(jí)計(jì)算機(jī)作風(fēng)洞實(shí)驗(yàn)三級(jí)模擬。由Burroughs公司及CDC公司推出“數(shù)值航空動(dòng)力學(xué)模擬設(shè)備“（NAFS）的兩臺(tái)10億次超級(jí)計(jì)算機(jī)可以模擬完整的飛機(jī)設(shè)計(jì)。19工程計(jì)算水壩、橋梁、船只、超音速飛機(jī)、高層建筑、太空飛行138社會(huì)經(jīng)濟(jì)學(xué)及政府部門計(jì)量經(jīng)濟(jì)學(xué)、社會(huì)工程、政府人口普查、犯罪控制2000年世界經(jīng)濟(jì)模型構(gòu)造等計(jì)算的計(jì)算量大，需并行計(jì)算。諾貝爾獎(jiǎng)學(xué)金獲得者W.W.Leontief1980年提出一個(gè)世界經(jīng)濟(jì)輸入/輸出模型，在CDC科學(xué)計(jì)算機(jī)上運(yùn)算，認(rèn)為一個(gè)以部分裁軍為特征的國(guó)際性經(jīng)濟(jì)關(guān)系系統(tǒng)，可以縮小貧富國(guó)家的差距，該項(xiàng)目受到聯(lián)合國(guó)支持。美國(guó)使用大型計(jì)算機(jī)控制犯罪、收稅與審計(jì)，進(jìn)行人口普查及民意測(cè)驗(yàn)。過去美國(guó)制造的大型計(jì)算機(jī)57%由政府使用。20社會(huì)經(jīng)濟(jì)學(xué)及政府部門計(jì)量經(jīng)濟(jì)學(xué)、社會(huì)工程、政府人口普查、139國(guó)防、人工智能、基礎(chǔ)研究國(guó)防軍事部門使用現(xiàn)存的大部分超級(jí)計(jì)算機(jī)，如Cray-1多用于彈頭核武器設(shè)計(jì)。在關(guān)聯(lián)處理機(jī)上為反彈道導(dǎo)彈程序處理雷達(dá)信號(hào)，用S-1多處理機(jī)做反潛艇海洋監(jiān)視。21國(guó)防、人工智能、基礎(chǔ)研究國(guó)防140國(guó)防、人工智能、基礎(chǔ)研究人工智能圖像處理模式識(shí)別計(jì)算機(jī)視覺自然語言理解機(jī)器推理智能機(jī)器人專家系統(tǒng)知識(shí)工程基礎(chǔ)研究計(jì)算化學(xué)計(jì)算物理計(jì)算幾何VLSI輔助設(shè)計(jì)22國(guó)防、人工智能、基礎(chǔ)研究人工智能141當(dāng)代科學(xué)與工程問題的計(jì)算需求評(píng)測(cè)計(jì)算機(jī)性能的指標(biāo)70年代Mflops106

百萬現(xiàn)在Pflops1015

千萬億次90年代Tflops1012

萬億80年代Gflops109

十億世界上第一臺(tái)峰值速度超過1Tflops的高性能計(jì)算機(jī)是由Intel公司于1996年12月研制成功的。23當(dāng)代科學(xué)與工程問題的計(jì)算需求評(píng)測(cè)計(jì)算機(jī)性能的指標(biāo)70年代142當(dāng)代科學(xué)與工程問題的計(jì)算需求美國(guó)HPCC計(jì)劃（HighPerformanceComputing&Communication）為了保持美國(guó)的世界領(lǐng)先地位，1993年，美國(guó)科學(xué)、工程、技術(shù)聯(lián)邦協(xié)調(diào)理事會(huì)的國(guó)會(huì)提出了題為“重大挑戰(zhàn)項(xiàng)目：高性能計(jì)算與通信”的報(bào)告，簡(jiǎn)稱HPCC計(jì)劃3T性能目標(biāo)

Tflops計(jì)算能力、1TB主存容量、1TB/s的I/O帶寬24當(dāng)代科學(xué)與工程問題的計(jì)算需求美國(guó)HPCC計(jì)劃（High143HPCC應(yīng)用領(lǐng)域高速民航用計(jì)算流體動(dòng)力學(xué)來研制超音速噴氣發(fā)動(dòng)機(jī)新藥設(shè)計(jì)研制癌癥和艾滋病的藥物催化作用仿生催化劑計(jì)算機(jī)建模，分析合成過程中酶的作用燃料燃燒通過化學(xué)動(dòng)力學(xué)，揭示流體力學(xué)的作用，設(shè)計(jì)新型發(fā)動(dòng)機(jī)海洋建模對(duì)海洋活動(dòng)與大氣流的熱交換進(jìn)行整體海洋模擬大氣污染對(duì)大氣質(zhì)量模型進(jìn)行模擬研究，揭示其物理和化學(xué)機(jī)理蛋白質(zhì)結(jié)構(gòu)設(shè)計(jì)使用計(jì)算機(jī)模擬，對(duì)蛋白質(zhì)組成的三維結(jié)構(gòu)進(jìn)行研究圖像理解實(shí)時(shí)繪制圖像或動(dòng)畫密碼破譯破譯由長(zhǎng)位數(shù)組成的密碼，求找該數(shù)的兩個(gè)乘積因子1994年4月26日，美國(guó)宣布破譯了世界上最長(zhǎng)的RSA129密碼，在因特網(wǎng)上使用1600臺(tái)計(jì)算機(jī)，600多人工作8個(gè)月，破譯了129位數(shù)字組成的密碼25HPCC應(yīng)用領(lǐng)域高速民航用計(jì)算流體動(dòng)力學(xué)來研制超音速噴氣144科學(xué)計(jì)算的需要26科學(xué)計(jì)算的需要145當(dāng)代科學(xué)與工程問題的計(jì)算需求美國(guó)ASCI計(jì)劃（AcceleratedStrategicComputingInitiative）全面禁止核實(shí)驗(yàn)條約簽訂后，1996年6月能源部聯(lián)合美國(guó)三大武器實(shí)驗(yàn)室共同提出了“加速戰(zhàn)略計(jì)劃創(chuàng)新”，簡(jiǎn)稱為ASCI計(jì)劃27當(dāng)代科學(xué)與工程問題的計(jì)算需求美國(guó)ASCI計(jì)劃（Accel146美國(guó)ASCI計(jì)劃目的通過數(shù)值模擬，評(píng)估核武器的性能、安全性、可靠性等，達(dá)到高分辨率、高逼真度、三維、全物理、全系統(tǒng)的規(guī)模和能力，該計(jì)劃被認(rèn)為是與當(dāng)年曼哈頓計(jì)劃等同的一個(gè)巨大的挑戰(zhàn)。平臺(tái)三大核武器實(shí)驗(yàn)室向三大公司（Intel，IBM和SGI/Cray）預(yù)訂了峰值超過1Tflops的并行計(jì)算機(jī)，預(yù)計(jì)2003年使用運(yùn)算100Tflops，50TB存儲(chǔ)容量，I/O傳輸速率為5000GB/s的并行機(jī)28美國(guó)ASCI計(jì)劃147并行處理中的幾個(gè)難題任務(wù)分配非常困難考慮時(shí)空復(fù)雜度，還需考慮模塊之間的通信量很難擺脫串行處理方式的約束軟件和算法大都是按照串行結(jié)構(gòu)設(shè)計(jì)的現(xiàn)有的算法語言對(duì)并行性限制很大現(xiàn)有語言以VonNeumann方式為基礎(chǔ)，對(duì)并行性限

制嚴(yán)重：語句執(zhí)行結(jié)果、執(zhí)行順序與前面結(jié)果和狀態(tài)相關(guān)大量賦值語句使得處理器與存儲(chǔ)器頻繁交換信息，

降低系統(tǒng)效率29并行處理中的幾個(gè)難題任務(wù)分配非常困難148并行處理中的幾個(gè)難題VonNeumann模式一直伴隨著并行機(jī)未擺脫以指令流為主導(dǎo)的VonNeumann模式，由于指令相關(guān)及地址空間相關(guān)，使并行受到制約處理機(jī)間的通訊開銷使并行處理技術(shù)可能得不償失

并行處理技術(shù)的主要難點(diǎn)在于軟件串行機(jī)中軟件好壞對(duì)于工作性能影響2-3倍，并行計(jì)算機(jī)中卻是50-100倍，而且最困難的在于并行編譯程序30并行處理中的幾個(gè)難題VonNeumann模式一直伴隨著傳統(tǒng)VonNeumann結(jié)構(gòu)及其存在問題存儲(chǔ)程序控制方式149存儲(chǔ)器指令寄存器、計(jì)數(shù)器存儲(chǔ)器指令數(shù)據(jù)指令流驅(qū)動(dòng)傳統(tǒng)VonNeumann結(jié)構(gòu)及其存在問題存儲(chǔ)程序控制方式3150研究并行處理應(yīng)考慮的幾個(gè)問題算法、體系結(jié)構(gòu)、高級(jí)語言三者之間的關(guān)系應(yīng)考慮：對(duì)于一些特定的計(jì)算機(jī)如何設(shè)計(jì)軟件對(duì)于一個(gè)給定的程序如何使之結(jié)構(gòu)化以便在給定的計(jì)算機(jī)上處理對(duì)于一個(gè)給定的計(jì)算機(jī)和一組應(yīng)用軟件怎樣設(shè)計(jì)語言及編譯系統(tǒng)對(duì)于給定的計(jì)算機(jī)、語言及編譯系統(tǒng)如何設(shè)計(jì)算法與程序32研究并行處理應(yīng)考慮的幾個(gè)問題算法、體系結(jié)構(gòu)、高級(jí)語言三者151并行處理機(jī)系統(tǒng)的優(yōu)點(diǎn)具有很高的性能價(jià)格比由于系統(tǒng)的模塊性，使之便于維護(hù)具有較高的可靠性具有較高的處理速度結(jié)構(gòu)的靈活性便于VLSI實(shí)現(xiàn)33并行處理機(jī)系統(tǒng)的優(yōu)點(diǎn)具有很高的性能價(jià)格比1521.1.3并行處理機(jī)的分類1342341.1.3并行處理機(jī)的分類1342153Flynn分類法單指令流單數(shù)據(jù)流SISD單指令流多數(shù)據(jù)流SIMD多指令流單數(shù)據(jù)流MISD（實(shí)際不存在）多指令流多數(shù)據(jù)流MIMD35Flynn分類法單指令流單數(shù)據(jù)流SISD154SISDCUPUMMISDSISCU：控制單元PU：處理單元MM：存儲(chǔ)器IS：指令流DS：數(shù)據(jù)流36SISDCUPUMMISDSISCU：控制單元PU155SIMDCUPU1ISPU2PUn…MM1MM2MMn…DS1DS2DSnIS37SIMDCUPU1ISPU2PUn…MM1MM2MMn…156MIMDPU1PU2PUn…MM1MM2MMn…DS1DS2DSnIS1IS2ISnCU1CU2CUn…IS1IS2ISn38MIMDPU1PU2PUn…MM1MM2MMn…DS1D157Handler分類法1977年，Handler根據(jù)計(jì)算機(jī)系統(tǒng)中流水線和并行度出現(xiàn)的級(jí)別，將一臺(tái)計(jì)算機(jī)表示為三對(duì)整數(shù)：

CPU數(shù)目能執(zhí)行流水線的CPU數(shù)目CPU所控制的ALU數(shù)目

能執(zhí)行流水線的ALU數(shù)目ALU或PE中的位數(shù)ALU或PE中流水線的位數(shù)39Handler分類法1977年，Handler根據(jù)計(jì)算機(jī)158按體系結(jié)構(gòu)分類同步系統(tǒng)向量流水機(jī)陣列處理機(jī)：（含心動(dòng)陣列）SIMD關(guān)聯(lián)處理機(jī)：具有聯(lián)想存儲(chǔ)、按內(nèi)容存取、邏輯操作等多處理機(jī)系統(tǒng)MIMD:由獨(dú)立執(zhí)行指令的處理器構(gòu)成分布存儲(chǔ)系統(tǒng)：每個(gè)結(jié)點(diǎn)有獨(dú)立的存儲(chǔ)單元共享存儲(chǔ)系統(tǒng)MIMD變體（MIMD/SIMD混合型）40按體系結(jié)構(gòu)分類同步系統(tǒng)159現(xiàn)代并行機(jī)結(jié)構(gòu)分類SIMDPVP并行向量處理機(jī)SMP對(duì)稱多處理機(jī)MPP大規(guī)模并行處理機(jī)DSM分布式共享存儲(chǔ)多處理機(jī)COW工作站機(jī)群GrayC-90GrayT-90銀河1號(hào)41現(xiàn)代并行機(jī)結(jié)構(gòu)分類SIMDGrayC-90160對(duì)稱多處理機(jī)SMPIBMR50、SGIPowerChakenge、曙光1號(hào)使用商用微處理的芯片，由高速總線連向共享存儲(chǔ)器，對(duì)稱性共享存儲(chǔ)，PE個(gè)數(shù)不能太多。系統(tǒng)是對(duì)稱的，每個(gè)處理器可等同的訪問共享存儲(chǔ)，I/O設(shè)備。42對(duì)稱多處理機(jī)SMPIBMR50、SGIPower161大規(guī)模并行處理機(jī)MPP經(jīng)典機(jī)型：IBMSP2、IntelParagon、IntelTFLOPS、曙光1000等。特性：節(jié)點(diǎn)為微處理器物理上的分布存儲(chǔ)高帶寬、低延遲的網(wǎng)絡(luò)成百上千個(gè)PE異步MIMD，程序由多個(gè)進(jìn)程組成，每個(gè)進(jìn)程有私有空間，進(jìn)程間采用消息傳遞的方式43大規(guī)模并行處理機(jī)MPP經(jīng)典機(jī)型：IBMSP2、Inte162分布式共享存儲(chǔ)多處理機(jī)DSM經(jīng)典機(jī)型：CrayT3D、SGI/GrayOrigin2000特點(diǎn)：分布在各個(gè)節(jié)點(diǎn)上的局存形成了一個(gè)共享的存儲(chǔ)器與SIMD相同，在物理上有分布在各點(diǎn)的共享主存，但采用單一地址空間，與MPP相比，易于編程44分布式共享存儲(chǔ)多處理機(jī)DSM經(jīng)典機(jī)型：CrayT3D、163工作站機(jī)群COW經(jīng)典機(jī)型：BerkeleyNow、Digital、Toucluster等特點(diǎn)：每個(gè)節(jié)點(diǎn)都是一個(gè)工作站、PC機(jī)或SMP各節(jié)點(diǎn)由低成本網(wǎng)絡(luò)相連（商品網(wǎng)絡(luò)、以太網(wǎng)、FDDI等）各節(jié)點(diǎn)有本地磁盤各節(jié)點(diǎn)有一完整的OS（MPP中只有一個(gè)微核），整個(gè)系統(tǒng)是工作站Unix45工作站機(jī)群COW經(jīng)典機(jī)型：BerkeleyNow、Di1641.2并行計(jì)算機(jī)系統(tǒng)互連靜態(tài)互連網(wǎng)絡(luò)：處理單元間有著固定連接的一類網(wǎng)絡(luò)，在程序執(zhí)行期間，這種點(diǎn)到點(diǎn)的連接保持不變動(dòng)態(tài)網(wǎng)絡(luò)：用交換開關(guān)構(gòu)成的，可按應(yīng)用程序的要求動(dòng)態(tài)地改變連接組成461.2并行計(jì)算機(jī)系統(tǒng)互連靜態(tài)互連網(wǎng)絡(luò)：165靜態(tài)互連網(wǎng)絡(luò)一維線性陣列二維網(wǎng)孔樹形連接超立方網(wǎng)絡(luò)立方環(huán)洗牌交換網(wǎng)蝶形網(wǎng)絡(luò)…47靜態(tài)互連網(wǎng)絡(luò)一維線性陣列166動(dòng)態(tài)連接總線交叉開關(guān)多級(jí)互連網(wǎng)絡(luò)…48動(dòng)態(tài)連接總線167網(wǎng)絡(luò)性能指標(biāo)網(wǎng)絡(luò)直徑對(duì)剖寬度49網(wǎng)絡(luò)性能指標(biāo)網(wǎng)絡(luò)直徑對(duì)剖寬度168網(wǎng)絡(luò)性能指標(biāo)節(jié)點(diǎn)：用圖表示網(wǎng)絡(luò)，則處理機(jī)或存儲(chǔ)器為節(jié)點(diǎn)，連接為邊節(jié)點(diǎn)度（NodeDegree）：射入或射出一個(gè)節(jié)點(diǎn)的邊數(shù)。在單向網(wǎng)絡(luò)中，射入和射出邊之和稱為節(jié)點(diǎn)度網(wǎng)絡(luò)直徑（NetworkDiameter）：

網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)之間的最長(zhǎng)距離，即最大路徑數(shù)對(duì)剖寬度（BisectionWidth）：將網(wǎng)絡(luò)分成兩部分必須移去的最少邊數(shù)如果從任一節(jié)點(diǎn)觀看網(wǎng)絡(luò)都一樣，則稱網(wǎng)絡(luò)為對(duì)稱的（Symmetry）50網(wǎng)絡(luò)性能指標(biāo)節(jié)點(diǎn)：用圖表示網(wǎng)絡(luò)，則處理機(jī)或存儲(chǔ)器為節(jié)點(diǎn)，169靜態(tài)互連網(wǎng)絡(luò)（1）一維線性陣列（1-DLinearArray）：并行機(jī)中最簡(jiǎn)單、最基本的互連方式每個(gè)節(jié)點(diǎn)只與其左、右近鄰相連，也叫二近鄰連接節(jié)點(diǎn)度為直徑為對(duì)剖寬度為21N-151靜態(tài)互連網(wǎng)絡(luò)（1）一維線性陣列（1-DLinearA170一維線性陣列線性連接函數(shù)：52一維線性陣列線性連接函數(shù)：171一維線性陣列當(dāng)首、尾節(jié)點(diǎn)相連時(shí)可構(gòu)成循環(huán)移位器，在拓?fù)浣Y(jié)構(gòu)上等同于環(huán)，環(huán)可以是雙向的或單向的互連網(wǎng)絡(luò)節(jié)點(diǎn)度直徑對(duì)剖寬度單向環(huán)雙向環(huán)222N-12雙向環(huán)單向環(huán)53一維線性陣列當(dāng)首、尾節(jié)點(diǎn)相連時(shí)可構(gòu)成循環(huán)移位器，在拓?fù)浣Y(jié)172二維網(wǎng)孔四近鄰連接：每個(gè)節(jié)點(diǎn)只與其上、下、左、右的近鄰相連54二維網(wǎng)孔四近鄰連接：每個(gè)節(jié)點(diǎn)只與其上、下、左、右的近鄰相173二維網(wǎng)孔Illiac網(wǎng)孔：簡(jiǎn)記為MC2，在垂直方向上帶環(huán)繞，水平方向呈蛇狀55二維網(wǎng)孔Illiac網(wǎng)孔：簡(jiǎn)記為MC2，在垂直方向上帶環(huán)174二維網(wǎng)孔2-D環(huán)繞：垂直和水平方向均帶環(huán)繞56二維網(wǎng)孔2-D環(huán)繞：垂直和水平方向均帶環(huán)繞175二維網(wǎng)孔4互連網(wǎng)絡(luò)節(jié)點(diǎn)度直徑對(duì)剖寬度四近鄰連接Illiac網(wǎng)孔2-D環(huán)繞4457二維網(wǎng)孔4互連網(wǎng)絡(luò)節(jié)點(diǎn)度直徑對(duì)剖寬度四近鄰連接Illia176網(wǎng)孔連接網(wǎng)孔中的PE節(jié)點(diǎn)編號(hào)是按行為主順序，編號(hào)為0～N-1連接函數(shù)：012345678910111213141558網(wǎng)孔連接網(wǎng)孔中的PE節(jié)點(diǎn)編號(hào)是按行為主順序，編號(hào)為0～N177網(wǎng)孔連接例：n=16時(shí)的網(wǎng)孔012345678910111213141559網(wǎng)孔連接例：n=16時(shí)的網(wǎng)孔012345678910119-1-57-56-48-47-46-45網(wǎng)孔連接在MC2上已經(jīng)有許多有效的并行算法，但MC2通信功能較差，在最壞情況下，任意兩個(gè)PE間信息交換至少要步。如N=64時(shí)P63-P10：P9-P45：63-7-8-9-109-1-57-56-48-47-46-45網(wǎng)孔連接在MC2上179樹形連接二叉樹連接（簡(jiǎn)記為TC）：P1P8P2P3P4P5P6P7P9P10P11P12P13P14P1561樹形連接二叉樹連接（簡(jiǎn)記為TC）：P1P8P2P3P4P180樹形連接除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)相連設(shè)二叉樹有d層，層號(hào)由根至葉子為1~d，則共有個(gè)節(jié)點(diǎn)節(jié)點(diǎn)度為：對(duì)剖寬度為：直徑為：2d-13162樹形連接除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)樹形連接的典型用法P1P8P2P3P4P5P6P7P9P10P11P12P13P14P15根及葉子節(jié)點(diǎn)具有I/O功能，且葉子節(jié)點(diǎn)執(zhí)行并行計(jì)算，內(nèi)節(jié)點(diǎn)負(fù)責(zé)節(jié)點(diǎn)間的通信樹型連接的最長(zhǎng)通