并行程序設(shè)計(jì)

1、第一章 并行計(jì)算機(jī)1.1 1.1 對(duì)計(jì)算機(jī)速度的需求對(duì)計(jì)算機(jī)速度的需求1.2 1.2 并行計(jì)算機(jī)的類型并行計(jì)算機(jī)的類型1.3 1.3 消息傳遞多計(jì)算機(jī)的體系結(jié)構(gòu)特征消息傳遞多計(jì)算機(jī)的體系結(jié)構(gòu)特征1.4 1.4 用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)1.5 1.5 提高計(jì)算機(jī)速度的潛力提高計(jì)算機(jī)速度的潛力1.1 The Demand For Computational Speed1.1 The Demand For Computational Speed A grand challenge problem is one that cannot be A grand challe

2、nge problem is one that cannot be solved in a reasonable amount of time with solved in a reasonable amount of time with todaytodays computers.s computers. Examples:Examples: Global weather forecasting Global weather forecasting Modeling the motion of astronomical bodies Modeling the motion of astron

3、omical bodies Modeling large DNA structure Modeling large DNA structure科學(xué)和工程領(lǐng)域有數(shù)值建模和模擬，需對(duì)大科學(xué)和工程領(lǐng)域有數(shù)值建模和模擬，需對(duì)大量數(shù)據(jù)進(jìn)行多次重復(fù)計(jì)算，計(jì)算必須在合理量數(shù)據(jù)進(jìn)行多次重復(fù)計(jì)算，計(jì)算必須在合理時(shí)間內(nèi)完成，故需要很高計(jì)算速度。時(shí)間內(nèi)完成，故需要很高計(jì)算速度。1.1 The Demand For Computational Speed1.1 The Demand For Computational SpeedWhatever the computational speed of current W

4、hatever the computational speed of current processors, there will be applications that processors, there will be applications that requires more computational power.requires more computational power. Human nature: Human nature:不斷想象那些超過計(jì)算機(jī)系統(tǒng)能不斷想象那些超過計(jì)算機(jī)系統(tǒng)能力的新應(yīng)用，從而需要比目前可提供的更高速力的新應(yīng)用，從而需要比目前可提供的更高速度。度。并

5、行編程有時(shí)有助于求解更精確的解并行編程有時(shí)有助于求解更精確的解并行計(jì)算機(jī)比單機(jī)有更大的主存儲(chǔ)器容量，使并行計(jì)算機(jī)比單機(jī)有更大的主存儲(chǔ)器容量，使得需要較大主存儲(chǔ)器容量的求解問題得到解決。得需要較大主存儲(chǔ)器容量的求解問題得到解決。1.1 The Demand for Computational Speed1.1 The Demand for Computational SpeedThe ideal effect of parallel computer:The ideal effect of parallel computer:n n臺(tái)計(jì)算機(jī)應(yīng)能提供臺(tái)計(jì)算機(jī)應(yīng)能提供n n倍的單機(jī)速度，不論當(dāng)前倍的

6、單機(jī)速度，不論當(dāng)前計(jì)算機(jī)速度為多少，可期待求解的問題以計(jì)算機(jī)速度為多少，可期待求解的問題以1/n1/n時(shí)時(shí)間完成。間完成。實(shí)際很難達(dá)到：實(shí)際很難達(dá)到： 求解問題常不能完全分解成各自獨(dú)立的部求解問題常不能完全分解成各自獨(dú)立的部 分，各部分之間有交互（數(shù)據(jù)傳送、同步）分，各部分之間有交互（數(shù)據(jù)傳送、同步） 但仍可達(dá)到實(shí)質(zhì)性改善。但仍可達(dá)到實(shí)質(zhì)性改善。結(jié)論：結(jié)論：Future is parallelFuture is parallel云計(jì)算案例云計(jì)算案例20082008年年3 3月月1919日上午日上午1010點(diǎn)，美國(guó)國(guó)家檔案館公開了希點(diǎn)，美國(guó)國(guó)家檔案館公開了希拉里拉里. .克林頓在克林頓在1993

7、200119932001年作為第一夫人期間的白宮年作為第一夫人期間的白宮日程檔案。日程檔案。華盛頓郵報(bào)希望將這些檔案在第一時(shí)間上傳到互聯(lián)網(wǎng)，華盛頓郵報(bào)希望將這些檔案在第一時(shí)間上傳到互聯(lián)網(wǎng)，以便公眾查詢。具有極高的社會(huì)關(guān)注度和新聞時(shí)效性。以便公眾查詢。具有極高的社會(huì)關(guān)注度和新聞時(shí)效性。這些檔案是不可檢索的低質(zhì)量這些檔案是不可檢索的低質(zhì)量PDFPDF文件，若想將其轉(zhuǎn)文件，若想將其轉(zhuǎn)換為可以檢索并便于瀏覽的文件格式，需要進(jìn)行再處換為可以檢索并便于瀏覽的文件格式，需要進(jìn)行再處理。理。據(jù)估算，僅每一頁(yè)的操作，以報(bào)社現(xiàn)有的計(jì)算能力就據(jù)估算，僅每一頁(yè)的操作，以報(bào)社現(xiàn)有的計(jì)算能力就需要需要3030分鐘。分鐘。

