
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Parallel Transferable Uniform MultiRound Algorithm for Minimizing Makespan
Hiroshi YAMAMOTO Masato TSURU Katsuyuki YAMAZAKI Yuji OIE
Publication
IEICE TRANSACTIONS on Communications
Vol.E95B
No.5
pp.16691678 Publication Date: 2012/05/01
Online ISSN: 17451345
DOI: 10.1587/transcom.E95.B.1669
Print ISSN: 09168516 Type of Manuscript: PAPER Category: Network Keyword: grid computing, Master/Worker Model, divisible workload, MultiRound scheduling, UMR,
Full Text: PDF>>
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, multipleround 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 multipleround scheduling algorithm, Uniform MultiRound (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 workerside capacity. In the present study, a Parallel Transferable Uniform MultiRound 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.

