LecNote_9_并行计算中的任务分配

1、第九讲 并行计算中的任务分配n任务分配方法n静态任务分配n动态任务分配n动态任务分配的实现n对等协同：peer-to-peer collaboratingn集中调度：master-slavenPOSIX并行程序中的计算任务划分n对等协同n锁n信号量nCELL BE上的计算任务划分n集中调度n邮箱nDMA数据传输并行算法设计：BSP与PCAMnBSP：子任务在时间和空间上的规划n时间上的规划：整个算法由若干个串行执行的superstep组成n空间上的规划：每个superstep上包含一组互相独立的子任务nPCAM：发现问题中的子任务、产生规划的方法nP：通过功能分解、数据分解，寻找并行性。解决两

2、方面的问题n并行程序的伸缩性n并行计算任务划分的负载均衡性nC：检查子任务间的依赖关系，发现规划必须满足的约束条件nA：选择合适的子任务粒度，减小并行计算的额外开销n子任务分配开销n子任务间的通信开销n子任务间的同步开销nM：将子任务组织成若干个superstep并行计算中的任务分配方法n并行算法设计的结果: BSP模型n若干个顺序执行的superstepn每个superstep上是一组互相独立的子任务n这些子任务是通过功能分解功能分解发现的：子任务的数量有限、与被处理数据的规模无关n这些子任务是通过数据分解数据分解发现的：被处理的数据规模越大，子任务的数量越多n在每个superstep上，如

3、何确定各个处理器/执行内核上的子任务n静态任务分配：在开始superstep上的数据处理之前，已经确定了需要执行其中的哪些子任务n例如N-Body问题的实现n动态任务分配：superstep的数据处理过程中，动态确定每个处理器/执行内核上的子任务。n例如求素数问题静态任务分配：通过功能分解得到superstep上的一组子任务n每个子任务分别实现一个子功能，子任务的数量有限n一个处理器/执行内核负责一个子任务n并行程序伸缩性(scalability)不好n负载均衡难以控制：取决于子任务算法的复杂性、所涉及的数据规模等n子任务之间的关系n形式1：互相独立，各自处理不同的数据集合n形式2：构成一个流

4、水，依次对一组数据集合进行处理。数据集合的数量很大子任务1子任务2子任务3子任务4数据集合1数据集合2数据集合3数据集合4数据集合数据集合1 1数据集合数据集合1 1数据集合数据集合2 2数据集合数据集合2 2数据集合数据集合3 3数据集合数据集合3 3数据集合数据集合4 4数据集合数据集合5 5数据集合数据集合4 4数据集合数据集合1 1数据集合数据集合2 2数据集合数据集合3 3数据集合数据集合1 1数据集合数据集合2 2子任务的计算复杂性形式1的数据划分形式2的数据划分静态任务分配：通过数据分解得到superstep上的一组子任务n各个子任务的数据处理功能相同，各自处理不同的数据集合n子

5、任务之间互相独立n子任务的数量大n一个处理器/执行内核在开始superstep上的数据处理之前，先确定需要处理其中哪些子任务n并行程序有好的伸缩性(scalability)n负载均衡问题n子任务具有相同的运算量、且处理器/执行内核的性能相同，具有好的负载均衡性n例如在Intel多核处理器上执行Laplace计算n子任务的运算量不一致、或者处理器/执行内核的性能不一致时，难以控制负载均衡。例如n在Intel多核处理器上执行求素数计算n在CELL处理器上执行Laplace计算，让PPE和8个SPE分别负责一部分数据处理静态任务分配在POSIX线程并行程序中的实现nsuperstep上的子任务是通过

6、功能分解发现的：每个子任务分别处理不同的数据集合n为每个子任务各编写一个函数，分别由一个并发线程执行nsuperstep上的子任务是通过功能分解发现：每个数据集合要经过这些子任务依次处理流水并行流水并行n每个子任务分别开发一个函数，各由一个线程执行n子任务之间通过条件信号进行同步nsuperstep上的子任务是通过数据分解发现的：数据并行数据并行子任务的数量确定、子任务的复杂性一致n编写一个函数n根据并发线程的数量和自己的ID，计算自己负责哪些子任务n实现子任务的数据处理功能n创建多个并发线程，同时执行这个函数动态任务分配n动态任务分配：处理器/执行内核完成一个子任务后，再分配一个新的子任务n

7、什么样的并行子任务能够动态分配动态分配？基于数据分解发现的子任务基于数据分解发现的子任务n各个处理器/执行内核运行的算法要相同：都能实现子任务需要的数据处理功能n子任务要互相独立，分别处理不同的数据集合n为什么需要动态任务分配动态任务分配？平衡负载平衡负载n子任务的计算量不一致。例如求素数问题n处理器/执行内核的性能不一致。例如：在CELL处理器上，让PPE和8个SPE分别负责一部分子任务的处理n子任务的数量不确定。例如n图书馆查询、银行记帐等大规模并发用户的计算问题n处理一个数据文件中的记录，每个记录作为一个子任务分别处理。各个记录不定长，读到文件末尾才知道总的记录数。例如：一个稀疏矩阵与向

