The impact of if-conversion and branch prediction on program execution on the Intel® Itanium™ processor

ABSTRACT

The research community has studied if-conversion for many years. However, due to the lack of existing hardware, studies were conducted by simulating code generated by experimental compilers. This paper presents the first comprehensive study of the use of predication to implement if-conversion on production hardware with a near-production compiler. To better understand trends in the measurements, we generated binaries at three increasing levels of if-conversion aggressiveness. For each level, we gathered data regarding the global runtime effects of if-conversion on overall execution time, register pressure, code size, and branch behavior. Furthermore, we studied the inherent characteristics of program control-flow structure related to branching to help determine fundamental limits of if-conversion. Our results show that on the Itanium™ processor if-conversion could potentially remove 29% of the branch mispredictions in SPEC2OOOCINT but that this accounts for a substantially smaller overall program speedup than previously reported.

REFERENCES

• 1: Intel Corporation. Intel® Itanium™ Architecture Software Developer's Manual. Available from http://developer.intel.com/design/ia-64/manuals/, July 2000.
• 2: Intel Corporation. Itanium™ Processor Microarchitecture Reference for Software Optimization. Available from http://developer.intel.com/design/ia-64/manuals/, August 2000.
• 3: Intel Corporation. Flexible Annotations API Programming Guide. Available from http://developer.intel.com/software/product/opensource/tools/perftools.htm, June 2001.
• 4: 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]
• 5: Srinivas Mantripragada , Alexandru Nicolau, Using profiling to reduce branch misprediction costs on a dynamically scheduled processor, Proceedings of the 14th international conference on Supercomputing, p.206-214, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335251]
• 6: 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
• 7: 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
• 8: 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
• 9: 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]
• 10: Alexandre Eichenberger , Alexandre E. Eichenberger , Waleed Meleis , Suman Maradani, An integrated approach to accelerate data and predicate computations in hyperblocks, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.101-111, December 2000, Monterey, California, United States [doi>10.1145/360128.360140]
• 11: 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
• 12: Jay Bharadwaj , Kishore Menezes , Chris McKinsey, Wavefront scheduling: path based data representation and scheduling of subgraphs, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.262-271, November 16-18, 1999, Haifa, Israel
• 13: 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
• 14: 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
• 15: N. J. Warter, D. M. Lavery, and W. W. Hwu. The benefit of predicated execution for software pipelining. Proceeding of the Twenty-Sixth Hawaii International Conference on System Sciences, Vol. I, pages 496-506, 1993.
• 16: James C. Dehnert , Peter Y.-T. Hsu , Joseph P. Bratt, Overlapped loop support in the Cydra 5, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.26-38, April 03-06, 1989, Boston, Massachusetts, United States
• 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: 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]
• 19: 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]
• 20: 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
• 21: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• 22: 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]