Novel Methods for Divisible Load Distribution with Start-Up Costs on a Complete b-Ary Tree
Chi‐Yeh Chen, Chih‐Ping Chu · IEEE Transactions on Parallel and Distributed Systems · 2014
This work investigates divisible load distribution using multi-installment processing on completeb-ary tree networks. Classic methods of distributing a divisible load divide the computation and communication processes into multiple time intervals in a pipelined fashion. The algorithm$\mathbb {M}$(multi-installment) herein uses multi-installment processing with pipelined communication to reduce the initial distribution time and to improve the performance. Closed-form expressions for the parallel processing time and speed-up are derived. This work reveals that the asymptotic speed-up of the proposed algorithm is$b\beta +1$where$\beta$is the computation-to-communication ratio of a node in the system. Algorithm$\mathbb {M}$outperforms the classic algorithm in all cases. The algorithm$\mathbb {S}$(start-up cost) that is developed herein includes the computation and communication start-up costs. Finally, two algorithms$\mathbb {M}$and$\mathbb {S}$are combined to form algorithm$\mathbb {MS}$with even better performance than each.