8、量的乘法运算，部分行中全部是0元素。稀疏矩阵按照行优先存储在文件中NiC1 Val1C2 Val2C2 Val3Cni ValniNi+1第I行非0元素的数量第I行第2个非0元素所在的列号第I行第2个非0元素的值第I+1行非0元素的数量动态任务分配的实现n可以将整个superstep看做一个“子任务池”( pool)n每次从“子任务池”中取一个出来，交给当前空闲的某个处理器/执行内核去执行n实现方式1：对等协同的(peer-to-peer collaborating)动态任务分配n全部处理器/执行内核扮演的角色都是相同角色都是相同的n负责处理“子任务池”中若干个子任务n与其他处理器/执行内核协

9、作，实现“子任务池”中子任务的分配n采用“锁”机制实现“子任务池”操作的确定性n任何时刻，只有一个处理器/执行内核操作“子任务池”n例如求素数问题的pthread并行程序n实现方式2：集中调度的(master-slave)动态任务分配n各处理器扮演不同的角色不同的角色：一个处理器/执行内核(master)专门负责“子任务池”的维护，其他处理器/执行内核(slave)负责子任务的数据处理nmaster和slave采用“消息交换”机制实现子任务的分配n当一个slave空闲时，通过消息告诉masternmaster从“子任务池”中取出一个任务，通过消息通知slave执行该子任务POSIX并行程序中的

10、动态任务分配nsuperstep是数据并行的：子任务的数量不确定、或者子任务的复杂性不一致npeer-to-peer collaborating的动态任务划分n开发一个函数，同时由各个并发线程分别执行n锁机制，实现线程之间对“子任务池”操作的同步CELL处理器上的计算任务分配nPCAM：将问题表示成若干个superstepn四类superstepn只有一个子任务：PPE做、还是SPE做？n流水并行nMailbox：子任务间的同步nDMA：子任务间的数据交换n数据并行，子任务的数量确定、子任务的复杂性一致：还能静态任务划分吗？还能静态任务划分吗？n数据并行，但子任务的数量不确定、或者子任务的复杂

11、性不一致：master-slave的动态任务划分n无论是流水并行、还是数据并行，无论是流水并行、还是数据并行，PPE扮演什么样的角扮演什么样的角色？色？Cell programming modelsnSingle Cell environment:nPPE programming modelsnSPE Programming modelsnSmall single-SPE modelsnLarge single-SPE modelsnMulti-SPE parallel programming modelsnCell Embedded SPE Object Format (CESOF)nMul

12、ti-tasking SPEsnLocal Store resident multi-taskingnSelf-managed multi-taskingnKernel-managed SPE scheduling and virtualizationPPE programming modelnPPE is a 64-bit PowerPC core, hosting operating systems and hypervisornPPE program inherits traditional programming modelsnCell environment: a PPE progr

13、am serves as a controller or facilitatornCESOF support provides SPE image handles to the PPE runtimenPPE program establishes a runtime environment for SPE programsn e.g. memory mapping, exception handling, SPE run controlnIt allocates and manages Cell system resourcesn SPE scheduling, hypervisor CBE

14、A resource managementnIt provides OS services to SPE programs and threadsn e.g. printf, file I/OSmall single-SPE modelsnSingle tasked environmentnSmall enough to fit into a 256KB- local storenSufficient for many dedicated workloadsnSeparated SPE and PPE address spaces LS / EAnExplicit input and outp

15、ut of the SPE programnProgram arguments and exit code per SPE ABI (application binary interface)nDMAnMailboxesnSPE side system callsSmall single-SPE models tools and environmentnSPE compiler/linker compiles and links an SPE executablenThe SPE executable image is embedded as reference-able RO data in

16、 the PPE executable (CESOF)nA Cell programmer controls an SPE program via a PPE controlling process and its SPE management libraryni.e. loads, initializes, starts/stops an SPE programnThe PPE controlling process, OS/PPE, and runtime/(PPE or SPE) together establish the SPE runtime environment, e.g. a

17、rgument passing, memory mapping, system call service.outputSmall single-SPE models a sample/* spe_foo.c: A C program to be compiled into an executable called “spe_foo” */int main( int speid, addr64 argp, addr64 envp) char i;/* do something intelligent here */i = func_foo (argp);/* when the syscall i

18、s supported */printf( “Hello world! my result is %d n”, i);return i;nABI: application binary interfaceABISmall single-SPE models PPE controlling programextern spe_program_handle spe_foo; /* the spe image handle from CESOF */int main() int rc, status;speid_t spe_id;/* load & start the spe_foo pro

19、gram on an allocated spe */spe_id = spe_create_thread (0, &spe_foo, 0, NULL, -1, 0);/* wait for spe prog. to complete and return final status */rc = spe_wait (spe_id, &status, 0);return status;Large single-SPE programming modelsnData or code working set cannot fit completely into a local sto

20、renThe PPE controlling process, kernel, and libspe runtime set up the system memory mapping as SPEs secondary memory storenThe SPE program accesses the secondary memory store via its software-controlled SPE DMA enginenMemory Flow Controller (MFC)Large single-SPE programming models I/O datanSystem me

