并行算法南京林業大學-信息學院并行算法南京林業大學-信息學院2任課教師：章春芳辦公室：0250E-mail：cfzhang1982@2任課教師：章春芳3教材、參考書—教材并行計算-結構·算法·編程陳國良高等教育出版社并行算法實踐陳國良高等教育出版社—參考書并行處理技術

張德富

南京大學出版社面向結構的并行算法設計與分析李曉梅

國防科技大學出版社3教材、參考書—教材主要內容

并行處理概論

1

并行計算性能測評

2

并行算法的一般設計方法

4

并行算法的基本設計技術5非數值并行算法

6圖論

7矩陣運算

8

并行算法的設計基礎

3并行程序設計基礎

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

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

*+11并行性的含義遞歸模式：*+121.1.2并行處理的應用高速并行計算主要有三種類型的應用需求：121.1.2并行處理的應用高速并行計算主要有三種類型的應13并行處理的應用主要應用領域：氣象、海洋、天體物理遙測地球資源數據處理

石油開采及管理磁聚變及核反應堆生物及醫學工程計算社會經濟學及政府部門國防

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

1985年，我國南海西部石油公司向美國訂購PE3230MPS并行處理計算機。地震數據處理費用占地震探測總費用的10%，地震數據相當多，僅1979年就有1015位地震數據處理。美國休斯頓一家地球物理公司存儲的地球地震數據有200萬個磁帶卷。17石油開采及管理地震探測18石油開采及管理儲油層模型的建立

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

百萬現在Pflops1015

千萬億次90年代Tflops1012

萬億80年代Gflops109

十億世界上第一臺峰值速度超過1Tflops的高性能計算機是由Intel公司于1996年12月研制成功的。23當代科學與工程問題的計算需求評測計算機性能的指標70年代24當代科學與工程問題的計算需求美國HPCC計劃（HighPerformanceComputing&Communication）為了保持美國的世界領先地位，1993年，美國科學、工程、技術聯邦協調理事會的國會提出了題為“重大挑戰項目：高性能計算與通信”的報告，簡稱HPCC計劃3T性能目標

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

制嚴重：語句執行結果、執行順序與前面結果和狀態相關大量賦值語句使得處理器與存儲器頻繁交換信息，

降低系統效率29并行處理中的幾個難題任務分配非常困難30并行處理中的幾個難題VonNeumann模式一直伴隨著并行機未擺脫以指令流為主導的VonNeumann模式，由于指令相關及地址空間相關，使并行受到制約處理機間的通訊開銷使并行處理技術可能得不償失

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

CPU數目能執行流水線的CPU數目CPU所控制的ALU數目

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

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

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

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

30=（11110）2

k=111i=10

k(i)=011

30是環號為7上的第2個頂點，連向第3個環的第2個頂點1471立方環連接例1：編號為30的處理機72立方環連接例2：編號為25的處理機

25=（11001）2

k=110i=01

k(i)=100

25是環號為6上的第1個頂點，連向第4個環的第1個頂

17例3：編號為27的處理機

27=（11011）2

k=110i=11

k(i)不存在

27是環號為6上的第3個頂點，無連接頂點72立方環連接例2：編號為25的處理機73網絡名稱網絡規模節點度網絡直徑對剖寬度對稱鏈路數線性陣列21非環形2（雙向）2是2-D網孔

4非Illiac網孔

4非2-D環繞4是二叉樹31非星形2非超立方

nn是立方環3是靜態互連網絡特性比較73網絡名稱網絡規模節點度網絡直徑對剖寬度對稱鏈路數線性陣列74洗牌交換網絡洗牌網絡：

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

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

83多級互連網絡單級互連網絡的局限性:84多級互連網絡單級交叉開關級聯起來形成多級互連網絡MIN（MultistageInterconnectionNetwork）優點：速度快，靈活性好，傳輸率低于完全開關網絡，適用于PE較多的情形84多級互連網絡單級交叉開關級聯起來形成多級互連網絡MIN（85多級互連網絡多級互連網絡的性能反映在三個方面：交換開關拓撲結構控制方式85多級互連網絡多級互連網絡的性能反映在三個方面：86多級互連網絡-交換開關交換開關：由2×2的交叉開關構成，具有兩個輸入和兩個輸出的交換單元四種關聯狀態：直連、交換、下播和上播

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

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

