A comparative study of modulo scheduling techniques

ABSTRACT

Modulo Scheduling is an instruction scheduling technique that is used by many current compilers. Different approaches have been proposed in the past but there is not a quantitative comparison among them, using the same compiling platform, benchmarks and architectures.This paper presents a performance comparison of the most relevant Modulo Scheduling techniques, based on a detailed quantitative evaluation of them. The results point out which are the most effective techniques for different architectures, which is useful for compiler designers when choosing the most appropriate technique for a particular processor architecture.

REFERENCES

• 1: A. Aiken , A. Nicolau, Optimal loop parallelization, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.308-317, June 20-24, 1988, Atlanta, Georgia, United States
• 2: Alexander Aiken , Alexandru Nicolau, Perfect Pipelining: A New Loop Parallelization Technique, Proceedings of the 2nd European Symposium on Programming, p.221-235, March 21-24, 1988
• 3: A. Aiken and A. Nicolau. A Realistic Resource-constrained Software Pipelining Algorithm. Advances in Languages and Compilers for Parallel Processing, pages 274--290, 1991.
• 4: Vicki H. Allan , U. R. Shah , K. M. Reddy, Petri net versus modulo scheduling for software pipelining, Proceedings of the 28th annual international symposium on Microarchitecture, p.105-110, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 5: 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]
• 6: Erik R. Altman , Guang R. Gao, Optimal Modulo Scheduling Through Enumeration, International Journal of Parallel Programming, v.26 n.3, p.313-344, June 1998 [doi>10.1023/A:1018742213548]
• 7: E. Ayguadé, C. Barrado, A. González, J. Labarta, D. López, S. Moreno, D. Padua, F. Reig, Q. Riera, and M. Valero. Ictineo: A Tool for Research on ILP. In Int. Conference on Supercomputing, 1996.
• 8: Vasanth Bala , Norman Rubin, Efficient instruction scheduling using finite state automata, Proceedings of the 28th annual international symposium on Microarchitecture, p.46-56, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 9: A. Charlesworth. An Approach to Scientific Array Processing: The Architectural Design of the AP120B/FPS-164 Family. Computer, 14(9):18--27, 1981.
• 10: A. Dani, Register-Sensitive Software Pipelining, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.194, March 30-April 03, 1998
• 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: 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: 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
• 14: Alexandre E. Eichenberger , Edward S. Davidson , Santosh G. Abraham, Optimum modulo schedules for minimum register requirements, Proceedings of the 9th international conference on Supercomputing, p.31-40, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224542]
• 15: Alexandre E. Eichenberger , Edward S. Davidson, Stage scheduling: a technique to reduce the register requirements of a modulo schedule, Proceedings of the 28th annual international symposium on Microarchitecture, p.338-349, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 16: R. Govindarajan , Erik R. Altman , Guang R. Gao, Minimizing register requirements under resource-constrained rate-optimal software pipelining, Proceedings of the 27th annual international symposium on Microarchitecture, p.85-94, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192733]
• 17: 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
• 18: 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
• 19: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 20: Josep Llosa, Swing Modulo Scheduling: A Lifetime-Sensitive Approach, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.80, October 20-23, 1996
• 21: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 22: A. Nicolau. Uniform Parallelism Exploitation in Ordinary Programs. In Proc., of the Int. Conf. on Parallel Processing, August 1985.
• 23: 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]
• 24: 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
• 25: 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
• 26: 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
• 27: B. Ramakrishna Rau, Iterative modulo scheduling: an algorithm for software pipelining loops, Proceedings of the 27th annual international symposium on Microarchitecture, p.63-74, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192731]
• 28: Javier Zalamea , Josep Llosa , Eduard Ayguadé , Mateo Valero, Improved spill code generation for software pipelined loops, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.134-144, June 18-21, 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures
          Subjects: RISC/CISC, VLIW architectures

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Code generation

General Terms:
Algorithms, Experimentation, Languages, Measurement, Performance

Keywords:
Modulo scheduling, comparative study, instruction level parallel architectures, instruction scheduling, quantitative evaluation