Analysis of Scalable Algorithms for Dynamic Load Balancing and Mapping with Application to Photo-realistic Rendering
Analysis of Scalable Algorithms for Dynamic Load Balancing and Mapping with Application to Photo-realistic Rendering
复制标题
DOI：
10.7907/zvyw-h876
复制
发表时间：
1997-05
期刊：
影响因子：
--
通讯作者：
A. Heirich
中科院分区：
文献类型：
--
作者：
A. Heirich
本文提出并分析了分布式计算机系统中动态负载平衡与映射的可扩展算法。这些算法是分布式和并发的，没有中央控制线程，也不需要集中通信。它们是利用图的谱性质推导出来的：在负载平衡问题中，计算机之间的物理网络链路图；在映射问题中，进程之间的逻辑通信通道图。这些算法的一个显著特征是它们是可伸缩的：预期的执行成本不会随着问题规模的增加而增加。用可扩展性定理证明了这一点，该定理表明，对于几个简单的扰动模型，收敛到解的速度与尺度无关。通过模拟实例和非正式论证，将这一性质推广到一般扰动和随机扰动。给出了最坏情况下的扰动，并表明随着问题规模的增大，扰动的发生概率为零。为了验证这些结论，负载平衡算法被部署在一个基于蒙特卡罗路径跟踪的并行计算机系统上，以支持逼真的渲染应用程序。在不同数量的计算机上测量了该应用程序以及动态负载平衡算法的性能和可伸缩性。结果与可伸缩性的预测一致，并且随着计算机数量的增加，负载平衡的成本似乎不会增加。对负载平衡的质量进行评估，并与竞争方法产生的解决方案的质量进行比较，最多可用于1,024台计算机。这个比较表明，这里给出的算法与此应用程序中最流行的竞争方法一样好，甚至更好。然后，论文提出了动态映射算法，并模拟了一个模型问题，并建议这里提出的这对算法可能是对更昂贵的算法（如众所周知的递归光谱平分）的理想补充。
This thesis presents and analyzes scalable algorithms for dynamic load balancing and mapping in distributed computer systems. The algorithms are distributed and concurrent, have no central thread of control, and require no centralized communication. They are derived using spectral properties of graphs: graphs of physical network links among computers in the load balancing problem, and graphs of logical communication channels among processes in the mapping problem. A distinguishing characteristic of these algorithms is that they are scalable: the expected cost of execution does not increase with problem scale. This is proven in a scalability theorem which shows that, for several simple disturbance models, the rate of convergence to a solution is independent of scale. This property is extended through simulated examples and informal argument to general and random disturbances. A worst case disturbance is presented and shown to occur with vanishing probability as the problem scale increases. To verify these conclusions the load balancing algorithm is deployed in support of a photo-realistic rendering application on a parallel computer system based on Monte Carlo path tracing. The performance and scaling of this application, and of the dynamic load balancing algorithm, are measured on different numbers of computers. The results are consistent with the predictions of scalability, and the cost of load balancing is seen to be non-increasing for increasing numbers of computers. The quality of load balancing is evaluated and compared with the quality of solutions produced by competing approaches for up to 1,024 computers. This comparison shows that the algorithm presented here is as good as or better than the most popular competing approaches for this application. The thesis then presents the dynamic mapping algorithm, with simulations of a model problem, and suggests that the pair of algorithms presented here may be an ideal complement to more expensive algorithms such as the well-known recursive spectral bisection.