Fri 22 Jun 2018 11:25 - 11:50 at Grand Ballroom AB - Optimization and Locality Chair(s): Milind Kulkarni

If-conversion is a fundamental technique for vectorization. It accounts for the fact that in a SIMD program, several targets of a branch might be executed because of divergence. Especially for irregular data-parallel workloads, it is crucial to avoid if-converting non-divergent branches to increase SIMD utilization. In this paper, we present partial linearization, a simple and efficient if-conversion algorithm that overcomes several limitations of existing if-conversion techniques. In contrast to prior work, it has provable guarantees on which non-divergent branches are retained and will never duplicate code or insert additional branches. We show how our algorithm can be used in a classic loop vectorizer as well as to implement data-parallel languages such as ISPC or OpenCL. Furthermore, we implement prior vectorizer optimizations on top of partial linearization in a more general way. We evaluate the implementation of our algorithm in LLVM on a range of irregular data analytics kernels, a neutronics simulation benchmark and NAB, a molecular dynamics benchmark from SPEC2017 on AVX2, AVX512, and ARM Advanced SIMD machines and report speedups of up to 146% over ICC, GCC and Clang O3.

Fri 22 Jun

Displayed time zone: Eastern Time (US & Canada) change

11:00 - 12:15
Optimization and LocalityPLDI Research Papers at Grand Ballroom AB
Chair(s): Milind Kulkarni Purdue University
11:00
25m
Talk
Polyhedral Auto-transformation with No Integer Linear Programming
PLDI Research Papers
Aravind Acharya Indian Institute of Science, Bangalore, Uday Bondhugula Indian Institute of Science, Albert Cohen Inria, France / ENS, France
Media Attached
11:25
25m
Talk
Partial Control-Flow Linearization
PLDI Research Papers
Simon Moll Saarland University, Germany, Sebastian Hack Saarland University, Germany
Media Attached
11:50
25m
Talk
Locality Analysis through Static Parallel Sampling
PLDI Research Papers
Dong Chen University of Rochester, Fangzhou Liu University of Rochester, Chen Ding University of Rochester, Sreepathi Pai University of Rochester
Media Attached