并行程序設(shè)計(jì)-第2講并行計(jì)算基礎(chǔ)lecnote

第二講概述(2)概念：并行計(jì)算機(jī)、并行計(jì)算機(jī)模型并行程序開發(fā)考慮并行程序開發(fā)環(huán)境問題的并行性計(jì)算任務(wù)的劃分計(jì)算任務(wù)的通行、同步數(shù)據(jù)相關(guān)性、負(fù)載均衡問題我們能從并行計(jì)算技術(shù)期待什么？并行計(jì)算機(jī)的分類分類方法1：Flynn分類依據(jù)：同時(shí)執(zhí)行的指令數(shù)量、訪問的數(shù)據(jù)數(shù)量SISD/SIMD/MIMD/MISD分類方法2：存儲(chǔ)體系結(jié)構(gòu)依據(jù)：地址空間的數(shù)量、處理器執(zhí)行核的數(shù)量UMA/NUMA/MPP/CLUSTER共享存儲(chǔ)系統(tǒng)(UMA/NUMA)/分布存儲(chǔ)系統(tǒng)(MPP/CLUSTER)并行計(jì)算機(jī)通常，一個(gè)計(jì)算系統(tǒng)的組成包括兩部分——硬件資源和軟件資源Aparallelcomputerisasetofprocessingunitsthatareabletoworkcooperativelytosolveacomputationalproblem運(yùn)算單元(processingunit)≠處理器執(zhí)行核≠處理器封裝程序運(yùn)行時(shí),使用向量處理器:處理器為每條指令提供多個(gè)數(shù)據(jù)處理單元程序運(yùn)行時(shí),可以使用多顆處理器:通過硬件和軟件手段,實(shí)現(xiàn)處理器之間的協(xié)作硬件資源第一層軟件，例如OS內(nèi)核第二層軟件，例如systemfunctions第三層軟件，例如編譯和運(yùn)行庫(kù)高層軟件，例如用戶程序并行計(jì)算機(jī)中處理單元間的協(xié)作計(jì)算過程中協(xié)作：同步、數(shù)據(jù)交換同步：發(fā)生數(shù)據(jù)訪問沖突時(shí)，解決沖突的實(shí)現(xiàn)手段。表現(xiàn)形式讀讀沖突(RAR)：a=b+cd=e-c。物理實(shí)現(xiàn)上當(dāng)前只能將c的值給其中一個(gè)數(shù)據(jù)處理單元先讀后寫(WAR)：a=b+c→b=e-d。在讀出b的值之前，不能對(duì)其值進(jìn)行更新先寫后讀(RAW)：a=b+c→b=a-d。在讀出a的值之前，必須完成對(duì)其值的更新寫寫沖突(WAW)：語(yǔ)義確定的情形：a=a+ca=a+b，例如SUM。任何一方完成a的更新后，另一方才可以讀a的值有二義的情形：a=b+ca=d+e。程序員要解決結(jié)果的歧義性數(shù)據(jù)交換：解決RAR/RAW/WAR/WAW中數(shù)據(jù)訪問的順序后，實(shí)現(xiàn)數(shù)據(jù)訪問的手段討論：超標(biāo)量技術(shù)中的同步超標(biāo)量技術(shù)中的執(zhí)行過程：數(shù)據(jù)/指令讀取、按序解碼、指令發(fā)射和執(zhí)行、結(jié)果提交維護(hù)一個(gè)緩沖區(qū)，存儲(chǔ)解碼后、發(fā)射前的指令指令解碼后，發(fā)射的充要條件需要的數(shù)據(jù)執(zhí)行單元空閑所讀的數(shù)據(jù)已準(zhǔn)備好沖突解決RAR？WAR？RAW？WAW？并行計(jì)算機(jī)兩方面的含義硬件的拓?fù)浣Y(jié)構(gòu)與行為特征從硬件的拓?fù)浣Y(jié)構(gòu)的角度看(主要是數(shù)據(jù)處理單元與數(shù)據(jù)存儲(chǔ)單元的物理連接方式).硬件之間的物理連接是數(shù)據(jù)處理單元之間協(xié)作的基礎(chǔ)。共享存儲(chǔ)體系結(jié)構(gòu)：UMA(UnifiedMemoryArchitecture)、NUMA(NonUniformMemoryAccessAchitecture)大規(guī)模并行處理存儲(chǔ)體系結(jié)構(gòu)：MPP(Massiveparallelprocessing)分布存儲(chǔ)體系結(jié)構(gòu)：CLUSTERCPUCPUMemoryCPUCPUMemorynetworkMemoryCPUCPUMemorynetworkDiskMemoryDisk并行計(jì)算機(jī)兩方面的含義從硬件的行為特征的角度看(主要是指令數(shù)量與數(shù)據(jù)處理容量的關(guān)系)MISD:UMA,NUMA,MPPorCluster?SIMD:UMA,NUMA,MPPorCluster?MIMD:UMA,NUMA,MPPorCluster?并行計(jì)算機(jī)的分類：Flynn分類法(行為特征)SISDSingleInstruction,SingleData

