Abstract
Conventional divisible load scheduling algorithms attempt to achieve optimal partitioning of massive loads to be distributed among processors in a distributed computing system in the presence of communication delays in the network. However, these algorithms depend strongly upon the assumption of prior knowledge of network parameters and cannot handle variations or lack of information about these parameters. In this paper, we present an adaptive strategy that estimates network parameter values using a probing technique and uses them to obtain optimal load partitioning. Three algorithms, based on the same strategy, are presented in the paper, incorporating the ability to cope with unknown network parameters. Several illustrative numerical examples are given. Finally, we implement the adaptive algorithms on an actual network of processor nodes using MPI implementation and demonstrate the feasibility of the adaptive approach.
| Original language | English |
|---|---|
| Pages (from-to) | 897-907 |
| Number of pages | 11 |
| Journal | IEEE Transactions on Parallel and Distributed Systems |
| Volume | 16 |
| Issue number | 10 |
| DOIs | |
| Publication status | Published - 2005 Oct |
Bibliographical note
Funding Information:This work was in part supported by the Media Service Research Center (MSRC-ITRC), Ministry of Information and Communication, Korea. The authors would like to thank T.G. Robertazzi for drawing their attention to the use of probing technique in the QoS literature and the reviewers for their excellent comments and suggestions.
Keywords
- Distributed applications
- Divisible loads
- Multiprocessor systems
- Scheduling and task partitioning
- Workstations
ASJC Scopus subject areas
- Signal Processing
- Hardware and Architecture
- Computational Theory and Mathematics