8、華盛頓郵報(bào)將檔案的轉(zhuǎn)換工程交給華盛頓郵報(bào)將檔案的轉(zhuǎn)換工程交給Amazon EC2 Amazon EC2 (Elastic Compute Cloud)(Elastic Compute Cloud)。 Amazon EC2Amazon EC2同時(shí)使用同時(shí)使用200200個(gè)虛擬服務(wù)器實(shí)例，每個(gè)服務(wù)器的單頁(yè)平均處理時(shí)間個(gè)虛擬服務(wù)器實(shí)例，每個(gè)服務(wù)器的單頁(yè)平均處理時(shí)間都縮短為都縮短為1 1分鐘，并在分鐘，并在9 9小時(shí)內(nèi)將所有檔案轉(zhuǎn)換完畢，小時(shí)內(nèi)將所有檔案轉(zhuǎn)換完畢，以最快的速度將這些第一手資料呈現(xiàn)給讀者。以最快的速度將這些第一手資料呈現(xiàn)給讀者。大數(shù)據(jù)時(shí)代央視著名“對(duì)話”欄目專題討論大數(shù)據(jù)技術(shù)央視著名“對(duì)

9、話”節(jié)目4月14和21日邀請(qǐng)了牛津大學(xué)教授、大數(shù)據(jù)領(lǐng)域權(quán)威專家、大數(shù)據(jù)時(shí)代作者維克托邁爾-舍恩伯格，以及美國(guó)大數(shù)據(jù)存儲(chǔ)技術(shù)公司LSI總裁阿比分別做客“對(duì)話”節(jié)目，做了兩期大數(shù)據(jù)專題談話節(jié)目“誰(shuí)在引爆大數(shù)據(jù)”、“誰(shuí)在掘金大數(shù)據(jù)”4月14日“對(duì)話”節(jié)目專題訪談：誰(shuí)在引爆大數(shù)據(jù)http:/ 4月21日“對(duì)話”節(jié)目專題訪談：誰(shuí)在掘金大數(shù)據(jù)http:/ 1.2 并行計(jì)算機(jī)的類型并行編程：并行編程：多個(gè)處理器協(xié)同求解一個(gè)問題，將多個(gè)處理器協(xié)同求解一個(gè)問題，將整個(gè)求解問題分成若干部分，每部分各由一個(gè)整個(gè)求解問題分成若干部分，每部分各由一個(gè)處理器并行地計(jì)算，編寫這種形式的程序，稱處理器并行地計(jì)算，編寫這種形式

10、的程序，稱為并行編程。為并行編程。并行計(jì)算機(jī)：并行計(jì)算機(jī)：是并行編程的計(jì)算平臺(tái)，可以是是并行編程的計(jì)算平臺(tái)，可以是具有多個(gè)內(nèi)部處理器的單計(jì)算機(jī)或是以某種方具有多個(gè)內(nèi)部處理器的單計(jì)算機(jī)或是以某種方式互連的若干臺(tái)獨(dú)立的計(jì)算機(jī)。式互連的若干臺(tái)獨(dú)立的計(jì)算機(jī)。 A Parallel Computer is a collection of A Parallel Computer is a collection of processing elements that communicate and processing elements that communicate and cooperate to s

11、olve large problem erate to solve large problem fast.1.2 并行計(jì)算機(jī)的類型1.2.1 1.2.1 共享存儲(chǔ)器多處理機(jī)系統(tǒng)共享存儲(chǔ)器多處理機(jī)系統(tǒng) Share Memory Multiprocessor SystemShare Memory Multiprocessor System1.2.2 1.2.2 消息傳遞多計(jì)算機(jī)系統(tǒng)消息傳遞多計(jì)算機(jī)系統(tǒng) Message-Passing MulticomputerMessage-Passing Multicomputer1.2.3 1.2.3 分布式共享存儲(chǔ)器系統(tǒng)分布式共享存儲(chǔ)器系統(tǒng)

12、 Distributed Shared MemoryDistributed Shared Memory1.2.4 MIMD1.2.4 MIMD和和SIMDSIMD分類法分類法 MIMD and SIMD ClassificationsMIMD and SIMD Classifications1.2.1 Shared Memory Multiprocessor System1.2.1 Shared Memory Multiprocessor System普通計(jì)算機(jī)普通計(jì)算機(jī)ProcessorMemory共享存儲(chǔ)器多處理機(jī)模型共享存儲(chǔ)器多處理機(jī)模型MMMInterconnection networ

13、kPPP UMAUMA（均勻存儲(chǔ)訪問）模型（均勻存儲(chǔ)訪問）模型 物理存儲(chǔ)器被所有節(jié)點(diǎn)共享；物理存儲(chǔ)器被所有節(jié)點(diǎn)共享； 所有節(jié)點(diǎn)訪問任意存儲(chǔ)單元的所有節(jié)點(diǎn)訪問任意存儲(chǔ)單元的時(shí)間相同時(shí)間相同； 發(fā)生訪存競(jìng)爭(zhēng)時(shí)，仲裁策略平等對(duì)待每個(gè)節(jié)發(fā)生訪存競(jìng)爭(zhēng)時(shí)，仲裁策略平等對(duì)待每個(gè)節(jié) 點(diǎn)，即每個(gè)節(jié)點(diǎn)點(diǎn)，即每個(gè)節(jié)點(diǎn)機(jī)會(huì)均等機(jī)會(huì)均等； 各節(jié)點(diǎn)的各節(jié)點(diǎn)的CPUCPU可帶有可帶有局部私有高速緩存局部私有高速緩存； 外圍外圍I/OI/O設(shè)備也可以共享，且每個(gè)節(jié)點(diǎn)有平等設(shè)備也可以共享，且每個(gè)節(jié)點(diǎn)有平等 的訪問權(quán)利。的訪問權(quán)利。1.2.1 Shared Memory Multiprocessor System1.2.1 Sh

