Iterative modulo scheduling: an algorithm for software pipelining loops

ABSTRACT

Modulo scheduling is a framework within which a wide variety of algorithms and heuristics may be defined for software pipelining innermost loops. This paper presents a practical algorithm, iterative modulo scheduling, that is capable of dealing with realistic machine models. This paper also characterizes the algorithm in terms of the quality of the generated schedules as well the computational expense incurred.

REFERENCES

• 1: Thomas L. Adam , K. M. Chandy , J. R. Dickson, A comparison of list schedules for parallel processing systems, Communications of the ACM, v.17 n.12, p.685-690, Dec 1974 [doi>10.1145/361604.361619]
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Aiken, A., and Nicolau, A. A realistic resource-constrained software pipelining algorithm. In Advances in Languages and Compilers for Parallel Processing, Nicolau, A., Gelernter, D., Gross, T., and Padua, D., (Editor). Pitman/The MIT Press, London, 1991, 274-290.
• 4: 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]
• 5: Gary R. Beck , David W. L. Yen , Thomas L. Anderson, The Cydra 5 minisupercomputer: architecture and implementation, The Journal of Supercomputing, v.7 n.1-2, p.143-180, May 1993 [doi>10.1007/BF01205183]
• 6: Berry, M., Chen, D., Kuck, D., Lo, S., Pang, Y., Pointer, L., Roloff, R., Samah, A., Clementi, E., Chin, S., Schneider, D., Fox, G., Messina, P., Walker, D., Hsiung, C., Schwarzmeier, J., Lue, L., Orszag, S., Seidl, F., Johnson, O., Goodrum, R., and Martin, J. The Perfect Club Benchmarks: Effective Performance Evaluation of Supercomputers. The international Journal of Supercomputer Applications 3, 3 (Fall 1989), 5-40.
• 7: François Bodin , François Charot, Loop optimization for horizontal microcoded machines, Proceedings of the 4th international conference on Supercomputing, p.164-176, June 11-15, 1990, Amsterdam, The Netherlands
• 8: Charlesworth, A.E. An approach to scientific array processing: the architectural design of the AP-120B/FPS- 164 Family. Computer 14, 9 (1981), 18-27.
• 9: Davidson, E.S., Shar, L.E., Thomas, A.T., and PateI, J.H. Effective control for pipelined computers. In Proc. COMPCON '90, (San Francisco, February 1975), 181-184.
• 10: 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]
• 11: Kemal Ebcioğlu, A compilation technique for software pipelining of loops with conditional jumps, Proceedings of the 20th annual workshop on Microprogramming, p.69-79, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255317]
• 12: 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
• 13: Fisher, J.A. Trace scheduling: a technique for global microcode compaction. IEEE Transactions on Computers C~30, 7 (July 1981), 478-490.
• 14: Fisher, J.A., Landskov, D., and Shriver, B.D. Microcode compaction: looking backward and looking forward. In Proc. 1981 National Computer Conference, (1981), 95- 102.
• 15: Franco Gasperoni , Uwe Schwiegelshohn, Scheduling Loops on Parallel Processors: A Simple Algorithm with Close to Optimum Performance, Proceedings of the Second Joint International Conference on Vector and Parallel Processing: Parallel Processing, p.625-636, September 01-04, 1992
• 16: P Y Hsu, Highly concurrent scalar processing, University of Illinois, Department of Computer Science, Urbana, IL, 1986
• 17: Hu, T.C. Parallel sequencing and assembly line problems Operations Research 9, 6 (1961), 841-848.
• 18: 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
• 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: 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
• 21: 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
• 22: Lawler, E.L. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.
• 23: 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]
• 24: Scott A. Mahlke , William Y. Chen , Roger A. Bringmann , Richard E. Hank , Wen-Mei W. Hwu , B. Ramakrishna Rau , Michael S. Schlansker, Sentinel scheduling: a model for compiler-controlled speculative execution, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.376-408, Nov. 1993 [doi>10.1145/161541.159765]
• 25: 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
• 26: Mateti, P., and Deo, N. On algorithms for enumerating all circuits of a graph. SIAM Journal of Computing 5, 1 (1976), 90-99.
• 27: McMahon, F.H. The Livermore Fortran kernels: a computer test of the numerical performance range. Technical Report UCRL-53745. Lawrence Livermore National Laboratory. Livermore, California, 1986.
• 28: 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
• 29: Park, J.C.H., and Schlansker, M.S. On predicated execution. Technical Report HPL-91-58. Hewlett Packard Laboratories, 1991.
• 30: Ramakrishnan, S. Software pipelining in PA-RiSC compilers. Hewlett-Packard Journal, (July 1992), 39-45.
• 31: Ramamoorthy, C.V., Chandy, K.M., and Gonzalez, M.J. Optimal scheduling strategies in a multiprocessor system. IEEE Transactions on Computers C-21, 2 (February 1972), 137-146.
• 32: B. Ramakrishna Rau, Data Flow and Dependence Analysis for Instruction Level Parallelism, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.236-250, August 07-09, 1991
• 33: Rau, B.R. Iterative Modulo Scheduling. HPL Technical Report. Hewlett-Packard Laboratories, 1994.
• 34: 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
• 35: 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
• 36: 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
• 37: 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]
• 38: 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
• 39: Bogong Su , Jian Wang, GURPR*: a new global software pipelining algorithm, Proceedings of the 24th annual international symposium on Microarchitecture, p.212-216, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123509]
• 40: James C. Tiernan, An efficient search algorithm to find the elementary circuits of a graph, Communications of the ACM, v.13 n.12, p.722-726, Dec. 1970 [doi>10.1145/362814.362819]
• 41: 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
• 42: Mario Tokoro , Takashi Takizuka , Eiji Tamura , Ichiro Yamaura, A technique of global optimization of microprograms, Proceedings of the 11th annual workshop on Microprogramming, p.41-50, November 19-22, 1978, Pacific Grove, California, United States
• 43: Uniejewski, J. SPEC Benchmark Suite: Designed for Today's Advanced Systems. SPEC Newsletter 1, 1 (Fall 1989).
• 44: Vincent Van Dongen , Guang R. Gao , Qi Ning, A Polynomial Time Method for Optimal Software Pipelining, Proceedings of the Second Joint International Conference on Vector and Parallel Processing: Parallel Processing, p.613-624, September 01-04, 1992
• 45: Warter, N.J., Lavery, D.M., and Hwu, W.W. The benefit of predicated execution for software pipelining. In Proc. 26th Annual Hawaii international Conference on System Sciences, (Hawaii, 1993).
• 46: 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.4 OPERATING SYSTEMS

Additional Classification:
  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:
Algorithms, Measurement, Performance, Theory

Keywords:
instruction scheduling, loop scheduling, modulo scheduling, software pipelining