Static Load Distribution for Communication Intensive Parallel Computing in Multiclusters
Static Load Distribution for Communication Intensive Parallel Computing in Multiclusters
复制标题
DOI：
10.1109/pdp.2008.58
复制
发表时间：
2008-02
期刊：
影响因子：
--
通讯作者：
E. Heien;N. Fujimoto;K. Hagihara
中科院分区：
文献类型：
--
作者：
E. Heien;N. Fujimoto;K. Hagihara
在本文中，我们通过应用可分割负载理论技术来检查负载分布，以最小化多集群并行计算算法中的总运行时间。即使具有同质的处理器速度，由于通信异构性，均匀分配负载的多集群中的并行计算也可能以低于最大效率的方式运行。使用 LogP 并行计算模型的修改版本，我们提出了一种在多个集群之间分配负载的通用技术，以最大限度地减少每个处理器等待的时间。该技术用于确定多集群系统中旋转玻璃模拟和并行桶排序的最佳负载分布。它还允许快速分析在计算中添加处理器或集群的效果。我们通过实验证明了模型的准确性，并展示了它如何消除多集群并行计算中的等待时间。使用从我们的技术得出的负载分布可以使执行时间减少高达 50%，具体取决于集群之间的异构程度和计算的通信特性。
In this paper, we examine load distributions to minimize total run time in multi-cluster parallel computing algorithms by applying divisible load theory techniques. Even with homogeneous processor speeds, parallel computations in multi-clusters that evenly assign load can run at less than maximum efficiency due to communication heterogeneity. Using a modified version of the LogP parallel computing model, we propose a general technique of assigning load among multiple clusters to minimize the time each processor spends waiting. This technique is used to determine optimal load distribution for spin glass simulation and parallel bucket sort in multi-cluster systems. It also allows fast analysis of the effects of adding processors or clusters to the computation. We experimentally demonstrate the accuracy of our model, and show how it eliminates wait time in multi-cluster parallel computations. Using load distributions derived from our technique results in an execution time decrease of up to 50%, depending on the degree of heterogeneity among clusters and communication characteristics of the computation.