Per-thread cycle accounting in SMT processors

ABSTRACT

This paper proposes a cycle accounting architecture for Simultaneous Multithreading (SMT) processors that estimates the execution times for each of the threads had they been executed alone, while they are running simultaneously on the SMT processor. This is done by accounting each cycle to either a base, miss event or waiting cycle component during multi-threaded execution. Single-threaded alone execution time is then estimated as the sum of the base and miss event components; the waiting cycle component represents the lost cycle count due to SMT execution. The cycle accounting architecture incurs reasonable hardware cost (around 1KB of storage) and estimates single-threaded performance with average prediction errors around 7.2% for two-program workloads and 11.7% for four-program workloads.

The cycle accounting architecture has several important applications to system software and its interaction with SMT hardware. For one, the estimated single-thread alone execution time provides an accurate picture to system software of the actually consumed processor cycles per thread. The alone execution time instead of the total execution time (timeslice) may make system software scheduling policies more effective. Second, a new class of thread-progress aware SMT fetch policies based on per-thread progress indicators enable system software level priorities to be enforced at the hardware level.

REFERENCES

• 1: Carlos Boneti , Francisco J. Cazorla , Roberto Gioiosa , Alper Buyuktosunoglu , Chen-Yong Cher , Mateo Valero, Software-Controlled Priority Characterization of POWER5 Processor, Proceedings of the 35th International Symposium on Computer Architecture, p.415-426, June 21-25, 2008
• 2: Francisco J. Cazorla , Peter M. W. Knijnenburg , Rizos Sakellariou , Enrique Fernandez , Alex Ramirez , Mateo Valero, Predictable Performance in SMT Processors: Synergy between the OS and SMTs, IEEE Transactions on Computers, v.55 n.7, p.785-799, July 2006 [doi>10.1109/TC.2006.108]
• 3: Francisco J. Cazorla , Alex Ramirez , Mateo Valero , Enrique Fernandez, Dynamically Controlled Resource Allocation in SMT Processors, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.171-182, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.17]
• 4: Francisco J. Cazorla , Alex Ramirez , Mateo Valero , Peter M. W. Knijnenburg , Rizos Sakellariou , Enrique Fernández, QoS for High-Performance SMT Processors in Embedded Systems, IEEE Micro, v.24 n.4, p.24-31, July 2004 [doi>10.1109/MM.2004.37]
• 5: Seungryul Choi , Donald Yeung, Learning-Based SMT Processor Resource Distribution via Hill-Climbing, Proceedings of the 33rd annual international symposium on Computer Architecture, p.239-251, June 17-21, 2006
• 6: Yuan Chou , Brian Fahs , Santosh Abraham, Microarchitecture Optimizations for Exploiting Memory-Level Parallelism, Proceedings of the 31st annual international symposium on Computer architecture, p.76, June 19-23, 2004, München, Germany
• 7: E. Cota=Robles. Priority Based Simultaneous Multi-Threading, Dec. 2003. United States Patent No. 6,658,447 B2.
• 8: 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
• 9: J. Emer. EV8: The post-ultimate alpha. Keynote presentation at PACT, Sept. 2001.
• 10: Stijn Everman , Lieven Eeckhout, A Memory-Level Parallelism Aware Fetch Policy for SMT Processors, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.240-249, February 10-14, 2007 [doi>10.1109/HPCA.2007.346201]
• 11: Stijn Eyerman , Lieven Eeckhout, System-Level Performance Metrics for Multiprogram Workloads, IEEE Micro, v.28 n.3, p.42-53, May 2008 [doi>10.1109/MM.2008.44]
• 12: Stijn Eyerman , Lieven Eeckhout , Tejas Karkhanis , James E. Smith, A performance counter architecture for computing accurate CPI components, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 13: A. Fedorova, M. Seltzer, and M. D. Smith. A non-work-conserving operating system scheduler for SMT processors. In WIOSCA, in conjunction with ISCA, June 2006.
• 14: Brian A. Fields , Rastislav Bodik , Mark D. Hill , Chris J. Newburn, Interaction cost and shotgun profiling, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.3, p.272-304, September 2004 [doi>10.1145/1022969.1022971]
• 15: Ron Gabor , Shlomo Weiss , Avi Mendelson, Fairness enforcement in switch on event multithreading, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.3, p.15-es, September 2007 [doi>10.1145/1275937.1275939]
• 16: Rohit Jain , Christopher J. Hughes , Sarita V. Adve, Soft Real- Time Scheduling on Simultaneous Multithreaded Processors, Proceedings of the 23rd IEEE Real-Time Systems Symposium, p.134, December 03-05, 2002
• 17: Tejas S. Karkhanis , James E. Smith, A First-Order Superscalar Processor Model, Proceedings of the 31st annual international symposium on Computer architecture, p.338, June 19-23, 2004, München, Germany
• 18: K. Luo, J. Gummaraju, and M. Franklin. Balancing throughput and fairness in SMT processors. In ISPASS, pages 164--171, Nov. 2001.
• 19: A. Mericas. Performance monitoring on the POWER5 microprocessor. In L. K. John and L. Eeckhout, editors, Performance Evaluation and Benchmarking, pages 247--266. CRC Press, 2006.
• 20: Moinuddin K. Qureshi , Daniel N. Lynch , Onur Mutlu , Yale N. Patt, A Case for MLP-Aware Cache Replacement, Proceedings of the 33rd annual international symposium on Computer Architecture, p.167-178, June 17-21, 2006
• 21: Steven E. Raasch , Steven K. Reinhardt, The Impact of Resource Partitioning on SMT Processors, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.15, September 27-October 01, 2003
• 22: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 23: 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
• 24: 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
• 25: William Stallings, Operating systems (3rd ed.): internals and design principles, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 26: D. Tullsen. Simulation and modeling of a simultaneous multithreading processor. In Proceedings of the 22nd Annual Computer Measurement Group Conference, Dec. 1996.
• 27: Dean M. Tullsen , Jeffery A. Brown, Handling long-latency loads in a simultaneous multithreading processor, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 28: Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, Proceedings of the 23rd annual international symposium on Computer architecture, p.191-202, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 29: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Design, Experimentation, Performance

Keywords:
cycle accounting, simultaneous multithreading (smt), thread-progress aware fetch policy