Applying the Feedback Guided Dynamic Loop Scheduling Method for the Shortest Path Problem
Abstract
Feedback Guided Dynamic Loop Scheduling is a recent dynamic method for loop scheduling. The method has been mainly studied for synthetic examples so far and it has always offered the lowest computational times against other dynamic scheduling methods. In this article we show how the method is applied to the shortest path problem and also present some execution times that prove the efficiency.
References
-
R. K. Ahuja , T. L. Magnanti and J. B. Orlin , Network Flows: Theory, Algorithms, and Applications ( Prentice-Hall , 1993 ) . Google Scholar -
J. M. Bull , Feedback Guided Loop Scheduling: Algorithm and Experiments , Proceedings of Euro-Par'98 ,Lecture Notes in Computer Science ( Springer Verlag , 1998 ) . Google Scholar -
J. M. Bull , R. W. Ford and A. Dickinson , A Feedback Based Load Balance rithm for Physics Routines in NWP , Proceedings of Seventh Workshop on the Use of Parallel Processors in Meteorology ( World Scientific , 1996 ) . Google Scholar -
J. M. Bull , A Theoretical Investigation of Feedback Guided Loop Scheduling , Proceedings of Ninth SIAM Conference on Parallel Processing for Scientific Computing ( SIAM Press , 1999 ) . Google Scholar - D. L. Eager and J. Zahorjan (1992) Adaptive Guided Self-Scheduling, Technical Report 92-01-01, Department of Computer Science and Engineering, University of Washington, USA . Google Scholar
- Communications of the ACM 35(8), 90 (1992). Crossref, Google Scholar
-
J. Jaja , An Introduction to Parallel Algorithms ( Addison-Wesley , 1992 ) . Google Scholar - IEEE Trans. on Software Engineering 11(10), 1001 (1985). ISI, Google Scholar
- IEEE Trans. on Computers 36(12), 1425 (1987). ISI, Google Scholar
S. Sabramanian and D. L. Eager , Affinity Scheduling of Unbalanced Workloads, Proceedings of SuperComputing 94 (IEEE Comp. Soc. Press, 1994) pp. 214–226. Google Scholar- R. Sakellariou (1997) On the Quest for Perfect Load Balance in Loop-Based Parallel Computation, PhD Thesis, Department of Computer Science, Manchester University . Google Scholar
- IEEE Trans. on Parallel and Distributed Systems 4(1), 87 (1993). Crossref, ISI, Google Scholar
- IEEE Trans. on Parallel and Distributed Systems 8(1), 70 (1997). ISI, Google Scholar


