Using predicate path information in hardware to determine true dependences

ABSTRACT

Predicated Execution has been put forth as a method for improving processor performance by removing hard-to-predict branches. As part of the process of turning a set of basic blocks into a predicated region, both paths of a branch are combined into a single path. There can be multiple definitions from disjoint paths that reach a use. Waiting to find out the correct definition that actually reaches the use can cause pipeline stalls.In this paper we examine a hardware optimization that dynamically collects and analyzes path information to determine valid dependences for predicated regions of code. We then use this information for an in-order VLIW predicated processor, so that instructions can continue towards execution without having to wait on operands from false dependences. Our results show that using our Disjoint Path Analysis System provides speedups over 6% and elimination of false RAW dependences of up to 14% due to the detection of erroneous dependences in if-converted regions of code.

REFERENCES

• 1: Trimaran, An Infrastructure for Research in Instruction Level Parallelism, 1998. http: //www.trimaran.org
• 2: IA-64 Application Instruction Set Architecture Guide, Revision 1.0, 1999
• 3: Intel IA-64 Architecture Software Developer's Manual. Intel, 2000
• 4: Itanium Processor Microarchitecture Reference:for Software Optimization., 2000. http: //www.developer.intel.com/design/ia64/itanium.htm
• 5: 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]
• 6: David I. August , John W. Sias , Jean-Michel Puiatti , Scott A. Mahlke , Daniel A. Connors , Kevin M. Crozier , Wen-mei W. Hwu, The program decision logic approach to predicated execution, Proceedings of the 26th annual international symposium on Computer architecture, p.208-219, May 01-04, 1999, Atlanta, Georgia, United States
• 7: Jay Bharadwaj , William Y. Chen , Weihaw Chuang , Gerolf Hoflehner , Kishore Menezes , Kalyan Muthukumar , Jim Pierce, The Intel IA-64 Compiler Code Generator, IEEE Micro, v.20 n.5, p.44-53, September 2000 [doi>10.1109/40.877949]
• 8: D.C. Burger and T.M. Austin. The Simplescalar Tool Set, version 2.0. Technical Report CS-TR-97-1342, University of Wisconsin, Madison, Jun 1997
• 9: Lori Carter , Beth Simon , Brad Calder , Larry Carter , Jeanne Ferrante, Predicated Static Single Assignment, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.245, October 12-16, 1999
• 10: 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]
• 11: S. Eranian and D. Mosberger. The Linux/IA64 Project: Kernel Design and Status Update. Technical Report HPL-2000-85, HP Labs, June 2000
• 12: David M. Gillies , Dz-ching Roy Ju , Richard Johnson , Michael Schlansker, Global predicate analysis and its application to register allocation, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.114-125, December 02-04, 1996, Paris, France
• 13: Jerry Huck , Dale Morris , Jonathan Ross , Allan Knies , Hans Mulder , Rumi Zahir, Introducing the IA-64 Architecture, IEEE Micro, v.20 n.5, p.12-23, September 2000 [doi>10.1109/40.877947]
• 14: 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
• 15: J. C. H. Park and M. Schlansker. On Predicated Execution. Technical Report HPL-91-58, HP Labs, May 1991
• 16: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 17: Richard Johnson , Michael Schlansker, Analysis techniques for predicated code, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.100-113, December 02-04, 1996, Paris, France
• 18: Harsh Sharangpani , Ken Arora, Itanium Processor Microarchitecture, IEEE Micro, v.20 n.5, p.24-43, September 2000 [doi>10.1109/40.877948]
• 19: John W. Sias , Wen-Mei W. Hwu , David I. August, Accurate and efficient predicate analysis with binary decision diagrams, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.112-123, December 2000, Monterey, California, United States [doi>10.1145/360128.360141]
• 20: 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

INDEX TERMS

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

General Terms:
Performance

Keywords:
dependence analysis, path analysis, predicated execution