Control CPR: a branch height reduction optimization for EPIC architectures

ABSTRACT

The challenge of exploiting high degrees of instruction-level parallelism is often hampered by frequent branching. Both exposed branch latency and low branch throughput can restrict parallelism. Control critical path reduction (control CPR) is a compilation technique to address these problems. Control CPR can reduce the dependence height of critical paths through branch operations as well as decrease the number of executed branches. In this paper, we present an approach to control CPR that recognizes sequences of branches using profiling statistics. The control CPR transformation is applied to the predominant path through this sequence. Our approach, its implementation, and experimental results are presented. This work demonstrates that control CPR enhances instruction-level parallelism for a variety of application programs and improves their performance across a range of processors.

REFERENCES

• AKPW83: 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]
• BGS95: Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Interprocedural conditional branch elimination, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.146-158, June 16-18, 1997, Las Vegas, Nevada, United States
• DT93: James C. Dehnert , Ross A. Towle, Compiling for the Cydra 5, The Journal of Supercomputing, v.7 n.1-2, p.181-227, May 1993 [doi>10.1007/BF01205184]
• FF92: Joseph A. Fisher , Stefan M. Freudenberger, Predicting conditional branch directions from previous runs of a program, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.85-95, October 12-15, 1992, Boston, Massachusetts, United States
• GK92: Torbjörn Granlund , Richard Kenner, Eliminating branches using a superoptimizer and the GNU C compiler, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.341-352, June 15-19, 1992, San Francisco, California, United States
• H+93: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• HBC98: W. Havanki , S. Banerjia , T. Conte, Treegion Scheduling for Wide Issue Processors, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.266, January 31-February 04, 1998
• JS96: 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
• KSR93: V. Kathail, M. Schlansker, and B. Rau. HPL PlayDoh architecture specification: Version 1.0. Technical Report HPL-93-80, H.P. Laboratories, Feb. 1993.
• Kuc78: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• LFK+93: P. Geoffrey Lowney , Stefan M. Freudenberger , Thomas J. Karzes , W. D. Lichtenstein , Robert P. Nix , John S. O'Donnell , John Ruttenberg, The multiflow trace scheduling compiler, The Journal of Supercomputing, v.7 n.1-2, p.51-142, May 1993 [doi>10.1007/BF01205182]
• ME92: Soo-Mook Moon , Kemal Ebcioğlu, An efficient resource-constrained global scheduling technique for superscalar and VLIW processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.55-71, December 01-04, 1992, Portland, Oregon, United States
• MLC+92: 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
• MW92: Frank Mueller , David B. Whalley, Avoiding unconditional jumps by code replication, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.322-330, June 15-19, 1992, San Francisco, California, United States
• MW95: Frank Mueller , David B. Whalley, Avoiding conditional branches by code replication, ACM SIGPLAN Notices, v.30 n.6, p.56-66, June 1995
• SK93: Michael S. Schlansker , Vinod Kathail, Acceleration of First and Higher Order Recurrences on Processors with Instruction Level Parallelism, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.406-429, August 12-14, 1993
• SK95: Michael Schlansker , Vinod Kathail, Critical path reduction for scalar programs, Proceedings of the 28th annual international symposium on Microarchitecture, p.57-69, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• TLS90: P. Tirumalai , M. Lee , M. Schlansker, Parallelization of loops with exits on pipelined architectures, Proceedings of the 1990 conference on Supercomputing, p.200-212, October 1990, New York, New York, United States
• YUW98: Minghui Yang , Gang-Ryung Uh , David B. Whalley, Improving performance by branch reordering, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.130-141, June 17-19, 1998, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Design, Experimentation, Languages, Measurement, Performance, Theory