串行計(jì)算機(jī)(vonNeumann計(jì)算機(jī))SIMDSingleInstruction,MultipleData適用性很有限(如MPEG類計(jì)算、字符串匹配計(jì)算)MISDMultipleInstruction,SingleData為分類的的完美而設(shè)置，意義不大MIMDMultipleInstruction,MultipleData常見的并行計(jì)算機(jī)都可歸入此類MPP/Cluster/SMP/當(dāng)前基于Cache的Multi-core(Intel、AMD)SIMD處理器陣列機(jī)、向量機(jī):CELL、GPU適用于規(guī)則的向量/矩陣計(jì)算，例如：視頻、音頻處理的MPEG算法；密集矩陣的運(yùn)算優(yōu)勢(shì):解碼效率高,一次解碼可用于規(guī)劃多個(gè)數(shù)據(jù)處理單元的動(dòng)作缺點(diǎn):并行處理的數(shù)據(jù)處理容量(capacity)有限陣列處理器實(shí)例：GPU為什么GPU是眾核的而CPU是多核的？處理一個(gè)數(shù)據(jù)陣列，數(shù)據(jù)陣列中每個(gè)元素都可以單獨(dú)處理各個(gè)元素需要的運(yùn)算完全相同陣列處理器并行計(jì)算機(jī)一個(gè)存儲(chǔ)空間一個(gè)同構(gòu)的處理器執(zhí)行核陣列，各個(gè)執(zhí)行核在同一時(shí)刻執(zhí)行的指令都相同、分別處理不同的數(shù)據(jù)。即：各執(zhí)行核執(zhí)行相同的線程，分別處理不同的數(shù)據(jù)可以將SIMD并行計(jì)算機(jī)看作是整列處理器并行計(jì)算機(jī)的簡(jiǎn)化形式，其中每個(gè)線程只有一條指令陣列處理器并行計(jì)算機(jī)可以象SIMD并行計(jì)算機(jī)一樣，各個(gè)數(shù)據(jù)處理單元共享同一個(gè)指令解碼單元，一次指令解碼的結(jié)果同時(shí)給各個(gè)執(zhí)行核共享使用MISD很少見優(yōu)勢(shì):數(shù)據(jù)訪問效率高,一次數(shù)據(jù)存取可滿足多個(gè)數(shù)據(jù)處理單元的需要MIMD最常見的并行計(jì)算機(jī)優(yōu)勢(shì):適用范圍廣,硬件和軟件的伸縮性好缺點(diǎn):處理成本高:各個(gè)數(shù)據(jù)處理單元都需要解碼器件指令流間的存儲(chǔ)一致性維護(hù)難度大,成本高分布存儲(chǔ)體系結(jié)構(gòu)MPP多個(gè)尋址空間并存不同存儲(chǔ)單元的訪問方式不同共享存儲(chǔ)體系結(jié)構(gòu)UMA:UniformMemoryAccess當(dāng)前主要是SMP硬件上支持多個(gè)處理器對(duì)存儲(chǔ)空間的一致訪問NUMA:Non-UniformMemoryAccess通常多個(gè)SMP互聯(lián)軟件和硬件協(xié)作,實(shí)現(xiàn)存儲(chǔ)空間的統(tǒng)一尋址不同存儲(chǔ)單元的訪問效率不同常見的并行機(jī)存儲(chǔ)體系結(jié)構(gòu)Cluster存儲(chǔ)體系結(jié)構(gòu)多個(gè)尋址空間并存每個(gè)尋址空間互相獨(dú)立、可以看作一個(gè)獨(dú)立的系統(tǒng)不同存儲(chǔ)單元的訪問方式不同分布-共享的混合存儲(chǔ)體系結(jié)構(gòu)DiskDiskDiskDisk多顆同等的處理器核一個(gè)CPU中有多個(gè)執(zhí)行核(executioncore)每個(gè)執(zhí)行核有自己獨(dú)立的一級(jí)cacheFPUnitFPUnitExeCoreExeCoreL1CacheL1CacheL2CacheSystemBusIntelCore微架構(gòu)示意圖UMA實(shí)例：基于Cache的multi-core幾種常見并行計(jì)算機(jī)存儲(chǔ)體系機(jī)構(gòu)的對(duì)比邏輯地址指向的存儲(chǔ)單元是否唯一各存儲(chǔ)單元的訪問方式是否一致存儲(chǔ)單元的訪問效率是否一致處理器的存儲(chǔ)訪問方式是否一致UMA是是是是NUMA是是否是MPP否否否是Cluster否否否是現(xiàn)代并行計(jì)算機(jī)存儲(chǔ)結(jié)構(gòu)示意圖NETWORKMPCnodeNETWORKCPUmemoryCPUCPUCPUNICGPU/MICNICGPU/MICDiskMPC(massiveparallelcomputing)node

SystembusmemorySystembusMPCnode嚴(yán)格意義上的MPP在今天已經(jīng)很少存在

