LecNote-9-并行計(jì)算中的任務(wù)分配

第九講并行計(jì)算中的任務(wù)分配任務(wù)分配方法靜態(tài)任務(wù)分配動態(tài)任務(wù)分配動態(tài)任務(wù)分配的實(shí)現(xiàn)對等協(xié)同：peer-to-peercollaborating集中調(diào)度：master-slavePOSIX并行程序中的計(jì)算任務(wù)劃分對等協(xié)同鎖信號量CELLBE上的計(jì)算任務(wù)劃分集中調(diào)度郵箱DMA數(shù)據(jù)傳輸并行算法設(shè)計(jì)：BSP與PCAMBSP：子任務(wù)在時(shí)間和空間上的規(guī)劃時(shí)間上的規(guī)劃：整個算法由若干個串行執(zhí)行的superstep組成空間上的規(guī)劃：每個superstep上包含一組互相獨(dú)立的子任務(wù)PCAM：發(fā)現(xiàn)問題中的子任務(wù)、產(chǎn)生規(guī)劃的方法P：通過功能分解、數(shù)據(jù)分解，尋找并行性。解決兩方面的問題并行程序的伸縮性并行計(jì)算任務(wù)劃分的負(fù)載均衡性C：檢查子任務(wù)間的依賴關(guān)系，發(fā)現(xiàn)規(guī)劃必須滿足的約束條件A：選擇合適的子任務(wù)粒度，減小并行計(jì)算的額外開銷子任務(wù)分配開銷子任務(wù)間的通信開銷子任務(wù)間的同步開銷M：將子任務(wù)組織成若干個superstep并行計(jì)算中的任務(wù)分配方法并行算法設(shè)計(jì)的結(jié)果:BSP模型若干個順序執(zhí)行的superstep每個superstep上是一組互相獨(dú)立的子任務(wù)這些子任務(wù)是通過功能分解發(fā)現(xiàn)的：子任務(wù)的數(shù)量有限、與被處理數(shù)據(jù)的規(guī)模無關(guān)這些子任務(wù)是通過數(shù)據(jù)分解發(fā)現(xiàn)的：被處理的數(shù)據(jù)規(guī)模越大，子任務(wù)的數(shù)量越多在每個superstep上，如何確定各個處理器/執(zhí)行內(nèi)核上的子任務(wù)靜態(tài)任務(wù)分配：在開始superstep上的數(shù)據(jù)處理之前，已經(jīng)確定了需要執(zhí)行其中的哪些子任務(wù)例如N-Body問題的實(shí)現(xiàn)動態(tài)任務(wù)分配：superstep的數(shù)據(jù)處理過程中，動態(tài)確定每個處理器/執(zhí)行內(nèi)核上的子任務(wù)。例如求素?cái)?shù)問題靜態(tài)任務(wù)分配：通過功能分解得到superstep上的一組子任務(wù)每個子任務(wù)分別實(shí)現(xiàn)一個子功能，子任務(wù)的數(shù)量有限一個處理器/執(zhí)行內(nèi)核負(fù)責(zé)一個子任務(wù)并行程序伸縮性(scalability)不好負(fù)載均衡難以控制：取決于子任務(wù)算法的復(fù)雜性、所涉及的數(shù)據(jù)規(guī)模等子任務(wù)之間的關(guān)系形式1：互相獨(dú)立，各自處理不同的數(shù)據(jù)集合形式2：構(gòu)成一個流水，依次對一組數(shù)據(jù)集合進(jìn)行處理。數(shù)據(jù)集合的數(shù)量很大子任務(wù)1子任務(wù)2子任務(wù)3子任務(wù)4數(shù)據(jù)集合1數(shù)據(jù)集合2數(shù)據(jù)集合3數(shù)據(jù)集合4數(shù)據(jù)集合1數(shù)據(jù)集合1數(shù)據(jù)集合2數(shù)據(jù)集合2數(shù)據(jù)集合3數(shù)據(jù)集合3數(shù)據(jù)集合4數(shù)據(jù)集合5數(shù)據(jù)集合4數(shù)據(jù)集合1數(shù)據(jù)集合2數(shù)據(jù)集合3數(shù)據(jù)集合1數(shù)據(jù)集合2子任務(wù)的計(jì)算復(fù)雜性形式1的數(shù)據(jù)劃分形式2的數(shù)據(jù)劃分靜態(tài)任務(wù)分配：通過數(shù)據(jù)分解得到superstep上的一組子任務(wù)各個子任務(wù)的數(shù)據(jù)處理功能相同，各自處理不同的數(shù)據(jù)集合子任務(wù)之間互相獨(dú)立子任務(wù)的數(shù)量大一個處理器/執(zhí)行內(nèi)核在開始superstep上的數(shù)據(jù)處理之前，先確定需要處理其中哪些子任務(wù)并行程序有好的伸縮性(scalability)負(fù)載均衡問題子任務(wù)具有相同的運(yùn)算量、且處理器/執(zhí)行內(nèi)核的性能相同，具有好的負(fù)載均衡性例如在Intel多核處理器上執(zhí)行Laplace計(jì)算子任務(wù)的運(yùn)算量不一致、或者處理器/執(zhí)行內(nèi)核的性能不一致時(shí)，難以控制負(fù)載均衡。例如在Intel多核處理器上執(zhí)行求素?cái)?shù)計(jì)算在CELL處理器上執(zhí)行Laplace計(jì)算，讓PPE和8個SPE分別負(fù)責(zé)一部分?jǐn)?shù)據(jù)處理靜態(tài)任務(wù)分配在POSIX線程并行程序中的實(shí)現(xiàn)superstep上的子任務(wù)是通過功能分解發(fā)現(xiàn)的：每個子任務(wù)分別處理不同的數(shù)據(jù)集合為每個子任務(wù)各編寫一個函數(shù)，分別由一個并發(fā)線程執(zhí)行superstep上的子任務(wù)是通過功能分解發(fā)現(xiàn)：每個數(shù)據(jù)集合要經(jīng)過這些子任務(wù)依次處理——流水并行每個子任務(wù)分別開發(fā)一個函數(shù)，各由一個線程執(zhí)行子任務(wù)之間通過條件信號進(jìn)行同步superstep上的子任務(wù)是通過數(shù)據(jù)分解發(fā)現(xiàn)的：數(shù)據(jù)并行——子任務(wù)的數(shù)量確定、子任務(wù)的復(fù)雜性一致編寫一個函數(shù)根據(jù)并發(fā)線程的數(shù)量和自己的ID，計(jì)算自己負(fù)責(zé)哪些子任務(wù)實(shí)現(xiàn)子任務(wù)的數(shù)據(jù)處理功能創(chuàng)建多個并發(fā)線程，同時(shí)執(zhí)行這個函數(shù)動態(tài)任務(wù)分配動態(tài)任務(wù)分配：處理器/執(zhí)行內(nèi)核完成一個子任務(wù)后，再分配一個新的子任務(wù)什么樣的并行子任務(wù)能夠動態(tài)分配？基于數(shù)據(jù)分解發(fā)現(xiàn)的子任務(wù)各個處理器/執(zhí)行內(nèi)核運(yùn)行的算法要相同：都能實(shí)現(xiàn)子任務(wù)需要的數(shù)據(jù)處理功能子任務(wù)要互相獨(dú)立，分別處理不同的數(shù)據(jù)集合為什么需要動態(tài)任務(wù)分配？平衡負(fù)載子任務(wù)的計(jì)算量不一致。例如求素?cái)?shù)問題處理器/執(zhí)行內(nèi)核的性能不一致。例如：在CELL處理器上，讓PPE和8個SPE分別負(fù)責(zé)一部分子任務(wù)的處理子任務(wù)的數(shù)量不確定。例如圖書館查詢、銀行記帳等大規(guī)模并發(fā)用戶的計(jì)算問題處理一個數(shù)據(jù)文件中的記錄，每個記錄作為一個子任務(wù)分別處理。各個記錄不定長，讀到文件末尾才知道總的記錄數(shù)。例如：一個稀疏矩陣與向量的乘法運(yùn)算，部分行中全部是0元素。稀疏矩陣按照行優(yōu)先存儲在文件中NiC1Val1C2Val2C2Val3Cni

