Novel Methods for Divisible Load Distribution with Start-Up Costs on a Complete b-Ary Tree

Chi Yeh Chen, Chih Ping Chu

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


This work investigates divisible load distribution using multi-installment processing on complete b -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 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β +1 where β is the computation-to-communication ratio of a node in the system. Algorithm M outperforms the classic algorithm in all cases. The algorithm S (start-up cost) that is developed herein includes the computation and communication start-up costs. Finally, two algorithms M and S are combined to form algorithm MS with even better performance than each.

Original languageEnglish
Article number6919308
Pages (from-to)2836-2848
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number10
Publication statusPublished - 2015 Oct 1

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Novel Methods for Divisible Load Distribution with Start-Up Costs on a Complete b-Ary Tree'. Together they form a unique fingerprint.

Cite this