Adaptive execution techniques for SMT multiprocessor architectures

ABSTRACT

In simultaneous multithreading (SMT) multiprocessors, using all the available threads (logical processors) to run a parallel loop is not always beneficial due to the interference between threads and parallel execution overhead. To maximize performance in an SMT multiprocessor, finding the optimal number of threads is important. This paper presents adaptive execution techniques to find the optimal execution mode for SMT multiprocessor architectures. A compiler preprocessor generates code that, based on dynamic feedback, automatically determines at run time the optimal number of threads for each parallel loop in the application. Using 10 standard numerical applications and running them with our techniques on an Intel 4-processor Hyper-Threading Xeon SMP with 8 logical processors, our code is, on average, about 2 and 18 times faster than the original code executed on 4 and 8 logical processors, respectively.

REFERENCES

• 1: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 2: William Blume , Ramon Doallo , Rudolf Eigenmann , John Grout , Jay Hoeflinger , Thomas Lawrence , Jaejin Lee , David Padua , Yunheung Paek , Bill Pottenger , Lawrence Rauchwerger , Peng Tu, Parallel Programming with Polaris, Computer, v.29 n.12, p.78-82, December 1996 [doi>10.1109/2.546612]
• 3: John Borozan. Microsoft Windows-Based Servers and Intel Hyper-Threading Technology. Microsoft Corporation, April 2002.
• 4: Mark Byler, James Davies, Christopher Huson, Bruce Leasure, and Michael Wolfe. Multiple Version Loops. In Proceedings of the International Conference on Parallel Processing (ICPP), pages 312--318, August 1987.
• 5: Calin Cascaval , Luiz De Rose , David A. Padua , Daniel A. Reed, Compile-Time Based Performance Prediction, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.365-379, August 04-06, 1999
• 6: Robit Chandra , Leonardo Dagum , Dave Kohr , Dror Maydan , Jeff McDonald , Ramesh Menon, Parallel programming in OpenMP, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 7: Alan L. Cox , Robert J. Fowler, Adaptive cache coherency for detecting migratory shared data, Proceedings of the 20th annual international symposium on Computer architecture, p.98-108, May 16-19, 1993, San Diego, California, United States
• 8: Pedro C. Diniz , Martin C. Rinard, Dynamic feedback: an effective technique for adaptive computing, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.71-84, June 16-18, 1997, Las Vegas, Nevada, United States
• 9: Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm , Dean M. Tullsen, Simultaneous Multithreading: A Platform for Next-Generation Processors, IEEE Micro, v.17 n.5, p.12-19, September 1997 [doi>10.1109/40.621209]
• 10: R. Gupta , R. Bodik, Adaptive loop transformations for scientific programs, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.368, October 25-28, 1995
• 11: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
• 12: Intel. Intel Fortran Compiler User's Guide, 2002.
• 13: Intel. Intel Fortran Programmer's Reference Manual, 2002.
• 14: Intel. IA-32 Intel Architecture Software Developer's Manual, 2004.
• 15: Ron Kalla, Balaram Sinharoy, and Joel M. Tendler. IBM Power5 Chip: A Dual-Core Multithreaded Processor. IEEE Micro, pages 40--47, March-April 2004.
• 16: Jaejin Lee , David A. Padua, Compilation techniques for explicitly parallel programs, 1999
• 17: Jaejin Lee and H. D. K. Moonesinghe. Adaptively Increasing Performance and Scalability of Automatically Parallelized Programs. In Proceedings of the 15th Workshop on Languages and Compilers for Parallel Computing (LCPC), July 2002.
• 18: Jaeji Lee, Automatically Mapping Code on an Intelligent Memory Architecture, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.121, January 20-24, 2001
• 19: Deborah T. Marr, Frank Binns, David L. Hill, Glenn Hinton, David A. Kaufaty, J. Alan Miller, and Michael Upton. Hyper-Threading Technology Architecture and Microarchitecture. Intel Technology Journal, 6(1), February 2002.
• 20: R. L. Mattson, J. Gecsei, D. Slutz, and I. Traiger. Evaluation Techniques for Storage Hierarchies. IBM Systems Journal, 9(2):78--117, December 1970.
• 21: OpenMP Standard Board. OpenMP Fortran Interpretations, April 1999. Version 1.0.
• 22: Martin Rinard , Pedro Diniz, Eliminating synchronization bottlenecks in object-based programs using adaptive replication, Proceedings of the 13th international conference on Supercomputing, p.83-92, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305167]
• 23: Theodore H. Romer, Dennis Lee, Brian N. Bershad, and Bradley Chen. Dynamic Page Mapping Policies for Cache Conflict Resolution on Standard Hardware. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation, pages 255--266, November 1994.
• 24: Rafael H. Saavedra , Daeyeon Park, Improving the Effectiveness of Software Prefetching with Adaptive Execution, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.68, October 20-23, 1996
• 25: Michael Voss , Rudolf Eigenmann, Reducing Parallel Overheads Through Dynamic Serialization, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.88-92, April 12-16, 1999
• 26: Michael J. Voss , Rudolf Eigenmann, ADAPT: Automated De-Coupled Adaptive Program Transformation, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.163, August 21-24, 2000
• 27: Michael J. Voss , Rudolf Eigemann, High-level adaptive program optimization with ADAPT, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.93-102, June 2001, Snowbird, Utah, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Performance

Keywords:
adaptive execution, compilers, performance counters, performance estimation, simultaneous multi-threading