并行計算的基本原理

單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,并行計算的基本原理,并行計算（,Parallel Computing,）是指同時使用多種計算資源解決計算問題的過程。并行計算的主要目的是快速解決大型且復雜的計算問題。此外還包括：利用非本地資源，節(jié)約成本,使用多個“廉價”計算資源取代大型計算機，同時克服單個計算機上存在的存儲器限制。,傳統(tǒng)地，串行計算是指在單個計算機（具有單個中央處理單元）上執(zhí)行軟件寫操作。,CPU,逐個使用一系列指令解決問題，但其中只有一種指令可提供隨時并及時的使用。并行計算是在串行計算的基礎(chǔ)上演變而來，它努力仿真自然世界中的事務(wù)狀態(tài)：一個序列中眾多同時發(fā)生的、復雜且相關(guān)的事件。,并行計算的特點,為利用并行計算，通常計算問題表現(xiàn)為以下特征：,（,1,）將工作分離成離散部分，有助于同時解決；,（,2,）隨時并及時地執(zhí)行多個程序指令；,（,3,）多計算資源下解決問題的耗時要少于單個計算資源下的耗時。,并行計算是相對于串行計算來說的，所謂并行計算分為時間上的并行和空間上的并行。時間上的并行就是指流水線技術(shù)，而空間上的并行則是指用多個處理器并發(fā)的執(zhí)行計算。,并行計算機的分類,并行計算科學中主要研究的是空間上的并行問題?？臻g上的并行導致了兩類并行機的產(chǎn)生，按照,Flynn,的說法分為：單指令流多數(shù)據(jù)流（,SIMD,）和多指令流多數(shù)據(jù)流（,MIMD,）。我們常用的串行機也叫做單指令流單數(shù)據(jù)流（,SISD,）。,SISD,SIMD,MIMD,并行計算的術(shù)語（,1,）,Task,：可計算工作在邏輯上不連續(xù)的分區(qū)。一個任務(wù)通常是一個程序或者類似程序一樣的可以被處理器執(zhí)行的指令集。,Parallel Task,：一個任務(wù)可以被多個處理器安全的并行的執(zhí)行，產(chǎn)生正確的結(jié)果。,Serial Execution,：程序相繼的執(zhí)行，每次一個狀態(tài)。在最簡單的情況下，單核處理器就是這樣運行的。可是，實際上所有并行的任務(wù)有一些并行程序的區(qū)域一定要串行的執(zhí)行。,Parallel Execution,：一個或多個任務(wù)同時執(zhí)行的程序，每個任務(wù)同時能夠執(zhí)行相同的或不同的代碼語句。,Pipelining,：不同的處理器單元把一個任務(wù)根據(jù)輸入流來分解成一系列步驟來執(zhí)行，相當于一條流水線；并行計算的一種。,并行計算的術(shù)語（,2),Shared Memory,（共享內(nèi)存）：,完全從硬件的視角來描述計算機體系結(jié)構(gòu)，所有的處理器直接存取通用的物理內(nèi)存（基于總線結(jié)構(gòu)）。在編程的角度上來看，他指出從并行任務(wù)看內(nèi)存是同樣的視圖，并且能夠直接定位存取相同的邏輯內(nèi)存位置上的內(nèi)容，不管物理內(nèi)存是否真的存在。,Symmetric Multi-Processor,（對稱多處理器）：,這種硬件體系結(jié)構(gòu)是多處理器共享一個地址空間訪問所有資源的模型；共享內(nèi)存計算。,Distributed Memory,（分布式存儲）：,從硬件的角度來看，基于網(wǎng)絡(luò)存儲的物理內(nèi)存訪問是不常見的。在程序模型中，任務(wù)只能看到本地機器的內(nèi)存，當任務(wù)執(zhí)行時一定要用通信才能訪問其他機器上的內(nèi)存空間。,Communication,：,并行任務(wù)都需要交換數(shù)據(jù)。有幾種方法可以完成，例如：共享內(nèi)存總線、網(wǎng)絡(luò)傳輸，然而不管用什么方法，真實的數(shù)據(jù)交換事件通常與通信相關(guān)。,Synchronization,：,實時并行任務(wù)的調(diào)度通常與通信相關(guān)?？偸峭ㄟ^建立一個程序內(nèi)的同步點來完成，一個任務(wù)在這個程序點上等待，直到另一個任務(wù)到達相同的邏輯設(shè)備點是才能繼續(xù)執(zhí)行。同步至少要等待一個任務(wù)，致使并行程序的執(zhí)行時間增加。,并行計算的術(shù)語,(3),Observed Speedup,：測量代碼并行化之后的加速比。這是最簡單也最廣泛使用的測量并行程序性能的方法。,Parallel Overhead,（并行開銷）,：對并行任務(wù)調(diào)度花費的時間沒有做有用的工作。并行開銷可以包含如下因素：任務(wù)啟動時間、同步、數(shù)據(jù)通信、并行編譯器、庫、工具、操作系統(tǒng)等花費的軟件開銷，任務(wù)終止的時間等。,Scalability,：指的是并行系統(tǒng)通過增加更多的處理器的個數(shù)按比例提高并行性能的能力。促進可擴展性的因素有：硬件,特別是內(nèi)存、,CPU,帶寬和網(wǎng)絡(luò)通信，應(yīng)用程序算法，相關(guān)的并行開銷、特定的應(yīng)用和編碼方式的特征。,Multi-core Processors,：一個,CPU,上有多個處理器。,Cluster Computing,：用一般的處理器單元（處理器、網(wǎng)絡(luò)、,SMP,）來構(gòu)建并行系統(tǒng)。,Supercomputing/High Performance Computing,（高性能計算）,：使用世界上最快最大的機器來解決大規(guī)模的問題。,并行計算機的存儲結(jié)構(gòu),共享內(nèi)存、分布式內(nèi)存、混合型分布式共享內(nèi)寸,接點間的連接,按連接方式分類：,Completely-connected,Star,Tree,Linear Array and Ring,Hypercube,集群計算機：,通過高速網(wǎng)絡(luò),LAN,將,PC,機或工作站連結(jié)而成。,并行編程,1.,線程模型（,OpenMP,POSIX,),2.,消息傳遞模型（,MPI,，,PVM,）,3.,數(shù)據(jù)并行模型（,HPF,）,問題分解,1.,作用域分解：,與問題相關(guān)的數(shù)據(jù)將會被分解。每個并行的任務(wù)只能使用部分數(shù)據(jù)。,2.,功能分解：關(guān)注要被完成的計算而不是操作數(shù)據(jù)的計算。問題是根據(jù)當前一定要完成的任務(wù)劃分的。每個任務(wù)完成全部工作的一部分。,關(guān)注的問題,1,、通信,2,、同步,3,、數(shù)據(jù)依賴,4,、負載平衡,5,、,I/O,并行計算的性能分析,1,、加速比（,speedup),2,、并行效率,