Modulo scheduling without overlapped lifetimes

ABSTRACT

This paper describes complementary software- and hardware-based approaches for handling overlapping register lifetimes that occur in modulo scheduled loops. Modulo scheduling takes the N-instructions in a loop body and constructs an M-stage software pipeline. The length of each stage in the software pipeline is the Initiation Interval (II), which is the rate at which new loop iterations are started. An overlapped lifetime has a live range longer than the II, and as a consequence, the current iteration writes a new value to a register before a previous loop iteration has fin-ished using the old value. Hardware and software solutions for dealing with overlapped lifetimes have been proposed by re-searchers and also implemented in commercial products. These solutions include rotating register files, register queues, modulo variable expansion, and post-scheduling live range splitting. Each of these approaches has drawbacks for embedded systems such as an increase in silicon area, power consumption, and code size.

Our approach, which is an improvement to the current solutions, prevents overlapped lifetimes through a combination of hardware and software techniques. The hardware element of our approach implements a register assignment latency that allows multiple in-flight writes to be pending to the same register. The software element of our approach uses dependence analysis and a constrained modulo scheduling algorithm to prevent overlapped lifetimes. We describe how to use these hardware and software techniques during modulo scheduling. Finally, we present the results of using our approach to compile embedded application code and present results in terms of modulo schedule quality and application performance.

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: 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: 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]
• 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: Partitioned Schedules for Clustered VLIW Architectures, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.386, March 30-April 03, 1998
• 6: E. Granston, R. Scales, E. Stotzer, A. Ward, and J. Zbiciak. Controlling code size of software-pipelined loops on the TMS320C6000 VLIW DSP architecture. In Proc. of the 3rd Workshop on Media and Streaming Processors held in conjunction with MICRO-34, pages 29--38, Dec. 2001.
• 7: Jerry Huck , Dale Morris , Jonathan Ross , Allan Knies , Hans Mulder , Rumi Zahir, Introducing the IA-64 Architecture, IEEE Micro, v.20 n.5, p.12-23, September 2000 [doi>10.1109/40.877947]
• 8: 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
• 9: 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
• 10: Ernst L. Leiss, Parallel and vector computing: a practical introduction, McGraw-Hill, Inc., New York, NY, 1995
• 11: 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
• 12: Josep Llosa , Stefan M. Freudenberger, Reduced code size modulo scheduling in the absence of hardware support, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 13: 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
• 14: Janak H. Patel , Edward S. Davidson, Improving the throughput of a pipeline by insertion of delays, Proceedings of the 3rd annual symposium on Computer architecture, p.159-164, January 19-21, 1976
• 15: 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
• 16: 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
• 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: Eric Stotzer , Ernst Leiss, Modulo scheduling for the TMS320C6x VLIW DSP architecture, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.28-34, May 05-05, 1999, Atlanta, Georgia, United States
• 19: Texas Instruments, Inc., TMS320C674x DSP CPU Instruction Set User's Guide, (literature number sprufe8), Oct. 2008.
• 20: Texas Instruments Inc., TMS320C6000 Optimizing Compiler User's Guide, (literature number spru187o), May 2008.
• 21: Gary S. Tyson , Mikhail Smelyanskiy , Edward S. Davidson, Evaluating the Use of Register Queues in Software Pipelined Loops, IEEE Transactions on Computers, v.50 n.8, p.769-783, August 2001 [doi>10.1109/12.946998]
• 22: Javier Zalamea , Josep Llosa , Eduard Ayguadé , Mateo Valero, Register Constrained Modulo Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.15 n.5, p.417-430, May 2004 [doi>10.1109/TPDS.2004.1278099]
• 23: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM, New York, NY, 1990

INDEX TERMS

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

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: Code generation; Optimization

General Terms:
Algorithms, Languages, Performance

Keywords:
instruction level parallelism, modulo scheduling, register allocation, software pipelining