Dynamic run-time architecture techniques for enabling continuous optimization

ABSTRACT

Future computer systems will integrate tens of multithreaded processor cores on a single chip die, resulting in hundreds of concurrent program threads sharing system resources. These designs will be the cornerstone of improving throughput in high-performance computing and server environments. However, to date, appropriate systems software (operating system, run-time system, and compiler) technologies for these emerging machines have not been adequately explored. Future processors will require sophisticated hardware monitoring units to continuously feed back resource utilization information to allow the operating system to make optimal thread co-scheduling decisions and also to software that continuously optimizes the program itselfNevertheless, in order to continually and automatically adapt systems resources to program behaviors and application needs, specific run-time information must be collected to adequately enable dynamic code optimization and operating system scheduling. Generally, run-time optimization is limited by the time required to collect profiles, the time required to perform optimization, and the inherent benefits of any optimization or decisions. Initial techniques for effectively utilizing run-time information for dynamic optimization and informed thread scheduling in future multithreaded architectures are presented

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: Apple Computer, Inc. http://developer.apple.com/tools/performance/.
• 3: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 4: Thomas Ball , Peter Mataga , Mooly Sagiv, Edge profiling versus path profiling: the showdown, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.134-148, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268958]
• 5: Michael D. Bond , Kathryn S. McKinley, Practical Path Profiling for Dynamic Optimizers, Proceedings of the international symposium on Code generation and optimization, p.205-216, March 20-23, 2005 [doi>10.1109/CGO.2005.28]
• 6: J. M. Borkenhagen, R. J. Eickemeyer, R. N. Kalla, and S. R. Kunkel. A multithreaded powerpc processor for commercial servers. IBM Journal of Research and Development, 44(6):885--898, November 2000.
• 7: Howard Chen , Wei-Chung Hsu , Jiwei Lu , Pen-Chung Yew , Dong-Yuan Chen, Dynamic trace selection using performance monitoring hardware sampling, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 8: Thomas M. Conte , Burzin A. Patel , Kishore N. Menezes , J. Stan Cox, Hardware-based profiling: an effective technique for profile-driven optimization, International Journal of Parallel Programming, v.24 n.2, p.187-206, April 1996
• 9: A. Eustace and A. Srivastava. ATOM: A flexible interface for building high performance program analysis tools. In Proceedings of the Winter 1995 USENIX Conference, January 1995.
• 10: Hewlett-Packard Development Company. perfmon project http://www.hpl.hp.com/research/linux/perfmon/.
• 11: P. P. Chang , W.-W. Hwu, Inline function expansion for compiling C programs, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.246-257, June 19-23, 1989, Portland, Oregon, United States
• 12: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• 13: Intel Corporation. Special issue on intel hyperthreading in pentium-4 processors. Intel Technology Journal, 1(1), January 2002.
• 14: Intel Corporation. Intel Itanium 2 processor reference manual: For software development and optimization. May 2004.
• 15: Canturk Isci , Margaret Martonosi, Runtime Power Monitoring in High-End Processors: Methodology and Empirical Data, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.93, December 03-05, 2003
• 16: Thomas Kistler , Michael Franz, Continuous Program Optimization: Design and Evaluation, IEEE Transactions on Computers, v.50 n.6, p.549-566, June 2001 [doi>10.1109/12.931893]
• 17: Venkata Krishnan , Josep Torrellas, A Chip-Multiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers, v.48 n.9, p.866-880, September 1999 [doi>10.1109/12.795218]
• 18: J. Lu, H. Chen, P.-C. Yew, and W.-C. Hsu. Design and implementation of a lightweight dynamic optimization system. In Journal of Instruction-Level Parallelism 6(2004), pages 1--24, April 2004.
• 19: D. T. Marr, F. Binns, D. L. Hill, G. Hinton, D. A. Koufaty, J. A. Miller, and M. Upton. Hyper-threading technology architecture and microarchitecture. Intel Technology Journal, 6(1):4--15, Feb. 2002.
• 20: Matthew C. Merten , Andrew R. Trick , Erik M. Nystrom , Ronald D. Barnes , Wen-mei W. Hmu, A hardware mechanism for dynamic extraction and relayout of program hot spots, Proceedings of the 27th annual international symposium on Computer architecture, p.59-70, June 2000, Vancouver, British Columbia, Canada
• 21: OpenIMPACT Research Compiler. http://www.gelato.uiuc.edu/.
• 22: 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
• 23: R Development Core Team. R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria, 2004. 3-900051-07-0.
• 24: A. Settle, J. Kihm, , A. Janiszewski, and D. Connors. Performance analysis of simultaneous multithreading in a powerpc-based processor. In Proceedings of the International Conference on Parallel Architectures and Compiler Techniques, October 2004.
• 25: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 26: A. Snavely and L. Carter. Symbiotic jobscheduling on the tera mta. In Workshop on Multi-Threaded Execution Architecture and Compilers, Jan 2000.
• 27: Allan Snavely , Dean M. Tullsen, Symbiotic jobscheduling for a simultaneous multithreaded processor, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.234-244, November 2000, Cambridge, Massachusetts, United States
• 28: Allan Snavely , Dean M. Tullsen , Geoff Voelker, Symbiotic jobscheduling with priorities for a simultaneous multithreading processor, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 29: Brinkley Sprunt, Pentium 4 Performance-Monitoring Features, IEEE Micro, v.22 n.4, p.72-82, July 2002 [doi>10.1109/MM.2002.1028478]
• 30: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 31: D. M. Tullsen, J. L. Lo, S. J. Eggers, and H. M. Levy. Supporting fine-grained synchronization on a simultaneous multithreading processor. In International Symposium on Architectural Support for Programming Languages and Operating Systems, pages 54--58, 2000.
• 32: David W. Wall, Predicting program behavior using real or estimated profiles, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.59-70, June 24-28, 1991, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management

General Terms:
Design, Performance

Keywords:
multithreading, performance counters, profiling, scheduling