Eliminating redundancies in sum-of-product array computations

ABSTRACT

Array programming languages such as Fortran 90, High Performance Fortran and ZPL are well-suited to scientific computing because they free the scientist from the responsibility of managing burdensome low-level details that complicate programming in languages like C and Fortran 77. However, these burdensome details are critical to performance, thus necessitating aggressive compilation techniques for their optimization. In this paper, we present a new compiler optimization called Array Subexpression Elimination (ASE) that lets a programmer take advantage of the expressibility afforded by array languages and achieve enviable portability and performance. We design a set of micro-benchmarks that model an important class of computations known as stencils and we report on our implementation of this optimization in the context of this micro-benchmark suite. Our results include a 125% improvement on one of these benchmarks and a 50% average speedup across the suite. Also we show a speedup of 32% improvement on the ZPL port of the NAS MG Parallel Benchmark and a 29% speedup over the hand-optimized Fortran version. Further, the compilation time is only negligibly affected.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: Jeanne C. Adams , Brian T. Smith , Jeanne T. Martin , Walter S. Brainerd , Jerrold L. Wagener, FORTRAN 95 Handbook, MIT Press, Cambridge, MA, 1997
• 3: A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 4: D. Bailey, E. Barszcz, J. Barton, D. Browning, R. Carter, L. Dagum, R. Fatoohi, S. Fineberg, P. Frederickson, T. Lasinski, R. Schreiber, H. Simon, V. Venkatakrishnan, and S. Weeratunga. The NAS parallel benchmarks (94). Technical report, RNR Technical Report RNR-94-007, March 1994.
• 5: D. Bailey, T. Harris, W. Saphir, R. van der Wijngaart, A. Woo, and M. Yarrow. The NAS parallel benchmarks 2.0. Technical report, NAS Report NAS-95-020, December 1995.
• 6: R. G. Brickner, K. Holian, B. Thiagarajan, and S. L. Johnson. A stencil compiler for the connection machine model cm-5. Technical report, Center for Research onParallel Computation CRPC-TR94457, June 1994.
• 7: 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
• 8: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 9: 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]
• 10: C. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via coloring. Computer Languages, 6:45-57, January 1981.
• 11: Bradford L. Chamberlain , Steven J. Deitz , Lawrence Snyder, A comparative study of the NAS MG benchmark across parallel languages and architectures, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.46-es, November 04-10, 2000, Dallas, Texas, United States
• 12: M. D. Ernst, Serializing Parallel Programs by Removing Redundant Computation, Massachusetts Institute of Technology, Cambridge, MA, 1994
• 13: A. L. Fisher and P. T. Highnam. Communication and code optimization in simd programs. In International Conference onParallel Processing, 1988.
• 14: A. L. Fisher, J. Leon, and P. T. Highnam. Design and performance of an optimizing simd compiler. In Frontiers of Massively Parallel Computation, 1990.
• 15: Robert M. Haralick , Linda G. Shapiro, Computer and Robot Vision, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 16: High Performance Fortran Forum. High Performance Fortran Langauge Specification, Version 2.0. January 1997.
• 17: E. Christopher Lewis , Calvin Lin , Lawrence Snyder, The implementation and evaluation of fusion and contraction in array languages, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.50-59, June 17-19, 1998, Montreal, Quebec, Canada
• 18: Yanhong A. Liu , Scott D. Stoller, Loop optimization for aggregate array computations, Proceedings of the 1998 International Conference on Computer Languages, p.262, May 14-16, 1998
• 19: Gerald Roth , John Mellor-Crummey , Ken Kennedy , R. Gregg Brickner, Compiling stencils in high performance Fortran, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-20, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509605]
• 20: L. Snyder. Programming Guide to ZPL. MIT Press, 1999.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Algorithms, Design, Performance