Paper Info
Title
Improving the effectiveness of searching for isomorphic chains in superword level parallelism.
Abstract
Most high-performance microprocessors come equipped with general-purpose Single Instruction Multiple Data (SIMD) execution engines to enhance performance. Compilers use auto-vectorization techniques to identify vector parallelism and generate SIMD code so that applications can enjoy the performance benefits provided by SIMD units. Superword Level Parallelism (SLP), one such vectorization technique, forms vector operations by merging isomorphic instructions into a vector operation and linking many such operations into long isomorphic chains. However, effective grouping of isomorphic instructions remains a key challenge for SLP algorithms. In this work, we describe a new hierarchical approach for SLP. We decouple the selection of isomorphic chains and arrange them in a hierarchy of choices at the local and global levels. First, we form small local chains from a set of preferred patterns and rank them. Next, we form long global chains from the local chains using a few simple heuristics. Hierarchy allows us to balance the grouping choices of individual instructions more effectively within the context of larger local and global chains, thereby finding better opportunities for vectorization. We implement our algorithm in LLVM, and we compare it against prior work and the current SLP implementation in LLVM. A set of applications that benefit from vectorization are taken from the NAS Parallel Benchmarks and SPEC CPU 2006 suite to compare our approach and prior techniques. We demonstrate that our new algorithm finds better isomorphic chains. Our new approach achieves an 8.6% speedup, on average, compared to non-vectorized code and 2.5% speedup, on average, over LLVM-SLP. In the best case, the BT application has 11% fewer total dynamic instructions and achieves a 10.9% speedup over LLVM-SLP.
Year
DOI
Venue
2017
10.1145/3123939.3124554
MICRO-50: The 50th Annual IEEE/ACM International Symposium on Microarchitecture Cambridge Massachusetts October, 2017
Keywords
Field
DocType
SIMD, automatic vectorization, superword-level parallelism, LLVM
Source code,Computer science,Parallel computing,SIMD,Vectorization (mathematics),Theoretical computer science,Compiler,Real-time computing,Heuristics,Software,Superword Level Parallelism,Speedup
Conference
ISSN
ISBN
Citations 
1072-4451
978-1-4503-4952-9
2
PageRank 
References 
Authors
0.36
20
2
Name
Order
Citations
PageRank
Joonmoo Huh121.04
James Tuck256433.06