A Blocked All-Pairs Shortest-Paths Algorithm

1. W. AbuSufah, D. J. Kuck, and D. H. Lawrie. Automatic program transformation for virtual memory computers. In Proc. of the 1979 National Computer Conference, pages 969–974, New York, 1979.

   Google Scholar 

2. A. Aggarwal, K. Chandra, and M. Snir. A model for hierarchical memory. In The 19th Annual ACM Symposium on Theory of Computing, pages 305–314, New York, 1987.

   Google Scholar 

3. A. Aggarwal, K. Chandra, and M. Snir. Hierarchical memory with block transfer. In The 28th Annual IEEE Symposium on Foundations of Computer Science, pages 204–216, LosAngeles, CA, 1987.

   Google Scholar 

4. A. Aggarwal, M. Horowitz, and Hennessey. An analytical cache model. The ACM Transactions on Computer Systems, 7(2):184–215, 1989.

   Article  Google Scholar 

5. I. Al-Furaih and S. Ranka, Memory hierarchy management for iterative graph structures. Proc. 12th International Parallel Processing Symposium’ 98. (IPPS98), Orlando, Florida.

   Google Scholar 

6. I. Al-Furaih and S. Ranka, Ibraheem Al-Furaih and Sanjay Ranka, Practical Algorithms for Internal and External Sorting, Proc. the Second International Conference on Parallel and Distributed Computing and Networks (PDCN’98), Brisbane, Australia, 14–16 December 1998.

   Google Scholar 

7. B. Alpern, L. Carter, E. Feig, and T. Selker. The uniform memory hierarchy model of computation. Algorithmica, 12(2–3):72–109, 1994.

   Article  MATH  MathSciNet  Google Scholar 

8. D. Callahan, S. Carr, and K. Kennedy. Improving register allocation for subscripted variables. In In Proceedings of the ACM SIGPLAN’ 90 Conference on Programming Language Design and Implementation, White Plains, New York, 1990.

   Google Scholar 

9. D. Gannon and W. Jalby. The influence of memory hierarchy on algorithm organization: Programming FFTs on a vector multiprocessor. In The Characteristics of Parallel Algorithms, MIT Press, Cambridge, 1987.

   Google Scholar 

10. G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 1989.

    Google Scholar 

11. E. Horowitz, S. Sahni, and S. Rajasekaran. Computer Algorithms. Computer Science Press, New York, 1998.

    Google Scholar 

12. M. S. Lam, E. E. Rothberg, and M. E. Wolf. The cache performance and optimizations of blocked algorithms. ACM, 26:63–74, 1991.

    Google Scholar 

13. A. LaMarca and R. E. Ladner. The influences of caches on the performance of heaps. The ACM Journal of Experimental Algorithms, 1(4), 1996.

    Google Scholar 

14. A. LaMarca and R. E. Ladner. The influences of caches on the performance of sorting. In The ACM-SIAM Symposium on Discrete Algortihms, pages 370–379, New Orleans, Louisiana, 5–7 January, 1997.

    Google Scholar 

15. M. Martonosi, A. Gupta, and T. Anderson. Memspy: analyzing memory system bottlenecks in programs. In Proceedings of the 1992 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pages 1–12, Newport, Rhode Island, 1992.

    Google Scholar 

16. A. C. McKeller and E. G. Coffman. The organization of matrices and matrix operations in a paged multiprogramming environment. CACM, 12(3):153–165, 1969.

    Google Scholar 

17. Sun Microsytems. Introduction to Shade. Manual, Sun Microsytems, Mountain View, CA, 1998.

    Google Scholar 

18. D. Patterson and J. L. Hennessy. Computer Architecture: A Quantitative Analysis. Morgan Kaufmann, San Mateo, CA, 1996.

    Google Scholar 

19. J. P. Singh, H. S. Stone, and D. F. Thiebaut. A model of workloads and its use in miss-rate prediction for fully assocaitive caches. IEEE Transactions on Computers, 41(7):811–825, 1992.

    Article  Google Scholar 

20. Larry Stewart. Programming to Optimize Cache Memory on the SUN Ultrasparc-IIi Processor. Master’s thesis, University of Florida, Gainesville, FL, April 1999.

    Google Scholar 

21. P. Sulatycke and K. Ghose, Caching-efficient multithreaded fast multiplication of sparse matrices. Proceedings 12the International Parallel Processing Symposium, 117–123, 1998.

    Google Scholar 

22. O. Temam, C. Fricker, and W. Jalby. Cache interference phenomena. In Proceedings of the 1994 ACM SIGMETRICS: Conference on Measurement and Modelling of Computer Systems, pages 261–271, Nashville, Tennessee, 1994.

    Google Scholar 

23. O. Temam, C. Fricker, and W. Jalby. Influence of cross-interference on blocked loops: A case study with matrix-vector multiply. The ACM Transactions on Programming Languages and Systems, 17(4):561–575, 1994.

    Google Scholar 

24. H. Wen and J. L. Baer. Efficient trace driven simulation methods for cache performance analysis. The ACM Transactions on Computer Systems, 9(3):222–241, 1991.

    Article  Google Scholar 

25. M. E. Wolf and M. S. Lam. A data locality optimizing. In In Proceedings of the SIGPLAN’ 91 Conference on Programming Language Design and Implementation, pages 30–44, Toronto, Ontario, Canada, 1991.

    Google Scholar 

Download references