Code layout optimizations for transaction processing workloads

ABSTRACT

Commercial applications such as databases and Web servers constitute the most important market segment for high-performance servers. Among these applications, on-line transaction processing (OLTP) workloads provide a challenging set of requirements for system designs since they often exhibit inefficient executions dominated by a large memory stall component. This behavior arises from large instruction and data footprints and high communication miss rates. A number of recent studies have characterized the behavior of commercial workloads and proposed architectural features to improve their performance. However, there has been little research on the impact of software and compiler-level optimizations for improving the behavior of such workloads.

This paper provides a detailed study of profile-driven compiler optimizations to improve the code layout in commercial workloads with large instruction footprints. Our compiler algorithms are implemented in the context of Spike, an executable optimizer for the Alpha architecture. Our experiments use the Oracle commercial database engine running an OLTP workload, with results generated using both full system simulations and actual runs on Alpha multiprocessors. Our results show that code layout optimizations can provide a major improvement in the instruction cache behavior, providing a 55% to 65% reduction in the application misses for 64-128K caches. Our analysis shows that this improvement primarily arises from longer sequences of consecutively executed instructions and more reuse of cache lines before they are replaced. We also show that the majority of application instruction misses are caused by self-interference. However, code layout optimizations significantly reduce the amount of self-interference, thus elevating the relative importance of interference with operating system code. Finally, we show that better code layout can also provide substantial improvements in the behavior of other memory system components such as the instruction TLB and the unified second-level cache. The overall performance impact of our code layout optimizations is an improvement of 1.33 times in the execution time of our workload.

REFERENCES

