Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper proposes a new processor architecture for handling hard-to-predict branches, the diverge-merge processor (DMP). The goal of this paradigm is to eliminate branch mispredictions due to hard-to-predict dynamic branches by dynamically predicating them without requiring ISA support for predicate registers and predicated instructions. To achieve this without incurring large hardware cost and complexity, the compiler provides control-flow information by hints and the processor dynamically predicates instructions only on frequently executed program paths. The key insight behind DMP is that most control-flow graphs look and behave like simple hammock (if-else) structures when only frequently executed paths in the graphs are considered. Therefore, DMP can dynamically predicate a much larger set of branches than simple hammock branches. This paper proposes a new processor architecture for handling hard-to-predict branches, the diverge-merge processor (DMP). The goal of this paradigm is to eliminate branch mispredictions due to hard-to-predict dynamic branches by dynamically predicating them without requiring ISA support for predicate registers and predicated instructions. To achieve this without incurring large hardware cost and complexity, the compiler provides control-flow information by hints and the processor dynamically predicates instructions only on frequently executed program paths. The key insight behind DMP is that most control-flow graphs look and behave like simple hammock (if-else) structures when only frequently executed paths in the graphs are considered. Therefore, DMP can dynamically predicate a much larger set of branches than simple hammock branches.

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: J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
• 3: David I. August , Daniel A. Connors , John C. Gyllenhaal , Wen-mei W. Hwu, Architectural Support for Compiler-Synthesized Dynamic Branch Prediction Strategies: Rationale and Initial Results, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.84, February 01-05, 1997
• 4: David I. August , Wen-mei W. Hwu , Scott A. Mahlke, A framework for balancing control flow and predication, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.92-103, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 5: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 6: Po-Yung Chang , Eric Hao , Yale N. Patt , Pohua P. Chang, Using predicated execution to improve the performance of a dynamically scheduled machine with speculative execution, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.99-108, June 27-29, 1995, Limassol, Cyprus
• 7: Shailender Chaudhry , Paul Caprioli , Sherman Yip , Marc Tremblay, High-Performance Throughput Computing, IEEE Micro, v.25 n.3, p.32-45, May 2005 [doi>10.1109/MM.2005.49]
• 8: 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
• 9: Youngsoo Choi , Allan Knies , Luke Gerke , Tin-Fook Ngai, The impact of if-conversion and branch prediction on program execution on the Intel® Itanium™ processor, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 10: 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
• 11: 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]
• 12: 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]
• 13: 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]
• 14: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 15: [15] M. Farrens, T. Heil, J. E. Smith, and G. Tyson. Restricted dual path execution. Technical Report CSE-97-18, University of California at Davis, Nov. 1997.
• 16: 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]
• 17: Dirk Grunwald , Artur Klauser , Srilatha Manne , Andrew Pleszkun, Confidence estimation for speculation control, Proceedings of the 25th annual international symposium on Computer architecture, p.122-131, June 27-July 02, 1998, Barcelona, Spain
• 18: [18] T. Heil and J. E. Smith. Selective dual path execution. Technical report, University of Wisconsin-Madison, Nov. 1996.
• 19: 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
• 20: 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
• 21: [21] H. Kim, J. A. Joao, O. Mutlu, and Y. N. Patt. Diverge-merge processor (DMP): Dynamic predicated execution of complex control-flow graphs based on frequently executed paths. Technical Report TR-HPS-2006-008, The University of Texas at Austin, Sept. 2006.
• 22: 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]
• 23: 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
• 24: Artur Klauser , Dirk Grunwald, Instruction fetch mechanisms for multipath execution processors, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.38-47, November 16-18, 1999, Haifa, Israel
• 25: 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
• 26: A J KleinOsowski , David J. Lilja, MinneSPEC: A New SPEC Benchmark Workload for Simulation-Based Computer Architecture Research, IEEE Computer Architecture Letters, v.1 n.1, p.7, January 2006 [doi>10.1109/L-CA.2002.8]
• 27: 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
• 28: Scott A. Mahlke , Richard E. Hank , Roger A. Bringmann , John C. Gyllenhaal , David M. Gallagher , Wen-mei W. Hwu, Characterizing the impact of predicated execution on branch prediction, Proceedings of the 27th annual international symposium on Microarchitecture, p.217-227, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192755]
• 29: Scott A. Mahlke , David C. Lin , William Y. Chen , Richard E. Hank , Roger A. Bringmann, Effective compiler support for predicated execution using the hyperblock, Proceedings of the 25th annual international symposium on Microarchitecture, p.45-54, December 01-04, 1992, Portland, Oregon, United States
• 30: Onur Mutlu , Jared Stark , Chris Wilkerson , Yale N. Patt, Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-Order Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.129, February 08-12, 2003
• 31: [31] ORC. Open research compiler for Itanium processor family. http://ipforc.sourceforge.net/.
• 32: [32] J. C. H. Park and M. Schlansker. On predicated execution. Technical Report HPL-91-58, Hewlett-Packard Labs, Palo Alto CA, May 1991.
• 33: 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
• 34: [34] E. M. Riseman and C. C. Foster. The inhibition of potential parallelism by conditional jumps. IEEE Transactions on Computers, C-21(12):1405- 1411, 1972.
• 35: 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
• 36: 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
• 37: 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
• 38: John W. Sias , Sain-zee Ueng , Geoff A. Kent , Ian M. Steiner , Erik M. Nystrom , Wen-mei W. Hwu, Field-testing IMPACT EPIC research results in Itanium 2, Proceedings of the 31st annual international symposium on Computer architecture, p.26, June 19-23, 2004, München, Germany
• 39: Beth Simon , Brad Calder , Jeanne Ferrante, Incorporating Predicate Information into Branch Predictors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.53, February 08-12, 2003
• 40: Kevin Skadron , Pritpal S. Ahuja , Margaret Martonosi , Douglas W. Clark, Branch Prediction, Instruction-Window Size, and Cache Size: Performance Trade-Offs and Simulation Techniques, IEEE Transactions on Computers, v.48 n.11, p.1260-1281, November 1999 [doi>10.1109/12.811115]
• 41: Eric Sprangle , Doug Carmean, Increasing processor performance by implementing deeper pipelines, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 42: 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
• 43: [43] J. M. Tendler, J. S. Dodson, J. S. Fields, H. Le, and B. Sinharoy. POWER4 system microarchitecture. IBM Technical White Paper, Oct. 2001.
• 44: Gary Scott Tyson, The effects of predicated execution on branch prediction, Proceedings of the 27th annual international symposium on Microarchitecture, p.196-206, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192753]
• 45: Ralph M. Kling , Kalpana Ramakrishnan, Register Renaming and Scheduling for Dynamic Execution of Predicated Code, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.15, January 20-24, 2001
• 46: Nancy J. Warter , Scott A. Mahlke , Wen-Mei W. Hwu , B. Ramakrishna Rau, Reverse If-Conversion, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.290-299, June 21-25, 1993, Albuquerque, New Mexico, United States

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Data-flow architectures

General Terms:
Design, Performance