World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

SCHEDULING ALGORITHMS FOR DATA REDISTRIBUTION AND LOAD-BALANCING ON MASTER-SLAVE PLATFORMS

    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 ) . CrossrefGoogle Scholar
    • J. M. Moore, 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
    • M.-Y. Wu, IEEE Trans. Parallel and Distributed Systems 8(2), 173 (1997). ISIGoogle Scholar
    • M. Cierniak, M. J. Zaki and W. Li, Journal of Parallel and Distributed Computing 43, 156 (1997). ISIGoogle 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
    • M. Nibhanupudi and B. Szymanski, High Performance Cluster Computing. Volume 1: Architecture and Systems, ed. R. Buyya (Prentice-Hall, 1999) pp. 702–721. Google Scholar
    • Alessandro Bevilacqua, Informatica 23(1), 49 (1999). Google Scholar