21、mory for large size input / output datane.g. Streaming modelLarge single-SPE programming models - DMAnDMA latency handling is critical to overall performance for SPE programs moving large data or codenData pre-fetching is a key technique to hide DMA latencyne.g. double-bufferingn在此策略下，SPE上每个子任务的数据规模

22、要更小Large single-SPE programming models Job QueuenCode and data packaged together as inputs to an SPE kernel programnA multi-tasking modelnmore discussion laterCELL上的计算任务划分：superstep上只有一个子任务nPPE控制：决定何时开始子任务的执行n与上、下的superstep同步nSPE做子任务的数据处理n子任务足够“小”：数据+代码256KBn代码不可拆、数据可拆：流计算模式(streaming model) nLarge

23、single-SPE programming models I/O datan开发一个SPE程序：取一部分数据，做完后回写结果，再取一部分数据n可采用双缓冲技术，降低DMA延迟对性能的影响n代码和数据要同时拆nLarge single-SPE programming models Job Queuen开发多个SPE程序，构成一个SPE的执行队列n执行完一个SPE程序后，在执行另一个SPE程序Multi-tasking：站在PPE的角度，如何看SPEsnSPE as a device resourcenSPE as a heterogeneous processornSPE resource r

24、epresented as a file systemnPPE按照Function offloading模式，利用SPE提高计算效率nPPE维护一个子任务池，通过CESOF机制，建立每个子任务与SPE程序的对应关系n需要执行子任务池中的某个子任务时，通过SPE Management Runtime Libraryn分配一个SPU、启动SPE程序运行nPPE和SPE之间通过MFC通信nMailbox：同步、任务描述数据nDMA：任务数据到LS的数据传输Parallel programming models StreamingnSPE initiated DMAnLarge array of da

25、ta fed through a group of SPE programsnA special case of job queue with regular datanEach SPE program locks on the shared job queue to obtain next jobnFor uneven jobs, workloads are self-balanced among available SPEsCELL上的计算任务划分：基于数据分解发现superstep上的子任务n动态任务分配n无所谓静态任务分配，SPE只有256KBn开发一个SPE程序，在各个SPU上运行n

26、PPE通过Mailboxn分派SPE需要执行的子任务：输入数据、输出数据的EAn获得子任务的执行进度：一个子任务完成后，再分配一个新的子任务nSPE/PPE通过DMAn将子任务处理的数据传输到LSn将子任务的结果从LS传输到MemoryParallel programming models PipelinenUse LS to LS DMA bandwidth, not system memory bandwidthnFlexibility in connecting pipeline functionsnLarger collective code size per pipelinenLoa

27、d-balance is harderCELL上的计算任务划分：流水并行的superstepn为每个子任务，分别开发一个SPE程序，运行在一个SPU上nPPE通过Mailboxn向其中一个SPE分派需要处理的数据集合：输入数据、输出数据的EAn获得数据集合在该SPE上的执行进度：一数据集合完成后，再分配一个新的数据集合nSPE之间n通过DMA：将上一个子任务的结果传递到下一个子任务所在的LSn通过Mailbox：实现SPE之间的进度同步CELL处理器：PCAMnP：通过功能分解、数据分解，寻找并行性。解决三方面的问题n并行程序的伸缩性n并行计算任务划分的负载均衡性n每个子任务足够“小”：数据+

28、代码256KBnC：检查子任务间的依赖关系，发现规划必须满足的约束条件nA：选择合适的子任务粒度，减小并行计算的额外开销：合并后的子任务必须足够“小”n子任务分配开销n子任务间的通信开销n子任务间的同步开销nM：将子任务组织成若干个superstepn在相邻的superstep上，如果都只有一个子任务，不要轻易将他们合并成一个superstep：每个子任务要足够“小”CELL处理器：并行计算的实现n总有一个Master：PPEn每个superstep至少一个slavensuperstep上的所有子任务都由slave执行nslave是运行在SPU上的SPE程序n可以有多个slaven流水并行时，

29、各个slave分别运行不同的SPE程序n数据并行时，各个slave运行相同的SPE程序n并行程序：CESOFn一个PPE程序n多个SPE程序nSPE程序被嵌在PPE程序中并行计算机体系结构对并行程序开发的影响n从PCAM看，针对Intel多核处理器和IBM CELL处理器，并行算法的设计结果是不同的n靠编译技术实现串行程序的自动并行化成了一个不可能实现的梦想n从并行程序中数据并行的计算任务分配方法看nIntel多核处理器采用对等协作的计算模式nIBM CELL处理器采用集中调度的计算模式n从并行程序中对处理器/执行内核资源的管理方法看nIntel多核处理器采用POSIX线程库管理处理器/执行内核资源，实现子任务到处理器/执行内核资源的分配nIBM CELL处理器采用SPE Management runtime library管理处理器/执行内核资源，实现子任务到处理器/执行内核资源的分配不同并行计算机体系结构下的并行程序开发为什么会有这么大的差别？n串行编程时，为Power PC写的C语言程序可以直接在X8