14、ared Memory Multiprocessor System NUMANUMA（非均勻存儲(chǔ)訪問）模型（非均勻存儲(chǔ)訪問）模型 物理存儲(chǔ)器被所有節(jié)點(diǎn)共享，任意節(jié)點(diǎn)可以直接訪問物理存儲(chǔ)器被所有節(jié)點(diǎn)共享，任意節(jié)點(diǎn)可以直接訪問 任意內(nèi)存模塊；任意內(nèi)存模塊； 節(jié)點(diǎn)訪問內(nèi)存模塊的節(jié)點(diǎn)訪問內(nèi)存模塊的速度不同速度不同，訪問本地存儲(chǔ)模塊的，訪問本地存儲(chǔ)模塊的速度一般是訪問其它節(jié)點(diǎn)內(nèi)存模塊的速度一般是訪問其它節(jié)點(diǎn)內(nèi)存模塊的3 3倍以上；倍以上； 發(fā)生訪存競(jìng)爭(zhēng)時(shí)，仲裁策略對(duì)節(jié)點(diǎn)可能是發(fā)生訪存競(jìng)爭(zhēng)時(shí)，仲裁策略對(duì)節(jié)點(diǎn)可能是不等價(jià)的不等價(jià)的； 各節(jié)點(diǎn)的各節(jié)點(diǎn)的CPUCPU可帶有可帶有局部私有高速緩存局部私有高速緩存

15、（cachecache）； 外圍外圍I/OI/O設(shè)備也可以共享，但對(duì)各節(jié)點(diǎn)是不等價(jià)的設(shè)備也可以共享，但對(duì)各節(jié)點(diǎn)是不等價(jià)的。1.2.1 Shared Memory Multiprocessor System1.2.1 Shared Memory Multiprocessor System處理器和存儲(chǔ)器之間的連接是通過某種互連網(wǎng)絡(luò)實(shí)現(xiàn)的。處理器和存儲(chǔ)器之間的連接是通過某種互連網(wǎng)絡(luò)實(shí)現(xiàn)的。共享存儲(chǔ)器的多處理機(jī)系統(tǒng)使用共享存儲(chǔ)器的多處理機(jī)系統(tǒng)使用單地址空間單地址空間：整個(gè)主存儲(chǔ)器系統(tǒng)中：整個(gè)主存儲(chǔ)器系統(tǒng)中的每一個(gè)單元有一個(gè)唯一的地址。的每一個(gè)單元有一個(gè)唯一的地址。將單處理機(jī)將單處理機(jī)虛存儲(chǔ)器虛存儲(chǔ)器的

16、概念應(yīng)用其上，實(shí)現(xiàn)虛實(shí)地址轉(zhuǎn)換。每個(gè)存的概念應(yīng)用其上，實(shí)現(xiàn)虛實(shí)地址轉(zhuǎn)換。每個(gè)存儲(chǔ)器單元仍只有一個(gè)唯一的實(shí)地址，但各處理器能使用不同的虛地儲(chǔ)器單元仍只有一個(gè)唯一的實(shí)地址，但各處理器能使用不同的虛地址對(duì)它進(jìn)行訪問。址對(duì)它進(jìn)行訪問。訪問共享存儲(chǔ)器中的共享數(shù)據(jù)需小心，要考慮是否會(huì)產(chǎn)生沖突，有訪問共享存儲(chǔ)器中的共享數(shù)據(jù)需小心，要考慮是否會(huì)產(chǎn)生沖突，有一些類似操作系統(tǒng)的機(jī)制保證對(duì)一些類似操作系統(tǒng)的機(jī)制保證對(duì)共享數(shù)據(jù)共享數(shù)據(jù)的訪問是安全的（如加鎖、的訪問是安全的（如加鎖、信號(hào)量等）。信號(hào)量等）。對(duì)共享存儲(chǔ)器進(jìn)行編程有對(duì)共享存儲(chǔ)器進(jìn)行編程有多種方法多種方法，如可用全新的并行編程語(yǔ)言、，如可用全新的并行編程語(yǔ)言

17、、系統(tǒng)系統(tǒng)/ /庫(kù)方法、線程方法等。庫(kù)方法、線程方法等。1.2.1 Shared Memory Multiprocessor System1.2.1 Shared Memory Multiprocessor SystemMessage_passing multiprocessor modelMessage_passing multiprocessor modelMMMMMMP PP PP PInterconnection NetworkInterconnection NetworkLocalLocalmemorymemory1.2.2 Message-Passing Multicomputer

18、1.2.2 Message-Passing Multicomputer與共享存儲(chǔ)器多處理機(jī)是專門設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)不同，與共享存儲(chǔ)器多處理機(jī)是專門設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)不同，消息傳遞多計(jì)算機(jī)系統(tǒng)通過互連網(wǎng)絡(luò)連接多臺(tái)消息傳遞多計(jì)算機(jī)系統(tǒng)通過互連網(wǎng)絡(luò)連接多臺(tái)完整的完整的計(jì)計(jì)算機(jī)構(gòu)成，每臺(tái)計(jì)算機(jī)由一個(gè)處理器和算機(jī)構(gòu)成，每臺(tái)計(jì)算機(jī)由一個(gè)處理器和本地存儲(chǔ)器本地存儲(chǔ)器組成。組成。主存儲(chǔ)器分布在多臺(tái)計(jì)算機(jī)中，每臺(tái)計(jì)算機(jī)都有自己的主存儲(chǔ)器分布在多臺(tái)計(jì)算機(jī)中，每臺(tái)計(jì)算機(jī)都有自己的地址空間，每個(gè)處理器只能訪問自己的本地主存儲(chǔ)器中地址空間，每個(gè)處理器只能訪問自己的本地主存儲(chǔ)器中的單元，的單元，其他處理器不可訪問該本地的主存