并行計(jì)算與分布式計(jì)算的差異分布式計(jì)算:多臺(tái)計(jì)算機(jī)利用網(wǎng)絡(luò)通信進(jìn)行協(xié)作,共同完成某一項(xiàng)任務(wù).這些機(jī)器可以是同時(shí)做不同的子任務(wù),也可以是按工作流方式依次做不同的子任務(wù).運(yùn)行平臺(tái)在地理上的分布特征.P2P:完成文件數(shù)據(jù)的共享WEB:完成信息檢索視頻點(diǎn)播并行計(jì)算:多個(gè)數(shù)據(jù)處理單元協(xié)作,共同完成某一項(xiàng)任務(wù).各個(gè)數(shù)據(jù)處理單元同時(shí)工作,分別做不同的子任務(wù).這些數(shù)據(jù)處理單元可以在相同的計(jì)算機(jī)上(MPP/SMP/多核處理器/向量處理器),也可以在不同的計(jì)算機(jī)上(此時(shí)是一種形式的分布式計(jì)算).同一時(shí)刻的數(shù)據(jù)處理容量(processingcapacity)并行計(jì)算分布式計(jì)算大規(guī)模、粗粒度的并行計(jì)算硬件的行為受軟件的約束Aparallelmachinemodelisanabstractparallelcomputerfromtheprogrammer’sviewpoint,analogoustothevonNeumannmodelforsequentialcomputing硬件資源：共享/分布/分布-共享存儲(chǔ)體系結(jié)構(gòu)第一層軟件，例如OS內(nèi)核第二層軟件，例如systemfunctions第三層軟件，例如編譯和運(yùn)行庫(kù)高層軟件，例如用戶程序程序員看到的計(jì)算機(jī)：編程模型(編程語(yǔ)言、函數(shù)包的API)編程模型：編程語(yǔ)言、函數(shù)包API可執(zhí)行程序：SIMD/MIMD/MISD計(jì)算機(jī)模型計(jì)算機(jī)模型：對(duì)程序執(zhí)行過程中計(jì)算機(jī)行為的約束，確保存儲(chǔ)訪問一致性(coherence)：存儲(chǔ)單元的尋址方式例如：CACHE中的存儲(chǔ)單元不參加應(yīng)用程序的尋址計(jì)算過程的進(jìn)展性(progress)：并行計(jì)算獨(dú)有的問題計(jì)算結(jié)果的確定性(determinism)：并行計(jì)算獨(dú)有的問題計(jì)算機(jī)模型就是程序員眼里的計(jì)算機(jī)：程序設(shè)計(jì)語(yǔ)言提供的語(yǔ)句結(jié)構(gòu)、運(yùn)算符號(hào)、函數(shù)現(xiàn)代的CPU都通過多媒體擴(kuò)展指令支持向量并行計(jì)算C/C++語(yǔ)言提供串行語(yǔ)句、串行運(yùn)算、串行函數(shù)：程序員使用C/C++編寫程序時(shí)，算法中的運(yùn)算必須串行執(zhí)行，任何時(shí)刻最多執(zhí)行一個(gè)數(shù)據(jù)運(yùn)算計(jì)算機(jī)模型與計(jì)算機(jī)體系結(jié)構(gòu)可以不一致Intel多核處理器系統(tǒng)上,C/C++程序運(yùn)行時(shí),只能使用一個(gè)執(zhí)行核常見的并行計(jì)算機(jī)模型站在程序開發(fā)的角度，把并行計(jì)算機(jī)劃分成三類向量處理器(SIMD)：程序運(yùn)行時(shí)，只有一個(gè)線程，其中每條指令可以處理多個(gè)數(shù)據(jù)(CUDA可以歸為這一類)多處理器multi-processor：程序運(yùn)行時(shí)，只有一個(gè)進(jìn)程，其中可以包括多個(gè)并發(fā)運(yùn)行的線程進(jìn)程：OS的資源分配單位。一個(gè)進(jìn)程有一個(gè)存儲(chǔ)空間，進(jìn)程的所有操作都是在這個(gè)存儲(chǔ)空間上進(jìn)行的線程：處理器資源的調(diào)度單位多計(jì)算機(jī)puter：程序運(yùn)行時(shí)，有多個(gè)進(jìn)程每個(gè)進(jìn)程存儲(chǔ)程序的一部分?jǐn)?shù)據(jù)、執(zhí)行一部分計(jì)算任務(wù)進(jìn)程之間有協(xié)作：同步、交換數(shù)據(jù)Multi-processor：SMP并發(fā)threadspthreads(POSIX并發(fā)線程模型)/OpenMPCUDA線程模型CELLBE線程模型PRAM(ParallelRandomAccessMachine：理論模型)puter：MPP/CLUSTERMessagepassingDataparallelBSP(BulkSynchronousParallelism：理論模型；同時(shí)定義了一個(gè)函數(shù)包，可以用于并行程序開發(fā))理論模型：分析算法的復(fù)雜性，指導(dǎo)并行算法設(shè)計(jì)和程序性能優(yōu)化DiskNetworkinterfacecircuitryAcustom-designedcircuitrythatinterfacesacommoditymicroprocessortoC,M,D,NIC程序員眼中的Multi-processor有一個(gè)全局的存儲(chǔ)空間每個(gè)處理器都可以直接訪問任何存儲(chǔ)地址用“鎖”/“信號(hào)”/“條件”的辦法解決對(duì)共享變量的競(jìng)爭(zhēng)開發(fā)Multi-processor計(jì)算能力的基本途徑是線程并行SharedMemorySharedDisksPshellNICInterconnectionnetworkCNICPshellCCCacheMMemoryDPProcessorNICshellThreadsmodel——thread-levelparallelismasingleprocesscanhavemultiple,concurrentexecutionpathsMasterthread(themainprogram)performs:serialwork;fork/joinslavethreads每個(gè)線程分別由OS調(diào)度到不同的CPU上運(yùn)行從存儲(chǔ)空間的角度，看線程之間的關(guān)系(與C程序?qū)Ρ?Masterthread:mainfunctionSlavethreads:subroutinescalledinthemainfunctionMasterthread與slavethreads共享存儲(chǔ)空間mainfunctionandthecalledsubroutinesshareglobalvariablesMasterthread與slavethreads都可以有自己的私有數(shù)據(jù)Boththemainfunctionandcalledsubroutinescandeclarelocalvariables從程序運(yùn)行行為的角度，看線程之間的關(guān)系(與C程序?qū)Ρ?mainfunctioncall一個(gè)subroutine后，停止自己的工作，直到subroutine執(zhí)行完，再繼續(xù)自己的工作subroutine在運(yùn)行過程中獨(dú)占globalmemoryspace的訪問權(quán)subroutine在運(yùn)行結(jié)束后，可以通過返回參數(shù)將結(jié)果傳遞給mainfunction的localmemoryspaceMasterthreadfork一個(gè)slavethread后，繼續(xù)做自己的工作，將與slavethread并發(fā)執(zhí)行slave

