Paper Info
Title
Efficient Selection of Vector Instructions Using Dynamic Programming
Abstract
Accelerating program performance via SIMD vector units is very common in modern processors, as evidenced by the use of SSE, MMX, VSE, and VSX SIMD instructions in multimedia, scientific, and embedded applications. To take full advantage of the vector capabilities, a compiler needs to generate efficient vector code automatically. However, most commercial and open-source compilers fall short of using the full potential of vector units, and only generate vector code for simple innermost loops. In this paper, we present the design and implementation of anauto-vectorization framework in the back-end of a dynamic compiler that not only generates optimized vector code but is also well integrated with the instruction scheduler and register allocator. The framework includes a novel{\em compile-time efficient dynamic programming-based} vector instruction selection algorithm for straight-line code that expands opportunities for vectorization in the following ways: (1) {\em scalar packing} explores opportunities of packing multiple scalar variables into short vectors, (2)judicious use of {\em shuffle} and {\em horizontal} vector operations, when possible, and (3) {\em algebraic reassociation} expands opportunities for vectorization by algebraic simplification. We report performance results on the impact of auto-vectorization on a set of standard numerical benchmarks using the Jikes RVM dynamic compilation environment. Our results show performance improvement of up to 57.71\% on an Intel Xeon processor, compared tonon-vectorized execution, with a modest increase in compile-time in the range from 0.87\% to 9.992\%. An investigation of the SIMD parallelization performed by v11.1 of the Intel Fortran Compiler (IFC) on three benchmarks shows that our system achieves speedup with vectorization in all three cases and IFC does not. Finally, a comparison of our approach with an implementation of the Super word Level Parallelization (SLP) algorithm from~\cite{larsen00}, shows that our approach yields a performance improvement of up to 13.78\% relative to SLP.
Year
DOI
Venue
2010
10.1109/MICRO.2010.38
Microarchitecture
Keywords
Field
DocType
performance improvement,efficient selection,vector instruction selection algorithm,vector unit,vector code,efficient vector code,simd vector unit,vector operation,vector capability,optimized vector code,dynamic programming,short vector,vectorization,parallel processing,benchmark testing,registers,mmx,optimization,instruction sets
MMX,Dynamic compilation,Computer science,Instruction set,Parallel computing,Instruction selection,Vectorization (mathematics),SIMD,Compiler,Xeon
Conference
ISSN
ISBN
Citations 
1072-4451
978-1-4244-9071-4
26
PageRank 
References 
Authors
0.94
16
3
Name
Order
Citations
PageRank
Rajkishore Barik156243.70
Jisheng Zhao248024.34
Vivek Sarkar34318409.41