Towards a Systematic, Pragmatic and Architecture-Aware Program Optimization Process for Complex Processors

ABSTRACT

Because processor architectures are increasingly complex, it is increasingly difficult to embed accurate machine models within compilers. As a result, compiler efficiency tends to decrease. Currently, the trend is on top-down approaches: static compilers are progressively augmented with information from the architecture as in profile-based, iterative or dynamic compilation techniques. However, for the moment, fairly elementary architectural information is used. In this article, we adopt a bottom-up approach to the architecture complexity issue: we assume we know everything about the behavior of the program on the architecture. We present a manual but systematic process for optimizing a program on a complex processor architecture using extensive dynamic analysis, and we find that a small set of run-time information is sufficient to drive anefficient process. We have experimentally observed on an Alpha 21264 that this approach can yield significant performance improvement on Spec benchmarks, beyond peak Spec. We are currently using this approach for optimizing customer applications.

REFERENCES

• 1: [1] C. Bastoul, A. Cohen, S. Girbal, S. Sharma, and O. Temam. Putting polyhedral loop transformation to work. In 10th International Workshop on Languages and Compilers for Parallel Computing (LCPC), October 2003.
• 2: 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]
• 3: Jeffrey Dean , James E. Hicks , Carl A. Waldspurger , William E. Weihl , George Chrysos, ProfileMe: hardware support for instruction-level profiling on out-of-order processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.292-302, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 4: [4] G. Fursin, M. O'Boyle, and P. Knijnenburg. Evaluating iterative compilation. In 11th Workshop on Languages and Compilers for Parallel Computing, LNCS, Washington DC, July 2002. Springer-Verlag.
• 5: Sylvain Girbal , Gilles Mouchard , Albert Cohen , Olivier Temam, DiST: a simple, reliable and scalable method to significantly reduce processor architecture simulation time, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 6: [6] Intel Itanium2 processor reference manual for software development and optimization. http: //developer.intel.com/design/itatium2/manuals.
• 7: Thomas Kistler , Michael Franz, Continuous program optimization: A case study, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.4, p.500-548, July 2003 [doi>10.1145/778559.778562]
• 8: [8] T. Kisuki, P. Knijnenburg, M. O'Boyle, and H. Wijshoff. Iterative compilation in program optimization. In Proc. CPC'10 (Compilers for Parallel Computers), pages 35-44, 2000.
• 9: Kathryn S. McKinley , Olivier Temam, A quantitative analysis of loop nest locality, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.94-104, October 01-04, 1996, Cambridge, Massachusetts, United States
• 10: [10] Oprofile project. http://oprofile.sourceforge.net.
• 11: [11] Open research compiler. http://ipf-orc.sourceforge.net.
• 12: 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
• 13: Erez Perelman , Greg Hamerly , Michael Van Biesbrouck , Timothy Sherwood , Brad Calder, Using SimPoint for accurate and efficient simulation, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 14: [14] Perfmon project. http://www.hpl.hp.com/research/linux/perfmon.
• 15: [15] Standard performance evaluation corporation. http://www.spec.org.
• 16: Mark Stephenson , Saman Amarasinghe , Martin Martin , Una-May O'Reilly, Meta optimization: improving compiler heuristics with machine learning, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 17: [17] Intel VTune performance analysers. http://www.intel.com/software/products/vtune.
• 18: Roland E. Wunderlich , Thomas F. Wenisch , Babak Falsafi , James C. Hoe, SMARTS: accelerating microarchitecture simulation via rigorous statistical sampling, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 19: Kamen Yotov , Xiaoming Li , Gang Ren , Michael Cibulskis , Gerald DeJong , Maria Garzaran , David Padua , Keshav Pingali , Paul Stodghill , Peng Wu, A comparison of empirical and model-driven optimization, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA