Reduced code size modulo scheduling in the absence of hardware support

ABSTRACT

Modulo scheduling is a very effective instruction scheduling technique that exploits Instruction Level Parallelism (ILP) in loop bodies by overlapping the execution of successive iterations. Unfortunately, modulo scheduling has been shown to cause heavy code expansion. To avoid the penalties of code expansion, some processors have dedicated hardware support for modulo scheduled loops. However, this dedicated hardware support has a cost in chip area, cycle time, processor complexity, and compiler complexity.This paper shows that the right combination of scheduling heuristics combined with speculative modulo scheduling can significantly reduce code expansion. In addition, several code generation schema heuristics are proposed to further reduce code expansion. The evaluations show that loops can be effectively modulo scheduled with an average code expansion only 1.5 times the original loop size. Compared with a state of the art modulo scheduler, our code size sensitive heuristics reduce the size of embedded domain benchmarks binaries by 30% on average. While performance is mostly unchanged, some applications show speed-ups up to 20% due to a reduction in instruction cache capacity misses.

REFERENCES

• 1: Vicki H. Allan , Reese B. Jones , Randall M. Lee , Stephen J. Allan, Software pipelining, ACM Computing Surveys (CSUR), v.27 n.3, p.367-432, Sept. 1995 [doi>10.1145/212094.212131]
• 2: 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]
• 3: Josep M. Codina , Josep Llosa , Antonio González, A comparative study of modulo scheduling techniques, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514208]
• 4: 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
• 5: 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]
• 6: 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
• 7: Equator technologies. MAP1000 unfolds at Equator. Microprocessor report, 129160, Dec. 1998.
• 8: Paolo Faraboschi , Geoffrey Brown , Joseph A. Fisher , Giuseppe Desoli , Fred Homewood, Lx: a technology platform for customizable VLIW embedded processing, Proceedings of the 27th annual international symposium on Computer architecture, p.203-213, June 2000, Vancouver, British Columbia, Canada
• 9: Joseph A. Fisher , Paolo Faraboschi , Giuseppe Desoli, Custom-fit processors: letting applications define architectures, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.324-335, December 02-04, 1996, Paris, France
• 10: 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
• 11: Intel Corporation, Intel IA-64 Architecture Software Developer's Manual Volume 1: Application Architecture, Jan. 2000.
• 12: 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
• 13: Daniel M. Lavery , Wen-mei W. Hwu, Modulo scheduling of loops in control-intensive non-numeric programs, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.126-137, December 02-04, 1996, Paris, France
• 14: 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
• 15: Matthew C. Merten , Wen-mei W. Hwu, Modulo schedule buffers, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 16: S. Ramakrishnan. Software pipelining in PA-RISC compilers. Hewlett-Packard Journal, pp. 39--45, July 1992.
• 17: 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]
• 18: 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
• 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: Texas Instruments. TMS320C6000 CPU and instruction set reference guide. March 1999.
• 21: 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
• 22: Nancy J. Warter , Grant E. Haab , Krishna Subramanian , John W. Bockhaus, Enhanced modulo scheduling for loops with conditional branches, Proceedings of the 25th annual international symposium on Microarchitecture, p.170-179, December 01-04, 1992, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

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

  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.2 Hardware

General Terms:
Performance, Reliability