19、儲(chǔ)器。其他處理器不可訪問該本地的主存儲(chǔ)器。1.2.2 Message-Passing Multicomputer1.2.2 Message-Passing Multicomputer多臺(tái)計(jì)算機(jī)間的通信通過它們間消息在互連網(wǎng)絡(luò)多臺(tái)計(jì)算機(jī)間的通信通過它們間消息在互連網(wǎng)絡(luò)上傳遞完成上傳遞完成-故稱消息傳遞多處理機(jī)系統(tǒng)，簡(jiǎn)稱故稱消息傳遞多處理機(jī)系統(tǒng)，簡(jiǎn)稱多計(jì)算機(jī)。多計(jì)算機(jī)。對(duì)消息傳遞多計(jì)算機(jī)系統(tǒng)進(jìn)行編程需將問題分解，對(duì)消息傳遞多計(jì)算機(jī)系統(tǒng)進(jìn)行編程需將問題分解，每個(gè)部分同時(shí)執(zhí)行以完成求解。有多種方法：使每個(gè)部分同時(shí)執(zhí)行以完成求解。有多種方法：使用并行編程語(yǔ)言、擴(kuò)展的順序編程語(yǔ)言，使用消用并行編程語(yǔ)言、擴(kuò)

20、展的順序編程語(yǔ)言，使用消息傳遞庫(kù)例程等。息傳遞庫(kù)例程等。1.2.2 Message-Passing Multicomputer1.2.2 Message-Passing Multicomputer優(yōu)點(diǎn)：優(yōu)點(diǎn)：容易在物理上加以擴(kuò)展，易于構(gòu)成較大規(guī)模。容易在物理上加以擴(kuò)展，易于構(gòu)成較大規(guī)模。易于升級(jí)。易于升級(jí)。不需要專門的機(jī)制來控制對(duì)數(shù)據(jù)的同時(shí)訪問。不需要專門的機(jī)制來控制對(duì)數(shù)據(jù)的同時(shí)訪問。缺點(diǎn)：缺點(diǎn)：編程時(shí)需要程序員在代碼中提供顯式的消息傳遞調(diào)用。編程時(shí)需要程序員在代碼中提供顯式的消息傳遞調(diào)用。數(shù)據(jù)不能共享，需拷貝。數(shù)據(jù)不能共享，需拷貝。1.2.2 Message-Passing Multicom

21、puter1.2.2 Message-Passing Multicomputer1.2.3 Distributed Shared MemoryDistributed Shared memory multiprocessor modelMMMPPPInterconnection Networksharedmemory1.2.3 Distributed Shared Memory模型中本地存儲(chǔ)器變?yōu)楣蚕泶鎯?chǔ)器模型中本地存儲(chǔ)器變?yōu)楣蚕泶鎯?chǔ)器共享虛擬共享虛擬存儲(chǔ)器存儲(chǔ)器每個(gè)處理器使用單一的存儲(chǔ)器地址空間對(duì)整個(gè)存每個(gè)處理器使用單一的存儲(chǔ)器地址空間對(duì)整個(gè)存儲(chǔ)器進(jìn)行訪問儲(chǔ)器進(jìn)行訪問當(dāng)一個(gè)處理器要訪問的單元不

22、在本地存儲(chǔ)器中時(shí)，當(dāng)一個(gè)處理器要訪問的單元不在本地存儲(chǔ)器中時(shí)，通過消息傳遞在處理器與該單元間傳送數(shù)據(jù)通過消息傳遞在處理器與該單元間傳送數(shù)據(jù)消息傳遞以消息傳遞以自動(dòng)方式自動(dòng)方式進(jìn)行。盡管存儲(chǔ)器是分布式進(jìn)行。盡管存儲(chǔ)器是分布式的，但給用戶的感覺是共享存儲(chǔ)器。的，但給用戶的感覺是共享存儲(chǔ)器。共享虛共享虛擬存儲(chǔ)器擬存儲(chǔ)器1.2.4 MIMD and SIMD ClassificationFlynnFlynn計(jì)算機(jī)分類法計(jì)算機(jī)分類法最早但最流行的分類最早但最流行的分類任何系統(tǒng)都包含兩個(gè)重要的組成元素：指令任何系統(tǒng)都包含兩個(gè)重要的組成元素：指令 、數(shù)據(jù)、數(shù)據(jù)single instruction strea

23、m-single data streamsingle instruction stream-single data stream（SISD) SISD) computercomputer串行計(jì)算機(jī)，每條指令一次只對(duì)一個(gè)數(shù)據(jù)集執(zhí)行操作串行計(jì)算機(jī)，每條指令一次只對(duì)一個(gè)數(shù)據(jù)集執(zhí)行操作single instruction stream-multiple data stream(SIMD) single instruction stream-multiple data stream(SIMD) computercomputer同一指令同時(shí)對(duì)不同數(shù)據(jù)集進(jìn)行并行操作。數(shù)據(jù)集個(gè)數(shù)是同時(shí)進(jìn)行操作的同一指令同時(shí)對(duì)

