Compiling for an indirect vector register architecture

ABSTRACT

The iVMX architecture contains a novel vector register file of up to 4096 vector registers accessed indirectly via a mapping mechanism, providing compatibility with the VMX architecture, and potential for dramatic performance benefits [7]. The large number of vector registers and the unique indirection mechanism pose compilation challenges to be used efficiently: the indirection mechanism emphasizes spatial locality of registers and interaction among destination and source operands during register allocation, and the many vector registers call for aggressive automatic vectorization.

This work is a first step in addressing the compilability of iVMX, following the presentation and validation of its architectural aspects [7]. In this paper we present several compilation approaches to deal with the mapping mechanism and an outer-loop vectorization transformation developed to promote the use of many vector registers. We modified an existing register allocator to target all available registers and added a post-pass to rename live-ranges considering spatial locality and interaction among operand types. An FIR filter is used to demonstrate the effectiveness of the techniques developed compared to a version hand-optimized for iVMX. Initial results show that we can reduce the overhead of map management down to 29% of the total instruction count, compared to 22% obtained manually, and compared to 49% obtained using a naive scheme, while outperforming an equivalent VMX implementation by a factor of 2.

REFERENCES

• 1: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 2: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 3: Aart J. C. Bik, Software Vectorization Handbook, The: Applying Intel Multimedia Extensions for Maximum Performance, Intel Press, 2004
• 4: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 5: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 6: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 7: Jeff H. Derby , Robert K. Montoye , José Moreira, VICTORIA: VMX indirect compute technology oriented towards in-line acceleration, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128062]
• 8: J. H. Derby and J. H. Moreno. A high-performance embedded dsp core with novel simd features. In ICASSP, 2003.
• 9: Free Software Foundation. gcc.gnu.org/projects/tree-ssa/vectorization.html.
• 10: Freescale Semiconductor, http://www.freescale.com. Altivec real fir, October 2002.
• 11: Hillery C. Hunter , Jaime H. Moreno, A new look at exploiting data parallelism in embedded systems, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951733]
• 12: Suhyun Kim , Soo-Mook Moon, Rotating Register Allocation for Enhanced Pipeline Scheduling, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.60-72, September 15-19, 2007 [doi>10.1109/PACT.2007.61]
• 13: J. H. Moreno , V. Zyuban , U. Shvadron , F. D. Neeser , J. H. Derby , M. S. Ware , K. Kailas , A. Zaks , A. Geva , S. Ben-David , S. W. Asaad , T. W. Fox , D. Littrell , M. Biberstein , D. Naishlos , H. Hunter, An innovative low-power high-performance programmable signal processor for digital communications, IBM Journal of Research and Development, v.47 n.2-3, p.299-326, March 2003
• 14: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 15: D. Naishlos. Autovectorization in gcc. In GCC Developer?s summit, pages 105--118, June 2004.
• 16: Dorit Naishlos , Marina Biberstein , Shay Ben-David , Ayal Zaks, Vectorizing for a SIMdD DSP architecture, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951714]
• 17: M. Namolaru. Register allocation techniques for ivmx architecture. In Int?l Workshop on GCC for Research in Embedded and Parallel Systems, September 2007.
• 18: D. Nuzman and A. Zaks. Autovectorization in gcc - two years later. In GCC Developer?s summit, June 2006.
• 19: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Efficient Utilization of Scratch-Pad Memory in Embedded Processor Applications, Proceedings of the 1997 European conference on Design and Test, p.7, March 17-20, 1997
• 20: Matthew Allan Postiff , Trevor Mudge, Compiler and microarchitecture mechanisms for exploiting registers to improve memory performance, University of Michigan, Ann Arbor, MI, 2001
• 21: Randolf G Scarborough , Harwood G Kolsky, A vectorizing Fortran compiler, IBM Journal of Research and Development, v.30 n.2, p.163-171, March 1986
• 22: Jaewook Shin , Jacqueline Chame , Mary W. Hall, Compiler-Controlled Caching in Superword Register Files for Multimedia Extension Architectures, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.45-55, September 22-25, 2002
• 23: N. Sreraman , R. Govindarajan, A vectorizing compiler for multimedia extensions, International Journal of Parallel Programming, v.28 n.4, p.363-400, Aug. 2000 [doi>10.1023/A:1007559022013]
• 24: C. Tenllado, L. Piñuel, M. Prieto, and F. Catthoor. Pack transposition: Enhancing superword level parallelism exploitation. In Parallel Computing, 2005.
• 25: Christian Tenllado , Luis Piñuel , Manuel Prieto , Francisco Tirado , F. Catthoor, Improving superword level parallelism support in modern compilers, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084909]
• 26: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 27: Peng Wu , Alexandre E. Eichenberger , Amy Wang , Peng Zhao, An integrated simdization framework using virtual vectors, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088172]

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: Optimization

General Terms:
Algorithms, Performance

Keywords:
compiler controlled cache, data reuse, rotating register file, simd, subword parallelism, vectorization, viterbi