Improving superword level parallelism support in modern compilers

ABSTRACT

Multimedia vector instruction sets are becoming ubiquitous in most of the embedded systems used for multimedia, networking and communications. However, current compiler technology do not allow for an efficient exploitation of the inherent data parallelism available in many signal processing and multimedia applications. In this paper, we have explored the automatic vectorization of embedded applications. In particular, we have focused on algorithms in which the same computations are applied over a set of signals that are being processed simultaneously. Usually this set of signals is represented as a 2D array in which each row is an input signal that has to be filtered in some way. A motivating example, inspired by VoIP processing, illustrates that state-of-the-art vectorizing compilers inefficiently exploit the data parallelism inherent to this kind of applications. One of the main reasons behind this, is that they present inner loops that carry all the dependencies and external loops with strided memory accesses.We propose a modification of the Superword Level Parallelism (SLP) compiler, proposed in [9], that tries to overcome these problems. Experimental results show that our approach clearly outperforms commercial compilers.

REFERENCES

• 1: Arm11 family. http://www.arm.com/products/CPUs/families/ARM11Family.html.
• 2: A. Bik, M. Girkar, P. Grey, and X. Tian. Efficient exploitation of parallelism on pentium iii and pentium 4 processor-based systems. Intel Technology Journal, 2001.
• 3: I. Corpation. Intel c/c++ and intel fortran compilers for linux. Available at http://www.intel.com/software/products/compilers.
• 4: S. Fuller. Motorola's AltiVec technology. Technical Report ALTIVECWP/D, MOTOROLA, 1998.
• 5: H. Peter Hofstee, Power Efficient Processor Architecture and The Cell Processor, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.258-262, February 12-16, 2005 [doi>10.1109/HPCA.2005.26]
• 6: Mahmut Kandemir , Alok Choudhary , Nagaraj Shenoy , Prithviraj Banerjee , J. Ramanujam, A Linear Algebra Framework for Automatic Determination of Optimal Data Layouts, IEEE Transactions on Parallel and Distributed Systems, v.10 n.2, p.115-135, February 1999 [doi>10.1109/71.752779]
• 7: Andreas Krall , Sylvain Lelait, Compilation Techniques for Multimedia Processors, International Journal of Parallel Programming, v.28 n.4, p.347-361, August 2000 [doi>10.1023/A:1007507005174]
• 8: K. Krewell. Cell moves into the limelight. Microprocessor Report, (2/14/05-01), February 2005.
• 9: Samuel Larsen , Saman Amarasinghe, Exploiting superword level parallelism with multimedia instruction sets, ACM SIGPLAN Notices, v.35 n.5, p.145-156, May 2000
• 10: S. Larsen, E. Witchel, and S. Amarasinghe. Techniques for increasing and detecting memory alignment. Technical Report MIT-LCS-TM-621, MIT, USA, 2001.
• 11: 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
• 12: Shreekant (Ticky) Thakkar , Tom Huff, Internet Streaming SIMD Extensions, Computer, v.32 n.12, p.26-34, December 1999 [doi>10.1109/2.809248]
• 13: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990

INDEX TERMS

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

General Terms:
Algorithms, Languages, Performance

Keywords:
FIR, automatic vectorization, superword level parallelism