LecNote-9-并行計算中的任務分配

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

ValniNi+1第I行非0元素的數(shù)量第I行第2個非0元素所在的列號第I行第2個非0元素的值第I+1行非0元素的數(shù)量動態(tài)任務分配的實現(xiàn)可以將整個superstep看做一個“子任務池”(pool)每次從“子任務池”中取一個出來，交給當前空閑的某個處理器/執(zhí)行內(nèi)核去執(zhí)行實現(xiàn)方式1：對等協(xié)同的(peer-to-peercollaborating)動態(tài)任務分配全部處理器/執(zhí)行內(nèi)核扮演的角色都是相同的負責處理“子任務池”中若干個子任務與其他處理器/執(zhí)行內(nèi)核協(xié)作，實現(xiàn)“子任務池”中子任務的分配采用“鎖”機制實現(xiàn)“子任務池”操作的確定性任何時刻，只有一個處理器/執(zhí)行內(nèi)核操作“子任務池”例如求素數(shù)問題的pthread并行程序實現(xiàn)方式2：集中調(diào)度的(master-slave)動態(tài)任務分配各處理器扮演不同的角色：一個處理器/執(zhí)行內(nèi)核(master)專門負責“子任務池”的維護，其他處理器/執(zhí)行內(nèi)核(slave)負責子任務的數(shù)據(jù)處理master和slave采用“消息交換”機制實現(xiàn)子任務的分配當一個slave空閑時，通過消息告訴mastermaster從“子任務池”中取出一個任務，通過消息通知slave執(zhí)行該子任務POSIX并行程序中的動態(tài)任務分配superstep是數(shù)據(jù)并行的：子任務的數(shù)量不確定、或者子任務的復雜性不一致peer-to-peercollaborating的動態(tài)任務劃分開發(fā)一個函數(shù)，同時由各個并發(fā)線程分別執(zhí)行鎖機制，實現(xiàn)線程之間對“子任務池”操作的同步CELL處理器上的計算任務分配PCAM：將問題表示成若干個superstep四類superstep只有一個子任務：PPE做、還是SPE做？流水并行Mailbox：子任務間的同步DMA：子任務間的數(shù)據(jù)交換數(shù)據(jù)并行，子任務的數(shù)量確定、子任務的復雜性一致：還能靜態(tài)任務劃分嗎？數(shù)據(jù)并行，但子任務的數(shù)量不確定、或者子任務的復雜性不一致：master-slave的動態(tài)任務劃分無論是流水并行、還是數(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上每個子任務的數(shù)據(jù)規(guī)模要更小Largesingle-SPEprogrammingmodels–JobQueueCodeanddatapackagedtogetherasinputstoanSPEkernelprogramAmulti-taskingmodelmorediscussionlaterCELL上的計算任務劃分：superstep上只有一個子任務PPE控制：決定何時開始子任務的執(zhí)行與上、下的superstep同步SPE做子任務的數(shù)據(jù)處理子任務足夠“小”：數(shù)據(jù)+代碼<256KBSmallsingle-SPEmodels子任務比較“大”：數(shù)據(jù)+代碼>256KB代碼不可拆、數(shù)據(jù)可拆：流計算模式(streamingmodel)Largesingle-SPEprogrammingmodels–I/Odata開發(fā)一個SPE程序：取一部分數(shù)據(jù)，做完后回寫結果，再取一部分數(shù)據(jù)可采用雙緩沖技術，降低DMA延遲對性能的影響代碼和數(shù)據(jù)要同時拆Largesingle-SPEprogrammingmodels–JobQueue開發(fā)多個SPE程序，構成一個SPE的執(zhí)行隊列執(zhí)行完一個SPE程序后，在執(zhí)行另一個SPE程序Multi-tasking：站在PPE的角度，如何看SPEsSPEasadeviceresourceSPEasaheterogeneousprocessorSPEresourcerepresentedasafilesystemPPE按照Functionoffloading模式，利用SPE提高計算效率PPE維護一個子任務池，通過CESOF機制，建立每個子任務與SPE程序的對應關系需要執(zhí)行子任務池中的某個子任務時，通過SPEManagementRuntimeLibrary分配一個SPU、啟動SPE程序運行PPE和SPE之間通過MFC通信Mailbox：同步、任務描述數(shù)據(jù)DMA：任務數(shù)據(jù)到LS的數(shù)據(jù)傳輸Parallelprogrammingmodels–StreamingSPEinitiatedDMALargearrayofdatafedthroughagroupofSPEprogramsAspecialcaseofjobqueuewithregulardataEachSPEprogramlocksonthesharedjobqueuetoobtainnextjobForunevenjobs,workloadsareself-balancedamongavailableSPEsCELL上的計算任務劃分：基于數(shù)據(jù)分解發(fā)現(xiàn)superstep上的子任務動態(tài)任務分配無所謂靜態(tài)任務分配，SPE只有256KB開發(fā)一個SPE程序，在各個SPU上運行PPE通過Mailbox分派SPE需要執(zhí)行的子任務：輸入數(shù)據(jù)、輸出數(shù)據(jù)的EA獲得子任務的執(zhí)行進度：一個子任務完成后，再分配一個新的子任務SPE/PPE通過DMA將子任務處理的數(shù)據(jù)傳輸?shù)絃S將子任務的結果從LS傳輸?shù)組emoryParallelprogrammingmodels–PipelineUseLStoLSDMAbandwidth,notsystemmemorybandwidthFlexibilityinconnectingpipelinefunctionsLargercollectivecodesizeperpipelineLoad-balanceisharderCELL上的計算任務劃分：流水并行的superstep為每個子任務，分別開發(fā)一個SPE程序，運行在一個SPU上PPE通過Mailbox向其中一個SPE分派需要處理的數(shù)據(jù)集合：輸入數(shù)據(jù)、輸出數(shù)據(jù)的EA獲得數(shù)據(jù)集合在該SPE上的執(zhí)行進度：一數(shù)據(jù)集合完成后，再分配一個新的數(shù)據(jù)集合SPE之間通過DMA：將上一個子任務的結果傳遞到下一個子任務所在的LS通過Mailbox：實現(xiàn)SPE之間的進度同步CELL處理器：PCAMP：通過功能分解、數(shù)據(jù)分解，尋找并行性。解決三方面的問題并行程序的伸縮性并行計算任務劃分的負載均衡性每個子任務足夠“小”：數(shù)據(jù)+代碼<256KBC：檢查子任務間的依賴關系，發(fā)現(xiàn)規(guī)劃必須滿足的約束條件A：選擇合適的子任務粒度，減小并行計算的額外開銷：合并后的子任務必須足夠“小”子任務分配開銷子任務間的通信開銷子任務間的同步開銷M：將子任務組織成若干個superstep在相鄰的superstep上，如果都只有一個子任務，不要輕易將他們合并成一個superstep：每個子任務要足夠“小”CELL處理器：并行計算的實現(xiàn)總有一個Master：PPE每個superstep至少一個slavesuperstep上的所有子任務都由slave執(zhí)行slave是運行在SPU上的SPE程序可以有多個slave流水并行時，各個slave分別運行不同的SPE程序數(shù)據(jù)并行時，各個slave運行相同的SPE程序并行程序：CESOF一個PPE程序多個SPE程序SPE程序被嵌在PPE程序中并行計算機體系結構對并行程序開發(fā)的影響從PCAM看，針對Intel多核處理器和IBMCELL處理器，并行算法的設計結果是不同的靠編譯技術實現(xiàn)串行程序的自動并行化成了一個不可能實現(xiàn)的夢想從并行程序中數(shù)據(jù)并行的計算任務分配方法看Intel多核處理器采用對等協(xié)作的計算模式IBMCELL處理器采用集中調(diào)度的計算模式從并行程序中對處理器/執(zhí)行內(nèi)核資源的管理方法看Intel多核處理器采用POSIX線程庫管理處理器/執(zhí)行內(nèi)核資源，實現(xiàn)子任務到處理器/執(zhí)行內(nèi)核資源的分配IBMCELL處理器采用SPEManagementruntimelibrary管理處理器/執(zhí)行內(nèi)核資源，實現(xiàn)子任務到處理器/執(zhí)行內(nèi)核資源的分配不同并行計算機體系結構下的并行程序開發(fā)為什么會有這么大的差別？串行編程時，為PowerPC寫的C語言程序可以直接在