Parallel Transferable Uniform Multi-Round Algorithm for Minimizing Makespan
Parallel Transferable Uniform Multi-Round Algorithm for Minimizing Makespan
复制标题
DOI：
10.1587/transcom.e95.b.1669
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
Hiroshi Yamamoto;M. Tsuru;K. Yamazaki;Y. Oie
中科院分区：
文献类型：
--
作者：
Hiroshi Yamamoto;M. Tsuru;K. Yamazaki;Y. Oie
在使用主/工作者模型进行分布式网格计算的并行计算系统中，随着处理数据的大小的增长，数据传输时间的增加降低了性能。因此，对于可分割的工作负载应用，已经开发了多轮调度算法，以通过将数据划分为要在多轮中发送的块来减轻较长数据传输时间的不利影响，从而重叠计算和传输所需的时间。然而，标准的多轮调度算法Uniform Multi-Round（UMR）采用顺序传输模型，主机一次与一个工作者通信，因此主机所附链路的传输容量无法充分利用由于工作者侧容量的限制。本文提出了一种并行可转移均匀多轮算法（PTUMR）。它通过允许块并行传输到工作者，有效地利用了网络链路的数据传输能力。该算法在一定的约束条件下充分利用主节点的链路带宽，将工作节点分组，并将每组工作节点视为一个虚拟工作节点。特别是，引入一个阈值有效地处理非常异构的工人在数据传输和计算能力。然后，主机以最佳方式（如UMR中）调度到虚拟工作器的顺序数据传输。性能评估表明，所提出的算法实现了显着缩短周转时间（即，与不考虑工人异质性的UMR相比，其接近理论下限。
SUMMARY In parallel computing systems using the master / worker model for distributed grid computing, as the size of handling data grows, the increase in the data transmission time degrades the performance. For divisible workload applications, therefore, multiple-round scheduling algorithms have been being developed to mitigate the adverse e ff ect of longer data transmission time by dividing the data into chunks to be sent out in multiple rounds, thus overlapping the times required for computation and transmission. However, a standard multiple-round scheduling algorithm, Uniform Multi-Round (UMR), adopts a sequential transmission model where the master communicates with one worker at a time, thus the transmission capacity of the link attached to the master cannot be fully utilized due to the limits of worker-side capacity. In the present study, a Parallel Transferable Uniform Multi-Round algorithm (PTUMR) is proposed. It e ffi ciently utilizes the data transmission capacity of network links by allowing chunks to be transmitted in parallel to workers. This algorithm divides workers into groups in a way that fully uses the link bandwidth of the master under some constraints and considers each group of workers as one virtual worker. In particular, introducing a Grouping Threshold e ff ectively deals with very heterogeneous workers in both data transmission and computation capacities. Then, the master schedules sequential data transmissions to the virtual workers in an optimal way like in UMR. The performance evaluations show that the proposed algorithm achieves significantly shorter turnaround times (i.e., makespan) compared with UMR regardless of heterogeneity of workers, which are close to the theoretical lower limits.