24、不同數(shù)據(jù)集進(jìn)行并行操作。數(shù)據(jù)集個(gè)數(shù)是同時(shí)進(jìn)行操作的處理器的數(shù)量處理器的數(shù)量向量計(jì)算機(jī)向量計(jì)算機(jī)multiple instruction stream-single data stream(MISD) multiple instruction stream-single data stream(MISD) computercomputer對(duì)單個(gè)數(shù)據(jù)集執(zhí)行多個(gè)不同操作對(duì)單個(gè)數(shù)據(jù)集執(zhí)行多個(gè)不同操作multiple instruction stream-multiple data stream(MIMD) multiple instruction stream-multiple data stream

25、(MIMD) computercomputer多個(gè)處理器，每個(gè)處理器上運(yùn)行一個(gè)指令流，每條指令對(duì)不同的數(shù)據(jù)進(jìn)行多個(gè)處理器，每個(gè)處理器上運(yùn)行一個(gè)指令流，每條指令對(duì)不同的數(shù)據(jù)進(jìn)行操作。操作。二種并行編程軟件結(jié)構(gòu) MPMDmultiple program multiple data SPMD single program multiple data 1.3 ARCHITECTURE FEATURE OF 1.3 ARCHITECTURE FEATURE OF MESSAGE-PASSING MULTICOPUTERSMESSAGE-PASSING MULTICOPUTERS1.3.1 1.3.1 靜

26、態(tài)網(wǎng)絡(luò)消息傳遞多計(jì)算機(jī)靜態(tài)網(wǎng)絡(luò)消息傳遞多計(jì)算機(jī)1.3.2 1.3.2 嵌入嵌入1.3.3 1.3.3 通信方法通信方法1.3.1 Static Network Message-Passing 1.3.1 Static Network Message-Passing MulticomputerMulticomputer靜態(tài)網(wǎng)絡(luò)：靜態(tài)網(wǎng)絡(luò)：static interconnection network are those static interconnection network are those that have direct fixed physical links between tha

27、t have direct fixed physical links between computers(node) computers(node)1.3.1 Static Network Message-1.3.1 Static Network Message-Passing MulticomputerPassing Multicomputer1 1、網(wǎng)絡(luò)性能指標(biāo)、網(wǎng)絡(luò)性能指標(biāo) 帶寬帶寬 Bandwidth:Bandwidth: the number of bits that can be the number of bits that can be transmitted in unit

28、time. bit/sectransmitted in unit time. bit/sec 網(wǎng)絡(luò)延遲網(wǎng)絡(luò)延遲 Network latency:Network latency: the time to make a the time to make a message transfer through the network,message transfer through the network,又叫又叫通信延遲通信延遲，由啟動(dòng)時(shí)間和通信時(shí)間組成。由啟動(dòng)時(shí)間和通信時(shí)間組成。1.3.1 Static Network Message-1.3.1 Static Network Message-Pa

29、ssing MulticomputerPassing Multicomputer網(wǎng)絡(luò)直徑網(wǎng)絡(luò)直徑 Diameter:Diameter: the minimum number of the minimum number of links between the two farthest nodes in the links between the two farthest nodes in the work. NoteNote that only the shortest routes are used. that only the shortest routes are used. Diame

30、ter is used to determine the worst case Diameter is used to determine the worst case delays and find the communication lower delays and find the communication lower bound of some parallel algorithms.bound of some parallel algorithms.1.3.1 Static Network Message-1.3.1 Static Network Message-Passing M

31、ulticomputerPassing Multicomputer2 2、Completely Connected NetworkCompletely Connected Network每一結(jié)點(diǎn)與所有其他結(jié)點(diǎn)均有一條鏈路每一結(jié)點(diǎn)與所有其他結(jié)點(diǎn)均有一條鏈路有限互連的靜態(tài)網(wǎng)絡(luò)：有限互連的靜態(tài)網(wǎng)絡(luò)： 線線/ /環(huán)網(wǎng)絡(luò)環(huán)網(wǎng)絡(luò) Line/RingLine/Ring 網(wǎng)格網(wǎng)格/ /圓環(huán)形網(wǎng)絡(luò)圓環(huán)形網(wǎng)絡(luò) Mesh/TourMesh/Tour 樹狀網(wǎng)絡(luò)樹狀網(wǎng)絡(luò) Tree NetworksTree Networks 超立方體網(wǎng)絡(luò)超立方體網(wǎng)絡(luò) Hypercube NetworkHypercube Network1

32、.3.1 Static Network Message-1.3.1 Static Network Message-Passing MulticomputerPassing Multicomputer3 3、Ling/RingLing/Ring 線網(wǎng)：由一行結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)限定只能與其鄰接線網(wǎng)：由一行結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)限定只能與其鄰接 結(jié)點(diǎn)連接。每個(gè)結(jié)點(diǎn)有結(jié)點(diǎn)連接。每個(gè)結(jié)點(diǎn)有2 2條鏈路，條鏈路，n n 個(gè)結(jié)點(diǎn)有個(gè)結(jié)點(diǎn)有 n-1n-1條鏈路條鏈路 Diameter:n-1.Diameter:n-1. 環(huán)網(wǎng)：將線網(wǎng)兩端的自由結(jié)點(diǎn)連接。環(huán)網(wǎng)：將線網(wǎng)兩端的自由結(jié)點(diǎn)連接。 n n 個(gè)結(jié)點(diǎn)有個(gè)結(jié)點(diǎn)有 n