ValniNi+1第I行非0元素的數(shù)量第I行第2個非0元素所在的列號第I行第2個非0元素的值第I+1行非0元素的數(shù)量動態(tài)任務(wù)分配的實(shí)現(xiàn)可以將整個superstep看做一個“子任務(wù)池”(pool)每次從“子任務(wù)池”中取一個出來，交給當(dāng)前空閑的某個處理器/執(zhí)行內(nèi)核去執(zhí)行實(shí)現(xiàn)方式1：對等協(xié)同的(peer-to-peercollaborating)動態(tài)任務(wù)分配全部處理器/執(zhí)行內(nèi)核扮演的角色都是相同的負(fù)責(zé)處理“子任務(wù)池”中若干個子任務(wù)與其他處理器/執(zhí)行內(nèi)核協(xié)作，實(shí)現(xiàn)“子任務(wù)池”中子任務(wù)的分配采用“鎖”機(jī)制實(shí)現(xiàn)“子任務(wù)池”操作的確定性任何時(shí)刻，只有一個處理器/執(zhí)行內(nèi)核操作“子任務(wù)池”例如求素?cái)?shù)問題的pthread并行程序?qū)崿F(xiàn)方式2：集中調(diào)度的(master-slave)動態(tài)任務(wù)分配各處理器扮演不同的角色：一個處理器/執(zhí)行內(nèi)核(master)專門負(fù)責(zé)“子任務(wù)池”的維護(hù)，其他處理器/執(zhí)行內(nèi)核(slave)負(fù)責(zé)子任務(wù)的數(shù)據(jù)處理master和slave采用“消息交換”機(jī)制實(shí)現(xiàn)子任務(wù)的分配當(dāng)一個slave空閑時(shí)，通過消息告訴mastermaster從“子任務(wù)池”中取出一個任務(wù)，通過消息通知slave執(zhí)行該子任務(wù)POSIX并行程序中的動態(tài)任務(wù)分配superstep是數(shù)據(jù)并行的：子任務(wù)的數(shù)量不確定、或者子任務(wù)的復(fù)雜性不一致peer-to-peercollaborating的動態(tài)任務(wù)劃分開發(fā)一個函數(shù)，同時(shí)由各個并發(fā)線程分別執(zhí)行鎖機(jī)制，實(shí)現(xiàn)線程之間對“子任務(wù)池”操作的同步CELL處理器上的計(jì)算任務(wù)分配PCAM：將問題表示成若干個superstep四類superstep只有一個子任務(wù)：PPE做、還是SPE做？流水并行Mailbox：子任務(wù)間的同步DMA：子任務(wù)間的數(shù)據(jù)交換數(shù)據(jù)并行，子任務(wù)的數(shù)量確定、子任務(wù)的復(fù)雜性一致：還能靜態(tài)任務(wù)劃分嗎？數(shù)據(jù)并行，但子任務(wù)的數(shù)量不確定、或者子任務(wù)的復(fù)雜性不一致：master-slave的動態(tài)任務(wù)劃分無論是流水并行、還是數(shù)據(jù)并行，PPE扮演什么樣的角色？CellprogrammingmodelsSingleCellenvironment:PPEprogrammingmodelsSPEProgrammingmodelsSmallsingle-SPEmodelsLargesingle-SPEmodelsMulti-SPEparallelprogrammingmodelsCellEmbeddedSPEObjectFormat(CESOF)Multi-taskingSPEsLocalStoreresidentmulti-taskingSelf-managedmulti-taskingKernel-managedSPEschedulingandvirtualizationPPEprogrammingmodelPPEisa64-bitPowerPCcore,hostingoperatingsystemsandhypervisorPPEprograminheritstraditionalprogrammingmodelsCellenvironment:aPPEprogramservesasacontrollerorfacilitatorCESOFsupportprovidesSPEimagehandlestothePPEruntimePPEprogramestablishesaruntimeenvironmentforSPEprograms?e.g.memorymapping,exceptionhandling,SPEruncontrolItallocatesandmanagesCellsystemresources?SPEscheduling,hypervisorCBEAresourcemanagementItprovidesOSservicestoSPEprogramsandthreads?e.g.printf,fileI/OSmallsingle-SPEmodelsSingletaskedenvironmentSmallenoughtofitintoa256KB-localstoreSufficientformanydedicatedworkloadsSeparatedSPEandPPEaddressspaces–LS/EAExplicitinputandoutputoftheSPEprogramProgramargumentsandexitcodeperSPEABI(applicationbinaryinterface)DMAMailboxesSPEsidesystemcallsSmallsingle-SPEmodels–toolsandenvironmentSPEcompiler/linkercompilesandlinksanSPEexecutableTheSPEexecutableimageisembeddedasreference-ableROdatainthePPEexecutable(CESOF)ACellprogrammercontrolsanSPEprogramviaaPPEcontrollingprocessanditsSPEmanagementlibraryi.e.loads,initializes,starts/stopsanSPEprogramThePPEcontrollingprocess,OS/PPE,andruntime/(PPEorSPE)togetherestablishtheSPEruntimeenvironment,e.g.argumentpassing,memorymapping,systemcallservice.outputSmallsingle-SPEmodels–asample/*spe_foo.c:ACprogramtobecompiledintoanexecutablecalled“spe_foo”*/intmain(int

speid,addr64argp,addr64envp){chari;/*dosomethingintelligenthere*/i=func_foo(argp);/*whenthesyscallissupported*/printf(“Helloworld!myresultis%d\n”,i);returni;}ABI:applicationbinaryinterfaceABISmallsingle-SPEmodels–PPEcontrollingprogramexternspe_program_handle

