Applications of storage mapping optimization to register promotion

ABSTRACT

Storage mapping optimization is a flexible approach to folding array dimensions in numerical codes. It is designed to reduce the memory footprint after a wide spectrum of loop transformations, whether based on uniform dependence vectors or more expressive polyhedral abstractions. Conversely, few loop transformations have been proposed to facilitate register promotion, namely loop fusion, unroll-and-jam or tiling. Building on array data-flow analysis and expansion, we extend storage mapping optimization to improve opportunities for register promotion.Our work is motivated by the empirical study of a computational biology benchmark, the approximate string matching algorithm BPR from NR-grep, on a wide issue micro-architecture. Our experiments confirm the major benefit of register tiling (even on non-numerical benchmarks) but also shed the light on two novel issues: prior array expansion may be necessary to enable loop transformations that finally authorize profitable register promotion, and more advanced scheduling techniques (beyond tiling and unroll-and-jam) may significantly improve performance in fine-tuning register usage and instruction-level parallelism.

REFERENCES

• 1: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 2: Denis Barthou , Albert Cohen , Jean-François Collard, Maximal static expansion, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.98-106, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268955]
• 3: Denis Barthou , Jean-François Collard , Paul Feautrier, Fuzzy array dataflow analysis, Journal of Parallel and Distributed Computing, v.40 n.2, p.210-226, Feb. 1997 [doi>10.1006/jpdc.1996.1261 ]
• 4: C. Bastoul. Efficient code generation for automatic parallelization and optimization. In ISPDC'2 IEEE International Symposium on Parallel and Distributed Computing, Ljubjana, Slovenia, Oct. 2003.
• 5: C. Bastoul, A. Cohen, S. Girbal, S. Sharma, and O. Temam. Putting polyhedral loop transformations to work. In Workshop on Languages and Compilers for Parallel Computing (LCPC'03), LNCS, College Station, Texas, Oct. 2003.
• 6: C. Bastoul and P. Feautrier. Improving data locality by chunking. In CC'12 Intl. Conference on Compiler Construction, LNCS 2622, pages 320--335, Warsaw, Poland, april 2003.
• 7: Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Load-reuse analysis: design and evaluation, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.64-76, May 01-04, 1999, Atlanta, Georgia, United States
• 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: Pierre-Yves Calland , Alain Darte , Yves Robert , Frédéric Vivien, Plugging anti and output dependence removal techniques into loop parallelization algorithm, Parallel Computing, v.23 n.1-2, p.251-266, April 1997 [doi>10.1016/S0167-8191(96)00108-1 ]
• 10: Steve Carr , Ken Kennedy, Improving the ratio of memory operations to floating-point operations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1768-1810, Nov. 1994 [doi>10.1145/197320.197366]
• 11: L. Carter, J. Ferrante, and S. F. Hummel. Efficient multiprocessor parallelism via hierarchical tiling. In SIAM Conference on Parallel Processing for Scientific Computing, Feb. 1995.
• 12: A. Cohen, S. Girbal, and O. Temam. Facilitating the exploration of compositions of program transformations. Research report 5114, INRIA Futurs, France, Feb. 2004.
• 13: Albert Cohen , Vincent Lefebvre, Storage Mapping Optimization for Parallel Programs, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.375-382, August 31-September 03, 1999
• 14: Jean-François Collard , Denis Barthou , Paul Feautrier, Fuzzy array dataflow analysis, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.92-101, July 19-21, 1995, Santa Barbara, California, United States
• 15: Keith D. Cooper , Devika Subramanian , Linda Torczon, Adaptive Optimizing Compilers for the 21st Century, The Journal of Supercomputing, v.23 n.1, p.7-22, August 2002 [doi>10.1023/A:1015729001611 ]
• 16: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, A practical data flow framework for array reference analysis and its use in optimizations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.68-77, June 21-25, 1993, Albuquerque, New Mexico, United States
• 17: P. Feautrier, Array expansion, Proceedings of the 2nd international conference on Supercomputing, p.429-441, June 1988, St. Malo, France [doi>10.1145/55364.55406]
• 18: P. Feautrier. Parametric integer programming. RAIRO Recherche Opérationnelle, 22:243--268, Sept. 1988.
• 19: Paul Feautrier, Some efficient solutions to the affine scheduling problem: I. One-dimensional time, International Journal of Parallel Programming, v.21 n.5, p.313-348, Oct. 1992 [doi>10.1007/BF01407835]
• 20: G. Fursin, M. O'Boyle, and P. Knijnenburg. Evaluating iterative compilation. In 11 th Workshop on Languages and Compilers for Parallel Computing, LNCS, Washington DC, July 2002. Springer-Verlag.
• 21: Marta Jiménez , José M. Llabería , Agustín Fernández, Register tiling in nonrectangular iteration spaces, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.4, p.409-453, July 2002 [doi>10.1145/567097.567101]
• 22: W. Kelly. Optimization within a unified transformation framework. Technical Report CS-TR-3725, University of Maryland, 1996.
• 23: T. Kisuki, P. Knijnenburg, K. Gallivan, and M. O'Boyle. The effect of cache models on iterative compilation for combined tiling and unrolling. In Parallel Architectures and Compilation Techniques (PACT'00). IEEE Computer Society Press, Oct. 2001.
• 24: Kathleen Knobe , Vivek Sarkar, Array SSA form and its use in parallelization, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.107-120, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268956]
• 25: Induprakas Kodukula , Nawaaz Ahmed , Keshav Pingali, Data-centric multi-level blocking, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.346-357, June 16-18, 1997, Las Vegas, Nevada, United States
• 26: Vincent Lefebvre , Paul Feautrier, Automatic storage management for parallel programs, Parallel Computing, v.24 n.3-4, p.649-671, May, 1998 [doi>10.1016/S0167-8191(98)00029-5 ]
• 27: Amy W. Lim , Monica S. Lam, Maximizing parallelism and minimizing synchronization with affine transforms, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.201-214, January 15-17, 1997, Paris, France [doi>10.1145/263699.263719]
• 28: Amy W. Lim , Shih-Wei Liao , Monica S. Lam, Blocking and array contraction across arbitrarily nested loops using affine partitioning, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.103-112, June 2001, Snowbird, Utah, United States
• 29: Vincent Loechner , Benoît Meister , Philippe Clauss, Precise Data Locality Optimization of Nested Loops, The Journal of Supercomputing, v.21 n.1, p.37-76, January 2002 [doi>10.1023/A:1013535431127 ]
• 30: Vincent Loechner , Doran K. Wilde, Parameterized polyhedra and their vertices, International Journal of Parallel Programming, v.25 n.6, p.525-549, Dec. 1997 [doi>10.1023/A:1025117523902]
• 31: John Lu , Keith D. Cooper, Register promotion in C programs, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.308-319, June 16-18, 1997, Las Vegas, Nevada, United States
• 32: Dror E. Maydan , Saman P. Amarasinghe , Monica S. Lam, Array-data flow analysis and its use in array privatization, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.2-15, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158515]
• 33: Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
• 34: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 35: Gonzalo Navarro , Mathieu Raffinot, Flexible pattern matching in strings: practical on-line search algorithms for texts and biological sequences, Cambridge University Press, New York, NY, 2002
• 36: David Parello , Olivier Temam , Jean-Marie Verdun, On increasing architecture awareness in program optimizations to bridge the gap between peak and sustained processor performance: matrix-multiply revisited, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-11, November 16, 2002, Baltimore, Maryland
• 37: G.-R. Perrin and A. Darte, editors. The Data Parallel Programming Model. Number 1132 in LNCS. Springer-Verlag, 1996.
• 38: Geoffrey Roeder Pike , Paul N. Hilfinger, Reordering and storage optimizations for scientific programs, 2002
• 39: 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]
• 40: Fabien Quilleré , Sanjay Rajopadhye, Optimizing memory usage in the polyhedral model, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.5, p.773-815, Sept. 2000 [doi>10.1145/365151.365152]
• 41: Fabien Quilleré , Sanjay Rajopadhye , Doran Wilde, Generation of Efficient Nested Loops from Polyhedra, International Journal of Parallel Programming, v.28 n.5, p.469-498, Oct. 2000 [doi>10.1023/A:1007554627716 ]
• 42: R. Schreiber, S. Aditya, B. Rau, V. Kathail, S. Mahlke, S. Abraham, and G. Snider. High-level synthesis of nonprogrammable hardware accelerators. Technical report, Hewlett-Packard, May 2000.
• 43: Byoungro So , Mary W. Hall , Pedro C. Diniz, A compiler approach to fast hardware design space exploration in FPGA-based systems, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 44: Michelle Mills Strout , Larry Carter , Jeanne Ferrante , Beth Simon, Schedule-independent storage mapping for loops, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.24-33, October 02-07, 1998, San Jose, California, United States
• 45: William Thies , Frédéric Vivien , Jeffrey Sheldon , Saman Amarasinghe, A unified framework for schedule and storage optimization, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.232-242, June 2001, Snowbird, Utah, United States
• 46: Peng Tu , David A. Padua, Automatic Array Privatization, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.500-521, August 12-14, 1993
• 47: D. Wonnacott and W. Pugh. Nonlinear array dependence analysis. In Proc. Third Workshop on Languages, Compilers and Run-Time Systems for Scalable Computers, 1995. Troy, New York.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Performance

Keywords:
array contraction, array folding, blocking, itanium, pattern matching, register promotion, scheduling, string matching, tiling