Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

To achieve high performance on multi-cores, modern loop optimizers apply long sequences of transformations that produce complex loop structures. Downstream optimizations such as register tiling (unroll-and-jam plus scalar promotion) typically provide a significant performance improvement. Typical register tilers provide this performance improvement only when applied on simple loop structures. They often fail to operate on complex loop structures leaving a significant amount of performance on the table. We present a technique called compact multi-dimensional kernel extraction (COMDEX) which can make register tilers operate on arbitrarily complex loop structures and enable them to provide the performance benefits. COMDEX extracts compact unrollable kernels from complex loops. We show that by using COMDEX as a pre-processing to register tiling we can (i) enable register tiling on complex loop structures and (ii) realize a significant performance improvement on a variety of codes.

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: Uday Bondhugula, M. Baskaran, Sriram Krishnamoorthy, J. Ramanujam, A. Rountev, and P. Sadayappan. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. In International conference on Compiler Construction (ETAPS CC), April 2008.
• 3: Uday Bondhugula , Albert Hartono , J. Ramanujam , P. Sadayappan, A practical automatic polyhedral parallelizer and locality optimizer, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA [doi>10.1145/1375581.1375595]
• 4: 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 [doi>10.1145/93542.93553]
• 5: Steve Carr , Yiping Guan, Unroll-and-jam using uniformly generated sets, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.349-357, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 6: Steve Carr , Philip Sweany, An experimental evaluation of scalar replacement on scientific benchmarks, Software—Practice & Experience, v.33 n.15, p.1419-1445, December 2003 [doi>10.1002/spe.546]
• 7: L. Carter, J. Ferrante, F. Hummel, B. Alpern, and K. S. Gatlin. Hierarchical tiling: A methodology for high performance. Technical Report CS96-508, UCSD, Nov. 1996.
• 8: Larry Carter , Jeanne Ferrante , Susan Flynn Hummel, Hierarchical tiling for improved superscalar performance, Proceedings of the 9th International Symposium on Parallel Processing, p.239-245, April 25-28, 1995
• 9: Albert Cohen , Marc Sigler , Sylvain Girbal , Olivier Temam , David Parello , Nicolas Vasilache, Facilitating the search for compositions of program transformations, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088169]
• 10: Albert Hartono , Muthu Manikandan Baskaran , Cédric Bastoul , Albert Cohen , Sriram Krishnamoorthy , Boyana Norris , J. Ramanujam , P. Sadayappan, Parametric multi-level tiling of imperfectly nested loops, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, USA [doi>10.1145/1542275.1542301]
• 11: HiTLoG: Hierarchical Tiled Loop Generator. Available at: http://www.cs.colostate.edu/MMAlpha/HiTLoG/.
• 12: F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
• 13: 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]
• 14: P. M. W. Knijnenburg , T. Kisuki , K. Gallivan , M. F. P. O'Boyle, The effect of cache models on iterative compilation for combined tiling and unrolling: Research Articles, Concurrency and Computation: Practice & Experience, v.16 n.2-3, p.247-270, January 2004 [doi>10.1002/cpe.v16:2/3]
• 15: Nicholas Mitchell , Karin Högstedt , Larry Carter , Jeanne Ferrante, Quantifying the multi-level nature of tiling interactions, International Journal of Parallel Programming, v.26 n.6, p.641-670, Dec. 1998 [doi>10.1023/A:1018782528453]
• 16: 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]
• 17: Lakshminarayanan Renganarayana, Ramakrishna Upadrasta, and Sanjay Rajopadhye. Optimal ILP and register tiling: Analytical model and optimization framework. In LCPC 2005: 12th International Workshop on Languages and Compilers for Parallel Computing. Springer Verlag, 2005.
• 18: Lakshminarayanan Renganarayanan , DaeGon Kim , Sanjay Rajopadhye , Michelle Mills Strout, Parameterized tiled loops for free, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA [doi>10.1145/1250734.1250780]
• 19: Vivek Sarkar, Optimized unrolling of nested loops, Proceedings of the 14th international conference on Supercomputing, p.153-166, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335246]
• 20: Vivek Sarkar, Optimized Unrolling of Nested Loops, International Journal of Parallel Programming, v.29 n.5, p.545-581, October 2001 [doi>10.1023/A:1012246031671]
• 21: Nicolas Vasilache. Scalable Program Optimization Techniques in the Polyhedral Model. PhD thesis, Université de Paris-Sud, INRIA Futurs, September 2007.
• 22: R. Clint Whaley , Jack J. Dongarra, Automatically tuned linear algebra software, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-27, November 07-13, 1998, San Jose, CA
• 23: Jingling Xue, Loop tiling for parallelism, Kluwer Academic Publishers, Norwell, MA, 2000
• 24: K. Yotov, Xiaoming Li, Gang Ren, M. J. S. Garzaran, D. Padua, K. Pingali, and P. Stodghill. Is search really necessary to generate high-performance BLAS? Proceedings of the IEEE, 93:358--386, 2005.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Operational analysis
      D.4.m Miscellaneous

General Terms:
Design, Management, Performance, Theory