Minimizing register requirements under resource-constrained rate-optimal software pipelining

ABSTRACT

In this paper we address the following software pipelining problem: given a loop and a machine architecture with a fixed number of processor resources (e.g. function units), how can one construct a software-pipelined schedule which runs on the given architecture at the maximum possible iteration rate (a` la rate-optimal) while minimizing the number of registers?The main contributions of this paper are:•First, we demonstrate that such problem can be described by a simple mathematical formulation with precise optimization objectives under periodic linear scheduling framework. The mathematical formulation provides a clear picture which permits one to visualize the overall solution space (for rate-optimal schedules) under different sets of constraints.•Secondly, we show that a precise mathematical formulation and its solution does make a significant performance difference! We evaluated the performance of our method against three other leading contemporary heuristic methods: Huff's Slack Scheduling, Wang, Eisenbeis, Jourdan and Su's FRLC, and Gasperoni and Schwiegelshohn's modified list scheduling. Experimental results show that the method described in this paper performed significantly better than these methods.

REFERENCES

• 1: A. Aiken and A. Nicolau. A realistic resourceconstrained software pipelining algorithm. In A. Nicolau, D. Gelernter, T. Gross, and D. Padua, editors, Advances ~n Languages and Compilers for Parallel Processing, Res. Monographs in Parallel and Distrib. Computing, chapter 14, pages 274-290. 1991.
• 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: E. R. Altman, R. Govindarajan, and G. R. Gao. Software pipelining to minimize registers and resources. ACAPS Technical Memo 79, School of Computer Science, McGill University, Montrdal, Qua., 1994. under preparation.
• 4: 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]
• 5: 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
• 6: F. Gasperoni , U. Schwiegelshohn, Efficient Algorithms for Cyclic Scheduling, New York University, New York, NY, 1991
• 7: M. B. Girkar, M. R. Haghighat, C. L. Lee, B. P. Leung, and D. A. Schouten. Parafrase-2 user's manual. TR RC-17068(#75743), Center for Supercomputing Research and Development, University of Illinois at Urbana-Champagne, IL, 1991.
• 8: R. Govindarajan, E. R. Altman, and G. R. Gao. Minimizing register requirement in resource-constrained software pipelining. ACAPS Technical Memo 80, School of Computer Science, McGill University, MontrdM, Qud., 1994.
• 9: Richard A. Huff, Lifetime-sensitive modulo scheduling, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.258-267, June 21-25, 1993, Albuquerque, New Mexico, United States
• 10: C.-T. Hwang, J.-H. Lee, and Y.-C. Hsu. A formal approach to the scheduling problem in high-level synthesis. }EEE Trans. on Computer-A~ded Deszgn, 10(4):464-475, Apr. 1991.
• 11: 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
• 12: 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
• 13: Qi Ning , Guang R. Gao, A novel framework of register allocation for software pipelining, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.29-42, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158519]
• 14: M. Rajagopalan , V. H. Allan, Efficient scheduling of fine grain parallelism in loops, Proceedings of the 26th annual international symposium on Microarchitecture, p.2-11, December 01-03, 1993, Austin, Texas, United States
• 15: S. Ramakrishnan. Software pipelining in PA-RISC compilers. Hewlett-Packard J., pages 39-45, Jun. 1992.
• 16: 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]
• 17: 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
• 18: B. R. Rau , M. Lee , P. P. Tirumalai , M. S. Schlansker, Register allocation for software pipelined loops, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.283-299, June 15-19, 1992, San Francisco, California, United States
• 19: B. Ramakrishna Rau , Michael S. Schlansker , P. P. Tirumalai, Code generation schema for modulo scheduled loops, Proceedings of the 25th annual international symposium on Microarchitecture, p.158-169, December 01-04, 1992, Portland, Oregon, United States
• 20: 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]
• 21: Raymond Reiter, Scheduling Parallel Computations, Journal of the ACM (JACM), v.15 n.4, p.590-599, Oct. 1968 [doi>10.1145/321479.321485]
• 22: Roy F. Touzeau, A Fortran compiler for the FPS-164 scientific computer, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.48-57, June 17-22, 1984, Montreal, Canada
• 23: J. Wang, C. Eisenbeis, M. Jourdan, and B. Su. DE- composed Software Pipelining: A new approach to exploit irtstruc~ion-level parallelism for loop programs. Res. Rep. RR-1838, INRIA-Rocquencourt, France, Jan. 1993.
• 24: 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

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Design, Experimentation, Performance