Affinity-based cluster assignment for unrolled loops

ABSTRACT

To compete performance-wise, modern VLIW processors must have fast clock rates and high instruction-level parallelism (ILP). Partitioning resources (functional units and registers) into clusters allows the processor to be clocked faster, but operand transfers across clusters can easily become a bottleneck. Increasing the number of functional units increases the potential ILP, but only helps if the functional units can be kept busy.To support these features, optimizations such as loop unrolling must be applied to expose ILP, and instructions must be explicitly assigned to clusters to minimize cross-cluster transfers. In an architecture with homogeneous clusters, the number of functional units of a given type is typically a multiple of the number of clusters. Thus, it is common to unroll a loop so that the number of copies of the loop body is a multiple of the number of clusters. The result is that there is a natural mapping of instructions to clusters, which is often the best mapping. While this mapping can be obvious by inspection, we have found that existing cluster assignment algorithms often miss this natural split. The consequence is an excessive number of inter-cluster transfers, which slows down the loop.Because we were unable to find an existing cluster-assignment algorithm that performed well for unrolled loops, we developed our own. Our Affinity-Based Clustering (ABC) algorithm has been implemented in a production compiler for the Texas Instruments TMS320C6000, a two-cluster VLIW architecture. It is tailored for exploiting the patterns that result from either manual or compiler-based unrolling. As demonstrated experimentally, it performs well, even when post-unrolling optimizations partially obscure the natural split.

REFERENCES

• 1: Alex Aletà , Josep M. Codina , Jesús Sánchez , Antonio González, Graph-partitioning based instruction scheduling for clustered processors, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 2: Andrea Capitanio , Nikil Dutt , Alexandru Nicolau, Partitioned register files for VLIWs: a preliminary analysis of tradeoffs, Proceedings of the 25th annual international symposium on Microarchitecture, p.292-300, December 01-04, 1992, Portland, Oregon, United States
• 3: Josep M. Codina , Jesús Sánchez , Antonio González, A Unified Modulo Scheduling and Register Allocation Technique for Clustered Processors, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.175-184, September 08-12, 2001
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: Desoli, G., "Instruction Assignment for Clustered VLIW DSP Compilers: A New Approach". Technical Report HPL-98-13, Hewlett-Packard Laboratories, Jan. 1998.
• 6: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 7: 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
• 8: Krishnan Kailas , Ashok Agrawala , Kemal Ebcioglu, CARS: A New Code Generation Framework for Clustered ILP Processors, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.133, January 20-24, 2001
• 9: Kuras, D., S. Carr, and P. Sweany, "Value Cloning for Architectures with Partitioned Register Banks". The 1998 Workshop on Compiler Support for Embedded Systems (CASES '98), Dec. 1998.
• 10: 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
• 11: P. Geoffrey Lowney , Stefan M. Freudenberger , Thomas J. Karzes , W. D. Lichtenstein , Robert P. Nix , John S. O'Donnell , John Ruttenberg, The multiflow trace scheduling compiler, The Journal of Supercomputing, v.7 n.1-2, p.51-142, May 1993 [doi>10.1007/BF01205182]
• 12: 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
• 13: 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
• 14: 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
• 15: 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
• 16: 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
• 17: Texas Instruments, Inc., TMS320C6000 CPU and Instruction Set Reference Guide, (literature number SPRU189), 2000.

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, Performance

Keywords:
VLIW architectures, affinity-based clustering (ABC) algorithms, cluster assignment, homogeneous clusters, loop optimizations, loop scheduling, loop unrolling, partitioned register files, software pipelining