• 1: Jennifer M. Anderson , Lance M. Berc , Jeffrey Dean , Sanjay Ghemawat , Monika R. Henzinger , Shun-Tak A. Leung , Richard L. Sites , Mark T. Vandevoorde , Carl A. Waldspurger , William E. Weihl, Continuous profiling: where have all the cycles gone?, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.1-14, October 05-08, 1997, Saint Malo, France
• 2: Luiz André Barroso , Kourosh Gharachorloo , Edouard Bugnion, Memory system characterization of commercial workloads, Proceedings of the 25th annual international symposium on Computer architecture, p.3-14, June 27-July 02, 1998, Barcelona, Spain
• 3: Luiz André Barroso , Kourosh Gharachorloo , Robert McNamara , Andreas Nowatzyk , Shaz Qadeer , Barton Sano , Scott Smith , Robert Stets , Ben Verghese, Piranha: a scalable architecture based on single-chip multiprocessing, Proceedings of the 27th annual international symposium on Computer architecture, p.282-293, June 2000, Vancouver, British Columbia, Canada
• 4: L. A. Barroso, K. Gharachorloo, A. Nowatzyk, and B. Verghese. Impact of Chip-Level Integration on Performance of OLTP Workloads. In Proceedings of the 6th International Symposium on High Performance Comp,tter Architecture, January 2000.
• 5: Robert S. Cohn , David W. Goodwin , P. Geoffrey Lowney, Optimizing alpha executables on Windows NT with spike, Digital Technical Journal, v.9 n.4, p.3-20, April 1998
• 6: Z. Cvetanovic , D. Bhandarkar, Characterization of alpha AXP performance using TP and SPEC workloads, Proceedings of the 21ST annual international symposium on Computer architecture, p.60-70, April 18-21, 1994, Chicago, Illinois, United States
• 7: Z. Cvetanovic and D. D. Donaldson. AlphaServer 4100 performance characterization. Digital Technical Journal, 8(4):3-20, 1996.
• 8: Domenico Ferrari, Improving locality by critical working sets, Communications of the ACM, v.17 n.11, p.614-620, Nov. 1974 [doi>10.1145/361179.361195]
• 9: Nikolas Gloy , Trevor Blackwell , Michael D. Smith , Brad Calder, Procedure placement using temporal ordering information, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.303-313, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 10: D. J. Hartfield and J. Gerald. Program restructuring for virtual memory. IBM Systems Journal, 2:169-192, 1971.
• 11: S. J. Hartley, Compile-Time Program Restructuring in Multiprogrammed Virtual Memory Systems, IEEE Transactions on Software Engineering, v.14 n.11, p.1640-1644, November 1988 [doi>10.1109/32.9051]
• 12: Amir H. Hashemi , David R. Kaeli , Brad Calder, Efficient procedure mapping using cache line coloring, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.171-182, June 16-18, 1997, Las Vegas, Nevada, United States
• 13: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• 14: J. Kalamatianos , D. Kaeli, Temporal-Based Procedure Reordering for Improved Instruction Cache Performance, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.244, January 31-February 04, 1998
• 15: Kimberly Keeton , David A. Patterson , Yong Qiang He , Roger C. Raphael , Walter E. Baker, Performance characterization of a Quad Pentium Pro SMP using OLTP workloads, Proceedings of the 25th annual international symposium on Computer architecture, p.15-26, June 27-July 02, 1998, Barcelona, Spain
• 16: Jack L. Lo , Luiz André Barroso , Susan J. Eggers , Kourosh Gharachorloo , Henry M. Levy , Sujay S. Parekh, An analysis of database workload performance on simultaneous multithreaded processors, Proceedings of the 25th annual international symposium on Computer architecture, p.39-50, June 27-July 02, 1998, Barcelona, Spain
• 17: Ann Marie Grizzaffi Maynard , Colette M. Donnelly , Bret R. Olszewski, Contrasting characteristics and cache performance of technical and multi-user commercial workloads, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.145-156, October 05-07, 1994, San Jose, California, United States
• 18: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• 19: Sharon E. Perl , Richard L. Sites, Studies of Windows NT performance using dynamic execution traces, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.169-183, October 29-November 01, 1996, Seattle, Washington, United States
• 20: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 21: Alex Ramirez , Josep Ll. Larriba-Pey , Carlos Navarro , Xavi Serrano , Mateo Valero , Josep Torrellas, Optimization of Instruction Fetch for Decision Support Workloads, Proceedings of the 1999 International Conference on Parallel Processing, p.238, September 21-24, 1999
• 22: Alex Ramírez , Josep-L. Larriba-Pey , Carlos Navarro , Josep Torrellas , Mateo Valero, Software trace cache, Proceedings of the 13th international conference on Supercomputing, p.119-126, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305178]
• 23: Parthasarathy Ranganathan , Kourosh Gharachorloo , Sarita V. Adve , Luiz André Barroso, Performance of database workloads on shared-memory systems with out-of-order processors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.307-318, October 02-07, 1998, San Jose, California, United States
• 24: Mendel Rosenblum , Edouard Bugnion , Scott Devine , Stephen A. Herrod, Using the SimOS machine simulator to study complex computer systems, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.1, p.78-103, Jan. 1997 [doi>10.1145/244804.244807]
• 25: M. Rosenblum , E. Bugnion , S. A. Herrod , E. Witchel , A. Gupta, The impact of architectural trends on operating system performance, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.285-298, December 03-06, 1995, Copper Mountain, Colorado, United States
• 26: W. J. Schmidt , R. R. Roediger , C. S. Mestad , B. Mendelson , I. Shavit-Lottem , V. Bortnikov-Sitnitsky, Profile-directed restructuring of operating system code, IBM Systems Journal, v.37 n.2, p.270-297, April 1998
• 27: A. Srivastava and D. W. Wall. A practical system for intermodule code optimization at link-time. Journal of Programming Languages, 1(1):1-18, Dec. 1992.
• 28: J. Torrellas , Chun Xia , R. Daigle, Optimizing instruction cache performance for operating system intensive workloads, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.360, January 22-25, 1995
• 29: http://www.tpc.org.
• 30: Transaction Processing Performance Council. TPC Benchmark B (Online Transaction Processing) Standard Specification, 1990.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Languages, Management, Measurement, Performance, Theory