1、并行計(jì)算的基本原理,并行計(jì)算（Parallel Computing）是指同時(shí)使用多種計(jì)算資源解決計(jì)算問(wèn)題的過(guò)程。并行計(jì)算的主要目的是快速解決大型且復(fù)雜的計(jì)算問(wèn)題。此外還包括：利用非本地資源，節(jié)約成本 使用多個(gè)“廉價(jià)”計(jì)算資源取代大型計(jì)算機(jī)，同時(shí)克服單個(gè)計(jì)算機(jī)上存在的存儲(chǔ)器限制。 傳統(tǒng)地，串行計(jì)算是指在單個(gè)計(jì)算機(jī)（具有單個(gè)中央處理單元）上執(zhí)行軟件寫操作。CPU 逐個(gè)使用一系列指令解決問(wèn)題，但其中只有一種指令可提供隨時(shí)并及時(shí)的使用。并行計(jì)算是在串行計(jì)算的基礎(chǔ)上演變而來(lái)，它努力仿真自然世界中的事務(wù)狀態(tài)：一個(gè)序列中眾多同時(shí)發(fā)生的、復(fù)雜且相關(guān)的事件。,并行計(jì)算的特點(diǎn),為利用并行計(jì)算，通常計(jì)算問(wèn)題表現(xiàn)為以

2、下特征： （1）將工作分離成離散部分，有助于同時(shí)解決； （2）隨時(shí)并及時(shí)地執(zhí)行多個(gè)程序指令； （3）多計(jì)算資源下解決問(wèn)題的耗時(shí)要少于單個(gè)計(jì)算資源下的耗時(shí)。 并行計(jì)算是相對(duì)于串行計(jì)算來(lái)說(shuō)的，所謂并行計(jì)算分為時(shí)間上的并行和空間上的并行。 時(shí)間上的并行就是指流水線技術(shù)，而空間上的并行則是指用多個(gè)處理器并發(fā)的執(zhí)行計(jì)算。,并行計(jì)算機(jī)的分類,并行計(jì)算科學(xué)中主要研究的是空間上的并行問(wèn)題。 空間上的并行導(dǎo)致了兩類并行機(jī)的產(chǎn)生，按照Flynn的說(shuō)法分為：?jiǎn)沃噶盍鞫鄶?shù)據(jù)流（SIMD）和多指令流多數(shù)據(jù)流（MIMD）。我們常用的串行機(jī)也叫做單指令流單數(shù)據(jù)流（SISD）。,SISD,SIMD,MIMD,并行計(jì)算的術(shù)語(yǔ)（

3、1）,Task：可計(jì)算工作在邏輯上不連續(xù)的分區(qū)。一個(gè)任務(wù)通常是一個(gè)程序或者類似程序一樣的可以被處理器執(zhí)行的指令集。 Parallel Task：一個(gè)任務(wù)可以被多個(gè)處理器安全的并行的執(zhí)行，產(chǎn)生正確的結(jié)果。 Serial Execution：程序相繼的執(zhí)行，每次一個(gè)狀態(tài)。在最簡(jiǎn)單的情況下，單核處理器就是這樣運(yùn)行的。可是，實(shí)際上所有并行的任務(wù)有一些并行程序的區(qū)域一定要串行的執(zhí)行。 Parallel Execution：一個(gè)或多個(gè)任務(wù)同時(shí)執(zhí)行的程序，每個(gè)任務(wù)同時(shí)能夠執(zhí)行相同的或不同的代碼語(yǔ)句。 Pipelining：不同的處理器單元把一個(gè)任務(wù)根據(jù)輸入流來(lái)分解成一系列步驟來(lái)執(zhí)行，相當(dāng)于一條流水線；并行計(jì)