thread只能將自己的結(jié)果寫到globalmemoryspace每個(gè)thread訪問globalmemoryspace時(shí)，需要考慮與其它thread的同步(“鎖”、“信號(hào)量”)Materthread與slavethread是不同的Process占有的資源處理器資源：thread存儲(chǔ)資源：memoryaddress外設(shè)資源：IObufferMasterthread創(chuàng)建之前：存儲(chǔ)資源、外設(shè)資源均以分配結(jié)束之后：存儲(chǔ)資源、外設(shè)資源立即釋放Slavethread：與系統(tǒng)的存儲(chǔ)資源、外設(shè)資源的管理無(wú)關(guān)例子：計(jì)算小于N的全部素?cái)?shù)判斷K是素?cái)?shù)的算法：K不能被[2，x]之間的素?cái)?shù)整數(shù)x2

K(x+1)2K從3開始并行程序primes[5000];//存儲(chǔ)找到的素?cái)?shù)totalPrimes;//找到的素?cái)?shù)總數(shù)pthreads=0;//fork的線程總數(shù)K=3;main(){ k=3; primes[0]=2; primes[1]=3; totalPrimes=1；

創(chuàng)建一組線程； searchPrimes();

等待所創(chuàng)建的線程結(jié)束，此時(shí)pthreads=0；}每個(gè)線程執(zhí)行pthreads++;searchPrimes();pthreads--;searchPrimes():從剩下的數(shù)據(jù)中取一個(gè)最小的數(shù)K，判斷它是否為素?cái)?shù)，直到小于等于N的全部數(shù)都判斷完為止。算法的實(shí)現(xiàn)并不復(fù)雜，但需要使用“鎖”lock1：確保每個(gè)k只被取一次“鎖”lock2

：確保每次只有一個(gè)線程在對(duì)pthread執(zhí)行自增、自減運(yùn)算“鎖”lock3

