Accurate branch prediction for short threads

ABSTRACT

Multi-core processors, with low communication costs and high availability of execution cores, will increase the use of execution and compilation models that use short threads to expose parallelism. Current branch predictors seek to incorporate large amounts of control flow history to maximize accuracy. However, when that history is absent the predictor fails to work as intended. Thus, modern predictors are almost useless for threads below a certain length.

Using a Speculative Multithreaded (SpMT) architecture as an example of a system which generates shorter threads, this work examines techniques to improve branch prediction accuracy when a new thread begins to execute on a different core. This paper proposes a minor change to the branch predictor that gives virtually the same performance on short threads as an idealized predictor that incorporates unknowable pre-history of a spawned speculative thread. At the same time, strong performance on long threads is preserved. The proposed technique sets the global history register of the spawned thread to the initial value of the program counter. This novel and simple design reduces branch mispredicts by 29% and provides as much as a 13% IPC improvement on selected SPEC2000 benchmarks.

REFERENCES

• 1: Haitham Akkary , Michael A. Driscoll, A dynamic multithreading processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.226-236, November 1998, Dallas, Texas, United States
• 2: Murali Annavaram , Ed Grochowski , John Shen, Mitigating Amdahl's Law through EPI Throttling, Proceedings of the 32nd annual international symposium on Computer Architecture, p.298-309, June 04-08, 2005
• 3: Pedro Chaparro , Jose Gonzalez , Antonio Gonzalez, Thermal-Aware Clustered Microarchitectures, Proceedings of the IEEE International Conference on Computer Design, p.48-53, October 11-13, 2004
• 4: Robert S. Chappell , Jared Stark , Sangwook P. Kim , Steven K. Reinhardt , Yale N. Patt, Simultaneous subordinate microthreading (SSMT), Proceedings of the 26th annual international symposium on Computer architecture, p.186-195, May 01-04, 1999, Atlanta, Georgia, United States
• 5: I-Cheng K. Chen , John T. Coffey , Trevor N. Mudge, Analysis of branch prediction via data compression, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.128-137, October 01-04, 1996, Cambridge, Massachusetts, United States
• 6: J. Chung, H. Chafi, C. Minh, A. McDonald, B. Carlstrom, C. Kozyrakis, and K. Olukotun. The common case transactional behavior of multithreaded programs. In Sixth International Symposium on High-Performance Computer Architecture, pages 266--277, Feb. 2006.
• 7: 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
• 8: Jamison D. Collins , Hong Wang , Dean M. Tullsen , Christopher Hughes , Yong-Fong Lee , Dan Lavery , John P. Shen, Speculative precomputation: long-range prefetching of delinquent loads, Proceedings of the 28th annual international symposium on Computer architecture, p.14-25, June 30-July 04, 2001, Göteborg, Sweden
• 9: M. de Alba and D. Kaeli. Path-based hardware loop prediction. In 4th International Conference on Control, Virtual Instrumentation and Digital Systems, August 2002.
• 10: Jack B. Dennis , David P. Misunas, A preliminary architecture for a basic data-flow processor, Proceedings of the 2nd annual symposium on Computer architecture, p.126-132, January 20-22, 1975
• 11: A. N. Eden , T. Mudge, The YAGS branch prediction scheme, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.69-77, November 1998, Dallas, Texas, United States
• 12: Jayanth Gummaraju , Manoj Franklin, Branch Prediction in Multi-Threaded Processors, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.179, October 15-19, 2000
• 13: Lance Hammond , Brian D. Carlstrom , Vicky Wong , Ben Hertzberg , Mike Chen , Christos Kozyrakis , Kunle Olukotun, Programming with transactional coherence and consistency (TCC), Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 14: S. Hily , A. Seznec, Branch Prediction and Simultaneous Multithreading, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.169, October 20-23, 1996
• 15: Herbert H. J. Hum , Olivier Maquelin , Kevin B. Theobald , Xinmin Tian , Guang R. Gao , Laurie J. Hendren, A study of the EARTH-MANNA multithreaded system, International Journal of Parallel Programming, v.24 n.4, p.319-348, Aug. 1996
• 16: Daniel A. Jiménez, Fast Path-Based Neural Branch Prediction, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.243, December 03-05, 2003
• 17: Daniel A. Jiménez , Calvin Lin, Neural methods for dynamic branch prediction, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.369-397, November 2002 [doi>10.1145/571637.571639]
• 18: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465 ]
• 19: Rakesh Kumar , Keith I. Farkas , Norman P. Jouppi , Parthasarathy Ranganathan , Dean M. Tullsen, Single-ISA Heterogeneous Multi-Core Architectures: The Potential for Processor Power Reduction, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.81, December 03-05, 2003
• 20: Rakesh Kumar , Norman P. Jouppi , Dean M. Tullsen, Conjoined-Core Chip Multiprocessing, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.195-206, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.12]
• 21: Costas Kyriacou , Paraskevas Evripidou , Pedro Trancoso, Data-Driven Multithreading Using Conventional Microprocessors, IEEE Transactions on Parallel and Distributed Systems, v.17 n.10, p.1176-1188, October 2006 [doi>10.1109/TPDS.2006.136]
• 22: P. Marcuello. Speculative multithreaded processors, Ph. D. Thesis, Universitat Politecnica de Catalunya. 2003.
• 23: 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
• 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: 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
• 26: S. McFarling. Combining branch predictors. DEC WRL Technical Note TN-36, 1993.
• 27: Pierre Michaud , André Seznec , Richard Uhlig, Trading conflict and capacity aliasing in conditional branch predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.292-303, June 01-04, 1997, Denver, Colorado, United States
• 28: 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]
• 29: Guilherme Dal Pizzol , Philippe O. A. Navaux, Branch Prediction Topologies for SMT Architectures, Proceedings of the 17th International Symposium on Computer Architecture on High Performance Computing, p.118-125, October 24-27, 2005 [doi>10.1109/CAHPC.2005.16]
• 30: 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]
• 31: Zach Purser , Karthik Sundaramoorthy , Eric Rotenberg, A study of slipstream processors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.269-280, December 2000, Monterey, California, United States [doi>10.1145/360128.360155]
• 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: S. Sakai , y. Yamaguchi , K. Hiraki , Y. Kodama , T. Yuba, An architecture of a dataflow single chip processor, Proceedings of the 16th annual international symposium on Computer architecture, p.46-53, April 1989, Jerusalem, Israel
• 34: Andre Seznec, Analysis of the O-GEometric History Length Branch Predictor, Proceedings of the 32nd annual international symposium on Computer Architecture, p.394-405, June 04-08, 2005
• 35: A. Seznec. The L-TAGE branch predictor. In Journal of Instruction-Level Parallelism, vol. 9, May 2007.
• 36: André Seznec , Stephen Felix , Venkata Krishnan , Yiannakis Sazeides, Design tradeoffs for the Alpha EV8 conditional branch predictor, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 37: A. Seznec and P. Michaud. De-aliashed hybrid branch predictors. Technical Report RR-3618, Inria, Feb. 1999.
• 38: 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
• 39: James E. Smith, A study of branch prediction strategies, 25 years of the international symposia on Computer architecture (selected papers), p.202-215, June 27-July 02, 1998, Barcelona, Spain [doi>10.1145/285930.285980]
• 40: 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
• 41: Eric Sprangle , Robert S. Chappell , Mitch Alsup , Yale N. Patt, The agree predictor: a mechanism for reducing negative branch history interference, Proceedings of the 24th annual international symposium on Computer architecture, p.284-291, June 01-04, 1997, Denver, Colorado, United States
• 42: 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
• 43: 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
• 44: 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
• 45: 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 ]
• 46: D. Tullsen. Simulation and modeling of a simultaneous multithreading processor. In In 22nd Annual Computer Measurement Group Conference, December 1996.
• 47: T. N. Vijaykumar , Sridhar Gopal , James E. Smith , Gurindar Sohi, Speculative Versioning Cache, IEEE Transactions on Parallel and Distributed Systems, v.12 n.12, p.1305-1317, December 2001 [doi>10.1109/71.970565 ]
• 48: Christoph von Praun , Luis Ceze , Calin Caşcaval, Implicit parallelism with ordered transactions, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229443]
• 49: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States
• 50: Weifeng Zhang , Brad Calder , Dean M. Tullsen, An Event-Driven Multithreaded Dynamic Optimization Framework, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.87-98, September 17-21, 2005 [doi>10.1109/PACT.2005.7]
• 51: Weifeng Zhang , Brad Calder , Dean M. Tullsen, A Self-Repairing Prefetcher in an Event-Driven Dynamic Optimization Framework, Proceedings of the International Symposium on Code Generation and Optimization, p.50-64, March 26-29, 2006 [doi>10.1109/CGO.2006.4]
• 52: Craig Zilles , Gurindar Sohi, Execution-based prediction using speculative slices, ACM SIGARCH Computer Architecture News, v.29 n.2, p.2-13, May 2001

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
branch prediction, chip multiprocessors