PaperlayerView exact revision on arXiv

Source-linked AI summary

CLTune: A Generic Auto-Tuner for OpenCL Kernels

Cedric Nugteren, Valeriu Codreanu

arXiv:1703.06503v1cs.PFcs.AIcs.DC

TL;DR

CLTune addresses the challenge of tuning OpenCL kernels across large parameter spaces, devices, and input arguments. It provides a generic auto-tuner with multiple search strategies. In two GPU case studies, tuned kernels matched or improved on state-of-the-art results, and GEMM outperformed clBLAS in all reported cases.

Abstract

from arXiv · show

This work presents CLTune, an auto-tuner for OpenCL kernels. It evaluates and tunes kernel performance of a generic, user-defined search space of possible parameter-value combinations. Example parameters include the OpenCL workgroup size, vector data-types, tile sizes, and loop unrolling factors. CLTune can be used in the following scenarios: 1) when there are too many tunable parameters to explore manually, 2) when performance portability across OpenCL devices is desired, or 3) when the optimal parameters change based on input argument values (e.g. matrix dimensions). The auto-tuner is generic, easy to use, open-source, and supports multiple search strategies including simulated annealing and particle swarm optimisation. CLTune is evaluated on two GPU case-studies inspired by the recent successes in deep learning: 2D convolution and matrix-multiplication (GEMM). For 2D convolution, we demonstrate the need for auto-tuning by optimizing for different filter sizes, achieving performance on-par or better than the state-of-the-art. For matrix-multiplication, we use CLTune to explore a parameter space of more than two-hundred thousand configurations, we show the need for device-specific tuning, and outperform the clBLAS library on NVIDIA, AMD and Intel GPUs.

I. INTRODUCTION

CLTune is a generic auto-tuner for user-defined OpenCL kernel parameter spaces. It addresses manual search costs, device-specific performance, and parameter choices that vary with input arguments.

2) Efficient execution on a variety of devices is desired:

  • OpenCL code portability does not ensure performance portability, and workgroup configurations, loop unrolling, or vector widths may matter even within one vendor or architecture family.Tuning can therefore be relevant across devices with differing parameter sensitivities.Source: §I · p. 1, 2) Efficient execution on a variety of… · p. 1

1) The search-space is too large to explore manually:

  • Thousands of parameter combinations can arise from choices such as vector width, workgroup shape, thread coarsening, and local-memory caching.Library designers may spend extra effort exploring such spaces to seek the best performance.Source: 1) The search-space is too large to… · p. 1

3) The optimal parameters change based on input arguments:

  • Optimal parameters can depend on inputs such as data sizes or booleans, motivating compile-time or run-time tuning for specific arguments.A simulation with a fixed run-time input size could use its first tens of time-steps to find parameters for the remainder.Source: 3) The optimal parameters change based… · p. 1, §I · p. 1

I. INTRODUCTION

  • CLTune automatically explores user-defined OpenCL kernel parameters and supports full, random, simulated-annealing, and particle-swarm searches.The paper presents two case studies: 2D convolution and matrix-multiplication (GEMM).Source: 3) The optimal parameters change based… · p. 1

II. RELATED WORK

The paper positions CLTune as a generic OpenCL kernel tuner distinct from problem-specific or higher-level GPU tuners. It describes a C++ API and example features for configuring and checking parameterized kernels.

II. RELATED WORK

  • The authors report being unaware of another generic tuner for OpenCL kernels; prior OpenCL/GPU tuners were problem-specific, while higher-level tuners did not expose user-defined low-level parameters.Maestro is described as targeting data transfers rather than kernels.Source: §II · p. 2

III. CLTUNE: AN AUTO-TUNER FOR OPENCL KERNELS

  • CLTune’s C++ API hides host OpenCL calls and supports stand-alone off-line tuning or integration for on-line tuning.The copy-kernel example compiles and times WPT values 1, 2, and 4, then reports the best value.Source: §III · p. 2

A. Advanced usage

  • Advanced usage adds tunable workgroup dimensions, user- and device-imposed configuration constraints, and reference-kernel checks for parameter-dependent bugs.The copy example extends to workgroup-size tuning by multiplying the base local size by a tunable value.Source: A. Advanced usage · p. 2

B. Search strategies and search-space properties

Search-space size and repeated kernel recompilation can make exhaustive exploration impractical, especially for on-line tuning. CLTune offers alternatives and motivates heuristic methods by the discrete, nonlinear, and interdependent nature of kernel parameters.