：確保每次只有一個(gè)線程在對(duì)primes執(zhí)行write操作“信號(hào)量”signal：確保素?cái)?shù)在primes中從小到大順序存儲(chǔ)找到一個(gè)素?cái)?shù)prime后，查看期待的下一個(gè)素?cái)?shù)是否是prime，即：primes[totalPrimes+1]==prime??如果不是，等到primes[totalPrimes+1]被改變的信號(hào)出現(xiàn)每個(gè)數(shù)字k在判斷完成后，無(wú)論k是否是素?cái)?shù)，都將期待的下一個(gè)素?cái)?shù)的值置為K+1Pthreads定義了一個(gè)函數(shù)包，用來(lái)實(shí)現(xiàn)“鎖”、“信號(hào)量”機(jī)制在程序中管理處理器資源的編程接口API支持用C開發(fā)并行程序OpenMP基于編譯制導(dǎo)語(yǔ)句為C/C++和Fortran分別提供了不同的接口由并行編譯器根據(jù)指導(dǎo)語(yǔ)句提供的信息，生成可執(zhí)行的并行程序有興趣的同學(xué)可以繼續(xù)讀課程網(wǎng)站提供的資料PRAM在串行程序設(shè)計(jì)中，采用vonNeumanncomputer刻畫影響程序運(yùn)行性能的關(guān)鍵因素。串行程序的復(fù)雜性度量：程序中循環(huán)的迭代空間與問題規(guī)模N的關(guān)系，例如O(N)、O(NlogN)、O(N2)、……。每個(gè)循環(huán)體運(yùn)行一次的時(shí)間取決于問題的特征：循環(huán)體需要的運(yùn)算量CPU的速度MEMORY的數(shù)據(jù)存取速度對(duì)于multi-processor如何在算法設(shè)計(jì)和程序開發(fā)中解決存儲(chǔ)一致性問題？如何衡量并行程序的性能？PRAM試圖對(duì)multi-processor進(jìn)行抽象，刻畫其中對(duì)性能其本質(zhì)作用的特征N個(gè)處理器一個(gè)全局的內(nèi)存空間，由N個(gè)處理器共享每個(gè)處理器都可以通過系統(tǒng)總線直接訪問共享內(nèi)存中的任何元素對(duì)存儲(chǔ)空間中的任何元素，每個(gè)處理器的訪問開銷是相同的時(shí)間tPRAM上的并行程序一個(gè)并行程序由N個(gè)process(進(jìn)程?我覺得線程更合適)組成，第I個(gè)進(jìn)程位于第I個(gè)處理器上每個(gè)進(jìn)程是一組指令的線性序列在每個(gè)時(shí)間步(basictimestep/cycle)上，每個(gè)進(jìn)程分別執(zhí)行一條指令數(shù)據(jù)傳輸指令數(shù)學(xué)/邏輯運(yùn)算指令控制轉(zhuǎn)移指令I(lǐng)/O指令NULL指令等進(jìn)程之間通過共享變量進(jìn)行交互共享內(nèi)存的訪問沖突問題——一致性原則(consistencyrule)EREW(exclusivereadexclusivewrite)：每個(gè)CYCLE上，一個(gè)內(nèi)存單元最多只能被一個(gè)進(jìn)程訪問CREW(concurrentreadexclusivewrite)：每個(gè)CYCLE上，一個(gè)內(nèi)存單元可以被多個(gè)進(jìn)程讀，但最多只能被一個(gè)進(jìn)程寫CRCW(concurrentreadconcurrentwrite)：每個(gè)CYCLE上，多個(gè)進(jìn)程可以讀、寫同一個(gè)內(nèi)存單元的數(shù)據(jù)，而當(dāng)發(fā)生寫沖突時(shí)，則采用預(yù)先確定的訪問策略解決沖突問題common:所有進(jìn)程寫的數(shù)據(jù)相同priority:由最優(yōu)先的那個(gè)進(jìn)程寫數(shù)據(jù)arbitrary:允許任意處理器自由寫PRAM對(duì)Pthreads、OpenMP程序開發(fā)的指導(dǎo)進(jìn)程之間按照CYCLE進(jìn)行進(jìn)度同步“鎖”、“信號(hào)”機(jī)制的實(shí)現(xiàn)：插入NULL指令影響性能的因素單個(gè)進(jìn)程中的指令數(shù)量：并行程序需要的CYCLE數(shù)CYCLE需要的實(shí)際時(shí)間程序中NULL指令的數(shù)量：并行程序的EFFICIENCY提高并行程序性能的策略負(fù)載均衡：均衡每個(gè)進(jìn)程中的非空指令數(shù)優(yōu)化子任務(wù)的劃分：減少子任務(wù)之間的數(shù)據(jù)相關(guān)調(diào)度子任務(wù)內(nèi)部的指令：減少為實(shí)現(xiàn)同步需要的NULL指令PRAM并不僅僅用來(lái)刻畫multi-processor系統(tǒng)INTEL的IA64處理器按照bundle來(lái)組織應(yīng)用程序中的指令，每個(gè)bundle最多可以包括3條指令，其中可以包括NULL指令按照bundle調(diào)度執(zhí)行應(yīng)用程序，bundle中的指令并行執(zhí)行IA64與PRAMBundleVSCYCLE為IA64開發(fā)編譯運(yùn)行支持系統(tǒng)是重點(diǎn)：IA64上仍然采用Fortran、C/C++、Java等串行語(yǔ)言站在編譯器的角度看，IA64系統(tǒng)可以理解成一個(gè)有3顆處理器的PRAM站在普通程序員的角度看，IA64系統(tǒng)仍然是一臺(tái)VonNeumann計(jì)算機(jī)當(dāng)前國(guó)際上普遍采用“多核”處理器技術(shù)(mulit-core)：在一個(gè)處理器芯片上聚合多個(gè)運(yùn)算器單元策略一：編譯技術(shù)(通常建議使用OpenMP指導(dǎo)語(yǔ)句)用Fortran、C/C++、Java等語(yǔ)言編寫程序由編譯器和運(yùn)行支持系統(tǒng)負(fù)責(zé)把并發(fā)的指令調(diào)度到不同的運(yùn)算器單元上執(zhí)行策略二：線程(POSIX線程、CELLBE線程：本課程重點(diǎn)之一)策略一和策略二互相補(bǔ)充？小結(jié)（？）：C/C++V.S.X86andIA64計(jì)算機(jī)模型與計(jì)算機(jī)的體系結(jié)構(gòu)并不完全一致計(jì)算機(jī)模型是程序開發(fā)環(huán)境展現(xiàn)給編程人員的采用同一計(jì)算機(jī)模型開發(fā)的應(yīng)用程序，在不同體系結(jié)構(gòu)的計(jì)算機(jī)上性能會(huì)不同，這一點(diǎn)對(duì)并行程序開發(fā)而言要尤其值得注意程序員眼中的puterShareddisksHPF(dataparallel)BSP:BulkSynchronousparallelismSharedDisksProcessorshellNICInterconnectionnetworkCacheNode1NICNodeNMemPshellNICInterconnectionnetworkCNode1NICNodeNMDiskSharednothingMPI(messagepassing)MessagepassingAsetoftasksthatusetheirownlocalmemoryduringcomputationEachtaskisimplementedasaprocessMultipleprocessesmayresideononephysicalmachineTasksexchangedatathroughcommunicationsbysendingandreceivingmessagesDatatransferusuallyrequirescooperativeoperationstobeperformedbyeachprocess.ThisprocessesarecodedwithsomeseriallanguageandalibraryofroutinesforexchangingdatabetweenprocessesDataparallelTheparallelcomputerisNUMA(Non-Uniform-Memory-Access)AsetoftasksworkcollectivelyonthesamedatastructureeachtaskworksonadifferentpartitionofthesamedatastructureTasksperformthesameoperationontheirpartitionofwork有興趣的同學(xué)可以看課程網(wǎng)站chp7,DBPP

