并行計算的基本原理

單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,并行計算的基本原理,并行計算（Parallel Computing）是指同時使用多種計算資源解決計算問題的過程并行計算的主要目的是快速解決大型且復(fù)雜的計算問題此外還包括：利用非本地資源，節(jié)約成本 使用多個“廉價”計算資源取代大型計算機，同時克服單個計算機上存在的存儲器限制傳統(tǒng)地，串行計算是指在單個計算機（具有單個中央處理單元）上執(zhí)行軟件寫操作CPU 逐個使用一系列指令解決問題，但其中只有一種指令可提供隨時并及時的使用并行計算是在串行計算的基礎(chǔ)上演變而來，它努力仿真自然世界中的事務(wù)狀態(tài)：一個序列中眾多同時發(fā)生的、復(fù)雜且相關(guān)的事件并行計算的特點,為利用并行計算，通常計算問題表現(xiàn)為以下特征：,（1）將工作分離成離散部分，有助于同時解決；,（2）隨時并及時地執(zhí)行多個程序指令；,（3）多計算資源下解決問題的耗時要少于單個計算資源下的耗時并行計算是相對于串行計算來說的，所謂并行計算分為時間上的并行和空間上的并行時間上的并行就是指流水線技術(shù)，而空間上的并行則是指用多個處理器并發(fā)的執(zhí)行計算并行計算機的分類,并行計算科學(xué)中主要研究的是空間上的并行問題。

空間上的并行導(dǎo)致了兩類并行機的產(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í)行，相當(dāng)于一條流水線；并行計算的一種并行計算的術(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)存，當(dāng)任務(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ù)只能使用部分?jǐn)?shù)據(jù)。

2.功能分解：關(guān)注要被完成的計算而不是操作數(shù)據(jù)的計算問題是根據(jù)當(dāng)前一定要完成的任務(wù)劃分的每個任務(wù)完成全部工作的一部分關(guān)注的問題,1,、通信,2、同步,3、數(shù)據(jù)依賴,4、負載平衡,5、I/O,并行計算的性能分析,1、加速比（speedup),2、并行效率,。