B. Search strategies and search-space properties

  • When exhaustive search is infeasible or undesirable, including for on-line tuning, CLTune offers random search, simulated annealing, and particle swarm optimisation as alternatives to full search.Repeated recompilation, in addition to kernel execution, can constrain tuning time.Source: B. Search strategies and search-space… · pp. 2–3
  • Random search tests a configurable random fraction of the search space, but its chance of finding a good configuration depends on how common good combinations are.When good combinations are rare, the chance of finding one is low.Source: B. Search strategies and search-space… · p. 3
  • Kernel-tuning spaces may be high-dimensional despite having few values per parameter, with discrete, nonlinear performance and strong relations between parameters.The tuner’s search space is defined by its user, so these are useful observations rather than assumptions that apply to every space.Source: B. Search strategies and search-space… · p. 3
  • The authors focus on simulated annealing and particle swarm optimisation because derivatives are unsuitable for expected nonlinearities and direct search may require exploring too many neighbors.Other search methods can be plugged into CLTune for future evaluation.Source: B. Search strategies and search-space… · p. 3

C. Simulated annealing

Simulated annealing explores neighboring configurations with temperature-dependent acceptance, while CLTune adapts accelerated particle swarm optimisation to narrow, discrete search spaces.

C. Simulated annealing

  • As temperature decreases, simulated annealing becomes less likely to accept worse configurations, helping it avoid local optima earlier in the search.The probability also decreases as the performance difference between configurations grows.Source: C. Simulated annealing · p. 3
  • A random neighboring configuration is evaluated, and its chance of becoming current depends on execution times and annealing temperature.The search starts randomly and runs for a user-defined number of configurations.Source: C. Simulated annealing · p. 3

D. Particle swarm optimisation

  • Particle swarm optimisation has communicating particles explore the search space, with positions and velocities informed by each particle’s best and the swarm’s best configurations.The particles start at random positions with random velocities.Source: D. Particle swarm optimisation · p. 3
  • CLTune modifies accelerated particle swarm optimisation [22] for narrow, discrete spaces, calculating new positions without continuity or velocity.The method uses probability parameters α, β, and γ, plus a random value within each dimension’s parameter range.Source: D. Particle swarm optimisation · p. 3

IV. EXPERIMENTAL SETUP

The experiments use OpenCL GPUs from varied vendors, with device properties listed in Table I; non-GPU OpenCL devices are reserved for future work.

  • Experiments use OpenCL GPUs from different vendors, and Table I lists the devices and relevant properties.The authors plan to extend the experiments to OpenCL CPUs and MIC in future work.Source: §IV · p. 4, Table I · p. 4
  • All data types are single-precision floating point numbers.Source: §IV · p. 4
  • Simulated annealing uses variable temperature T = {2, 4, 6}; PSO uses α = 0.4, β = 0, γ = 0.4, and swarm size S = {3, 6}.The text states that β = 0 removes local-best influence, following [22].Source: §IV · p. 4

V. CASE-STUDY: 2D CONVOLUTION

The convolution case study applies filter operations to images and considers tuning for specific filter sizes, a setting relevant to GPU-based deep-learning workloads.

  • Convolution is used in deep-learning workloads with compile-time fixed filter sizes, making per-size tuning relevant.The passage gives example filter sizes from 3 by 3 to 11 by 11 and notes use in production and research libraries.Source: §V · p. 4
  • An Xf by Yf filter F is applied to an X by Y input image A to produce an output image B of the same size.Source: §V · p. 4
  • The filter coefficients are shared across image coordinates, making them a good match for OpenCL constant memory.The passage identifies w as a weighing factor.Source: §V · p. 4

A. Tuning parameters

CLTune’s convolution tuning space exposes workgroup, per-thread work, caching, vectorization, padding, and unrolling choices. In 2D convolution searches, random search performed well on average, simulated annealing improved results on some devices, and PSO underperformed random search.

A. Tuning parameters

  • The tunable convolution implementation varies workgroup dimensions, work per thread, local-memory caching, vector operations, padding, and loop unrolling.Caching includes hardware-only, input-plus-halo, and helper-thread strategies; vector loads apply only to one local-memory strategy.Source: A. Tuning parameters · p. 4

B. Evaluation of the search strategies

  • Each strategy tested 107 unique configurations from a 3,424-permutation space using an 8192 by 4096 image and a 7x7 filter.The study later also used 3x3 and 11x11 filters.Source: B. Evaluation of the search strategies · p. 4
  • Random search over 1/32 of the space averaged 77% on HD7970, 78% on K40m, 83% on GTX480, and 92% on Iris; random configurations averaged below 20%.The violin plot compares best-found configurations from each run with the full search-space distribution.Source: B. Evaluation of the search strategies · p. 5, Figure 5 · p. 5
  • Simulated annealing outperformed random search on average on K40m and GTX480, but could get stuck in local optima and was moderately sensitive to temperature T.In single-device traces, annealing generally moved toward better configurations but could jump to worse ones while temperature was high.Source: B. Evaluation of the search strategies · p. 5
  • PSO performed worse than random search in this search-space and was judged unsuitable for it.The authors leave open whether larger swarms and longer searches would change its performance.Source: B. Evaluation of the search strategies · p. 5

C. Best-found results

For 2D convolution, CLTune matched adaptive-tiling on GTX480 for 3x3 and 7x7 filters and exceeded it for 11x11. Best parameters varied by filter size and device, and using parameters tuned for another filter could substantially reduce performance.