33、 n條條 鏈路鏈路 . . Diameter: n/2 Diameter: n/21.3.1 Static Network Message-1.3.1 Static Network Message-Passing MulticomputerPassing Multicomputer4 4、MeshMesh 二維網(wǎng)格：二維陣列中的每個(gè)結(jié)點(diǎn)能與其二維網(wǎng)格：二維陣列中的每個(gè)結(jié)點(diǎn)能與其4 4個(gè)最鄰近的個(gè)最鄰近的 結(jié)點(diǎn)相連。結(jié)點(diǎn)相連。 Diameter of n Diameter of n * * n n Mesh : 2(n Mesh : 2(n -1)-1) 三維網(wǎng)格：每個(gè)結(jié)點(diǎn)在三維網(wǎng)格：每個(gè)結(jié)點(diǎn)在

34、xyzxyz三個(gè)維上各與兩個(gè)結(jié)點(diǎn)相連三個(gè)維上各與兩個(gè)結(jié)點(diǎn)相連 圓環(huán)形網(wǎng)絡(luò)（圓環(huán)形網(wǎng)絡(luò)（tours):tours):將網(wǎng)格中的所有自由端結(jié)點(diǎn)與其對(duì)將網(wǎng)格中的所有自由端結(jié)點(diǎn)與其對(duì)立端的結(jié)點(diǎn)循環(huán)相連。立端的結(jié)點(diǎn)循環(huán)相連。 在在n n * * n n tours tours 中，總鏈路數(shù)為中，總鏈路數(shù)為2n2n條。條。 1.3.1 Static Network Message-1.3.1 Static Network Message-Passing MulticomputerPassing Multicomputer 二維陣列（網(wǎng)格）二維陣列（網(wǎng)格）計(jì)算機(jī)計(jì)算機(jī) / / 處理器處理器1.3.1 Sta

35、tic Network Message-Passing Multicomputer5 5、Tree NetworksTree Networks1.3.1 Static Network Message-1.3.1 Static Network Message-Passing MulticomputerPassing Multicomputer6 6、Hypercube NetworkHypercube Network 每個(gè)結(jié)點(diǎn)與網(wǎng)絡(luò)中每一維上的一個(gè)結(jié)點(diǎn)相連接。每個(gè)結(jié)點(diǎn)與網(wǎng)絡(luò)中每一維上的一個(gè)結(jié)點(diǎn)相連接。 網(wǎng)絡(luò)直徑為網(wǎng)絡(luò)直徑為2 2n.n. 一個(gè)一個(gè)d d維超立方體中的每一結(jié)點(diǎn)，被分配一個(gè)維超立方體

36、中的每一結(jié)點(diǎn)，被分配一個(gè)d d 位二進(jìn)制地址。位二進(jìn)制地址。 存在有最小距離的無死鎖路由算法存在有最小距離的無死鎖路由算法 一個(gè)一個(gè)d d維超立方體由兩個(gè)維超立方體由兩個(gè)d-1d-1維超立方體用第維超立方體用第d d維維 鏈路將兩者連接起來組成。鏈路將兩者連接起來組成。1.3.1 Static Network Message-Passing Multicomputer 1.3.1 Static Network Message-Passing Multicomputer1.3.2 嵌入（embedding)嵌入：將一個(gè)網(wǎng)絡(luò)中的結(jié)點(diǎn)映射到另一網(wǎng)絡(luò)。嵌入：將一個(gè)網(wǎng)絡(luò)中的結(jié)點(diǎn)映射到另一網(wǎng)絡(luò)。線形網(wǎng)嵌入

37、到網(wǎng)格線形網(wǎng)嵌入到網(wǎng)格環(huán)形網(wǎng)嵌入圓環(huán)形網(wǎng)環(huán)形網(wǎng)嵌入圓環(huán)形網(wǎng)網(wǎng)格嵌入到超立方體中網(wǎng)格嵌入到超立方體中1.3.2 嵌入（embedding)1.3.3 通信方法電路交換電路交換(circuit switching)(circuit switching)包交換包交換(packet switching)(packet switching) 存儲(chǔ)轉(zhuǎn)發(fā)存儲(chǔ)轉(zhuǎn)發(fā)(store and forward)(store and forward) 虛擬直通虛擬直通(virtual cut through)(virtual cut through) 蟲洞蟲洞(wormhole)(wormhole)1.3.3 1.3.3

