Please use this identifier to cite or link to this item: https://doi.org/10.1109/HIPC.2009.5433225
Title: Spanning tree routing strategies for divisible load scheduling on arbitrary graphs - A comparative performance analysis
Authors: Viswanathan, S.
Veeravalli, B. 
Jingxi, J.
Keywords: Arbitrary graphs
Communication delays
Divisible loads
Load distribution
Processing time
Spanning tree networks
Issue Date: 2009
Citation: Viswanathan, S., Veeravalli, B., Jingxi, J. (2009). Spanning tree routing strategies for divisible load scheduling on arbitrary graphs - A comparative performance analysis. 16th International Conference on High Performance Computing, HiPC 2009 - Proceedings : 50-58. ScholarBank@NUS Repository. https://doi.org/10.1109/HIPC.2009.5433225
Abstract: In this paper, we evaluate and compare the performance of several spanning tree routing strategies for divisible load scheduling on arbitrary graphs and derive recommendations as to which routing strategy provides a better trade-off between complexity and time performance. We consider a network comprising heterogeneous processors interconnected by heterogeneous links in an arbitrary manner. We evaluate the performance over a wide range of arbitrary dense graphs with varying connectivity and processor densities and study the effect of network scalability. In addition, we introduce a novel spanning tree routing strategy, which is referred to as minimum equivalent network spanning tree (EST), and analyze its performance. We apply the resource-aware optimal load distribution with optimal sequencing (RAOLD-OS) scheduling algorithm presented in the literature for obtaining an optimal solution. This study attempts to pool all known and applicable divisible load scheduling algorithms for arbitrary networks and presents a collective and comparative view of their performance. ©2009 IEEE.
Source Title: 16th International Conference on High Performance Computing, HiPC 2009 - Proceedings
URI: http://scholarbank.nus.edu.sg/handle/10635/84208
ISBN: 9781424449224
DOI: 10.1109/HIPC.2009.5433225
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Oct 15, 2018

Page view(s)

39
checked on Oct 19, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.