spe_foo;/*thespeimagehandlefromCESOF*/intmain(){int

rc,status;speid_t

spe_id;/*load&startthespe_fooprogramonanallocatedspe*/spe_id=

spe_create_thread

(0,&spe_foo,0,NULL,-1,0);/*waitforspe

prog.tocompleteandreturnfinalstatus*/rc=spe_wait

(spe_id,&status,0);returnstatus;}Largesingle-SPEprogrammingmodelsDataorcodeworkingsetcannotfitcompletelyintoalocalstoreThePPEcontrollingprocess,kernel,andlibsperuntimesetupthesystemmemorymappingasSPE’ssecondarymemorystoreTheSPEprogramaccessesthesecondarymemorystoreviaitssoftware-controlledSPEDMAengineMemoryFlowController(MFC)Largesingle-SPEprogrammingmodels–I/OdataSystemmemoryforlargesizeinput/outputdatae.g.StreamingmodelLargesingle-SPEprogrammingmodels-DMADMAlatencyhandlingiscriticaltooverallperformanceforSPEprogramsmovinglargedataorcodeDatapre-fetchingisakeytechniquetohideDMAlatencye.g.double-buffering在此策略下，SPE上每個子任務(wù)的數(shù)據(jù)規(guī)模要更小Largesingle-SPEprogrammingmodels–JobQueueCodeanddatapackagedtogetherasinputstoanSPEkernelprogramAmulti-taskingmodelmorediscussionlaterCELL上的計(jì)算任務(wù)劃分：superstep上只有一個子任務(wù)PPE控制：決定何時(shí)開始子任務(wù)的執(zhí)行與上、下的superstep同步SPE做子任務(wù)的數(shù)據(jù)處理子任務(wù)足夠“小”：數(shù)據(jù)+代碼<256KBSmallsingle-SPEmodels子任務(wù)比較“大”：數(shù)據(jù)+代碼>256KB代碼不可拆、數(shù)據(jù)可拆：流計(jì)算模式(streamingmodel)Largesingle-SPEprogrammingmodels–I/Odata開發(fā)一個SPE程序：取一部分?jǐn)?shù)據(jù)，做完后回寫結(jié)果，再取一部分?jǐn)?shù)據(jù)可采用雙緩沖技術(shù)，降低DMA延遲對性能的影響代碼和數(shù)據(jù)要同時(shí)拆Largesingle-SPEprogrammingmodels–JobQueue開發(fā)多個SPE程序，構(gòu)成一個SPE的執(zhí)行隊(duì)列執(zhí)行完一個SPE程序后，在執(zhí)行另一個SPE程序Multi-tasking：站在PPE的角度，如何看SPEsSPEasadeviceresourceSPEasaheterogeneousprocessorSPEresourcerepresentedasafilesystemPPE按照Functionoffloading模式，利用SPE提高計(jì)算效率PPE維護(hù)一個子任務(wù)池，通過CESOF機(jī)制，建立每個子任務(wù)與SPE程序的對應(yīng)關(guān)系需要執(zhí)行子任務(wù)池中的某個子任務(wù)時(shí)，通過SPEManagementRuntimeLibrary分配一個SPU、啟動SPE程序運(yùn)行PPE和SPE之間通過MFC通信Mailbox：同步、任務(wù)描述數(shù)據(jù)DMA：任務(wù)數(shù)據(jù)到LS的數(shù)據(jù)傳輸Parallelprogrammingmodels–StreamingSPEinitiatedDMALargearrayofdatafedthroughagroupofSPEprogramsAspecialcaseofjobqueuewithregulardataEachSPEprogramlocksonthesharedjobqueuetoobtainnextjobForunevenjobs,workloadsareself-balancedamongavailableSPEsCELL上的計(jì)算任務(wù)劃分：基于數(shù)據(jù)分解發(fā)現(xiàn)superstep上的子任務(wù)動態(tài)任務(wù)分配無所謂靜態(tài)任務(wù)分配，SPE只有256KB開發(fā)一個SPE程序，在各個SPU上運(yùn)行PPE通過Mailbox分派SPE需要執(zhí)行的子任務(wù)：輸入數(shù)據(jù)、輸出數(shù)據(jù)的EA獲得子任務(wù)的執(zhí)行進(jìn)度：一個子任務(wù)完成后，再分配一個新的子任務(wù)SPE/PPE通過DMA將子任務(wù)處理的數(shù)據(jù)傳輸?shù)絃S將子任務(wù)的結(jié)果從LS傳輸?shù)組emoryParallelprogrammingmodels–PipelineUseLStoLSDMAbandwidth,notsystemmemorybandwidthFlexibilityinconnectingpipelinefunctionsLargercollectivecodesizeperpipelineLoad-balanceisharderCELL上的計(jì)算任務(wù)劃分：流水并行的superstep為每個子任務(wù)，分別開發(fā)一個SPE程序，運(yùn)行在一個SPU上PPE通過Mailbox向其中一個SPE分派需要處理的數(shù)據(jù)集合：輸入數(shù)據(jù)、輸出數(shù)據(jù)的EA獲得數(shù)據(jù)集合在該SPE上的執(zhí)行進(jìn)度：一數(shù)據(jù)集合完成后，再分配一個新的數(shù)據(jù)集合SPE之間通過DMA：將上一個子任務(wù)的結(jié)果傳遞到下一個子任務(wù)所在的LS通過Mailbox：實(shí)現(xiàn)SPE之間的進(jìn)度同步CELL處理器：PCAMP：通過功能分解、數(shù)據(jù)分解，尋找并行性。解決三方面的問題并行程序的伸縮性并行計(jì)算任務(wù)劃分的負(fù)載均衡性每個子任務(wù)足夠“小”：數(shù)據(jù)+代碼<256KBC：檢查子任務(wù)間的依賴關(guān)系，發(fā)現(xiàn)規(guī)劃必須滿足的約束條件A：選擇合適的子任務(wù)粒度，減小并行計(jì)算的額外開銷：合并后的子任務(wù)必須足夠“小”子任務(wù)分配開銷子任務(wù)間的通信開銷子任務(wù)間的同步開銷M：將子任務(wù)組織成若干個superstep在相鄰的superstep上，如果都只有一個子任務(wù)，不要輕易將他們合并成一個superstep：每個子任務(wù)要足夠“小”CELL處理器：并行計(jì)算的實(shí)現(xiàn)總有一個Master：PPE每個superstep至少一個slavesuperstep上的所有子任務(wù)都由slave執(zhí)行slave是運(yùn)行在SPU上的SPE程序可以有多個slave流水并行時(shí)，各個slave分別運(yùn)行不同的SPE程序數(shù)據(jù)并行時(shí)，各個slave運(yùn)行相同的SPE程序并行程序：CESOF一個PPE程序多個SPE程序SPE程序被嵌在PPE程序中并行計(jì)算機(jī)體系結(jié)構(gòu)對并行程序開發(fā)的影響從PCAM看，針對Intel多核處理器和IBMCELL處理器，并行算法的設(shè)計(jì)結(jié)果是不同的靠編譯技術(shù)實(shí)現(xiàn)串行程序的自動并行化成了一個不可能實(shí)現(xiàn)的夢想從并行程序中數(shù)據(jù)并行的計(jì)算任務(wù)分配方法看Intel多核處理器采用對等協(xié)作的計(jì)算模式IBMCELL處理器采用集中調(diào)度的計(jì)算模式從并行程序中對處理器/執(zhí)行內(nèi)核資源的管理方法看Intel多核處理器采用POSIX線程庫管理處理器/執(zhí)行內(nèi)核資源，實(shí)現(xiàn)子任務(wù)到處理器/執(zhí)行內(nèi)核資源的分配IBMCELL處理器采用SPEManagementruntimelibrary管理處理器/執(zhí)行內(nèi)核資源，實(shí)現(xiàn)子任務(wù)到處理器/執(zhí)行內(nèi)核資源的分配不同并行計(jì)算機(jī)體系結(jié)構(gòu)下的并行程序開發(fā)為什么會有這么大的差別？串行編程時(shí)，為PowerPC寫的C語言程序可以直接在