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.

Applying the Feedback Guided Dynamic Loop Scheduling Method for the Shortest Path Problem

    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 et al. , 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
    • S. F. Hummel, E. Schonberg and L. E. Flynn, Communications of the ACM 35(8), 90 (1992). CrossrefGoogle Scholar
    • J.   Jaja , An Introduction to Parallel Algorithms ( Addison-Wesley , 1992 ) . Google Scholar
    • C. P. Kruskal and A. Weiss, IEEE Trans. on Software Engineering 11(10), 1001 (1985). ISIGoogle Scholar
    • C. D. Polychronopolos and D. J. Kuck, IEEE Trans. on Computers 36(12), 1425 (1987). ISIGoogle 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
    • T. H. Tzen and L. M. Ni, IEEE Trans. on Parallel and Distributed Systems 4(1), 87 (1993). Crossref, ISIGoogle Scholar
    • Y. Yan, C. Jin and X. Zhang, IEEE Trans. on Parallel and Distributed Systems 8(1), 70 (1997). ISIGoogle Scholar