Parallel Transferable Uniform Multi-Round Algorithm for Minimizing Makespan

Hiroshi YAMAMOTO  Masato TSURU  Katsuyuki YAMAZAKI  Yuji OIE  

Publication
IEICE TRANSACTIONS on Communications   Vol.E95-B   No.5   pp.1669-1678
Publication Date: 2012/05/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E95.B.1669
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network
Keyword: 
grid computing,  Master/Worker Model,  divisible workload,  Multi-Round scheduling,  UMR,  

Full Text: PDF(1.2MB)>>
Buy this Article




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 effect 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 efficiently 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 effectively 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.