REALA(100),B(100)HPF$PROCESSORSprocs(4)HPF$DISTRIBUTEBLOCKONTOprocs::A DOk=1,num_iter FORALL(i=1:100) A(i)=B(i)*delta ENDFORALL ENDDO全局?jǐn)?shù)據(jù)NUMA全局?jǐn)?shù)據(jù)NUMAHPF編程模型接口提供的數(shù)據(jù)處理操作，可以是對(duì)標(biāo)量(單個(gè)的數(shù)據(jù)元素)的運(yùn)算，也可以是對(duì)向量(數(shù)據(jù)元素的集合)的運(yùn)算HPF程序HPF程序的執(zhí)行處理器實(shí)際執(zhí)行的操作可以是一個(gè)操作可以是一組操作可以是NULL每個(gè)非NULL的操作都是對(duì)標(biāo)量的運(yùn)算每個(gè)非NULL的操作可以直接訪問全局存儲(chǔ)空間中的任何一個(gè)元素處理器之間的同步基于編譯制導(dǎo)語(yǔ)句在處理器之間如何分布數(shù)據(jù)哪些計(jì)算是可以并行執(zhí)行的BSP在puter上：無(wú)論是MPI、還是HPF，最終在每個(gè)處理器上所執(zhí)行的程序是由計(jì)算語(yǔ)句和通信語(yǔ)句組成的線性序列整個(gè)并行程序由不同處理器上的程序通過它們中的消息“收發(fā)-接收”對(duì)聯(lián)系成一個(gè)整體在設(shè)計(jì)算法和開發(fā)并行程序時(shí)，需要考慮有什么機(jī)制來(lái)實(shí)現(xiàn)消息的傳遞有什么機(jī)制來(lái)實(shí)現(xiàn)消息收發(fā)過程中相關(guān)的進(jìn)程之間的進(jìn)度同步如何衡量這些消息收發(fā)對(duì)對(duì)并行程序性能的影響？傳遞消息包的大小消息“收發(fā)-接收”對(duì)所在兩個(gè)進(jìn)程執(zhí)行進(jìn)度的匹配BSP試圖對(duì)puter進(jìn)行抽象體系結(jié)構(gòu)：N個(gè)VonNeumannComputer通過網(wǎng)絡(luò)連接起來(lái)每個(gè)處理器分別有一個(gè)自己獨(dú)占的局部存儲(chǔ)空間每個(gè)處理器只能對(duì)自己局部空間中的數(shù)據(jù)元素進(jìn)行讀寫運(yùn)算處理器訪問自己局部存儲(chǔ)空間數(shù)據(jù)元素的速度遠(yuǎn)高于處理器之間交換數(shù)據(jù)的速度進(jìn)程1進(jìn)程2進(jìn)程n計(jì)算(1,1)通信(1,1)同步(1,1)計(jì)算(1,2)通信(1,2)同步(1,2)……計(jì)算(2,1)通信(2,1)同步(2,1)計(jì)算(2,2)通信(2,2)同步(2,2)……計(jì)算(n,1)通信(n,1)同步(n,1)計(jì)算(n,2)通信(n,2)同步(n,2)……Superstep1Superstep2BSP上的并行程序一個(gè)并行程序由N個(gè)process組成，第I個(gè)進(jìn)程位于第I個(gè)處理器上每個(gè)進(jìn)程都被組織成M段代碼的一個(gè)線性序列全部進(jìn)程的第I段代碼構(gòu)成并行程序的第I個(gè)superstep整個(gè)并行程序被嚴(yán)格劃分成M個(gè)superstep進(jìn)程之間按照supestep進(jìn)行同步在superstep內(nèi)通過消息傳遞來(lái)進(jìn)行數(shù)據(jù)交換程序啟動(dòng)時(shí)，數(shù)據(jù)被劃分到各個(gè)進(jìn)程，分別存儲(chǔ)在自己的本地存儲(chǔ)空間中每段代碼都包括三部分，依次如下Computationoperations：執(zhí)行對(duì)局部存儲(chǔ)空間中數(shù)據(jù)元素的運(yùn)算，最多需要w個(gè)cycleCommunicationoperation：執(zhí)行與其它節(jié)點(diǎn)之間的消息傳遞，最多需要gh個(gè)cycle執(zhí)行當(dāng)前Computationoperations結(jié)果的異地?cái)?shù)據(jù)更新取得下一個(gè)Computationoperations需要讀的異地?cái)?shù)據(jù)Barriersynchronization：強(qiáng)制同步，所有進(jìn)程都到達(dá)完成了當(dāng)前的Computationoperations和Communicationoperation后，才可以執(zhí)行下面的代碼BSP上并行程序的性能分析影響并行程序性能的因素SUPERSTEP的數(shù)量每個(gè)SUPERSTEP上，各個(gè)進(jìn)程COMPUTATIONOPERATIONS的均衡性：衡量并行程序的EFFICIENCY每個(gè)SUPERSTEP上，交換消息的大?。簲?shù)據(jù)局部性并行程序的執(zhí)行時(shí)間：第I個(gè)superstep的執(zhí)行時(shí)間第I個(gè)SUPERSTEP的執(zhí)行時(shí)間：MAX{進(jìn)程J在第I個(gè)SUPERSTEP上的COMPUTATIONOPERATIONS時(shí)間MUNICATIONOPERATION時(shí)間}提高并行程序性能的策略負(fù)載均衡：均衡每個(gè)每個(gè)時(shí)間步上各個(gè)進(jìn)程中的COMPUTATIONOPERATIONS優(yōu)化子任務(wù)的劃分：減少子任務(wù)之間的數(shù)據(jù)相關(guān)，避免COMMUNICATIONOPERATION中大量的數(shù)據(jù)交換在puter上求解小于N的全部素?cái)?shù)將[3,N)劃分成m個(gè)片段每個(gè)處理器一次處理一個(gè)片段：第1個(gè)片段給第一個(gè)處理器、第2個(gè)片段給第2個(gè)處理、如此循環(huán)每次計(jì)算完一個(gè)片段后，將找到的結(jié)果都通知給其它的處理器3N已找到的素?cái)?shù)在處理器1上求解在處理器2上求解在處理器3上求解在處理器4上求解puter上并行程序代碼結(jié)構(gòu)的特征SingleProgramMultipleData(SPMD)在每個(gè)處理器上，分別是不同子任務(wù)的數(shù)據(jù)所有處理器上運(yùn)行同一個(gè)可執(zhí)行程序，它根據(jù)處理器號(hào)、處理器上的數(shù)據(jù)確定自己的運(yùn)行邏輯if(rank==0){ dest=1;source=1; rc=MPI_Send(&outmsg,1,MPI_CHAR,dest,tag,M_WORLD); rc=MPI_Recv(&inmsg,1,MPI_CHAR,source,tag,M_WORLD,&Stat);}elseif(rank==1){ dest=0;source=0; rc=MPI_Recv(&inmsg,1,MPI_CHAR,source,tag,M_WORLD,&Stat); rc=MPI_Send(&outmsg,1,MPI_CHAR,dest,tag,M_WORLD);}MPI_Finalize();MultipleProgramMultipleData(MPMD)并行程序包括多個(gè)可執(zhí)行程序在每個(gè)處理器上，分別是不同子任務(wù)的數(shù)據(jù)；并根據(jù)所安排的子任務(wù)，安排相應(yīng)的可執(zhí)行程序采用MessagePassing、BSP模型編寫并行程序既可采用SPMD的表示、也可以用MPMD的表示通常采用SPMD的表示采用DataParallel模型編寫并行程序并行程序的表示由編譯器確定既可采用SPMD的表示、也可以用MPMD的表示通常采用SPMD的表示開發(fā)并行程序的三種途徑串行程序自動(dòng)并行化SUIF編譯指導(dǎo)HPF、OpenMP手工開發(fā)Pthreads、MPI、CELLBE的C/C++擴(kuò)展串行語(yǔ)言＋并行函數(shù)庫(kù)。并行函數(shù)庫(kù)的例子IntelMKL:Intelmathkernellibrary，常見數(shù)學(xué)運(yùn)算函數(shù)如BLAS和Lapack的并行線程實(shí)現(xiàn)IntelIPP:Intelintegratedperformanceprimitives，用于多媒體編碼／解碼以及其他非數(shù)學(xué)運(yùn)算的函數(shù)的并行線程實(shí)現(xiàn)串行程序自動(dòng)并行化20世紀(jì)70年代后，編譯的理論和技術(shù)都已經(jīng)成熟人們習(xí)慣于用Fortran、C這樣的高級(jí)串行語(yǔ)言開發(fā)應(yīng)用程序已經(jīng)有了很多非常成熟的應(yīng)用軟件重新開發(fā)的工作量非常大實(shí)踐表明這條途徑有局限編譯技術(shù)只能從代碼本身的數(shù)據(jù)相關(guān)性進(jìn)行分析主要用于循環(huán)代碼復(fù)雜后，尋找可并行的計(jì)算很困難。特別有條件分支的情況有大量循環(huán)存在間接下標(biāo)訪問，只有提供輸入數(shù)據(jù)后才可確定是否可以并行編譯技術(shù)不能對(duì)運(yùn)算量進(jìn)行估算，即使找到了可并行代碼，難以判斷是否值得并行。并行本身帶來(lái)的開銷不可忽視編譯器中一旦沒有考慮到某種數(shù)據(jù)相關(guān)的出現(xiàn)形式，就可能產(chǎn)生錯(cuò)誤的結(jié)果串行程序：求小于N的全部素?cái)?shù)voidmain(){intnumber;//小于N的素?cái)?shù)個(gè)數(shù)；

intprimes[n];//從primes[0]–primes[number-1]中存放生成的素?cái)?shù)；

inti,j,k;

primes[0]=2; for(i=3,j=1;i<n;i++){//從整數(shù)3開始檢查i是否為素?cái)?shù)

for(k=0;p[k]*p[k]<i;k++)//依次檢查i是否可以被前面的素?cái)?shù)整除

if(i%p[k]==0)break; if(p[k]*p[k]>i){//如果i不能被前面的素?cái)?shù)整除，

//則將它作為新素?cái)?shù)存入數(shù)組

p[j]=i; j++; } }外層循環(huán)相關(guān)，內(nèi)層循環(huán)并行做不值得(多數(shù)情況下只要計(jì)算前面的幾個(gè)素?cái)?shù)就可以得出不是i不是素?cái)?shù)的結(jié)論)并行編譯指導(dǎo)語(yǔ)句對(duì)串行語(yǔ)言擴(kuò)充，增加說明性的指導(dǎo)語(yǔ)句、并行算子程序員以指導(dǎo)語(yǔ)句的形式，告訴編譯器哪些計(jì)算是可以并行運(yùn)行的怎樣提高并行計(jì)算的效率優(yōu)勢(shì)：在從程序員開來(lái)，并行程序與串行程序的差別不算大程序員為開發(fā)并行程序所增加的工作量比較小局限一些并行的形式表達(dá)起來(lái)不方便、或者不能表達(dá)全部的并行性信息，比如稀疏矩陣的計(jì)算問題復(fù)雜后，并行計(jì)算的效果不能達(dá)到預(yù)期的目標(biāo)以并行方式求解小于N的全部素?cái)?shù)對(duì)每個(gè)整數(shù)K，需要將K與[2，x]之間的素?cái)?shù)依次整除。這是整個(gè)問題的主要計(jì)算開銷所在(hotspots)x2K(x+1)2在開發(fā)并行程序時(shí)，重點(diǎn)是將hotspots劃分(partitioning)到不同的處理器上并行執(zhí)行分析所給的兩種并行方案Multi-processor：對(duì)每個(gè)整數(shù)K，分別由一個(gè)處理器判斷是否是素?cái)?shù)puter：將[3，N)劃分成m個(gè)片段，分別由一個(gè)處理器搜索其中的素?cái)?shù)Multi-processor上，“鎖”和“信號(hào)量”的管理是并行計(jì)算帶來(lái)的額外開銷(paralleloverhead)，是決定程序性能的關(guān)鍵因素。對(duì)它們的操作是整個(gè)程序的“瓶頸”(bottleneck)puter上，每個(gè)處理器搜索完一個(gè)片段的素?cái)?shù)后，要把結(jié)果廣播給其他的處理器，這也帶來(lái)了并行計(jì)算的額外開銷(paralleloverhead)負(fù)載不均衡(load-balancing)：每個(gè)數(shù)值K需要的除法運(yùn)算次數(shù)相差很大通信開銷(communication)：通信啟動(dòng)的次數(shù)、每次交換的數(shù)據(jù)量提高并行的粒度(granularity),可以部分地解決“瓶頸”問題將[3，N)劃分成m個(gè)片段，分別由一個(gè)處理器搜索其中的素?cái)?shù)但并行的粒度要適中:在求素?cái)?shù)問題中,(1)確保沒有處理器等待進(jìn)入臨界區(qū)取得任務(wù),(2)確保沒有處理器等待要等待其他處理器的結(jié)果才能執(zhí)行自己的計(jì)算任務(wù),(3)減少每個(gè)處理器執(zhí)行的臨界區(qū)操作次數(shù),(4)處理器之間負(fù)載均衡粒度太小(fine-grain):對(duì)解決“瓶頸”的作用不大粒度太大(coarse-grain):將帶來(lái)兩方面的問題問題1：已完成了[3,x]中素?cái)?shù)的尋找，現(xiàn)在判斷K是否是素?cái)?shù)，但x2

