LecNote-9-并行计算中的任务分配

第九讲并行计算中的任务分配任务分配方法静态任务分配动态任务分配动态任务分配的实现对等协同：peer-to-peercollaborating集中调度：master-slavePOSIX并行程序中的计算任务划分对等协同锁信号量CELLBE上的计算任务划分集中调度邮箱DMA数据传输并行算法设计：BSP与PCAMBSP：子任务在时间和空间上的规划时间上的规划：整个算法由若干个串行执行的superstep组成空间上的规划：每个superstep上包含一组互相独立的子任务PCAM：发现问题中的子任务、产生规划的方法P：通过功能分解、数据分解，寻找并行性。解决两方面的问题并行程序的伸缩性并行计算任务划分的负载均衡性C：检查子任务间的依赖关系，发现规划必须满足的约束条件A：选择合适的子任务粒度，减小并行计算的额外开销子任务分配开销子任务间的通信开销子任务间的同步开销M：将子任务组织成若干个superstep并行计算中的任务分配方法并行算法设计的结果:BSP模型若干个顺序执行的superstep每个superstep上是一组互相独立的子任务这些子任务是通过功能分解发现的：子任务的数量有限、与被处理数据的规模无关这些子任务是通过数据分解发现的：被处理的数据规模越大，子任务的数量越多在每个superstep上，如何确定各个处理器/执行内核上的子任务静态任务分配：在开始superstep上的数据处理之前，已经确定了需要执行其中的哪些子任务例如N-Body问题的实现动态任务分配：superstep的数据处理过程中，动态确定每个处理器/执行内核上的子任务。例如求素数问题静态任务分配：通过功能分解得到superstep上的一组子任务每个子任务分别实现一个子功能，子任务的数量有限一个处理器/执行内核负责一个子任务并行程序伸缩性(scalability)不好负载均衡难以控制：取决于子任务算法的复杂性、所涉及的数据规模等子任务之间的关系形式1：互相独立，各自处理不同的数据集合形式2：构成一个流水，依次对一组数据集合进行处理。数据集合的数量很大子任务1子任务2子任务3子任务4数据集合1数据集合2数据集合3数据集合4数据集合1数据集合1数据集合2数据集合2数据集合3数据集合3数据集合4数据集合5数据集合4数据集合1数据集合2数据集合3数据集合1数据集合2子任务的计算复杂性形式1的数据划分形式2的数据划分静态任务分配：通过数据分解得到superstep上的一组子任务各个子任务的数据处理功能相同，各自处理不同的数据集合子任务之间互相独立子任务的数量大一个处理器/执行内核在开始superstep上的数据处理之前，先确定需要处理其中哪些子任务并行程序有好的伸缩性(scalability)负载均衡问题子任务具有相同的运算量、且处理器/执行内核的性能相同，具有好的负载均衡性例如在Intel多核处理器上执行Laplace计算子任务的运算量不一致、或者处理器/执行内核的性能不一致时，难以控制负载均衡。例如在Intel多核处理器上执行求素数计算在CELL处理器上执行Laplace计算，让PPE和8个SPE分别负责一部分数据处理静态任务分配在POSIX线程并行程序中的实现superstep上的子任务是通过功能分解发现的：每个子任务分别处理不同的数据集合为每个子任务各编写一个函数，分别由一个并发线程执行superstep上的子任务是通过功能分解发现：每个数据集合要经过这些子任务依次处理——流水并行每个子任务分别开发一个函数，各由一个线程执行子任务之间通过条件信号进行同步superstep上的子任务是通过数据分解发现的：数据并行——子任务的数量确定、子任务的复杂性一致编写一个函数根据并发线程的数量和自己的ID，计算自己负责哪些子任务实现子任务的数据处理功能创建多个并发线程，同时执行这个函数动态任务分配动态任务分配：处理器/执行内核完成一个子任务后，再分配一个新的子任务什么样的并行子任务能够动态分配？基于数据分解发现的子任务各个处理器/执行内核运行的算法要相同：都能实现子任务需要的数据处理功能子任务要互相独立，分别处理不同的数据集合为什么需要动态任务分配？平衡负载子任务的计算量不一致。例如求素数问题处理器/执行内核的性能不一致。例如：在CELL处理器上，让PPE和8个SPE分别负责一部分子任务的处理子任务的数量不确定。例如图书馆查询、银行记帐等大规模并发用户的计算问题处理一个数据文件中的记录，每个记录作为一个子任务分别处理。各个记录不定长，读到文件末尾才知道总的记录数。例如：一个稀疏矩阵与向量的乘法运算，部分行中全部是0元素。稀疏矩阵按照行优先存储在文件中NiC1Val1C2Val2C2Val3Cni

