SCHEDULING ALGORITHMS FOR DATA REDISTRIBUTION AND LOAD-BALANCING ON MASTER-SLAVE PLATFORMS
Abstract
In this work we are interested in the problem of scheduling and redistributing data on master-slave platforms. We consider the case were the workers possess initial loads, some of which having to be redistributed in order to balance their completion times. We assume that the data consists of independent and identical tasks. We prove the NP completeness of the problem for fully heterogeneous platforms. Also, we present optimal polynomial algorithms for special important topologies: a simple greedy algorithm for homogeneous star-networks, and a more complicated algorithm for platforms with homogeneous communication links and heterogeneous workers.
References
- BOINC: Berkeley Open Infrastructure for Network Computing, http://boinc.berkeley.edu . Google Scholar
- SETI. URL: http://setiathome.ssl.berkeley.edu . Google Scholar
- [email protected]. http://einstein.phys.usm.edu . Google Scholar
-
M. R. Garey and D. S. Johnson , Computers and Intractability, a Guide to the Theory of NP-Completeness ( W.H. Freeman and Company , 1979 ) . Google Scholar - Loris Marchal, Veronika Rehn, Yves Robert, and Frdric Vivien. Scheduling and data redistribution strategies on star platforms. Research Report 2006-23, LIP, ENS Lyon, France, June 2006 . Google Scholar
-
Peter Brucker , Scheduling Algorithms ( Springer-Verlag New York, Inc. , Secaucus, NJ, USA , 2004 ) . Crossref, Google Scholar - Management Science 15(1), (1968). Google Scholar
-
U. Kremer , NP-Completeness of dynamic remapping , Proceedings of the Fourth Workshop on Compilers for Parallel Computers ( 1993 ) . Google Scholar - H. Renard, Y. Robert, and F. Vivien. Data redistribution algorithms for heterogeneous processor rings. Research Report RR-2004-28, LIP, ENS Lyon, France, May 2004. Available at the url http://graal.ens-lyon.fr/~yrobert . Google Scholar
- IEEE Trans. Parallel and Distributed Systems 8(2), 173 (1997). ISI, Google Scholar
- Journal of Parallel and Distributed Computing 43, 156 (1997). ISI, Google Scholar
M. Hamdi and C. K. Lee , Dynamic load balancing of data parallel applications on a distributed network, 9th International Conference on Supercomputing ICS'95 (ACM Press, 1995) pp. 170–179. Google Scholar-
B. A. Shirazi , A. R. Hurson and K. M. Kavi , Scheduling and load balancing in parallel and distributed systems ( IEEE Computer Science Press , 1995 ) . Google Scholar - , High Performance Cluster Computing. Volume 1: Architecture and Systems, ed.
R. Buyya (Prentice-Hall, 1999) pp. 702–721. Google Scholar - Informatica 23(1), 49 (1999). Google Scholar


