GitHub

Tuning and capabilities (developer notes)

This page is for contributors and for AcceleratedKernels' own package extensions. Nothing here is public API: the hooks and tuning structs can change in any release, including patch releases.

Resolution

Every operation resolves its alg keyword once, on the host, before touching any data. For sorting, resolve_sort runs three steps:

  1. for Auto, select_sort picks an algorithm from the device's tuning, the backend's capabilities and the call's static facts, returning it with unset fields;
  2. fill_defaults fills the unset fields from the tuning;
  3. check_sort checks the complete algorithm against the capabilities, the operation and the arguments (with check_fields for its fields, e.g. a block_size that is not a power of two), and throws an ArgumentError for anything it cannot run.
AcceleratedKernels.resolve_sort — Function
resolve_sort(alg, backend, v, dims, ord; perm=false, pairs=false,
             merge_eltypes=(eltype(v), Nothing)) -> SortAlgorithm

Resolve alg for sorting v (the keys) along dims under ordering ord on backend, for sort! (perm == pairs == false), sortperm! (perm) or sort_by_key! (pairs). Returns a concrete algorithm with every field set, or throws an ArgumentError. merge_eltypes are the element types MergeSort holds in local memory: the keys it compares (by.(v) with a by) and the values it moves along with them (Nothing for none). perm and pairs are constant-propagated so that, with Auto(), the algorithm of sortperm! and sort_by_key! infers as the only one they can use on the backend, and their plans and workspaces infer with it.

source

The other families follow the same steps, with a one-line selection: reductions resolve with resolve_reduce, scans with resolve_scan, findall with resolve_findall and any/all with resolve_predicate.

AcceleratedKernels.resolve_reduce — Function
resolve_reduce(alg, backend, T, dims) -> Algorithm

Resolve alg for a reduction with accumulator type T along dims (nothing or : for a whole-array reduction) on backend. Returns BlockReduce or CPUThreads.Partitioned with every field set, or throws an ArgumentError.

source
AcceleratedKernels.resolve_scan — Function
resolve_scan(alg, backend, T, dims, S=T) -> Algorithm

Resolve alg for a scan of element type T along dims (nothing for the whole array in linear order) on backend, whose kernels hold partial results of type S in local memory (an Optional when the operator has no known neutral element). Returns ScanPrefixes, SliceScan or CPUThreads.Partitioned with every field set, or throws an ArgumentError.

source
AcceleratedKernels.resolve_predicate — Function
resolve_predicate(alg, backend, T) -> Algorithm

Resolve alg for any/all over elements of type T on backend: ConcurrentWrite, ViaReduce (with its reduction resolved) or CPUThreads.Partitioned, with every field set, or an ArgumentError.

source

Auto and explicit algorithms share steps 2 and 3, so a tuning cannot make an invalid algorithm run, and an explicit setting always wins over the tuning.

Tunings

One plain struct per operation family holds the values that drive selection and fill unset fields, and one hook returns it for a backend and element type:

AcceleratedKernels.SortTuning — Type
SortTuning(; kwargs...)

Values that drive Auto selection and fill unset algorithm fields for sorting on one device, as returned by sort_tuning.

  • bitonic_max_len: Auto picks BitonicSort for whole arrays up to this length, where its instability is allowed (see Auto).
  • radix_min_len: Auto picks RadixSort for whole arrays from this length, for the element types and orderings it supports.
  • bitonic_max_slice_len, radix_min_slice_len: the same along dims, for the length of the slices; RadixSort also needs at least radix_min_len elements in all. Sorting a single slice (a vector, or along the only non-singleton dimension) counts as sorting a whole array.
  • merge_block_size, radix_block_size, radix_items_per_thread, radix_chunk_size, bitonic_block_size, bitonic_items_per_thread: settings for the algorithms' unset fields.
  • threads_min_elems: the default min_elems of CPUThreads.SampleSort; max_tasks defaults to Threads.nthreads().

The defaults never pick BitonicSort or RadixSort, so GPUs sort with MergeSort where a backend's tuning does not set these thresholds.

source
AcceleratedKernels.sort_tuning — Function
sort_tuning(backend, T) -> SortTuning

The sorting tuning for element type T on backend's current device (the device the calling task would launch on). AK defines this generic method; AK's package extensions add one method per backend type, which may choose different values per device.

source
AcceleratedKernels.ReduceTuning — Type
ReduceTuning(; kwargs...)

Values that fill unset algorithm fields for reductions on one device, as returned by reduce_tuning.

  • block_size, items_per_thread, switch_below: settings for unset BlockReduce fields; items_per_thread=nothing chooses it by the size of the accumulator type, enough elements for 64 bytes, from 4 to 16.
  • target_blocks: the number of blocks a reduction aims to launch to fill the device: along dims when there are few outputs, and at most in the first pass of a whole-array reduction (whose second pass reduces their partial results in one block). Must be positive.
  • columns_split_min_elems: the fewest elements of a reduction along dims into contiguous outputs for which it splits each output's reduction across blocks of consecutive outputs; that can take a second launch, which costs more on some backends.
  • threads_min_elems: the default min_elems of CPUThreads.Partitioned.
  • lanes_max_bytes: a reduction along dims in which every output reduces a run of consecutive elements reads each run with a group of up to 32 threads, several runs per block, as long as each thread reduces at most this many bytes of its run; longer runs get a block per output. 0 disables it.
  • lanes_short_runs: whether runs shorter than a block are read by such groups too, rather than by one thread per output. GPUs load short runs faster with groups, as one thread per output loads with a stride; CPUs faster with a thread each.

