Optimizing aggregate array computations in loops

ABSTRACT

An aggregate array computation is a loop that computes accumulated quantities over array elements. Such computations are common in programs that use arrays, and the array elements involved in such computations often overlap, especially across iterations of loops, resulting in significant redundancy in the overall computations. This article presents a method and algorithms that eliminate such overlapping aggregate array redundancies and shows analytical and experimental performance improvements. The method is based on incrementalization, that is, updating the values of aggregate array computations from iteration to iteration rather than computing them from scratch in each iteration. This involves maintaining additional values not maintained in the original program. We reduce various analysis problems to solving inequality constraints on loop variables and array subscripts, and we apply results from work on array data dependence analysis. For aggregate array computations that have significant redundancy, incrementalization produces drastic speedup compared to previous optimizations; when there is little redundancy, the benefit might be offset by cache effects and other factors. Previous methods for loop optimizations of arrays do not perform incrementalization, and previous techniques for loop incrementalization do not handle arrays.

REFERENCES

• 1: Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Synthesizing Transformations for Locality Enhancement of Imperfectly-Nested Loop Nests, International Journal of Parallel Programming, v.29 n.5, p.493-544, October 2001 [doi>10.1023/A:1012293814832]
• 2: Vicki H. Allan , Reese B. Jones , Randall M. Lee , Stephen J. Allan, Software pipelining, ACM Computing Surveys (CSUR), v.27 n.3, p.367-432, Sept. 1995 [doi>10.1145/212094.212131]
• 3: Allen, F. E. and Cocke, J.1971. A catalogue of optimizing transformations. In Design and Optimization of Compilers. R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J. pp. 1--30.
• 4: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• 5: Banerjee, U.1990. Unimodular transformations of double loops. In Proceedings of the Workshop on Advances in Languages and Compilers for Parallel Processing (Aug.), pp. 192--219.
• 6: Friedrich Ludwig Bauer , Bernhard Möller , Helmut Partsch , Peter Pepper, Formal Program Construction by Transformations-Computer-Aided, Intuition-Guided Programming, IEEE Transactions on Software Engineering, v.15 n.2, p.165-180, February 1989 [doi>10.1109/32.21743]
• 7: R. S. Bird, The promotion and accumulation strategies in transformational programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.487-504, Oct. 1984 [doi>10.1145/1780.1781]
• 8: Booth, R. 1997. Inner Loops. Addison-Wesley Developers Press, Reading, Mass.
• 9: Mark Bromley , Steven Heller , Tim McNerney , Guy L. Steele, Jr., Fortran at ten gigaflops: the connection machine convolution compiler, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.145-156, June 24-28, 1991, Toronto, Ontario, Canada
• 10: Broy, M.1984. Algebraic methods for program construction: The project CIP. In Program Transformation and Programming Environments, P. Pepper, Ed., Springer-Verlag, Berlin, Germany. pp. 199--222.
• 11: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 12: J. Cai , R. Paige, Program derivation by fixed point computation, Science of Computer Programming, v.11 n.3, p.197-261, April 1989 [doi>10.1016/0167-6423(88)90033-0]
• 13: Steve Carr , Ken Kennedy, Scalar replacement in the presence of conditional control flow, Software—Practice & Experience, v.24 n.1, p.51-77, Jan. 1994 [doi>10.1002/spe.4380240104]
• 14: Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.286-297, June 2001, Snowbird, Utah, United States
• 15: Wei-Ngan Chin, Safe fusion of functional expressions, Proceedings of the 1992 ACM conference on LISP and functional programming, p.11-20, June 22-24, 1992, San Francisco, California, United States
• 16: John Cocke , Ken Kennedy, An algorithm for reduction of operator strength, Communications of the ACM, v.20 n.11, p.850-856, Nov. 1977 [doi>10.1145/359863.359888]
• 17: Charles Consel , François Noël, A general approach for run-time specialization and its application to C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-156, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237767]
• 18: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 19: Earley, J.1976. High level iterators and a method for automatically designing data structure representation. J. Comput. Lang. 1, 321--342.
• 20: Ernst, M. D.1992. Serializing parallel programs by removing redundant computation. Master's thesis. MIT, Cambridge, Mass. (Revised August 1994.)
• 21: Peter Faber , Martin Griebl , Christian Lengauer, Loop-Carried Code Placement, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.230-234, August 28-31, 2001
• 22: Feautrier, P.1988. Parametric integer programming. Operationnelle/Oper. Res. 22, 3 (Sept.), 243--268.
• 23: Feautrier, P.1991. Dataflow analysis of array and scalar references. Int. J. Parall. Prog. 20, 1 (Feb.).
• 24: Fisher, A. L. and Highnam, P. T.1988. Communication and code optimization in SIMD programs. In International Conference on Parallel Processing (Aug.).
• 25: Fisher, A. L., Leon, J., and Highnam, P. T.1990. Design and performance of an optimizing SIMD compiler. In Frontiers of Massively Parallel Computation.
• 26: Amelia C. Fong, Inductively computable constructs in very high level languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.21-28, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567755]
• 27: Amelia C. Fong , Jeffrey D. Ullman, Induction variables in very high level languages, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.104-112, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811544]
• 28: Ole Immanuel Franksen, Mr. Babbage's Secret: The Tale of a Cipher-and APL, Prentice Hall PTR, Upper Saddle River, NJ, 1985
• 29: Garg, V. K. and Mitchell, J. R.1996. An efficient algorithm for detecting conjunctions of general global predicates. Tech. Rep. TR-PDS-1996-005. University of Texas at Austin, Austin, Tex.
• 30: Allen Goldberg , Robert Paige, Stream processing, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.53-62, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802021]
• 31: Goldstine, H. H.1972. Charles Babbage and his analytical engine. In The Computer from Pascal to von Neumann, Princeton University Press, Princeton, N.J., Chap. 2, 10--26.
• 32: Eric Goubault, Static Analyses of the Precision of Floating-Point Operations, Proceedings of the 8th International Symposium on Static Analysis, p.234-259, July 16-18, 2001
• 33: Grau, A. A., Hill, U., and Langmaac, H.1967. Translation of ALGOL 60. Volume 1 of Handbook for Automatic Computation. Springer, Berlin, Germany.
• 34: Gries, D.1984. A note on a standard strategy for developing loop invariants and loops. Sci. Comput. Program., 2, 207--214.
• 35: Leo J. Guibas , Douglas K. Wyatt, Compilation and delayed evaluation in APL, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-8, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512761]
• 36: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996
• 37: Peter Thomas Highnam, Systems and programming issues in the design and use of a SIMD linear array for image processing, Carnegie Mellon University, Pittsburgh, PA, 1991
• 38: Katz, S.1978. Program optimization using invariants. IEEE Trans. Softw. Eng. SE-4, 5 (Nov.), 378--389.
• 39: Wayne Kelly , William Pugh, Finding Legal Reordering Transformations Using Mappings, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.107-124, August 08-10, 1994
• 40: Knuth, D. E.1971. An empirical study of FORTRAN programs. Softw. Pract. Exp. 1, 2, 105--133.
• 41: Li, K.1997. Interferometric strain/slope rosette for static and dynamic measurements. Exper. Mech. 37, 2, 111--118.
• 42: Yanhong A. Liu, Principled strength reduction, Proceedings of the IFIP TC 2 WG 2.1 international workshop on Algorithmic languages and calculi, p.357-381, January 1997, Alsace, France
• 43: Yanhong A. Liu, Efficiency by Incrementalization: An Introduction, Higher-Order and Symbolic Computation, v.13 n.4, p.289-313, Dec. 1, 2000 [doi>10.1023/A:1026547031739]
• 44: Yanhong A. Liu , Scott D. Stoller, Program optimization using indexed and recursive data structures, Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.108-118, January 14-15, 2002, Portland, Oregon
• 45: Yanhong A. Liu , Scott D. Stoller, Dynamic Programming via Static Incrementalization, Higher-Order and Symbolic Computation, v.16 n.1-2, p.37-62, March-June 2003 [doi>10.1023/A:1023068020483]
• 46: Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Static caching for incremental computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.546-585, May 1998 [doi>10.1145/291889.291895]
• 47: Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Strengthening invariants for efficient computation, Science of Computer Programming, v.41 n.2, p.139-172, October 2001 [doi>10.1016/S0167-6423(01)00003-X]
• 48: Yanhong A. Liu , Tim Teitelbaum, Systematic derivation of incremental programs, Science of Computer Programming, v.24 n.1, p.1-39, Feb. 1995 [doi>10.1016/0167-6423(94)00031-9]
• 49: Vadim Maslov, Lazy array data-flow dependence analysis, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-325, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177911]
• 50: R. Paige, Symbolic finite differencing, part I (invited lecture), Proceedings of the third European symposium on programming on ESOP '90, p.36-56, May 1990, Copenhagen, Denmark
• 51: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• 52: Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation. ACM, New York, 1996.
• 53: William Pugh, Uniform techniques for loop optimization, Proceedings of the 5th international conference on Supercomputing, p.341-352, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109108]
• 54: William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
• 55: William Pugh , David Wonnacott, Constraint-based array dependence analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.635-678, May 1998 [doi>10.1145/291889.291900]
• 56: Thomas W. Reps , Tim Teitelbaum, The synthesizer generator: a system for constructing language-based editors, Springer-Verlag New York, Inc., New York, NY, 1989
• 57: Vivek Sarkar , Radhika Thekkath, A general framework for iteration-reordering loop transformations, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.175-187, June 15-19, 1992, San Francisco, California, United States
• 58: D. R. Smith, KIDS: A Semiautomatic Program Development System, IEEE Transactions on Software Engineering, v.16 n.9, p.1024-1043, September 1990 [doi>10.1109/32.58788]
• 59: Philip Wadler, Deforestation: Transforming Programs to Eliminate Trees, Proceedings of the 2nd European Symposium on Programming, p.344-358, March 21-24, 1988
• 60: Joe Warren, A hierarchical basis for reordering transformations, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.272-282, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800539]
• 61: Richard C. Waters, Automatic transformation of series expressions into loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.52-98, Jan. 1991 [doi>10.1145/114005.102806]
• 62: Jon A. Webb, Steps Toward Architecture-Independent Image Processing, Computer, v.25 n.2, p.21-31, February 1992 [doi>10.1109/2.121472]
• 63: Wegbreit, B.1976. Goal-directed program transformation. IEEE Trans. Softw. Eng. SE-2, 2 (June), 69--80.
• 64: W Wells, III, Efficient synthesis of Gaussian filters by cascaded uniform filters, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.2, p.234-239, March 1986 [doi>10.1109/TPAMI.1986.4767776]
• 65: Daniel M. Yellin , Robert E. Strom, INC: a language for incremental computations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.211-236, April 1991 [doi>10.1145/103135.103137]
• 66: Ramin Zabih , Oussama Khatib, Individuating unknown objects by combining motion and stereo, 1994
• 67: Ramin Zabih , John Woodfill, Non-parametric Local Transforms for Computing Visual Correspondence, Proceedings of the Third European Conference-Volume II on Computer Vision, p.151-158, May 02-06, 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.2 Automatic Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Code generation

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Algorithms, Languages, Performance

Keywords:
Array dependence analysis, caching intermediate results, incremental computation, loop optimization, program transformation