负载平衡.ppt

Load Balancing and Termination Detection 负载平衡与终止检测 Lecture 8: Chapter 7 Load balancing –通过在处理器间均衡地分配计算任务获得最高可能的执行速度。 Termination detection –检测一次计算什么时候结束。当计算是分布平行的,检测比较苦难. 负载平衡可以在任何进程执行之前尝试静态负载平衡 Some potential static load balancing techniques: ? Round robin algorithm — passes out tasks in sequential order of processes coming back to the first when all processes have been given a task ? Randomized algorithms — selects processes at random to take tasks ? Recursive bisection — recursively divides the problem into sub-problems of equal computational effort while minimizing message passing ? Simulated annealing — an optimization technique ? ic algorithm — another optimization technique 静态的负载平衡调度问题静态平衡的几个根本缺陷: ?如果实际上不执行程序的各个部分,很难去估计程序各个部分的执行时间.?在不同情况下,通信延迟也不一样。?有些问题的求解步数不确定。在进程执行过程中考虑动态负载平衡。考虑前面提到的因素, 根据正在运行的各部分来划分各部分的负载。会造成额外的开销,但比静态的更高效。动态负载平衡 putation will be divided into work (工作) or tasks (任务) to be performed, and processes perform these tasks. Processes are mapped onto processors . Since our objective is to keep the processors busy, we are interested in the activity of the processors. Processes and Processors Can be classified as: ? Centralized 集中式? Decentralized 分散式 Dynamic Load Balancing Centralized dynamic load balancing Tasks 集中在一起从一个中心出发, Master- slave structure. Decentralized dynamic load balancing (worker processes) 对问题进行工作, 它们之间相互交互,最后向一个独立进程报告。一个工作进程可以从其他工作进程处接收任务,也可以向其他工作进程发送任务。集中式动态负载平衡 Master process 持有要执行的任务集合。任务发到从进程. 从进程完成一个任务后, 会主动向主进程请求另一个任务. work pool , replicated worker , processor farm .