An integrated simdization framework using virtual vectors

ABSTRACT

Automatic simdization for multimedia extensions faces several new challenges that are not present in traditional vectorization. Some of the new issues are due to the more restrictive SIMD architectures designed for multimedia extensions. Among them are alignment constraints, lack of memory gather and scatter support, and the short and fixed-length nature of SIMD vectors. Since these constraints affect some very basic components of a program, a compiler must not only provide solid solutions to individual issues, but also take an integrated approach to address these constraints in combination.In this paper, we propose a simdization framework that addresses several orthogonal aspects of simdization, such as alignment handling, simdization of loops with mixed data lengths, and SIMD parallelism extraction from different program scopes (from basic blocks to inner loops). The novelty of this framework is its ability to facilitate interactions between different techniques based on the simple intermediate representation of virtual vectors. Measurements on a PPC970 with a VMX SIMD unit indicate speedup factors of up to 8.11 for numerical/video/communication kernels and speedup factors of up to 2.16 for benchmarks, when automatic simdization is turned on.

REFERENCES

• 1: IBM Corporation. PowerPC Microprocessor Family: AltiVec Technology Programming Environments Manual, July 2004.
• 2: IA32 Intel Architecture Software Developer's Manual with Preliminary Intel Pentium 4 Processor Information Volume 1: Basic Architecture. Intel Corporation.
• 3: B. Flachs et al. A Streaming Processing Unit for a CELL Processor. In IEEE International Solid-State Circuits Conference, February 2005.
• 4: Aart J. C. Bik, Software Vectorization Handbook, The: Applying Intel Multimedia Extensions for Maximum Performance, Intel Press, 2004
• 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: 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
• 7: 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]
• 8: Nathan T. Slingerland , Alan Jay Smith, Design and characterization of the Berkeley multimedia workload, Multimedia Systems, v.8 n.4, p.315-327, July 2002 [doi>10.1007/s005300200052]
• 9: Aart J. C. Bik , Milind Girkar , Paul M. Grey , Xinmin Tian, Automatic intra-register vectorization for the Intel architecture, International Journal of Parallel Programming, v.30 n.2, p.65-98, April 2002 [doi>10.1023/A:1014230429447 ]
• 10: Gerald Cheong and Monica S. Lam. An Optimizer for Multimedia Instruction Sets. In Second SUIF Compiler Workshop, August 1997.
• 11: 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 ]
• 12: 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]
• 13: Free Software Foundation. http://gcc.gnu.org/projects/tree-ssa.
• 14: N. Sreraman , R. Govindarajan, A Vectorizing Compiler for Multimedia Extensions, International Journal of Parallel Programming, v.28 n.4, p.363-400, August 2000 [doi>10.1023/A:1007559022013 ]
• 15: Corinna G. Lee , Mark G. Stoodley, Simple vector microprocessors for multimedia applications, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.25-36, November 1998, Dallas, Texas, United States
• 16: 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]
• 17: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990
• 18: Franz Franchetti, Stefan Kral, Huergen Lorenz, and Christoph Ueberhuber. Efficient utilization of SIMD Extensions. In IEEE Proceedings Special Issue on Program Generation, Optimization, and Platform Adaptation, 2005.
• 19: 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
• 20: Crescent Bay Software. VAST-F/AltiVec: Automatic Fortran Vectorizer for PowerPC Vector Unit. http://www.psrv.com/vast_altivec.html, 2004.