C. Best-found results

  • Best-found parameters varied across the three filter sizes and across two devices, including devices from the same vendor.Table II presents the tuning parameters and their possible values alongside the best-found results.Source: C. Best-found results · p. 6, Table II · p. 6
  • Convolution becomes more compute-intensive as filter sizes increase; Iris was limited by memory bandwidth for 3x3 and 7x7, and by register count for 11x11.GTX480 and HD7970 performed relatively better than K40m because of their more balanced architecture.Source: C. Best-found results · p. 6, Figure 6 · p. 6
  • Only 64% of performance was achieved in the worst cross-filter case; running an 11x11 filter with 3x3-tuned parameters could gain 56% performance.Table III reports relative performance when the best-case parameters for each filter size are applied to other filter sizes.Source: C. Best-found results · p. 6, Table III · p. 6
  • CLTune matched adaptive-tiling’s 326 GFLOPS for 3x3 and 550 GFLOPS for 7x7, and improved on its 601 GFLOPS for 11x11 on GTX480.The comparison is against the adaptive-tiling results reported for GTX480.Source: C. Best-found results · p. 6, Figure 6 · p. 6
  • For filter sizes below 19 by 19, 2D convolution is significantly faster than the highly optimized cuFFT library, as discussed in.The paper notes FFT in frequency space as an alternative to 2D convolution.Source: C. Best-found results · p. 6

VI. CASE-STUDY: MATRIX-MULTIPLICATION

The matrix-multiplication case study implements generalized dense GEMM in OpenCL and describes its assumptions and tunable kernel parameters. Its design includes workgroup tiling, thread-level coarsening, memory controls, vector widths, and loop unrolling.

VI. CASE-STUDY: MATRIX-MULTIPLICATION

  • The case study targets generalized dense GEMM, assuming transposed A and matrix dimensions that are powers of 2 and multiples of tile sizes.The dimensions assumption can be resolved with a relatively cheap preprocessing kernel, as suggested in.Source: §VI · p. 6

A. Tuning parameters

  • Workgroup-level 2D tiling, tunable local workgroup dimensions, and register tiling set the work per thread; local-memory caching is configurable for each input matrix.Mwi and Nwi are the work per thread in the M and N dimensions, respectively.Source: A. Tuning parameters · p. 6, Figure 8 · p. 7
  • Additional controls reshape local memory, set memory-access strides and vector widths, and choose the unrolling factor for the Kwg kernel loop.The stride controls apply to A and C through Mstride and to B through Nstride.Source: A. Tuning parameters · pp. 6–7

B. Evaluation of the search strategies

CLTune’s GEMM search strategies and best-found configurations were evaluated across devices. The tuned implementation outperformed clBLAS in all reported cases, while results also showed benefits from device-specific tuning.

B. Evaluation of the search strategies

  • The search space contained 241.600 unique configurations, but the strategy experiments explored only 117 configurations on 2048-by-2048 squared matrices.The 117 configurations represented 1/2048th of the search space, chosen to keep runtime comparable to the convolution experiments.Source: B. Evaluation of the search strategies · p. 7
  • Simulated annealing and PSO outperformed random search on all devices; Fig. 7 summarizes 128 runs of the strategies.The authors also report that good-performing configurations were easier to find for GEMM than for 2D convolution.Source: B. Evaluation of the search strategies · p. 7

C. Best-found results

  • Best-found parameters for single-precision matrix-multiplication varied significantly across the four devices.Table IV presents the best-found parameter configurations.Source: C. Best-found results · p. 7, Table IV · p. 7
  • CLTune’s matrix-multiplication outperformed clBLAS in all cases, but did not match cuBLAS on the K40m.The comparison is against cuBLAS 7.0 on K40m and 5.5 on GTX480, and clBLAS 2.4.0 after running its included tuner.Source: C. Best-found results · pp. 7–8, Figure 9 · p. 8
  • On K40m, parameters from GTX480, HD7970, and Iris achieved 50%, 61%, and 79% of K40m’s best results, respectively.The paper states that device-specific tuning can yield up to a factor of 2 in performance.Source: C. Best-found results · p. 8

VII. CONCLUSIONS

The conclusions present CLTune as a generic, open-source OpenCL auto-tuner and report results from two case studies across four devices. The authors say its tuned convolution and GEMM kernels match or improve on the state of the art.

VII. CONCLUSIONS

  • Across four devices, the case studies explored more than two-hundred thousand configurations, found substantial device-specific parameter differences, and demonstrated input-argument tuning for convolution.The authors report that simulated annealing and particle swarm optimisation have merits, with efficacy depending on the problem.Source: §VII · p. 8
  • The authors report that CLTune-created OpenCL kernels for 2D convolution and GEMM match or improve upon the state of the art.They describe performance portability and availability on OpenCL devices as advantages over existing work.Source: §VII · p. 8
Loading 1703.06503v1…