Generation of permutations for SIMD processors

ABSTRACT

Short vector (SIMD) instructions are useful in signal processing, multimedia, and scientific applications. They offer higher performance, lower energy consumption, and better resource utilization. However, compilers still do not have good support for SIMD instructions, and often the code has to be written manually in assembly language or using compiler builtin functions. Also, in some applications, higher parallelism could be achieved if compilers inserted permutation instructions that reorder the data in registers. In this paper we describe how we create SIMD instructions from regular code, and determine ordering of individual operations in the SIMD instructions to minimize the number of permutation instructions. Individual memory operations are grouped into SIMD operations based on their effective addresses. The SIMD data flow graph is then constructed by following data dependences from SIMD memory operations. Then, the orderings of operations are propagated from SIMD memory operations into the graph.We also describe our approach to compute decomposition of a given permutation into the permutation instructions of the target architecture. Experiments with our prototype compiler show that this approach scales well with the number of operations in SIMD instructions (SIMD width) and can be used to compile a number of important kernels, achieving up to 35% speedup.

REFERENCES

• 1: Alfred V. Aho , Mahadevan Ganapathi , Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.491-516, Oct. 1989 [doi>10.1145/69558.75700]
• 2: Alexandre E. Eichenberger , Peng Wu , Kevin O'Brien, Vectorization for SIMD architectures with alignment constraints, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 3: Randall J. Fisher , Henry G. Dietz, Compiling for SIMD Within a Register, Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing, p.290-304, August 07-09, 1998
• 4: Intel Corporation. Intel® C++ Compiler for Linux* Systems User's Guide, 2003.
• 5: Samuel Larsen , Saman Amarasinghe, Exploiting superword level parallelism with multimedia instruction sets, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.145-156, June 18-21, 2000, Vancouver, British Columbia, Canada
• 6: Samuel Larsen , Emmett Witchel , Saman P. Amarasinghe, Increasing and Detecting Memory Address Congruence, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.18-29, September 22-25, 2002
• 7: Rainer Leupers, Code Optimization Techniques for Embedded Processors: Methods, Algorithms, and Tools, Kluwer Academic Publishers, Norwell, MA, 2000
• 8: Rainer Leupers, Code selection for media processors with SIMD instructions, Proceedings of the conference on Design, automation and test in Europe, p.4-8, March 27-30, 2000, Paris, France [doi>10.1145/343647.343679]
• 9: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 10: 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]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
SIMD, permutations