PARALLEL LOOP SCHEDULING APPROACHES FOR DISTRIBUTED AND SHARED MEMORY SYSTEMS
Abstract
In this paper, we propose different approaches for the parallel loop scheduling problem on distributed as well as shared memory systems. Specifically, we propose adaptive loop scheduling models in order to achieve load balancing, low runtime scheduling, low synchronization overhead and low communication overhead. Our models are based on an adaptive determination of the chunk size and an exploitation of the processor affinity property, and consider different situations (central or local queues, and dynamic or static loop partition).
References
- J. Aguilar, E. Leiss, "General Adaptive Parallel Loop Scheduling for Distributed and Shared Memory Systems", Technical Report, Department of Computer Science, University of Houston, September 2000 . Google Scholar
- A. Bull, "Feedback Guided Dynamic Loop Scheduling: Algorithms and Experiments", Lecture Notes on Computer Sciences, Vol. 1470, pp. 377-382, 1998 . Google Scholar
- The Computational Journal 40(6), 356 (1997). Crossref, ISI, Google Scholar
-
H. El_Rewini , T. Lewis and H. Ali , Task Scheduling in Parallel and Distributed Systems ( Prentice Hall , New Jersey , 1994 ) . Google Scholar - The Computational Journal 40(6), 303 (1997). Google Scholar
- Journal of Supercomputing 11(4), 333 (1997). Crossref, ISI, Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 5(4), 379 (1994). Crossref, ISI, Google Scholar
- ACM Transactions on Programming Language and Systems 21(1), 138 (1999). ISI, Google Scholar
- F. Rastello, Y. Robert, "Loop Partitioning versus Tiling for Cache-Based Multiprocessors", Technical Report RR1998-13, Laboratoire de l'Informatique du Parallélisme, Ecole Normale Supérieure. February 1998 . Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 10(2), 160 (1999). Crossref, ISI, Google Scholar
- Z. Szczerbinski, "Optimal Distribution of Loops Containing no Dependence Cycles", Lecture Notes on Computer Sciences, Vol. 1595, pp. 1254-1257, 1999 . Google Scholar
- S. Togsima, C. Chantrapornchai, E. Sha, "Probabilistic Loop Scheduling Considering Communication Overhead", Lecture Notes on Computer Sciences, Vol. 1459, pp-158-179, 1998 . Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 4(1), 87 (1993). Crossref, ISI, Google Scholar
- Journal of Parallel and Distributed Computing 42, 42 (1997). Crossref, ISI, Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 8(1), 70 (1997). ISI, Google Scholar


