Ginger: control independence using tag rewriting

ABSTRACT

The negative performance impact of branch mis-predictions can be reduced by exploiting control independence (CI). When a branch mis-predicts, the wrong-path instructions up to the point where control converges with the correct path are selectively squashed and replaced with correct-path instructions. Instructions beyond the convergence-point-the branch's control-independent (CI) instructions-are spared from squashing. Exploiting CI requires updating the input data dependences of CI instructions to reflect the selective removal and insertion of logically older instructions and transitively re-dispatching those CI instructions whose inputs have changed. This capability is generally called out-of-order renaming. Previously proposed CI designs use out-of-order renaming schemes that either consume excessive rename/dispatch bandwidth, can only be applied in limited cases, or incur a cost even when the branch would be correctly predicted.

Ginger is a CI design that is both general and bandwidth efficient. Ginger implements out-of-order renaming using tag rewriting, re-linking the input dependences of CI instructions as they sit in the window. To do this, Ginger halts the pipeline uses the idle map table read and write ports and the issue queue match lines and write lines to perform a register-tag "search-and-replace" operation. After a few cycles, the pipeline restarts and execution resumes with correct data dependences. Cycle-level simulation shows that Ginger out-performs previous CI designs, yielding geometric mean speedups over an aggressive non-CI processor of 5%, 12%, and 11%-on SPECint2000, MediaBench, and Comm-Bench-with speedups of 15% or greater on 11 of 46 programs.

REFERENCES

• 1: 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
• 2: K. Arvind , Rishiyur S. Nikhil, Executing a Program on the MIT Tagged-Token Dataflow Architecture, IEEE Transactions on Computers, v.39 n.3, p.300-318, March 1990 [doi>10.1109/12.48862]
• 3: Harold W. Cain , Mikko H. Lipasti, Memory Ordering: A Value-Based Approach, Proceedings of the 31st annual international symposium on Computer architecture, p.90, June 19-23, 2004, München, Germany
• 4: 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
• 5: 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]
• 6: Weihaw Chuang , Brad Calder, Predicate prediction for efficient out-of-order execution, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782840]
• 7: 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]
• 8: 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]
• 9: M. S. Hrishikesh , Doug Burger , Norman P. Jouppi , Stephen W. Keckler , Keith I. Farkas , Premkishore Shivakumar, The optimal logic depth per pipeline stage is 6 to 8 FO4 inverter delays, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 10: Erik Jacobsen , Eric Rotenberg , J. E. Smith, Assigning confidence to conditional branch predictions, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.142-152, December 02-04, 1996, Paris, France
• 11: Daniel A. Jimenez, Piecewise Linear Branch Prediction, Proceedings of the 32nd annual international symposium on Computer Architecture, p.382-393, June 04-08, 2005
• 12: Hyesoon Kim , Jose A. Joao , Onur Mutlu , Yale N. Patt, Diverge-Merge Processor (DMP): Dynamic Predicated Execution of Complex Control-Flow Graphs Based on Frequently Executed Paths, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.53-64, December 09-13, 2006 [doi>10.1109/MICRO.2006.20]
• 13: Hyesoon Kim , Onur Mutlu , Jared Stark , Yale N. Patt, Wish Branches: Combining Conditional Branching and Predication for Adaptive Predicated Execution, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.43-54, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.38]
• 14: 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
• 15: 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
• 16: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• 17: 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
• 18: K. Malik, K. Woley, S. Stone, M. Agarwal, V. Dhar, and M. Frank. "Confidence Based Out-of-Order Renaming for Speculatively Multithreaded Processors." Technical Report UILU-ENG-06-2208, University of Illinois, Jun. 2006.
• 19: Gregory A. Muthler , David Crowe , Sanjay J. Patel , Steven S. Lumetta, Instruction fetch deferral using static slack, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 20: Paramjit S. Oberoi , Gurindar S. Sohi, Parallelism in the front-end, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 21: D. N. Pnevmatikatos , G. S. Sohi, Guarded execution and branch prediction in dynamic ILP processors, Proceedings of the 21st annual international symposium on Computer architecture, p.120-129, April 18-21, 1994, Chicago, Illinois, United States
• 22: 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
• 23: 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
• 24: Amir Roth, Store Vulnerability Window (SVW): Re-Execution Filtering for Enhanced Load Optimization, Proceedings of the 32nd annual international symposium on Computer Architecture, p.458-468, June 04-08, 2005
• 25: Tingting Sha , Milo M. K. Martin , Amir Roth, Scalable Store-Load Forwarding via Store Queue Index Prediction, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.159-170, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.29]
• 26: B. Sinharoy , R. N. Kalla , J. M. Tendler , R. J. Eickemeyer , J. B. Joyner, POWER5 System microarchitecture, IBM Journal of Research and Development, v.49 n.4/5, p.505-521, July 2005
• 27: 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
• 28: 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
• 29: 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
• 30: Jared Warner Stark, IV , Yale N. Pratt, Out-of-order fetch, decode, and issue, University of Michigan, Ann Arbor, MI, 2000
• 31: Jared Stark , Paul Racunas , Yale N. Patt, Reducing the performance impact of instruction cache misses by writing instructions into the reservation stations out-of-order, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.34-43, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 32: Augustus K. Uht , Vijay Sindagi , Kelley Hall, Disjoint eager execution: an optimal form of speculative execution, Proceedings of the 28th annual international symposium on Microarchitecture, p.313-325, November 29-December 01, 1995, Ann Arbor, Michigan, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors

General Terms:
Design, Measurement, Performance

Keywords:
branch misprediction, control independence, out-of-order renaming, selective re-dispatch