Auto-vectorization of interleaved data for SIMD

ABSTRACT

Most implementations of the Single Instruction Multiple Data (SIMD) model available today require that data elements be packed in vector registers. Operations on disjoint vector elements are not supported directly and require explicit data reorganization manipulations. Computations on non-contiguous and especially interleaved data appear in important applications, which can greatly benefit from SIMD instructions once the data is reorganized properly. Vectorizing such computations efficiently is therefore an ambitious challenge for both programmers and vectorizing compilers. We demonstrate an automatic compilation scheme that supports effective vectorization in the presence of interleaved data with constant strides that are powers of 2, facilitating data reorganization. We demonstrate how our vectorization scheme applies to dominant SIMD architectures, and present experimental results on a wide range of key kernels, showing speedups in execution time up to 3.7 for interleaving levels (stride) as high as 8.

REFERENCES

• 1: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 2: Krste Asanovic , David Johnson, Torrent Architecture Manual, University of California at Berkeley, Berkeley, CA, 1997
• 3: Leonardo Bachega , Siddhartha Chatterjee , Kenneth A. Dockser , John A. Gunnels , Manish Gupta , Fred G. Gustavson , Christopher A. Lapkowski , Gary K. Liu , Mark P. Mendell , Charles D. Wait , T. J. Chris Ward, A High-Performance SIMD Floating Point Unit for BlueGene/L: Architecture, Compilation, and Algorithm Design, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.85-96, September 29-October 03, 2004 [doi>10.1109/PACT.2004.2]
• 4: A. J. C. Bik, M. Girkar, P. M. Grey, and X. Tian. Efficient exploitation of parallelism on Pentium III and Pentium 4 processor-based systems. Intel Technology J., February 2001.
• 5: Aart J. C. Bik, Software Vectorization Handbook, The: Applying Intel Multimedia Extensions for Maximum Performance, Intel Press, 2004
• 6: Jesus Corbal , Mateo Valero , Roger Espasa, Exploiting a new level of DLP in multimedia applications, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.72-79, November 16-18, 1999, Haifa, Israel
• 7: P. D'Arcy and S. Beach. StarCore SC140: A New DSP Architecture for Portable Devices. In Wireless Symposium. Motorola, September 1999.
• 8: Keith Diefendorff , Pradeep K. Dubey , Ron Hochsprung , Hunter Scales, AltiVec Extension to PowerPC Accelerates Media Processing, IEEE Micro, v.20 n.2, p.85-95, March 2000 [doi>10.1109/40.848475]
• 9: 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
• 10: Roger Espasa , Federico Ardanaz , Joel Emer , Stephen Felix , Julio Gago , Roger Gramunt , Isaac Hernandez , Toni Juan , Geoff Lowney , Matthew Mattina , André Seznec, Tarantula: a vector extension to the alpha architecture, Proceedings of the 29th annual international symposium on Computer architecture, p.281, May 25-29, 2002, Anchorage, Alaska
• 11: Free Software Foundation. Auto-Vectorization in GCC, http://gcc.gnu.org/projects/tree-ssa/vectorization.html.
• 12: Free Software Foundation. GCC, http://gcc.gnu.org.
• 13: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
• 14: Texas Instruments. www.ti.com/sc/c6x, 2000.
• 15: J. A. Kahle , M. N. Day , H. P. Hofstee , C. R. Johns , T. R. Maeurer , D. Shippy, Introduction to the cell multiprocessor, IBM Journal of Research and Development, v.49 n.4/5, p.589-604, July 2005
• 16: Alexei Kudriavtsev , Peter Kogge, Generation of permutations for SIMD processors, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 17: 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
• 18: J. Lorenz, S. Kral, F. Franchetti, and C. W. Ueberhuber. Vectorization Techniques for the BlueGene/L Double FPU. IBM Journal of Research and Development, 49(2-3), pages 437--446, March/May 2005.
• 19: J. Merrill. Generic and Gimple: A New Tree Representation for Entire Functions. In the GCC Developer's summit, pages 171--180, June 2003.
• 20: 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
• 21: 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]
• 22: Dorit Nuzman , Richard Henderson, Multi-platform Auto-vectorization, Proceedings of the International Symposium on Code Generation and Optimization, p.281-294, March 26-29, 2006 [doi>10.1109/CGO.2006.25]
• 23: Huy Nguyen , Lizy Kurian John, Exploiting SIMD parallelism in DSP and multimedia algorithms using the AltiVec technology, Proceedings of the 13th international conference on Supercomputing, p.11-20, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305150]
• 24: D. Novillo. Tree SSA - a New Optimization Infrastructure for GCC. In Proc. of the GCC Developers Summit, pages 181--194, June 2003.
• 25: Alex Peleg , Uri Weiser, MMX Technology Extension to the Intel Architecture, IEEE Micro, v.16 n.4, p.42-50, August 1996 [doi>10.1109/40.526924]
• 26: Gilles Pokam , Stéphane Bihan , Julien Simonnet , François Bodin, SWARP: a retargetable preprocessor for multimedia instructions: Research Articles, Concurrency and Computation: Practice & Experience, v.16 n.2-3, p.303-318, February 2004 [doi>10.1002/cpe.v16:2/3]
• 27: S. Pop, G. Silber, A. Cohen, P. Clauss, and V. Loechner. Fast Recognition of Scalar Evolutions on Three-address SSA Code. Research Report A/354/CRI, CRI/ENSMP, April 2004.
• 28: S. Pop, A. Cohen, and G. Silber. Induction Variable Analysis with Delayed Abstractions. In Proc. of the First International Conference of High Performance Embedded Architectures and Compilers (HiPEAC), pages 218--232, November 2005.
• 29: I. Pryanishnikov, A. Krall, and N. Horspool. Pointer Alignment Analysis for Processors with SIMD Instructions. In Proc. of the 5th Workshop on Media and Streaming Processors at Micro '03, pages 50--57, December 2003.
• 30: G. Ren, P. Wu, and D. Padua. A Preliminary Study on the Vectorization of Multimedia Applications for Multimedia Extensions. In 16th International Workshop of Languages and Compilers for Parallel Computing (LCPC), pages 420 -- 435, October 2003.
• 31: Gang Ren , Peng Wu , David Padua, Optimizing data permutations for SIMD devices, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 32: 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
• 33: Jaewook Shin , Mary Hall , Jacqueline Chame, Superword-Level Parallelism in the Presence of Control Flow, Proceedings of the international symposium on Code generation and optimization, p.165-175, March 20-23, 2005 [doi>10.1109/CGO.2005.33]
• 34: K. B. Smith, A. J. Bik, and X. Tian. Support for the Intel Pentium 4 Processor with Hyper-threading Technology in Intel 8.0 Compilers. Intel Technology Journal, 8(1), pages 19--31, February 2004.
• 35: Deepu Talla , Lizy Kurian John , Doug Burger, Bottlenecks in Multimedia Processing with SIMD Style Extensions and Architectural Enhancements, IEEE Transactions on Computers, v.52 n.8, p.1015-1031, August 2003 [doi>10.1109/TC.2003.1223637]
• 36: Crecent Bay Software. VAST-F/ALtivec: Automatic Fortran Vectorizer for PowerPC Vector Unit, http://www.crescentbaysoftware.com/docs/vastfav.pdf.
• 37: Crecent Bay Software. Vast/altivec faq: Vectorization for Altivec, http://www.crescentbaysoftware.com/altivec_FAQ.html.
• 38: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 39: Peng Wu , Alexandre E. Eichenberger , Amy Wang, Efficient SIMD Code Generation for Runtime Alignment and Length Conversion, Proceedings of the international symposium on Code generation and optimization, p.153-164, March 20-23, 2005 [doi>10.1109/CGO.2005.18]

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
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

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

General Terms:
Algorithms, Performance

Keywords:
SIMD, Viterbi, data reuse, subword parallelism, vectorization