Whole-Function Vectorization

Whole-Function Vectorization enables data-parallel languages to use SIMD instruction sets to exploit more data-level parallelism in addition to multi-threading. Our LLVM-based implementation achieves an average speedup factor of 3.9 for RenderMan shaders in a ray tracer and factors between 0.6 and 5.2 for OpenCL kernels (on hardware with SIMD width 4). The algorithm is based on SSA-form and is able to vectorize all kinds of control-flow graphs.

About

Data-parallel programming languages are an important component in today's parallel computing landscape. Among those are domain-specific languages like shading languages in graphics (HLSL, GLSL, RenderMan, etc.) and "general-purpose" languages like CUDA or OpenCL. In order to achieve maximum performance for such languages on CPUs one has to exploit both multi-threading and the additional intra-core parallelism provided by the SIMD instruction set of those processors (like Intel's SSE, AVX, and LRBni instruction sets). This intra-core parallelism is becoming increasingly important with increasing SIMD register sizes (e.g. SSE = 128bit, AVX = 256bit, LRBni = 512bit).

Whole-Function Vectorization is an algorithm that transforms a scalar function in such a way that it computes W executions of the original code in parallel using SIMD instructions (W is the target architecture's SIMD width). Our implementation of the algorithm is a language- and platform-independent code transformation that works on low-level intermediate code given by an arbitrary control-flow graph in SSA form (LLVM bitcode).

The algorithm was developed and implemented as part of the master's and PhD theses of Ralf Karrenberg and has been published at CGO 2011.

Vectorized RenderMan Shaders

We have integrated the "packetizer"—the implementation of the Whole-Function Vectorization algorithm—into the shading system of the real-time ray tracer RTfact. Shaders (programs that compute the visual appearance of objects) written in the RenderMan shading language are automatically vectorized.

Compared to sequential execution, we obtain an average speedup factor of 3.9 of the entire rendering process of the ray tracer. At the same time, we reach over 90% of the performance of the few existing, hand-optimized SIMD shaders.

Vectorized OpenCL Driver

We have implemented a custom CPU OpenCL driver on the basis of LLVM and the AMD APP SDK. This driver employs Whole-Function Vectorization in addition to multi-threading to fully exploit the available data-parallelism by executing as many kernel instances in parallel as possible.

The driver currently implements a subset of the OpenCL API that is sufficient to run benchmarks from the SDK for comparison purposes. Some supported features include kernels working on multiple dimensions and barrier synchronization.

Our benchmarks show speedup factors between 0.6 and 5.2 on a variety of applications (e.g. BlackScholes, NBody, Mandelbrot, FastWalshTransform, Histogram).

Open Source

The LLVM-based implementation of the Whole-Function Vectorization algorithm as well as the OpenCL driver will be made publicly available in the near future.

If you are interested in trying out the "packetizer" and/or the OpenCL driver, contact Ralf Karrenberg for an alpha version licensed under the GPL.

Publications

Conferences

Improving the Performance of OpenCL on CPUs - CC 2012
Karrenberg, R. and Hack, S.
Compiler Construction, 2012. [bib]

@CONFERENCE{KH:2012:opencl,
 	author = {Ralf Karrenberg and Sebastian Hack},
 	title = {Improving the Performance of OpenCL on CPUs},
 	booktitle = {Compiler Construction},
 	booktitle_short = {CC 2012},
 	year = {2012},
 },

Whole Function Vectorization - CGO 2011
Karrenberg, R. and Hack, S.
Code Generation and Optimization, 2011. [doi] [slides] [bib]

@CONFERENCE{KH:2011:cgo,
 	author = {Ralf Karrenberg and Sebastian Hack},
 	title = {{W}hole {F}unction {V}ectorization},
 	booktitle = {Code Generation and Optimization},
 	booktitle_short = {CGO 2011},
 	year = {2011},
 	doi = {10.1109/CGO.2011.5764682},
 	abstract = {
 		Abstract—Data-parallel programming languages are an important component 
 		in today's parallel computing landscape. Among those are domain-
 		specific languages like shading languages in graphics (HLSL, GLSL, 
 		RenderMan, etc.) and "general-purpose" languages like CUDA or OpenCL. 
 		Current implementations of those languages on CPUs solely rely on multi-
 		threading to implement parallelism and ignore the additional intra-core 
 		parallelism provided by the SIMD instruction set of those processors 
 		(like Intel's SSE and the upcoming AVX or Larrabee instruction sets).
 		In this paper, we discuss several aspects of implementing data-parallel 
 		languages on machines with SIMD instruction sets. Our main contribution 
 		is a language- and platform-independent code transformation that 
 		performs whole-function vectorization on low-level intermediate code 
 		given by a control flow graph in SSA form.
 		We evaluate our technique in two scenarios: First, incorporated in a 
 		compiler for a domain-specific language used in real-time ray tracing. 
 		Second, in a stand-alone OpenCL driver. We observe average speedup 
 		factors of 3.9 for the ray tracer and factors between 0.6 and 5.2 for 
 		different OpenCL kernels.
 	},
 	webslides = {http://www.cdl.uni-saarland.de/projects/wfv/wfv_cgo11_slides.pdf}
 	acc_rate = {26.7},
 	accepted = {28},
 	submitted = {105},
 }

MSc Thesis

Automatic Packetization
Karrenberg, R.
M.Sc. Thesis, Saarland University, 2009. [pdf] [bib]

@MASTERSTHESIS{Karrenberg:2009:MSc,
     author  = {Ralf Karrenberg},
     title   = {{Automatic Packetization}},
     school  = {Saarland University},
     year    = {2009},
     month   = {July},
     webpdf  = {http://www.cdl.uni-saarland.de/publications/theses/karrenberg_msc.pdf},
 	abstract = {
 		Modern processor architectures provide the possibility to execute an 
 		instruction on multiple values at once. So-called SIMD (Single 
 		Instruction, Multiple Data) instructions work on packets (or vectors) 
 		of data instead of scalar values. They offer a significant performance 
 		boost for data-parallel algorithms that perform the same operations on 
 		large amounts of data, e.g. data encoding and decoding, image 
 		processing, or ray tracing.
 		However, the performance gain comes at a price: programming languages
 		provide no elegant means to exploit SIMD instruction sets. Packet 
 		operations have to be coded by hand, which is complicated, unintuitive, 
 		and error prone.  Thus, packetization - the transformation of scalar 
 		code to packet form - is mostly applied automatically by local compiler 
 		optimizations (e.g. during loop vectorization) or with a lot of manual 
 		effort at performance-critical parts of a system.
 		This thesis describes an algorithm for automatic packetization that 
 		allows a programmer to write scalar functions but use them on packets 
 		of data. A compiler pass automatically transforms those functions to 
 		work on packets of the target-architecture's SIMD width. The resulting 
 		packetized function computes the same results as multiple executions of 
 		the scalar code.
 		The algorithm is implemented in a source-language and target-
 		architecture independent intermediate representation (the Low Level 
 		Virtual Machine (LLVM)), which enables its use in many different 
 		environments. The performance of the generated code is shown in a real-
 		world case study in the context of real-time ray tracing: serial shader 
 		code written in C++ is automatically specialized, optimized, and 
 		packetized at runtime. The packetized shaders outperform their scalar 
 		counterparts by an average factor of 3.6 on a standard SSE architecture 
 		of SIMD width 4.
 	}
 }