38、 通信方法通信方法1 1、電路交換、電路交換(circuit switching)(circuit switching) 在源和目的地之間建立通路，傳遞所在源和目的地之間建立通路，傳遞所需的鏈路均被保留，直到消息傳遞結(jié)束。需的鏈路均被保留，直到消息傳遞結(jié)束。如：簡(jiǎn)單的電話系統(tǒng)。如：簡(jiǎn)單的電話系統(tǒng)。 缺點(diǎn)：缺點(diǎn)：在整個(gè)傳遞消息過程中，要強(qiáng)行保在整個(gè)傳遞消息過程中，要強(qiáng)行保留通路中的所有鏈路，在消息傳遞結(jié)束之留通路中的所有鏈路，在消息傳遞結(jié)束之前，不允許其他消息使用通路中的任一鏈前，不允許其他消息使用通路中的任一鏈路。路。1.3.3 1.3.3 通信方法通信方法2 2、包交換、包交換(packet

39、 switching)(packet switching)存儲(chǔ)轉(zhuǎn)發(fā)存儲(chǔ)轉(zhuǎn)發(fā)(store and forward)(store and forward) 消息被分成包，包在被傳遞到下一結(jié)點(diǎn)之消息被分成包，包在被傳遞到下一結(jié)點(diǎn)之前結(jié)點(diǎn)內(nèi)部提供緩沖區(qū)保存這些包。如：前結(jié)點(diǎn)內(nèi)部提供緩沖區(qū)保存這些包。如：郵遞系統(tǒng)。郵遞系統(tǒng)。 優(yōu)點(diǎn)優(yōu)點(diǎn)：允許一旦當(dāng)前的包被轉(zhuǎn)發(fā)后，其鏈：允許一旦當(dāng)前的包被轉(zhuǎn)發(fā)后，其鏈路就可由其他包使用。路就可由其他包使用。 缺點(diǎn)缺點(diǎn)：不論輸出鏈路是否可用，包首先要：不論輸出鏈路是否可用，包首先要存到結(jié)點(diǎn)的緩沖區(qū)中，導(dǎo)致顯著的時(shí)間延存到結(jié)點(diǎn)的緩沖區(qū)中，導(dǎo)致顯著的時(shí)間延遲。遲。1.3.3 1.

40、3.3 通信方法通信方法2 2、包交換、包交換(packet switching)(packet switching)虛擬直通虛擬直通(virtual cut through)(virtual cut through) 如輸出鏈路可用，消息可直接向前傳遞而無需存入如輸出鏈路可用，消息可直接向前傳遞而無需存入結(jié)點(diǎn)緩沖區(qū)。結(jié)點(diǎn)緩沖區(qū)。蟲洞蟲洞(wormhole)(wormhole) 消息被分成更小的單位消息被分成更小的單位片。當(dāng)連接鏈路可用時(shí)，片。當(dāng)連接鏈路可用時(shí)，從原結(jié)點(diǎn)向下一結(jié)點(diǎn)傳送的初始消息只是消息的頭從原結(jié)點(diǎn)向下一結(jié)點(diǎn)傳送的初始消息只是消息的頭片，當(dāng)所有鏈路都可用時(shí)，消息的各后繼片才會(huì)被片

41、，當(dāng)所有鏈路都可用時(shí)，消息的各后繼片才會(huì)被傳送。在各結(jié)點(diǎn)間必須有一個(gè)請(qǐng)求傳送。在各結(jié)點(diǎn)間必須有一個(gè)請(qǐng)求/ /應(yīng)答系統(tǒng)。應(yīng)答系統(tǒng)。 優(yōu)點(diǎn)：優(yōu)點(diǎn)：每個(gè)結(jié)點(diǎn)所需的存儲(chǔ)容量較少，時(shí)延與通路每個(gè)結(jié)點(diǎn)所需的存儲(chǔ)容量較少，時(shí)延與通路長(zhǎng)度無關(guān)。片中各位可并行傳送。長(zhǎng)度無關(guān)。片中各位可并行傳送。1.3.3 通信方法1.4 1.4 用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)A network of workstations (NOW) or cluster ofworkstations(COW) became a very attractive alternative to expensive su

42、percomputers and parallel computer systems for high-performance computing in early 1990s.1.4 1.4 用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)采用工作站集群采用工作站集群(Cluster of Workstations,COW)(Cluster of Workstations,COW)的的優(yōu)點(diǎn)：優(yōu)點(diǎn)：工作站性能高而價(jià)格低工作站性能高而價(jià)格低當(dāng)出現(xiàn)新的高性能處理器，易于采用來升當(dāng)出現(xiàn)新的高性能處理器，易于采用來升級(jí)級(jí)COWS.COWS.串行機(jī)上的程序簡(jiǎn)單修改就可在串行機(jī)上的程序簡(jiǎn)單修改就可

43、在COWSCOWS上上運(yùn)行。運(yùn)行。1.4 1.4 用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)1.4 1.4 用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)并行軟件平臺(tái)：并行軟件平臺(tái)：并行虛擬機(jī)并行虛擬機(jī)（Parallel Virtual Machine PVM). Parallel Virtual Machine PVM). developed in late 1980developed in late 1980s. Became very s. Became very popular.popular.消息傳遞接口消息傳遞接口（Message-passing Inter

44、face, Message-passing Interface, MPI). standard defined in 1990s.MPI). standard defined in 1990s. Both provide a set of user-level libraries for Both provide a set of user-level libraries for message passing. Use with regular message passing. Use with regular programming languages (C, C+, .).program

45、ming languages (C, C+, .).1.4 1.4 用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)互連手段：互連手段： EthernetEthernet Ring structure Ring structure Star connection Star connection1.4 1.4 用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)1.4 1.4 用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)1.4 1.4 用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)1.4 1.4 用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)用連網(wǎng)計(jì)算機(jī)作為多計(jì)算機(jī)平臺(tái)使用使用連