items_per_thread defaults to the choice by type, and columns_split_min_elems to 2^18, measured on CUDA. lanes_max_bytes defaults to 128, beyond which AMD and Intel GPUs stop gaining (at 512, a Ryzen 9950X's integrated GPU and an Iris Xe take up to twice as long as with a block per output).

source
AcceleratedKernels.ScanTuning — Type
ScanTuning(; kwargs...)

Values that drive Auto selection and fill unset algorithm fields for scans on one device, as returned by scan_tuning.

  • block_size: the block size of every scan kernel algorithm.
  • local_mem_bytes, max_items: the default items_per_thread of the kernel algorithms is the largest that keeps a tile of the element type within local_mem_bytes, and at most max_items. It is derived from the effective block_size, so an explicit block_size gets a matching default.
  • threads_min_elems: the default min_elems of CPUThreads.Partitioned; at least 2.
  • target_blocks: the blocks a SliceScan aims to launch, splitting its slices into chunks when they would take fewer.
  • slice_serial_len: SliceScan scans slices of at most this many elements with one thread each.
  • slice_column_inner: SliceScan scans with one thread per slice when the dimensions before dims hold at least this many elements, so that neighbouring threads load neighbouring elements. (Contiguous slices short enough for a block's worth to fit local_mem_bytes are scanned one per thread from local memory.)
  • slice_min_chunk: the fewest elements per thread of a SliceScan that splits its slices.
  • slice_columns_len: in arrays too small to split, SliceScan scans slices of at most this many elements with one thread each (as for slice_column_inner), and longer ones a block each.
  • slice_split_min: SliceScan splits the slices it scans with one thread each only in arrays of at least this many elements.
  • slice_split_tiles: SliceScan splits slices it scans with a block each when there are too few to fill the device and a block would scan more than this many tiles.
  • reduce_then_scan: whether ScanPrefixes reduces the tiles and then scans them from their prefix, which reads the source twice and writes the result once; or scans the tiles and then adds their prefix, which reads and writes the result twice. GPUs are faster with the former, CPUs, whose caches hold the result, with the latter.
  • subgroups: whether the kernel algorithms scan the values of a block with sub-group operations, where the backend has them (from KernelAbstractions 0.10), rather than in local memory. CPUs, whose sub-group operations synchronize the whole block, scan faster without.

The SliceScan settings were measured on CUDA (RTX 5080 and 2070).

source
AcceleratedKernels.FindallTuning — Type
FindallTuning(; kwargs...)

Values that fill unset algorithm fields for findall on one device, as returned by findall_tuning: block_size and items_per_thread for ScanScatter, and threads_min_elems for CPUThreads.Partitioned.

source
AcceleratedKernels.PredicateTuning — Type
PredicateTuning(; kwargs...)

Values that drive Auto selection and fill unset algorithm fields for any and all on one device, as returned by predicate_tuning:

  • prefer_concurrent_write: whether Auto picks ConcurrentWrite, rather than ViaReduce().
  • block_size: for ConcurrentWrite.
  • threads_min_elems: the default min_elems of CPUThreads.Partitioned.
source

AcceleratedKernels defines the hook's generic method; values without a measurement next to them are AK's earlier defaults. A package extension adds one method for its backend type and may choose values per device, e.g. from the compute capability of the current CUDA device. Tuning queries run on the calling task, under its current device, never at load or precompilation time. Record the measurement behind each value next to it.

The sorting thresholds are crossovers between MergeSort and BitonicSort or RadixSort, timed on random keys of the element types they apply to. Measure the whole-array thresholds on vectors, and the slice thresholds along dims=1 and dims=2 for several total sizes: the crossovers move with the number of slices, as few of them leave the device short of work. radix_min_slice_len must hold from radix_min_len elements in all, the smallest array along dims it applies to.

Capabilities

Capabilities are correctness facts about a backend, checked for Auto and explicit algorithms alike; tunings cannot change them.

AcceleratedKernels.runs_kernels — Function
runs_kernels(backend)

Whether AK's kernels (@kernel cpu=false) run on backend: every GPU backend, and the host backend of KernelAbstractions 0.10, which compiles kernels for PoCL. KernelAbstractions 0.9's CPU backend cannot run them.

source
AcceleratedKernels.resolve_backend — Function
resolve_backend(backend, args...)

The backend an operation runs on: backend if given, else the one every array in args (destination first) agrees on, recursing into Broadcasted trees and into the arrays that wrappers wrap; ranges, CartesianIndices, LinearIndices, wrappers of only those, and non-array values do not count. Arguments on different backends are an ArgumentError. If no argument determines it, the host backend is used.

source