Complementing software pipelining with software thread integration

ABSTRACT

Software pipelining is a critical optimization for producing efficient code for VLIW/EPIC and superscalar processors in high-performance embedded applications such as digital signal processing. Software thread integration (STI) can often improve the performance of looping code in cases where software pipelining performs poorly or fails. This paper examines both situations, presenting methods to determine what and when to integrate.We evaluate our methods on C-language image and digital signal processing libraries and synthetic loop kernels. We compile them for a very long instruction word (VLIW) digital signal processor (DSP) -- the Texas Instruments (TI) C64x architecture. Loops which benefit little from software pipelining (SWP-Poor) speed up by 26% (harmonic mean, HM). Loops for which software pipelining fails (SWP-Fail) due to conditionals and calls speed up by 16% (HM). Combining SWP-Good and SWP-Poor loops leads to a speedup of 55% (HM).

REFERENCES

• 1: 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
• 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: Gérard Berry , Georges Gonthier, The ESTEREL synchronous programming language: design, semantics, implementation, Science of Computer Programming, v.19 n.2, p.87-152, Nov. 1992 [doi>10.1016/0167-6423(92)90005-V]
• 4: David Callahan , John Cocke , Ken Kennedy, Estimating interlock and improving balance for pipelined architectures, Journal of Parallel and Distributed Computing, v.5 n.4, p.334-358, August 1988 [doi>10.1016/0743-7315(88)90002-0]
• 5: Steve Carr , Chen Ding , Philip Sweany, Improving Software Pipelining With Unroll-and-Jam, Proceedings of the 29th Hawaii International Conference on System Sciences (HICSS'96) Volume 1: Software Technology and Architecture, p.183, January 03-06, 1996
• 6: Steve Carr , Yiping Guan, Unroll-and-jam using uniformly generated sets, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.349-357, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 7: K. D. Cooper, M. W. Hall, and K. Kennedy. A methodology for procedure cloning. Computer Languages, 19(2):105--117, 1993.
• 8: Alexander G. Dean, Compiling for Fine-Grain Concurrency: Planning and Performing Software Thread Integration, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.103, December 03-05, 2002
• 9: A. G. Dean , J. P. Shen, Techniques for Software Thread Integration in Real-Time Embedded Systems, Proceedings of the IEEE Real-Time Systems Symposium, p.322, December 02-04, 1998
• 10: Alexander G. Dean , John Paul Shen, System-Level Issues for Software Thread Integration: Guest Triggering and Host Selection, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.234, December 01-03, 1999
• 11: Jeffrey Dean , Craig Chambers , David Grove, Selective specialization for object-oriented languages, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.93-102, June 18-21, 1995, La Jolla, California, United States
• 12: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 13: Thierry Gautier , Paul Le Guernic , Löic Besnard, SIGNAL: A declarative language for synchronous programming of real-time systems, Proc. of a conference on Functional programming languages and computer architecture, p.257-277, October 1987, Portland, Oregon, United States
• 14: Michael I. Gordon , William Thies , Michal Karczmarek , Jasper Lin , Ali S. Meli , Andrew A. Lamb , Chris Leger , Jeremy Wong , Henry Hoffmann , David Maze , Saman Amarasinghe, A stream compiler for communication-exposed architectures, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 15: 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 Proceedings of the 3rd Workshop on Media and Stream Processors, Dec. 2001.
• 16: N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud. The synchronous data-flow programming language LUSTRE. Proceedings of the IEEE, 79(9):1305--1320, September 1991.
• 17: Mary W. Hall , John M. Mellor-Crummey , Alan Carle , René G. Rodríguez, FIAT: A Framework for Interprocedural Analysis and Transfomation, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.522-545, August 12-14, 1993
• 18: Mary W. Hall , Brian R. Murphy , Saman P. Amarasinghe , Shih-Wei Liao , Monica S. Lam, Interprocedural Analysis for Parallelization, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.61-80, August 10-12, 1995
• 19: 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
• 20: Brucek Khailany , William J. Dally , Ujval J. Kapasi , Peter Mattson , Jinyung Namkoong , John D. Owens , Brian Towles , Andrew Chang , Scott Rixner, Imagine: Media Processing with Streams, IEEE Micro, v.21 n.2, p.35-46, March 2001 [doi>10.1109/40.918001]
• 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: 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
• 23: M. Narayanan and K. A. Yelick. Generating permutation instructions from a high-level description. In Proceedings of the 6th Workshop on Media and Streaming Processors, 2004.
• 24: A. Nene, S. Talla, B. Goldberg, and R. Rabbah. Trimaran - an infrastructure for compiler research in instruction-level parallelism - user manual. New York University, 1998.
• 25: Satish Pillai , Margarida F. Jacome, Compiler-Directed ILP Extraction for Clustered VLIW/EPIC Machines: Predication, Speculation and Modulo Scheduling, Proceedings of the conference on Design, Automation and Test in Europe, p.10422, March 03-07, 2003
• 26: Yi Qian , Steve Carr , Philip Sweany, Loop fusion for clustered VLIW architectures, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 27: Yi Qian , Steve Carr , Philip H. Sweany, Optimizing Loop Performance for Clustered VLIW Architectures, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.271-280, September 22-25, 2002
• 28: Won So , Alex Dean, Procedure Cloning and Integration for Converting Parallelism from Coarse to Fine Grain, Proceedings of the Seventh Workshop on Interaction between Compilers and Computer Architectures, p.27, February 08-08, 2003
• 29: R. Stephens. A survey of stream processing. Acta Informatica, 34(7):491--541, 1997.
• 30: Mark G. Stoodley , Corinna G. Lee, Software pipelining loops with conditional branches, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.262-273, December 02-04, 1996, Paris, France
• 31: 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
• 32: Bogong Su , Shiyuan Ding , Jian Wang , Jinshi Xia, GURPR—a method for global software pipelining, Proceedings of the 20th annual workshop on Microprogramming, p.88-96, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255322]
• 33: Michael Bedford Taylor , Jason Kim , Jason Miller , David Wentzlaff , Fae Ghodrat , Ben Greenwald , Henry Hoffman , Paul Johnson , Jae-Wook Lee , Walter Lee , Albert Ma , Arvind Saraf , Mark Seneski , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs, IEEE Micro, v.22 n.2, p.25-35, March 2002 [doi>10.1109/MM.2002.997877]
• 34: Texas Instruments. Code Composer Studio User's Guide (Rev. B), Mar. 2000.
• 35: Texas Instruments. TMS320C6000 CPU and Instruction Set Reference Guide, Sept. 2000.
• 36: Texas Instruments. TMS320C64x Technical Overview, Jan. 2001.
• 37: Texas Instruments. TMS320C64x DSP Library Programmer's Reference, Apr. 2002.
• 38: Texas Instruments. TMS320C64x Image/Video Processing Library Programmer's Reference, Apr. 2002.
• 39: Texas Instruments. TMS320C6000 DSP Peripherals Overview Reference Guide (Rev. G), Sept. 2004.
• 40: William Thies , Michal Karczmarek , Saman P. Amarasinghe, StreamIt: A Language for Streaming Applications, Proceedings of the 11th International Conference on Compiler Construction, p.179-196, April 08-12, 2002
• 41: 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
• 42: 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
• 43: Nancy J. Warter-Perez , Noubar Partamian, Modulo scheduling with multiple initiation intervals, Proceedings of the 28th annual international symposium on Microarchitecture, p.111-119, November 29-December 01, 1995, Ann Arbor, Michigan, United States

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
DSP, TI C6000, VLIW, coarse-grain parallelism, software pipelining, software thread integration, stream programming