《并行計(jì)算的基本原理》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行計(jì)算的基本原理（14頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,并行計(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í)行軟件寫(xiě)操作。CPU 逐個(gè)使用一系列指令解決問(wèn)題，但其中只有一種指令可提供隨時(shí)并及時(shí)的使用。并行計(jì)算是在串行計(jì)算的基礎(chǔ)上演變而來(lái)，它努力仿真自然世界中的事務(wù)狀態(tài)：一個(gè)序列中

2、眾多同時(shí)發(fā)生的、復(fù)雜且相關(guān)的事件。,并行計(jì)算的特點(diǎn),為利用并行計(jì)算，通常計(jì)算問(wèn)題表現(xiàn)為以下特征：,（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ī)的分類(lèi),并行計(jì)算科學(xué)中主要研究的是空間上的并行問(wèn)題?？臻g上的并行導(dǎo)致了兩類(lèi)并行機(jī)的產(chǎn)生，按照Flynn的說(shuō)法分為：?jiǎn)沃噶盍鞫鄶?shù)據(jù)流（SIMD）和多指令流多數(shù)據(jù)流（MIMD）。我們常用的串行機(jī)

3、也叫做單指令流單數(shù)據(jù)流（SISD）。,SISD,SIMD,MIMD,并行計(jì)算的術(shù)語(yǔ)（1）,Task：可計(jì)算工作在邏輯上不連續(xù)的分區(qū)。一個(gè)任務(wù)通常是一個(gè)程序或者類(lèi)似程序一樣的可以被處理器執(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：不

4、同的處理器單元把一個(gè)任務(wù)根據(jù)輸入流來(lái)分解成一系列步驟來(lái)執(zhí)行，相當(dāng)于一條流水線；并行計(jì)算的一種。,并行計(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ì)稱(chēng)多處理器）：,這種硬件體系結(jié)構(gòu)是多處理器共享一個(gè)地址空間訪問(wèn)所有資源的模型；共享內(nèi)存計(jì)算。,Distributed Memory（分布式存儲(chǔ)）：,從硬件的角度來(lái)看

5、，基于網(wǎng)絡(luò)存儲(chǔ)的物理內(nèi)存訪問(wèn)是不常見(jiàn)的。在程序模型中，任務(wù)只能看到本地機(jī)器的內(nèi)存，當(dāng)任務(wù)執(zhí)行時(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è)量代

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

7、ting,：用一般的處理器單元（處理器、網(wǎng)絡(luò)、SMP）來(lái)構(gòu)建并行系統(tǒng)。,Supercomputing/High Performance Computing（高性能計(jì)算）,：使用世界上最快最大的機(jī)器來(lái)解決大規(guī)模的問(wèn)題。,并行計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu),共享內(nèi)存、分布式內(nèi)存、混合型分布式共享內(nèi)寸,接點(diǎn)間的連接,按連接方式分類(lèi)：,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ì)算而不是操作數(shù)據(jù)的計(jì)算。問(wèn)題是根據(jù)當(dāng)前一定要完成的任務(wù)劃分的。每個(gè)任務(wù)完成全部工作的一部分。,關(guān)注的問(wèn)題,1,、通信,2、同步,3、數(shù)據(jù)依賴(lài),4、負(fù)載平衡,5、I/O,并行計(jì)算的性能分析,1、加速比（speedup),2、并行效率,