Loop fusion for clustered VLIW architectures

ABSTRACT

Embedded systems require maximum performance from a processor within significant constraints in power consumption and chip cost. Using software pipelining, high-performance digital signal processors can often exploit considerable instruction-level parallelism (ILP), and thus significantly improve performance. However, software pipelining, in some instances, hinders the goals of low power consumption and low chip cost. Specifically, the registers required by a software pipelined loop may exceed the size of the physical register set.The register pressure problem incurred by software pipelining makes it difficult to build a high-performance embedded processor with a single, multi-ported register bank with enough registers to support high levels of ILP while maintaining clock speed and limiting power consumption. The large number of ports required to support a single register bank severely hampers access time. The port requirement for a register bank can be reduced via hardware by partitioning the register bank into multiple banks connected to disjoint subsets of functional units, called clusters. Since a functional unit is not directly connected to all register banks, wasted energy and resources can result due to delays incurred when accessing "non-local" registers.The overhead due to partitioning of the register set can be ameliorated by using high-level compiler loop optimization techniques such as unrolling, unroll-and-jam and fusion. High-level loop optimizations spread data-independent parallelism across clusters that may not require "non-local" register accesses and can provide work to hide the latency of any such register accesses that are needed.In this paper, we examine the effects of loop fusion on DSP loops run on four simulated, clustered VLIW architectures and the Texas Instruments TMS320C64x. Our experiments show a 1.3 -- 2 harmonic mean speedup.

REFERENCES

• 1: Vikram S. Adve , John Mellor-Crummey , Mark Anderson , Jhy-Chun Wang , Daniel A. Reed , Ken Kennedy, An integrated compilation and performance analysis environment for data parallel programs, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.50-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224340]
• 2: 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
• 3: 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]
• 4: Vicki H. Allan , M. Rajagopalan , Randall M. Lee, Software Pipelining: Petri Net Pacemaker, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.15-26, January 20-22, 1993
• 5: R. Allen and K. Kennedy. Advanced compilation for vector and parallel computers. Morgan Kaufmann Publishers, San Mateo CA
• 6: P. Briggs , K. D. Cooper , K. Kennedy , L. Torczon, Coloring heuristics for register allocation, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.275-284, June 19-23, 1989, Portland, Oregon, United States
• 7: Steve Carr , Ken Kennedy, Improving the ratio of memory operations to floating-point operations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1768-1810, Nov. 1994 [doi>10.1145/197320.197366]
• 8: J. R. Ellis. A Compiler for VLIW Architectures. PhD thesis, Yale University, 1984
• 9: Jason Hiser , Steve Carr , Philip Sweany, Global Register Partitioning, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.13, October 15-19, 2000
• 10: Register Assignment for Software Pipelining with Partitioned Register Banks, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.211, May 01-05, 2000
• 11: Xianglong Huang , Steve Carr , Philip Sweany, Loop Transformations for Architectures with Partitioned Register Banks, Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, p.48-55, August 2001, Snow Bird, Utah, United States
• 12: Ken Kennedy , Kathryn S. McKinley, Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.301-320, August 12-14, 1993
• 13: D. Kuras, S. Carr, and P. Sweany. Value cloning for architectures with partitioned register banks. In The 1998 Worshop on Compiler and Architecture Support for Embedded Systems, Washington D.C., December 1998
• 14: 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
• 15: Erik Nystrom , Alexandre E. Eichenberger, Effective cluster assignment for modulo scheduling, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.103-114, November 1998, Dallas, Texas, United States
• 16: Emre Özer , Sanjeev Banerjia , Thomas M. Conte, Unified assign and schedule: a new approach to scheduling for clustered register file microarchitectures, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.308-315, November 1998, Dallas, Texas, United States
• 17: D. Poplawski. The unlimited resource machine (URM). Technical Report 95-01, Michigan Technological University, Jan. 1995
• 18: 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]
• 19: Jesús Sánchez , Antonio González, The Effectiveness of Loop Unrolling for Modulo Scheduling in Clustered VLIW Architectures, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.555, August 21-24, 2000
• 20: Jesús Sánchez , Antonio González, Instruction scheduling for clustered VLIW architectures, Proceedings of the 13th international symposium on System synthesis, September 20-22, 2000, Madrid, Spain [doi>10.1145/501790.501801]
• 21: P. H. Sweany and S. J. Beaty. Overview of the Rocket retargetable C compiler. Technical Report CS-94-01, Department of Computer Science, Michigan Technological University, Houghton, January 1994
• 22: Texas Instruments. TMS320C6000 CPU and Instruction Set Reference Guide, 2000. literature number SPRU189
• 23: Texas Instruments. TMS320C6000 Optimizing Compiler User's Guide, 2000. literature number SPRU187

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

General Terms:
Languages

Keywords:
clustered VLIW architectures, loop fusion