4、算的一種。,并行計(jì)算的術(shù)語(yǔ)（2),Shared Memory（共享內(nèi)存）：完全從硬件的視角來(lái)描述計(jì)算機(jī)體系結(jié)構(gòu)，所有的處理器直接存取通用的物理內(nèi)存（基于總線結(jié)構(gòu)）。在編程的角度上來(lái)看，他指出從并行任務(wù)看內(nèi)存是同樣的視圖，并且能夠直接定位存取相同的邏輯內(nèi)存位置上的內(nèi)容，不管物理內(nèi)存是否真的存在。 Symmetric Multi-Processor（對(duì)稱多處理器）：這種硬件體系結(jié)構(gòu)是多處理器共享一個(gè)地址空間訪問(wèn)所有資源的模型；共享內(nèi)存計(jì)算。 Distributed Memory（分布式存儲(chǔ)）：從硬件的角度來(lái)看，基于網(wǎng)絡(luò)存儲(chǔ)的物理內(nèi)存訪問(wèn)是不常見的。在程序模型中，任務(wù)只能看到本地機(jī)器的內(nèi)存，當(dāng)任務(wù)執(zhí)

5、行時(shí)一定要用通信才能訪問(wèn)其他機(jī)器上的內(nèi)存空間。 Communication：并行任務(wù)都需要交換數(shù)據(jù)。有幾種方法可以完成，例如：共享內(nèi)存總線、網(wǎng)絡(luò)傳輸，然而不管用什么方法，真實(shí)的數(shù)據(jù)交換事件通常與通信相關(guān)。 Synchronization：實(shí)時(shí)并行任務(wù)的調(diào)度通常與通信相關(guān)?？偸峭ㄟ^(guò)建立一個(gè)程序內(nèi)的同步點(diǎn)來(lái)完成，一個(gè)任務(wù)在這個(gè)程序點(diǎn)上等待，直到另一個(gè)任務(wù)到達(dá)相同的邏輯設(shè)備點(diǎn)是才能繼續(xù)執(zhí)行。同步至少要等待一個(gè)任務(wù)，致使并行程序的執(zhí)行時(shí)間增加。,并行計(jì)算的術(shù)語(yǔ)(3),Observed Speedup：測(cè)量代碼并行化之后的加速比。這是最簡(jiǎn)單也最廣泛使用的測(cè)量并行程序性能的方法。 Parallel Ove

6、rhead（并行開銷）：對(duì)并行任務(wù)調(diào)度花費(fèi)的時(shí)間沒(méi)有做有用的工作。并行開銷可以包含如下因素：任務(wù)啟動(dòng)時(shí)間、同步、數(shù)據(jù)通信、并行編譯器、庫(kù)、工具、操作系統(tǒng)等花費(fèi)的軟件開銷，任務(wù)終止的時(shí)間等。 Scalability：指的是并行系統(tǒng)通過(guò)增加更多的處理器的個(gè)數(shù)按比例提高并行性能的能力。促進(jìn)可擴(kuò)展性的因素有：硬件特別是內(nèi)存、CPU帶寬和網(wǎng)絡(luò)通信，應(yīng)用程序算法，相關(guān)的并行開銷、特定的應(yīng)用和編碼方式的特征。 Multi-core Processors：一個(gè)CPU上有多個(gè)處理器。 Cluster Computing：用一般的處理器單元（處理器、網(wǎng)絡(luò)、SMP）來(lái)構(gòu)建并行系統(tǒng)。 Supercomputing /

7、 High Performance Computing（高性能計(jì)算）：使用世界上最快最大的機(jī)器來(lái)解決大規(guī)模的問(wèn)題。,并行計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu),共享內(nèi)存、分布式內(nèi)存、混合型分布式共享內(nèi)寸,接點(diǎn)間的連接,按連接方式分類： Completely-connected, Star, Tree, Linear Array and Ring, Hypercube 集群計(jì)算機(jī)： 通過(guò)高速網(wǎng)絡(luò)LAN將PC機(jī)或工作站連結(jié)而成。,并行編程,1.線程模型（OpenMP,POSIX) 2.消息傳遞模型（MPI，PVM） 3.數(shù)據(jù)并行模型（HPF）,問(wèn)題分解,1.作用域分解：與問(wèn)題相關(guān)的數(shù)據(jù)將會(huì)被分解。每個(gè)并行的任務(wù)只能使用部分?jǐn)?shù)據(jù) 。 2.功能分解：關(guān)注要被完成的計(jì)算而不是操