Gayathri Venkataraman
Sartaj Sahni
Skip Abstract Section
Skip Supplemental Material SectionAbstract
We propose a blocked version of Floyd's all-pairs shortest-paths algorithm. The blocked algorithm makes better utilization of cache than does Floyd's original algorithm. Experiments indicate that the blocked algorithm delivers a speedup (relative to the unblocked Floyd's algorithm) between 1.6 and 1.9 on a Sun Ultra Enterprise 4000/5000 for graphs that have between 480 and 3200 vertices. The measured speedup on an SGI O2 for graphs with between 240 and 1200 vertices is between 1.6 and 2.
Supplemental Material
Available for Download
- {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, 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, 305-314, New York, 1987. Google ScholarDigital Library
- {3} A. Aggarwal, K. Chandra, and M. Snir. Hierarchical memory with block transfer. In The 28th Annual IEEE Symposium on Foundations of Computer Science, 204-216, Los Angeles, CA, 1987.Google ScholarDigital Library
- {4} A. Aggarwal, M. Horowitz, and Hennessey. An analytical cache model. The ACM Transactions on Computer Systems, 7(2):184-215, 1989. Google ScholarDigital Library
- {5} B. Alpern, L. Carter, E. Feig, and T. Selker. The uniform memory hierarchy model of computation. Algorithmica, 12(2-3):72-109, 1994.Google ScholarDigital Library
- {6} D. Callahan, S. Carr, and K. Kennedy. Improving register allocation for subscripted variables. In Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, White Plains, New York, 53-65, 1990. Google ScholarDigital Library
- {7} N. Eiron, M. Rodeh, and I. Steinwarts. Matrix multiplication: a case study of enhanced data cache utilization. ACM JEA, 4, Article 3, 1999. Google Scholar
- {8} 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
- {9} G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 1989.Google Scholar
- {10} E. Horowitz, S. Sahni, and S. Rajasekaran. Computer Algorithms. Computer Science Press, New York, 1998. Google ScholarDigital Library
- {11} M. S. Lam, E. E. Rothberg, and M. E. Wolf. The cache performance and optimizations of blocked algorithms. ACM, 26:63-74, 1991.Google ScholarDigital Library
- {12} 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
- {13} A. LaMarca and R. E. Ladner. The influences of caches on the performance of sorting. Journal of Algorithms, 31, 66-104, 1999. Google ScholarDigital Library
- {14} R. Ladner, J. Fix, and A. LaMarca. The cache performance analysis of traversals and random accesses. In The ACM-SIAM Symposium on Discrete Algorithms, 613-622, 1999. 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, 1-12, Newport, Rhode Island, 1992. Google ScholarDigital Library
- {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 ScholarDigital Library
- {17} D. Patterson and J. L. Hennessy. Computer Architecture: A Quantitative Analysis. Morgan Kaufmann, San Mateo, CA, 1996. Google Scholar
- {18} N. Rahman and R. Raman. Analysing cache effects in distribution sorting. ACM JEA, 5, Article 14, 2000. 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 associative caches. IEEE Transactions on Computers, 41(7):811-825, 1992. Google ScholarDigital Library
- {20} Sun Microsystems. Introduction to Shade. Manual, Sun Microsystems, Mountain View, CA, 1998.Google Scholar
- {21} 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, 261-271, Nashville, Tennessee, 1994. Google ScholarCross Ref
- {22} 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
- {23} 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. Google ScholarDigital Library
- {24} M. E. Wolf and M. S. Lam. A data locality optimizing. In Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, 30-44, Toronto, Ontario, Canada, 1991. Google Scholar
- {25} L. Xiao, X. Zhang, and S. Kubricht. Improving memory performance of sorting algorithms, ACM JEA, 5, Article 3, 2000. Google Scholar
Index Terms
- A blocked all-pairs shortest-paths algorithm
Recommendations
Planar graph decomposition and all pairs shortest paths
An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The algorithm runs in O(pn) time, where n is the number of vertices in G,...
An O(n3loglogn/log2n) time algorithm for all pairs shortest paths
We present an O(n3loglogn/log2n) time algorithm for all pairs shortest paths. This algorithm improves on the best previous result of O(n3(loglogn)3/log2n) time.
Combining the shortest paths and the bottleneck paths problems
ACSC '14: Proceedings of the Thirty-Seventh Australasian Computer Science Conference - Volume 147We combine the well known Shortest Paths (SP) problem and the Bottleneck Paths (BP) problem to introduce a new problem called the Shortest Paths for All Flows (SP-AF) problem that has relevance in real life applications. We first solve the Single Source ...
Comments