K，需要對(duì)檢查[x+1,y]之間的奇數(shù)能否整除K(y2

K(y+1)2)，增加了除法運(yùn)算的次數(shù)問題2：處理器上分得的片段數(shù)會(huì)相差1，每個(gè)片段越大，負(fù)載越不均衡這兩個(gè)問題的解決只能靠人，根據(jù)具體的問題特征和計(jì)算平臺(tái)的特征來(lái)解決:保持消息交換/臨界區(qū)操作的成本與一個(gè)子任務(wù)的數(shù)據(jù)運(yùn)算成本的比率在合適的范圍比率太高,要提高任務(wù)的粒度,但會(huì)帶來(lái)負(fù)載均衡和伸縮性方面的問題.PRAM模型中,表現(xiàn)為NULL指令多BSP模型中,表現(xiàn)為每個(gè)superstep上通信成本的比重高比率太低,一般要減小任務(wù)的粒度并行程序的代碼結(jié)構(gòu)SPMD：SingleProgramMultipleData。編寫一個(gè)程序，該程序在執(zhí)行時(shí)同時(shí)求解不同的子任務(wù)。不同的子任務(wù)，執(zhí)行的控制流不同控制轉(zhuǎn)移、分支pthread、OpenMP、Dataparallel、CUDA、Messagepassing(通常用SPMD并行程序)MPMD：MultipleProgramMultipleData。編寫多個(gè)程序，分別求解不同的子任務(wù)CELLBE線程模型、Messagepassing(支持MPMD并行程序)并行程序開發(fā)涉及的問題問題的計(jì)算并行性分析劃分計(jì)算任務(wù)子任務(wù)間的數(shù)據(jù)交換和同步子任務(wù)間的同步處理器之間的負(fù)載均衡子任務(wù)的粒度并行程序開發(fā)涉及的問題問題的并行性分析：并行程序開發(fā)不是簡(jiǎn)單地將串行程序的循環(huán)分配到不同的處理器上執(zhí)行Identifyhotspots(通過編譯技術(shù)自動(dòng)識(shí)別有難度):應(yīng)用問題的主要計(jì)算開銷所在,集中精力做這部分的并行化Identifybottlenecks(通過編譯技術(shù)自動(dòng)識(shí)別有難度):兩類瓶頸沒有足夠多的并行子任務(wù)子任務(wù)的分配成本太高,消息交換分配/臨界區(qū)分配有時(shí)，需要設(shè)法打破數(shù)學(xué)算法引起的相關(guān)性(通過編譯技術(shù)自動(dòng)解決，一般效果不理想)在判斷一個(gè)整數(shù)K是否是素?cái)?shù)時(shí)，需要用到比K小的素?cái)?shù)用數(shù)組存儲(chǔ)找到的素?cái)?shù)時(shí)，從小到大依次存儲(chǔ)特別是對(duì)一些計(jì)算開銷大的循環(huán)，表面看起來(lái)是相關(guān)的，無(wú)法并行。仔細(xì)分析之后，是可以并行計(jì)算的計(jì)算小于N的素?cái)?shù):先計(jì)算小于SQRT(N)的素?cái)?shù),然后判斷其他的數(shù)字ai:先計(jì)算每個(gè)數(shù)組片段的局部和,再求總和劃分計(jì)算的策略:數(shù)據(jù)劃分也稱問題域劃分(domainposition)對(duì)問題涉及的數(shù)據(jù)進(jìn)行劃分每個(gè)子任務(wù)處理一部分?jǐn)?shù)據(jù)擁有者計(jì)算原則(putingrule):數(shù)據(jù)子集上的更新運(yùn)算作為一個(gè)子任務(wù)子任務(wù)需要訪問其它數(shù)據(jù)子集時(shí),執(zhí)行消息交換劃分計(jì)算的策略:任務(wù)劃分也成功能分解(functiona