46、網(wǎng)工作站連網(wǎng)工作站作為計(jì)算平臺(tái)與使用作為計(jì)算平臺(tái)與使用靜態(tài)網(wǎng)絡(luò)靜態(tài)網(wǎng)絡(luò)的的差別：差別： 通信延遲通信延遲 連網(wǎng)工作站的延遲遠(yuǎn)大于靜態(tài)連網(wǎng)工作站的延遲遠(yuǎn)大于靜態(tài) 鏈路多計(jì)算機(jī)的延遲。程序可移植。鏈路多計(jì)算機(jī)的延遲。程序可移植。 連網(wǎng)的各工作站可能具有不同的類型和速度。連網(wǎng)的各工作站可能具有不同的類型和速度。1.5 1.5 提高計(jì)算速度的潛力提高計(jì)算速度的潛力 粒度粒度(Granularity)(Granularity) 加速比加速比(Speedup Factor)(Speedup Factor) 開銷開銷(Overhead)(Overhead) Amdahl Amdahl定律定律 效率效率(Ef

47、fiency)(Effiency) 代價(jià)代價(jià)(cost)(cost) 可擴(kuò)展性可擴(kuò)展性(Scalability)(Scalability) Gustafson Gustafson定律定律1.5 1.5 提高計(jì)算速度的潛力提高計(jì)算速度的潛力1 1、粒度（粒度（granularity)granularity) 進(jìn)程的大小進(jìn)程的大小 必須將計(jì)算分成能同時(shí)執(zhí)行的多個(gè)任務(wù)或進(jìn)程，必須將計(jì)算分成能同時(shí)執(zhí)行的多個(gè)任務(wù)或進(jìn)程，才能改進(jìn)速度，達(dá)到并行。才能改進(jìn)速度，達(dá)到并行。粒度（粒度（granularity):granularity):描述描述process process 的大小。的大小。Coarse gr

48、anularity:Coarse granularity:每個(gè)每個(gè)processprocess含有大量的順序含有大量的順序指令且要用大量時(shí)間加以執(zhí)行。指令且要用大量時(shí)間加以執(zhí)行。Fine granularity:Fine granularity: process process可能只有幾條指令?？赡苤挥袔讞l指令。Medium granularity:Medium granularity:每個(gè)每個(gè)processprocess所含指令數(shù)為所含指令數(shù)為中等程度。中等程度。1.5 1.5 提高計(jì)算速度的潛力提高計(jì)算速度的潛力增大粒度，會(huì)減少創(chuàng)建進(jìn)程和進(jìn)程間的通信代增大粒度，會(huì)減少創(chuàng)建進(jìn)程和進(jìn)程間的通信

49、代價(jià)；但減少了并發(fā)進(jìn)程數(shù)和并行性。故需折衷。價(jià)；但減少了并發(fā)進(jìn)程數(shù)和并行性。故需折衷。計(jì)算計(jì)算/ /通信比通信比=計(jì)算時(shí)間計(jì)算時(shí)間/ /通信時(shí)間通信時(shí)間用作衡用作衡量粒度大小的指標(biāo)。量粒度大小的指標(biāo)。在保持有足夠并行性的同時(shí)，盡量增大在保持有足夠并行性的同時(shí)，盡量增大計(jì)算計(jì)算/ /通信比通信比。1.5 1.5 提高計(jì)算速度的潛力提高計(jì)算速度的潛力2 2、加速比（加速比（Speedup Factor)Speedup Factor) 單機(jī)運(yùn)行串行程序的時(shí)間單機(jī)運(yùn)行串行程序的時(shí)間S(n)= S(n)= 含有含有n n個(gè)處理器的并行計(jì)算機(jī)運(yùn)行并行程序的時(shí)間個(gè)處理器的并行計(jì)算機(jī)運(yùn)行并行程序的時(shí)間 = =

50、 t t s s / / t t p p 加速比用來衡量一個(gè)多處理機(jī)系統(tǒng)和一個(gè)單機(jī)加速比用來衡量一個(gè)多處理機(jī)系統(tǒng)和一個(gè)單機(jī)系統(tǒng)的相對(duì)性能。系統(tǒng)的相對(duì)性能。1.5 提高計(jì)算速度的潛力在理論分析中，也可用在理論分析中，也可用計(jì)算步計(jì)算步計(jì)算加速比。計(jì)算加速比。 單機(jī)運(yùn)行串行程序的計(jì)算步數(shù)單機(jī)運(yùn)行串行程序的計(jì)算步數(shù)S(n)= S(n)= 使用使用n n個(gè)處理器的并行計(jì)算步數(shù)個(gè)處理器的并行計(jì)算步數(shù)1.5 提高計(jì)算速度的潛力線性加速比線性加速比(Linear Speedup) S(n)=n(Linear Speedup) S(n)=n 當(dāng)計(jì)算被分成相等持續(xù)時(shí)間的進(jìn)程，每個(gè)進(jìn)程映當(dāng)計(jì)算被分成相等持續(xù)時(shí)間的進(jìn)程，每個(gè)進(jìn)程映射到一個(gè)處理器上時(shí)（假設(shè)無開銷），就可獲得射到一個(gè)處理器上時(shí)（假設(shè)無開銷），就可獲得最大加速最大加速n n。超線性加速比超線性加速比(Superlinear Speedup)S(n)n(Superlinear Speedup)S(n)n 使用了次優(yōu)化順序算法使用了次優(yōu)化順序算法 使用了有利于并行的使用了有利于并行的 體系結(jié)構(gòu)（存儲(chǔ)器容量）體系結(jié)構(gòu)（存儲(chǔ)器容量）1.5 1.5 提高計(jì)算速度的潛力提高計(jì)算速度的潛力3 3、開銷開銷（OverheadOverhead）影響加速比的因素影響加速比的因素 一些處理器處于閑置狀態(tài)。一些處理器處