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 four steps:

_checkdomain checks the fields the caller set (e.g. a block_size that is not a power of two), before any arithmetic uses them;
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;
_fill fills the unset fields from the tuning;
_check checks the complete algorithm against the capabilities, the operation and the arguments, and throws an ArgumentError for anything it cannot run.

AcceleratedKernels._resolve_sort — Function

_resolve_sort(alg, backend, v, dims, ord; perm=false, pairs=false) -> 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.

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.

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 (a lane type when the operator has no known neutral element). Returns ScanPrefixes, DecoupledLookback, SliceScan or CPUThreads.Partitioned with every field set, or throws an ArgumentError.

AcceleratedKernels._resolve_findall — Function

_resolve_findall(alg, backend, T) -> Algorithm

Resolve alg for findall over elements of type T on backend: ScanScatter or CPUThreads.Partitioned with every field set, or an ArgumentError.

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.

Auto and explicit algorithms share steps 3 and 4, 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 slices and arrays up to this length, where its instability is allowed (see Auto).
radix_min_len: Auto picks RadixSort for whole-array sorts from this length, for the element types and orderings it supports.
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, and reproduce AK's historical settings. Internal: the fields may change in any release.

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.

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 (see _reduce_items_per_thread).
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_min_elements: 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.

items_per_thread defaults to the choice by type, and columns_min_elements to 2^18, measured on CUDA; the other defaults reproduce AK's historical settings. Internal: the fields may change in any release.

AcceleratedKernels.reduce_tuning — Function

reduce_tuning(backend, T) -> ReduceTuning

The reduction tuning for accumulator type T on backend's current device; see sort_tuning for the conventions.

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.

prefer_lookback: Auto picks DecoupledLookback for whole-array scans where the backend supports it (_supports_lookback), else ScanPrefixes.
block_size: the block size of every scan kernel algorithm.
local_mem_bytes, max_items: the default items_per_thread of ScanPrefixes and DecoupledLookback 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.

The defaults reproduce AK's historical settings. Internal: the fields may change in any release.

AcceleratedKernels.scan_tuning — Function

scan_tuning(backend, T) -> ScanTuning

The scan tuning for element type T (the running-value type the scan computes in; see accumulate!) on backend's current device; see sort_tuning for the conventions.

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. The defaults reproduce AK's historical settings. Internal: the fields may change in any release.

AcceleratedKernels.findall_tuning — Function

findall_tuning(backend, T) -> FindallTuning

The findall tuning for element type T (the input's) on backend's current device; see sort_tuning for the conventions.

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.

The defaults reproduce AK's historical settings. Internal: the fields may change in any release.

AcceleratedKernels.predicate_tuning — Function

predicate_tuning(backend, T) -> PredicateTuning

The any/all tuning for element type T (the input's) on backend's current device; see sort_tuning for the conventions.

AcceleratedKernels defines the hook's generic method, whose values reproduce the library's historical 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 (see benchmark/tune_sort.jl) next to it.

Capabilities

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

AcceleratedKernels._runs_threads — Function

_runs_threads(backend)

Whether backend is the host backend, whose arrays the CPUThreads algorithms can process on Julia threads.

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.

AcceleratedKernels._supports_lookback — Function

_supports_lookback(backend)

Whether DecoupledLookback is correct on backend: it needs a device-scope memory fence (_decoupled_fence), atomic loads and stores of the block flags, and forward progress between workgroups, since a block spins until an earlier one publishes its prefix. AK's extensions declare it for the backends where all three are known to hold.

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; ranges, CartesianIndices, LinearIndices, Base's views, reshapes and permutations of them, and non-array values do not count. Arguments on different backends are an ArgumentError. If no argument determines it, the host backend is used.