Please use this identifier to cite or link to this item:
Title: PPDD: Scheduling multi-site divisible loads in single-level tree networks
Authors: Li, X.
Veeravalli, B. 
Keywords: Divisible load theory
Grid computing
Heterogeneous computing
Load scheduling
Single-level tree networks
Issue Date: Mar-2010
Citation: Li, X., Veeravalli, B. (2010-03). PPDD: Scheduling multi-site divisible loads in single-level tree networks. Cluster Computing 13 (1) : 31-46. ScholarBank@NUS Repository.
Abstract: This paper investigates scheduling strategies for divisible jobs/loads originating from multiple sites in hierarchical networks with heterogeneous processors and communication channels. In contrast, most previous work in the divisible load scheduling theory (DLT) literature mainly addressed scheduling problems with loads originating from a single processor. This is one of the first works that address scheduling multiple loads from multiple sites in the DLT paradigm. In addition, scheduling multi-site jobs is common in Grids and other general distributed systems for resource sharing and coordination. An efficient static scheduling algorithm PPDD (Processor-set Partitioning and Data Distribution Algorithm) is proposed to near-optimally distribute multiple loads among all processors so that the overall processing time of all jobs is minimized. The PPDD algorithm is applied to two cases: When processors are equipped with front-ends and when they are not equipped with front-ends. The application of the algorithm to homogeneous systems is also studied. Further, several important properties exhibited by the PPDD algorithm are proven through lemmas. To implement the PPDD algorithm, we propose a communication strategy. In addition, we compare the performance of the PPDD algorithm with a Round-robin Scheduling Algorithm (RSA), which is most commonly used. Extensive case studies through numerical analysis have been conducted to verify the theoretical findings. © Springer Science+Business Media, LLC 2009.
Source Title: Cluster Computing
ISSN: 13867857
DOI: 10.1007/s10586-009-0103-1
Appears in Collections:Staff Publications

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


checked on Feb 12, 2019


checked on Feb 12, 2019

Page view(s)

checked on Mar 11, 2018

Google ScholarTM



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