Transparent control independence (TCI)

ABSTRACT

Superscalar architectures have been proposed that exploit control independence, reducing the performance penalty of branch mispredictions by preserving the work of future misprediction-independent instructions. The essential goal of exploiting control independence is to completely decouple future misprediction-independent instructions from deferred misprediction-dependent instructions. Current implementations fall short of this goal because they explicitly maintain program order among misprediction-independent and misprediction-dependent instructions. Explicit approaches sacrifice design efficiency and ultimately performance.

We observe it is sufficient to emulate program order. Potential misprediction-dependent instructions are singled out a priori and their unchanging source values are checkpointed. These instructions and values are set aside as a "recovery program". Checkpointed source values break the data dependencies with co-mingled misprediction-independent instructions - now long since gone from the pipeline - achieving the essential decoupling objective. When the mispredicted branch resolves, recovery is achieved by fetching the self-sufficient, condensed recovery program. Recovery is effectively transparent to the pipeline, in that speculative state is not rolled back and recovery appears as a jump to code. A coarse-grain retirement substrate permits the relaxed order between the decoupled programs. Transparent control independence (TCI) yields a highly streamlined pipeline that quickly recycles resources based on conventional speculation, enabling a large window with small cycle-critical resources, and prevents many mispredictions from disrupting this large window.

TCI achieves speedups as high as 64% (16% average) and 88% (22% average) for 4-issue and 8-issue pipelines, respectively, among 15 SPEC integer benchmarks. Factors that limit the performance of explicitly ordered approaches are quantified.

REFERENCES

• 1: Pritpal S. Ahuja , Kevin Skadron , Margaret Martonosi , Douglas W. Clark, Multipath execution: opportunities and limits, Proceedings of the 12th international conference on Supercomputing, p.101-108, July 1998, Melbourne, Australia [doi>10.1145/277830.277854]
• 2: 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
• 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: D. Burger, T. Austin, S. Bennett. Evaluating Future Microprocessors: The Simplescalar Toolset. July 1996.
• 5: Chen-Yong Cher , T. N. Vijaykumar, Skipper: a microarchitecture for exploiting control-flow independence, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 6: Yuan Chou , Jason Fung , John Paul Shen, Reducing branch misprediction penalties via dynamic control independence detection, Proceedings of the 13th international conference on Supercomputing, p.109-118, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305175]
• 7: George Z. Chrysos , Joel S. Emer, Memory dependence prediction using store sets, Proceedings of the 25th annual international symposium on Computer architecture, p.142-153, June 27-July 02, 1998, Barcelona, Spain
• 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: 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]
• 10: Amit Gandhi , Haitham Akkary , Srikanth T. Srinivasan, Reducing Branch Misprediction Penalty via Selective Branch Recovery, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.254, February 14-18, 2004 [doi>10.1109/HPCA.2004.10004]
• 11: T. Heil and J. Smith. Selective Dual Path Execution. Tech. Report, ECE Department, UW-Madison, 1996.
• 12: W.-M. W. Hwu , Y. N. Patt, Checkpoint repair for high-performance out-of-order execution machines, IEEE Transactions on Computers, v.36 n.12, p.1496-1514, Dec. 1987 [doi>10.1109/TC.1987.5009500]
• 13: Daniel A. Jiménez , Calvin Lin, Dynamic Branch Prediction with Perceptrons, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.197, January 20-24, 2001
• 14: Artur Klauser , Abhijit Paithankar , Dirk Grunwald, Selective eager execution on the PolyPath architecture, Proceedings of the 25th annual international symposium on Computer architecture, p.250-259, June 27-July 02, 1998, Barcelona, Spain
• 15: A. Klauser , T. Austin , D. Grunwald , B. Calder, Dynamic Hammock Predication for Non-Predicated Instruction Set Architectures, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.278, October 12-18, 1998
• 16: 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
• 17: Scott A. Mahlke , Richard E. Hank , James E. McCormick , David I. August , Wen-Mei W. Hwu, A comparison of full and partial predicated execution support for ILP processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.138-150, June 22-24, 1995, S. Margherita Ligure, Italy
• 18: Mayan Moudgill , Keshav Pingali , Stamatis Vassiliadis, Register renaming and dynamic speculation: an alternative approach, Proceedings of the 26th annual international symposium on Microarchitecture, p.202-213, December 01-03, 1993, Austin, Texas, United States
• 19: E. Rotenberg , Q. Jacobson , J. Smith, A Study of Control Independence in Superscalar Processors, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.115, January 09-12, 1999
• 20: Eric Rotenberg , Jim Smith, Control independence in trace processors, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.4-15, November 16-18, 1999, Haifa, Israel
• 21: Avinash Sodani , Gurindar S. Sohi, Dynamic instruction reuse, Proceedings of the 24th annual international symposium on Computer architecture, p.194-205, June 01-04, 1997, Denver, Colorado, United States
• 22: 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
• 23: 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
• 24: Smruti R. Sarangi , Wei Liu, Josep Torrellas , Yuanyuan Zhou, ReSlice: Selective Re-Execution of Long-Retired Misspeculated Instructions Using Forward Slicing, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.257-270, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.28]
• 25: Steven Wallace , Brad Calder , Dean M. Tullsen, Threaded multiple path execution, Proceedings of the 25th annual international symposium on Computer architecture, p.238-249, June 27-July 02, 1998, Barcelona, Spain
• 26: Steven Wallace , Dean M. Tullsen , Brad Calder, Instruction Recycling on a Multiple-Path Processor, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.44, January 09-12, 1999
• 27: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.0 General

General Terms:
Design, Performance

Keywords:
branch prediction, checkpoints, control independence, selective re-execution, selective recovery, speculation