The program decision logic approach to predicated execution

ABSTRACT

Modern compilers must expose sufficient amounts of Instruction-Level Parallelism (ILP) to achieve the promised performance increases of superscalar and VLIW processors. One of the major impediments to achieving this goal has been inefficient programmatic control flow. Historically, the compiler has translated the programmer's original control structure directly into assembly code with conditional branch instructions. Eliminating inefficiencies in handling branch instructions and exploiting ILP has been the subject of much research. However, traditional branch handling techniques cannot significantly alter the program's inherent control structure. The advent of predication as a program control representation has enabled compilers to manipulate control in a form more closely related to the underlying program logic. This work takes full advantage of the predication paradigm by abstracting the program control flow into a logical form referred to as a program decision logic network. This network is modeled as a Boolean equation and minimized using modified versions of logic synthesis techniques. After minimization, the more efficient version of the program's original control flow is re-expressed in predicated code. Furthermore, this paper proposes extensions to the HPL PlayDoh predication model in support of more effective predicate decision logic network minimization. Finally, this paper shows the ability of the mechanisms presented to overcome limits on ILP previously imposed by rigid program control structure.

REFERENCES

• 1: S. B. Akers. Binary decision diagrams. IEEE Transaction on Computers, C-27(8):509-5t6, June t978.
• 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 , Scott A. Mahlke , John W. Sias , Kevin M. Crozier , Ben-Chung Cheng , Patrick R. Eaton , Qudus B. Olaniran , Wen-mei W. Hwu, Integrated predicated and speculative execution in the IMPACT EPIC architecture, Proceedings of the 25th annual international symposium on Computer architecture, p.227-237, June 27-July 02, 1998, Barcelona, Spain
• 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: 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
• 6: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 7: Randal E. Bryant, Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams, Carnegie Mellon University, Pittsburgh, PA, 1992
• 8: P. Y T Hsu , E. S. Davidson, Highly concurrent scalar processing, Proceedings of the 13th annual international symposium on Computer architecture, p.386-395, June 02-05, 1986, Tokyo, Japan
• 9: W. Hwu , Y. N. Patt, HPSm, a high performance restricted data flow architecture having minimal functionality, Proceedings of the 13th annual international symposium on Computer architecture, p.297-306, June 02-05, 1986, Tokyo, Japan
• 10: V. Kathail, M. S. Schlansker, and B. R. Rau. HPL Play- Doh architecture specification: Version 1.0. Technical Report HPL-93-80, Hewlett-Packard Laboratories, Palo Alto, CA, February t994.
• 11: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 12: 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]
• 13: 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
• 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: Frank Mueller , David B. Whalley, Avoiding conditional branches by code replication, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.56-66, June 18-21, 1995, La Jolla, California, United States
• 16: B. Ramakrishna Rau , David W. L. Yen , Wei Yen , Ross A. Towie, The Cydra 5 Departmental Supercomputer: Design Philosophies, Decisions, and Trade-Offs, Computer, v.22 n.1, p.12-26, 28-30, 32-35, January 1989 [doi>10.1109/2.19820]
• 17: 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
• 18: 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
• 19: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 20: John F. Wakerly, Digital design: principles and practices (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 21: 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
• 22: 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
• 23: Tse-Yu Yeh , Yale N. Patt, Two-level adaptive training branch prediction, Proceedings of the 24th annual international symposium on Microarchitecture, p.51-61, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123475]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Design, Management, Theory