Cache-oblivious dynamic programming

ABSTRACT

We present efficient cache-oblivious algorithms for several fundamental dynamic programs. These include new algorithms with improved cache performance for longest common subsequence (LCS), edit distance, gap (i.e., edit distance with gaps), and least weight subsequence. We present a new cache-oblivious framework called the Gaussian Elimination Paradigm (GEP) for Gaussian elimination without pivoting that also gives cache-oblivious algorithms for Floyd-Warshall all-pairs shortest paths in graphs and 'simple DP', among other problems.

REFERENCES

• 1: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 2: A. Apostolico , S. Browne , C. Guerra, Fast linear-space computations of longest common subsequences, Theoretical Computer Science, v.92 n.1, p.3-17, Jan. 6, 1992 [doi>10.1016/0304-3975(92)90132-Y ]
• 3: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 4: Robert D. Blumofe , Matteo Frigo , Christopher F. Joerg , Charles E. Leiserson , Keith H. Randall, An analysis of dag-consistent distributed shared-memory algorithms, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.297-308, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237574]
• 5: R. A. Chowdhury. Experimental Evaluation of a Cache-Oblivious LCS Algorithm. Tech. Rep. TR-05-43, Dept. of Comp. Sci., University of Texas at Austin, Oct. 2005.
• 6: C. Cherng and R. E. Ladner. Cache efficient simple dynamic programming. In Proc. of the International Conf. on the Analysis of Algorithms, pp. 49--58, 2005.
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 8: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 9: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 10: Matteo Frigo , Volker Strumpen, Cache oblivious stencil computations, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088197]
• 11: Zvi Galil , Raffaele Giancarlo, Speeding up dynamic programming with application to molecular biology, Theoretical Computer Science, v.64 n.1, p.107-118, April 1989 [doi>10.1016/0304-3975(89)90101-1 ]
• 12: Zvi Galil , Kunsoo Park, Parallel algorithms for dynamic programming recurrences with more than O(1) dependency, Journal of Parallel and Distributed Computing, v.21 n.2, p.213-222, May 1994 [doi>10.1006/jpdc.1994.1053 ]
• 13: D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, v.18 n.6, p.341-343, June 1975 [doi>10.1145/360825.360861]
• 14: Daniel S. Hirschberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.24 n.4, p.664-675, Oct. 1977 [doi>10.1145/322033.322044]
• 15: D. S. Hirschberg , L. L. Larmore, The least weight subsequence problem, SIAM Journal on Computing, v.16 n.4, p.628-638, Aug. 1987 [doi>10.1137/0216043]
• 16: Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
• 17: Ellis Horowitz , Sartaj Sahni , Sanguthevar Rajasckaran, Computer Algorithms: C++, W. H. Freeman & Co., New York, NY, 1996
• 18: S K Kumar , C P Rangan, A linear space algorithm for the LCS problem, Acta Informatica, v.24 n.3, p.353-362, June 1987
• 19: Jon Kleinberg , Eva Tardos, Algorithm Design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 20: Joon-Sang Park , Michael Penner , Viktor K. Prasanna, Optimizing Graph Algorithms for Improved Cache Performance, IEEE Transactions on Parallel and Distributed Systems, v.15 n.9, p.769-782, September 2004 [doi>10.1109/TPDS.2004.44]
• 21: Mashe Sniedovich, Dynamic Programming, Marcel Dekker, Inc., New York, NY, 1991
• 22: J. W. Thomas, J. W. Touchman, R. W. Blakesley, G. G. Bouffard, S. M. Beckstrom-Sternberg, E. H. Margulies, M. Blanchette, A. C. Siepel, P. J. Thomas, J. C. McDowell, B. Maskeri, N. F. Hansen, M. S. Schwartz, R. J. Weber, W. J. Kent, D. Karolchik, T. C. Bruen, R. Bevan, D. J. Cutler, S. Schwartz, L. Elnitski, J. R. Idol, A. B. Prasad, S.-Q. Lee-Lin, V. V. B. Maduro, T. J. Summers, M. E. Portnoy, N. L. Dietrich, N. Akhter, K. Ayele, B. Benjamin, K. Cariaga, C. P. Brinkley, S. Y. Brooks, S. Granite, X. Guan, J. Gupta, P. Haghihi, S.-L. Ho, M. C. Huang, E. Karlins, P. L. Laric, R. Legaspi, M. J. Lim, Q. L. Maduro, C. A. Masiello, S. D. Mastrian, J. C. McCloskey, R. Pearson, S. Stantripop, E. E. Tiongson, J. T. Tran, C. Tsurgeon, J. L. Vogt, M. A. Walker, K. D. Wetherby, L. S. Wiggins, A. C. Young, L.-H. Zhang, K. Osoegawa, B. Zhu, B. Zhao, C. L. Shu, P. J. De Jong, C. E. Lawrence, A. F. Smit, A. Chakravarti, D. Haussler, P. Green, W. Miller, and E. D. Green. Comparative analyses of multi-species sequences from targeted genomic regions. Nature, vol. 424, pp. 788--793, 2003.
• 23: Sivan Toledo, Locality of Reference in LU Decomposition with Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.18 n.4, p.1065-1081, Oct. 1997 [doi>10.1137/S0895479896297744]
• 24: L. G. Valiant. General context-free recognition in less than cubic time. Journal of Compute and System Sciences, vol. 10, pp. 308--315, 1975.
• 25: Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
• 26: M. S. Waterman. Introduction to Computational Biology. Chapman & Hall, London, UK, 1995.
• 27: D. Womble, D. Greenberg, S. Wheat, and R. Riesen. Beyond core: making parallel computer I/O practical. In Proc. of the DAGS/PC Symposium, pp. 56--63, 1993.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms, Theory