Parallelizing nonnumerical code with selective scheduling and software pipelining

ABSTRACT

Instruction-level parallelism (ILP) in nonnumerical code is regarded as scarce and hard to exploit due to its irregularity. In this article, we introduce a new code-scheduling technique for irregular ILP called “selective scheduling” which can be used as a component for superscalar and VLIW compilers. Selective scheduling can compute a wide set of independent operations across all execution paths based on renaming and forward-substitution and can compute available operations across loop iterations if combined with software pipelining. This scheduling approach has better heuristics for determining the usefulness of moving one operation versus moving another and can successfully find useful code motions without resorting to branch profiling. The compile-time overhead of selective scheduling is low due to its incremental computation technique and its controlled code duplication. We parallelized the SPEC integer benchmarks and five AIX utilities without using branch probabilities. The experiments indicate that a fivefold speedup is achievable on realistic resources with a reasonable overhead in compilation time and code expansion and that a solid speedup increase is also obtainable on machines with fewer resources. These results improve previously known characteristics of irregular ILP.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: A. Aiken , A. Nicolau, A Development Environment for Horizontal Microcode, IEEE Transactions on Software Engineering, v.14 n.5, p.584-594, May 1988 [doi>10.1109/32.6136]
• 3: Mark Atkins, Performance and the i860 Microprocessor, IEEE Micro, v.11 n.5, p.24-27, 72-78, September 1991 [doi>10.1109/40.108548]
• 4: David Bernstein , Michael Rodeh, Global instruction scheduling for superscalar machines, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.241-255, June 24-28, 1991, Toronto, Ontario, Canada
• 5: Robert P. Colwell , Robert P. Nix , John J. O'Donnell , David B. Papworth , Paul K. Rodman, A VLIW architecture for a trace Scheduling Compiler, IEEE Transactions on Computers, v.37 n.8, p.967-979, August 1988 [doi>10.1109/12.2247]
• 6: 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]
• 7: 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]
• 8: EBCIO(~LU, I{. 1988. Some design ideas for a VLIW architecture for sequential natured software. In Parallel Processing (Proceedings of IFIP WG 10.3 Working Conference on Parallel Processing). North Holland, Amsterdam, 3-21.
• 9: EBCIO(~LU, I{. AND GROVES, R. 1990. Some global compilation optimizations and architectural features for improving performance of superscMars. Res. Rep. RC-16145, IBM T. J. Watson Research Center, Yorktown Heights, N.Y.
• 10: Kemal Ebcioglu , Randy D. Groves , Ki-Chang Kim , Gabriel M. Silberman , Isaac Ziv, VLIW compilation techniques in a superscalar environment, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.36-48, June 20-24, 1994, Orlando, Florida, United States
• 11: K. Ebcioğlu , Toshio Nakatani, A new compilation technique for parallelizing loops with unpredictable branches on a VLIW architecture, Selected papers of the second workshop on Languages and compilers for parallel computing, p.213-229, May 1990, Urbana, Illinois, United States
• 12: EBCIO(~LU, K. AND NICOLAU, A. 1989. Percolation scheduling with resource constraints. Tech. Rep. 89-31, Univ. of California, Irvine, Calif.
• 13: John R. Ellis, Bulldog: a compiler for vliw architectures (parallel computing, reduced-instruction-set, trace scheduling, scientific), 1985
• 14: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 15: 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
• 16: Stefan M. Freudenberger , Thomas R. Gross , P. Geoffrey Lowney, Avoidance and suppression of compensation code in a trace scheduling compiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1156-1214, July 1994 [doi>10.1145/183432.183446]
• 17: Nicolas Gloy , Michael D. Smith , Cliff Young, Performance issues in correlated branch prediction schemes, Proceedings of the 28th annual international symposium on Microarchitecture, p.3-14, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 18: Rajiv Gupta , Mary Lou Soffa, Region Scheduling: An Approach for Detecting and Redistributing Parallelism, IEEE Transactions on Software Engineering, v.16 n.4, p.421-431, April 1990 [doi>10.1109/32.54294]
• 19: 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]
• 20: IBM. 1990. A special issue on IBM RISC System/6000. IBM J. Res. Devel. 34, 1 (Jan.).
• 21: Suneel Jain, Circular scheduling: a new technique to perform software pipelining, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.219-228, June 24-28, 1991, Toronto, Ontario, Canada
• 22: N. P. Jouppi , D. W. Wall, Available instruction-level parallelism for superscalar and superpipelined machines, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.272-282, April 03-06, 1989, Boston, Massachusetts, United States
• 23: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 24: Soo-Mook Moon, Compile-time parallelization of non-numerical code: VLIW superscalar, University of Maryland at College Park, College Park, MD, 1993
• 25: MOON, S.-M. 1997. Increasing cache bandwidth using multiport caches for exploiting ILP in non-numerical codes. IEEE Proceedings - Computers and Digital Techniques 1~, 5 (Sept.), 295-303.
• 26: Soo-Mook Moon , Scott D. Carson, Generalized Multiway Branch Unit for VLIW Microprocessors, IEEE Transactions on Parallel and Distributed Systems, v.6 n.8, p.850-862, August 1995 [doi>10.1109/71.406961]
• 27: Soo-Mook Moon , Kemal Ebcioğlu, A study on the number of memory ports in multiple instruction issue machines, Proceedings of the 26th annual international symposium on Microarchitecture, p.49-59, December 01-03, 1993, Austin, Texas, United States
• 28: Soo-Mook Moon , Kemal Ebcioğlu, Performance analysis of tree VLIW architecture for exploiting branch ILP in non-numerical code, Proceedings of the 11th international conference on Supercomputing, p.301-308, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263653]
• 29: MOON, S.-M., KIM, S., PARK, J., AND EBCIOGLU, K. 1997. Unrolling-based copy coalescing. Tech. Rep. SNU-EE-TR-1997-7, Seoul National Univ., Seoul, Korea.
• 30: T. Nakatani , K. Ebcioğlu, “Combining” as a compilation technique for VLIW architectures, Proceedings of the 22nd annual workshop on Microprogramming and microarchitecture, p.43-55, August 14-16, 1989, Dublin, Ireland
• 31: T. Nakatani , K. Ebcioglu, Making Compaction-Based Parallelization Affordable, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.1014-1029, September 1993 [doi>10.1109/71.243528]
• 32: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 33: Seongbae Park , SangMin Shim , Soo-Mook Moon, Evaluation of scheduling techniques on a SPARC-based VLIW testbed, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.104-113, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 34: David A. Patterson, Reduced instruction set computers, Communications of the ACM, v.28 n.1, p.8-21, Jan. 1985 [doi>10.1145/2465.214917]
• 35: 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]
• 36: B. Ramakrishna Rau , Joseph A. Fisher, Instruction-level parallel processing: history, overview, and perspective, The Journal of Supercomputing, v.7 n.1-2, p.9-50, May 1993 [doi>10.1007/BF01205181]
• 37: B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States
• 38: SCHWARTZ, J. AND SHARIR, M. 1979. A design for optimizations of the bit vectoring class. Tech. Rep. 17, Courant Inst. of Computer Science, New York Univ., New York.
• 39: Gabriel M. Silberman , Kemal Ebcioglu, An Architectural Framework for Supporting Heterogeneous Instruction-Set Architectures, Computer, v.26 n.6, p.39-56, June 1993 [doi>10.1109/2.214441]
• 40: Richard L. Sites, Alpha AXP architecture, Communications of the ACM, v.36 n.2, p.33-44, Feb. 1993 [doi>10.1145/151220.151226]
• 41: Michael D. Smith , Mark Horowitz , Monica S. Lam, Efficient superscalar performance through boosting, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.248-259, October 12-15, 1992, Boston, Massachusetts, United States
• 42: M. D. Smith , M. Johnson , M. A. Horowitz, Limits on multiple instruction issue, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.290-302, April 03-06, 1989, Boston, Massachusetts, United States
• 43: WARREN, H., AUSLANDER, M., CHAITIN, G., CHIBIB, A., HOPKINS, M., AND MACKAY, A. Jun 1986. Final code generation in the PL.8 compiler. Res. Rep. RC 11974, IBM T.J. Watson Research Center, Yorktown Heights, N.Y.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

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

General Terms:
Algorithms, Experimentation, Languages

Keywords:
VLIW, global instruction scheduling, instruction-level parallelism, software pipelining, speculative code motion, superscalar