ValniNi+1第I行非0元素的数量第I行第2个非0元素所在的列号第I行第2个非0元素的值第I+1行非0元素的数量动态任务分配的实现可以将整个superstep看做一个“子任务池”(pool)每次从“子任务池”中取一个出来，交给当前空闲的某个处理器/执行内核去执行实现方式1：对等协同的(peer-to-peercollaborating)动态任务分配全部处理器/执行内核扮演的角色都是相同的负责处理“子任务池”中若干个子任务与其他处理器/执行内核协作，实现“子任务池”中子任务的分配采用“锁”机制实现“子任务池”操作的确定性任何时刻，只有一个处理器/执行内核操作“子任务池”例如求素数问题的pthread并行程序实现方式2：集中调度的(master-slave)动态任务分配各处理器扮演不同的角色：一个处理器/执行内核(master)专门负责“子任务池”的维护，其他处理器/执行内核(slave)负责子任务的数据处理master和slave采用“消息交换”机制实现子任务的分配当一个slave空闲时，通过消息告诉mastermaster从“子任务池”中取出一个任务，通过消息通知slave执行该子任务POSIX并行程序中的动态任务分配superstep是数据并行的：子任务的数量不确定、或者子任务的复杂性不一致peer-to-peercollaborating的动态任务划分开发一个函数，同时由各个并发线程分别执行锁机制，实现线程之间对“子任务池”操作的同步CELL处理器上的计算任务分配PCAM：将问题表示成若干个superstep四类superstep只有一个子任务：PPE做、还是SPE做？流水并行Mailbox：子任务间的同步DMA：子任务间的数据交换数据并行，子任务的数量确定、子任务的复杂性一致：还能静态任务划分吗？数据并行，但子任务的数量不确定、或者子任务的复杂性不一致：master-slave的动态任务划分无论是流水并行、还是数据并行，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上每个子任务的数据规模要更小Largesingle-SPEprogrammingmodels–JobQueueCodeanddatapackagedtogetherasinputstoanSPEkernelprogramAmulti-taskingmodelmorediscussionlaterCELL上的计算任务划分：superstep上只有一个子任务PPE控制：决定何时开始子任务的执行与上、下的superstep同步SPE做子任务的数据处理子任务足够“小”：数据+代码<256KBSmallsingle-SPEmodels子任务比较“大”：数据+代码>256KB代码不可拆、数据可拆：流计算模式(streamingmodel)Largesingle-SPEprogrammingmodels–I/Odata开发一个SPE程序：取一部分数据，做完后回写结果，再取一部分数据可采用双缓冲技术，降低DMA延迟对性能的影响代码和数据要同时拆Largesingle-SPEprogrammingmodels–JobQueue开发多个SPE程序，构成一个SPE的执行队列执行完一个SPE程序后，在执行另一个SPE程序Multi-tasking：站在PPE的角度，如何看SPEsSPEasadeviceresourceSPEasaheterogeneousprocessorSPEresourcerepresentedasafilesystemPPE按照Functionoffloading模式，利用SPE提高计算效率PPE维护一个子任务池，通过CESOF机制，建立每个子任务与SPE程序的对应关系需要执行子任务池中的某个子任务时，通过SPEManagementRuntimeLibrary分配一个SPU、启动SPE程序运行PPE和SPE之间通过MFC通信Mailbox：同步、任务描述数据DMA：任务数据到LS的数据传输Parallelprogrammingmodels–StreamingSPEinitiatedDMALargearrayofdatafedthroughagroupofSPEprogramsAspecialcaseofjobqueuewithregulardataEachSPEprogramlocksonthesharedjobqueuetoobtainnextjobForunevenjobs,workloadsareself-balancedamongavailableSPEsCELL上的计算任务划分：基于数据分解发现superstep上的子任务动态任务分配无所谓静态任务分配，SPE只有256KB开发一个SPE程序，在各个SPU上运行PPE通过Mailbox分派SPE需要执行的子任务：输入数据、输出数据的EA获得子任务的执行进度：一个子任务完成后，再分配一个新的子任务SPE/PPE通过DMA将子任务处理的数据传输到LS将子任务的结果从LS传输到MemoryParallelprogrammingmodels–PipelineUseLStoLSDMAbandwidth,notsystemmemorybandwidthFlexibilityinconnectingpipelinefunctionsLargercollectivecodesizeperpipelineLoad-balanceisharderCELL上的计算任务划分：流水并行的superstep为每个子任务，分别开发一个SPE程序，运行在一个SPU上PPE通过Mailbox向其中一个SPE分派需要处理的数据集合：输入数据、输出数据的EA获得数据集合在该SPE上的执行进度：一数据集合完成后，再分配一个新的数据集合SPE之间通过DMA：将上一个子任务的结果传递到下一个子任务所在的LS通过Mailbox：实现SPE之间的进度同步CELL处理器：PCAMP：通过功能分解、数据分解，寻找并行性。解决三方面的问题并行程序的伸缩性并行计算任务划分的负载均衡性每个子任务足够“小”：数据+代码<256KBC：检查子任务间的依赖关系，发现规划必须满足的约束条件A：选择合适的子任务粒度，减小并行计算的额外开销：合并后的子任务必须足够“小”子任务分配开销子任务间的通信开销子任务间的同步开销M：将子任务组织成若干个superstep在相邻的superstep上，如果都只有一个子任务，不要轻易将他们合并成一个superstep：每个子任务要足够“小”CELL处理器：并行计算的实现总有一个Master：PPE每个superstep至少一个slavesuperstep上的所有子任务都由slave执行slave是运行在SPU上的SPE程序可以有多个slave流水并行时，各个slave分别运行不同的SPE程序数据并行时，各个slave运行相同的SPE程序并行程序：CESOF一个PPE程序多个SPE程序SPE程序被嵌在PPE程序中并行计算机体系结构对并行程序开发的影响从PCAM看，针对Intel多核处理器和IBMCELL处理器，并行算法的设计结果是不同的靠编译技术实现串行程序的自动并行化成了一个不可能实现的梦想从并行程序中数据并行的计算任务分配方法看Intel多核处理器采用对等协作的计算模式IBMCELL处理器采用集中调度的计算模式从并行程序中对处理器/执行内核资源的管理方法看Intel多核处理器采用POSIX线程库管理处理器/执行内核资源，实现子任务到处理器/执行内核资源的分配IBMCELL处理器采用SPEManagementruntimelibrary管理处理器/执行内核资源，实现子任务到处理器/执行内核资源的分配不同并行计算机体系结构下的并行程序开发为什么会有这么大的差别？串行编程时，为PowerPC写的C语言程序可以直接在