On the potential of latency tolerant execution in speculative multithreading

ABSTRACT

High performance superscalar architectures used to exploit instruction level parallelism in single-thread applications have become too complex and too power hungry for the many-core processors era. We propose a new architecture that uses multiple latency-tolerant in-order cores to improve single-thread performance, without requiring complex out-of-order execution hardware or large, power hungry register files and instruction buffers. Using simple cores to provide improved single-thread performance for conventional difficult-to-parallelize applications allows designers to place many more of these cores on the same die. Consequently, emerging highly parallel applications can take full advantage of the many-core parallel hardware without sacrificing performance of inherently serial applications.

Our architecture splits single-thread program execution into disjoint control and data threads that execute concurrently on multiple latency-tolerant in-order cores. Hence we call this style of execution Disjoint Out-of-Order Execution (DOE). DOE is a novel implementation of Speculative Multithreading (SpMT). It uses latency tolerance to overcome performance issues of SpMT caused by load imbalance and inter-thread data communication delays.

Using control independence prediction hardware to spawn threads, we simulate the potential performance of DOE on a subset of Spec2000 integer benchmarks under various parallelism scenarios and for DOE configurations of 2, 4, 6 and 8 single-issue latency tolerant cores.

REFERENCES

• 1: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 2: H. Akkary and M. Driscoll. A Dynamic Multithreading Processor. MICRO-31, November 1998.
• 3: Haitham Akkary , Ravi Rajwar , Srikanth T. Srinivasan, Checkpoint Processing and Recovery: Towards Scalable Large Instruction Window Processors, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.423, December 03-05, 2003
• 4: Ahmed S. Al-Zawawi , Vimal K. Reddy , Eric Rotenberg , Haitham H. Akkary, Transparent control independence (TCI), Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 5: Marcelo Cintra , José F. Martínez , Josep Torrellas, Architectural support for scalable speculative parallelization in shared-memory multiprocessors, Proceedings of the 27th annual international symposium on Computer architecture, p.13-24, June 2000, Vancouver, British Columbia, Canada
• 6: Lucian Codrescu , D. Scott Wills, On Dynamic Speculative Thread Partitioning and the MEM-Slicing Algorithm, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.40, October 12-16, 1999
• 7: Lucian Codrescu , D. Scott Wills , James Meindl, Architecture of the Atlas Chip-Multiprocessor: Dynamically Parallelizing Irregular Applications, IEEE Transactions on Computers, v.50 n.1, p.67-82, January 2001 [doi>10.1109/12.902753]
• 8: Jamison D. Collins , Dean M. Tullsen , Hong Wang, Control Flow Optimization Via Dynamic Reconvergence Prediction, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.129-140, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.13]
• 9: A. Cristal, M. Valero, J. Llosa, and A. Gonzalez. Large Virtual ROBs by Processor Checkpointing. Tech. Report, UPC-DAC-2002-39, Department of Computer Science, Barcelona, Spain, July 2002.
• 10: Adrian Cristal , Oliverio J. Santana , Francisco Cazorla , Marco Galluzzi , Tanausu Ramirez , Miquel Pericas , Mateo Valero, Kilo-Instruction Processors: Overcoming the Memory Wall, IEEE Micro, v.25 n.3, p.48-57, May 2005 [doi>10.1109/MM.2005.53]
• 11: Adrian Cristal , Daniel Ortega , Josep Llosa , Mateo Valero, Out-of-Order Commit Processors, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.48, February 14-18, 2004 [doi>10.1109/HPCA.2004.10008]
• 12: Manoj Franklin , Gurindar S. Sohi, The expandable split window paradigm for exploiting fine-grain parallelsim, Proceedings of the 19th annual international symposium on Computer architecture, p.58-67, May 19-21, 1992, Queensland, Australia
• 13: Manoj Franklin, The multiscalar architecture, University of Wisconsin at Madison, Madison, WI, 1993
• 14: Amit Gandhi , Haitham Akkary , Ravi Rajwar , Srikanth T. Srinivasan , Konrad Lai, Scalable Load and Store Processing in Latency Tolerant Processors, Proceedings of the 32nd annual international symposium on Computer Architecture, p.446-457, June 04-08, 2005
• 15: J. Held, J. Bautista, and S. Koehl. From a Few Cores to Many: A Tera-Scale Computing Research Review. Intel Corporation, Research White Paper. http://download.intel.com/research/platform/terascale/terascale_overview_paper.pdf.
• 16: Quinn Jacobson , Steve Bennett , Nikhil Sharma , James E. Smith, Control Flow Speculation in Multiscalar Processors, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.218, February 01-05, 1997
• 17: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• 18: M. S. Lam and R. P. Wilson. Limits of Control Flow on Parallelism. ISCA-19, May 1992.
• 19: Alvin R. Lebeck , Jinson Koppanalil , Tong Li , Jaidev Patwardhan , Eric Rotenberg, A large, fast instruction window for tolerating cache misses, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 20: P. Marcuello. Speculative Multithreaded Processors, Ph.D. Dissertation, Universitat Politecnica de Catalunya, 2003.
• 21: Pedro Marcuello , Antonio González, Thread-Spawning Schemes for Speculative Multithreading, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.55, February 02-06, 2002
• 22: A Quantitative Assessment of Thread-Level Speculation Techniques, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.595, May 01-05, 2000
• 23: Pedro Marcuello , Antonio González , Jordi Tubella, Speculative multithreaded processors, Proceedings of the 12th international conference on Supercomputing, p.77-84, July 1998, Melbourne, Australia [doi>10.1145/277830.277850]
• 24: Pedro Marcuello , Jordi Tubella , Antonio González, Value prediction for speculative multithreaded architectures, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.230-236, November 16-18, 1999, Haifa, Israel
• 25: José F. Martínez , Jose Renau , Michael C. Huang , Milos Prvulovic , Josep Torrellas, Cherry: checkpointed early resource recycling in out-of-order microprocessors, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 26: Andreas Moshovos , Scott E. Breach , T. N. Vijaykumar , Gurindar S. Sohi, Dynamic speculation and synchronization of data dependences, Proceedings of the 24th annual international symposium on Computer architecture, p.181-193, June 01-04, 1997, Denver, Colorado, United States
• 27: S. Nekkalapu, H. Akkary, K. Jothi, R. Retnamma, and X. Song. A Simple Latency Tolerant Processor. In Proceedings of the IEEE 26^th International Conference on Computer Design, October 2008.
• 28: A. Nicolau , J. A. Fisher, Measuring the Parallelism Available for Very Long Instruction Word Architectures, IEEE Transactions on Computers, v.33 n.11, p.968-976, November 1984 [doi>10.1109/TC.1984.1676371]
• 29: Kunle Olukotun , Lance Hammond , Mark Willey, Improving the performance of speculatively parallel applications on the Hydra CMP, Proceedings of the 13th international conference on Supercomputing, p.21-30, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305155]
• 30: David B. Papworth, Tuning the Pentium Pro Microarchitecture, IEEE Micro, v.16 n.2, p.8-15, April 1996 [doi>10.1109/40.491458]
• 31: Manohar K. Prabhu , Kunle Olukotun, Exposing speculative thread parallelism in SPEC2000, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065964]
• 32: Carlos García Quiñones , Carlos Madriles , Jesús Sánchez , Pedro Marcuello , Antonio González , Dean M. Tullsen, Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 33: E. M. Riseman , C. C. Foster, The Inhibition of Potential Parallelism by Conditional Jumps, IEEE Transactions on Computers, v.21 n.12, p.1405-1411, December 1972 [doi>10.1109/T-C.1972.223514]
• 34: Eric Rotenberg , Quinn Jacobson , Yiannakis Sazeides , Jim Smith, Trace processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.138-148, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 35: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 36: Srikanth T. Srinivasan , Haitham Akkary , Tom Holman , Konrad Lai, A Minimal Dual-Core Speculative Multi-Threading Architecture, Proceedings of the IEEE International Conference on Computer Design, p.360-367, October 11-13, 2004
• 37: Srikanth T. Srinivasan , Ravi Rajwar , Haitham Akkary , Amit Gandhi , Mike Upton, Continual flow pipelines, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 38: J. Greggory Steffan , Christopher B. Colohan , Antonia Zhai , Todd C. Mowry, A scalable approach to thread-level speculation, Proceedings of the 27th annual international symposium on Computer architecture, p.1-12, June 2000, Vancouver, British Columbia, Canada
• 39: J. Steffan , T Mowry, The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.2, January 31-February 04, 1998
• 40: Jenn-Yaun Tsai , Jian Huang , Christoffer Amlo , David J. Lilja , Pen-Chung Yew, The Superthreaded Processor Architecture, IEEE Transactions on Computers, v.48 n.9, p.881-902, September 1999 [doi>10.1109/12.795219]
• 41: J.-Y. Tsai , Z. Jiang , E. Ness , P.-C. Yew, Performance Study of a Concurrent Multithreaded Processor, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.24, January 31-February 04, 1998
• 42: T. N. Vijaykumar , Gurindar S. Sohi, Task selection for a multiscalar processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.81-92, November 1998, Dallas, Texas, United States
• 43: X86 Cycle Accurate Processor Simulation Design Infrastructure. http://www.ptlsim.org/
• 44: Antonia Zhai , Christopher B. Colohan , J. Gregory Steffan , Todd C. Mowry, Compiler optimization of scalar value communication between speculative threads, ACM SIGPLAN Notices, v.37 n.10, October 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

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

General Terms:
Design, Performance

Keywords:
chip multiprocessors, latency-tolerant architectures, many-core processors, speculative multithreading