PQABBA111高速緩存一致性非均勻存儲訪問模型例：某個程序有P和Q兩112非遠程存儲訪問模型NORMAP消息傳遞互連網絡（網絡、超立方、立方環等）…MPMPMMP…MPPM…PMMPMPMPNORMA：No-RemoteMemoryAccess112非遠程存儲訪問模型NORMAP消息傳遞互連網絡…MPM非遠程存儲訪問模型NORMA特點：所有存儲器皆為私有絕大多數NORMA不支持遠程M的訪問系統中的多個計算節點通過消息傳遞互連成網絡

非遠程存儲訪問模型NORMA特點：小結注意：（1）物理上分布的存儲器從編程的觀點看可以是共享的，也可以非共享的（2）共享存儲結構多處理機可以同時支持共享存儲及消息傳遞編程模型（3）共享存儲的編程模型可同時執行于共享存儲結構和分布存儲結構的計算機上114小結注意：114115小結屬性PVPSMPMPPDSMCOW結構類型處理器類型互連網絡通信機制地址空間系統存儲器訪存模型MIMDMIMDMIMDMIMDMIMD專用定制商用商用商用商用定制交叉

開關總線交叉開關定制網絡定制網絡商用網絡共享變量共享變量共享變量消息傳遞消息傳遞單地址單地址單地址多地址多地址集中共享集中共享分布不共享分布不共享分布共享UMAUMANORMANUMANORMA115小結屬性PVPSMPMPPDSMCOW結構類型處理器類練習測評并行計算機運行速度的性能指標是每秒鐘執行的指令條數，若單位是pflops時表示的數量級是10的________次方。DSM結構的并行機的訪存模型是________，SMP結構的并行機的訪存模型是________。在含有N個節點的2-D環繞互連結構中，節點的度為________，網絡直徑為________，對剖寬度為________。11615NUMAUMA4練習測評并行計算機運行速度的性能指標是每秒鐘執行的指令條數，練習117請在表格的單元格中填入相應的編碼二進制編碼格雷碼1111110001100010110110000110011111001001練習117請在表格的單元格中填入相應的編碼二進制編碼格雷碼1練習美國的HPCC計劃是在全面禁止核試驗條約簽訂后提出的，該計劃的目的是利用并行機在實驗室進行核武器的數值模擬。

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

張德富

南京大學出版社面向結構的并行算法設計與分析李曉梅

國防科技大學出版社3教材、參考書—教材主要內容

并行處理概論

1

并行計算性能測評

2

并行算法的一般設計方法

4

并行算法的基本設計技術5非數值并行算法

6圖論

7矩陣運算

8

并行算法的設計基礎

3并行程序設計基礎

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

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

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

石油開采及管理磁聚變及核反應堆生物及醫學工程計算社會經濟學及政府部門國防

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

1985年，我國南海西部石油公司向美國訂購PE3230MPS并行處理計算機。地震數據處理費用占地震探測總費用的10%，地震數據相當多，僅1979年就有1015位地震數據處理。美國休斯頓一家地球物理公司存儲的地球地震數據有200萬個磁帶卷。17石油開采及管理地震探測136石油開采及管理儲油層模型的建立

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

百萬現在Pflops1015

千萬億次90年代Tflops1012

萬億80年代Gflops109

十億世界上第一臺峰值速度超過1Tflops的高性能計算機是由Intel公司于1996年12月研制成功的。23當代科學與工程問題的計算需求評測計算機性能的指標70年代142當代科學與工程問題的計算需求美國HPCC計劃（HighPerformanceComputing&Communication）為了保持美國的世界領先地位，1993年，美國科學、工程、技術聯邦協調理事會的國會提出了題為“重大挑戰項目：高性能計算與通信”的報告，簡稱HPCC計劃3T性能目標

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

制嚴重：語句執行結果、執行順序與前面結果和狀態相關大量賦值語句使得處理器與存儲器頻繁交換信息，

降低系統效率29并行處理中的幾個難題任務分配非常困難148并行處理中的幾個難題VonNeumann模式一直伴隨著并行機未擺脫以指令流為主導的VonNeumann模式，由于指令相關及地址空間相關，使并行受到制約處理機間的通訊開銷使并行處理技術可能得不償失

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

CPU數目能執行流水線的CPU數目CPU所控制的ALU數目

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

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