loading...
Divisible Load Scheduling on a Hypercube Cluster with Finite-Size Buffers and Granularity Constraints
Brisbane, Australia May 15-May 18
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCGRID.2001.923257First IEEE International Symposium on ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Xiaolin Li, The National University of Singapore
Bharadwaj Veeravalli, The National University of Singapore
Chi Chung Ko, The National University of Singapore
In this paper, we address the problem of scheduling a large size divisible load on a hypercube cluster of processors. Unlike in earlier studies in the divisible load theory (DLT) literature, here, we assume that the processors have finite-size buffers. Further, we impose constraints on the extent to which the load can be divided, referred to as granularity constraint. We first present the closed-form solutions for the case with infinite-size buffers. For the case with load granularity constraint, we propose a simple algorithm to find the sub-optimal solution and then we analyze the case when these buffer are of finite size. For this case, we present an elegant strategy, referred to as Incremental Balancing Strategy (IBS), to obtain an optimal load distribution. Based on the rigorous mathematical analysis, a number of interesting and useful properties exhibited by the algorithm are proven. Numerical examples are presented for the ease of understanding. Keywords: Divisible load theory, hypercube, finite-size buffer, communication delays, granularity
Citation:
Xiaolin Li, Bharadwaj Veeravalli, Chi Chung Ko, "Divisible Load Scheduling on a Hypercube Cluster with Finite-Size Buffers and Granularity Constraints," ccgrid, pp.660, First IEEE International Symposium on Cluster Computing and the Grid (CCGrid'01), 2001
Usage of this product signifies your acceptance of the Terms of Use.