Scan#
A scan gives each item the aggregate of earlier items in its group. An
inclusive scan includes the current item; an exclusive scan stops before it.
The order is blocked: all of thread zero’s items, then thread one’s items,
and so on. Scans return a new scalar or ThreadData without modifying the
input.
The explorer covers cuda.coop.cutlass.exclusive_sum(),
cuda.coop.cutlass.inclusive_sum(), cuda.coop.cutlass.exclusive_scan(), and
cuda.coop.cutlass.inclusive_scan(). cuda.coop.cutlass.scan() also exposes these
semantics through its mode and scan_op arguments. The eight teaching
threads represent one block, two four-lane physical warps, or four two-lane
logical warps. Physical CUDA warps have 32 lanes.
Exclusive block sum with two items per thread.#
Local sums establish the prefix entering each thread. Each thread then applies that prefix to its own ordered items.
Thread 0 1 2 3 4 5 6 7
Input 1,2 3,4 5,6 7,8 9,10 11,12 13,14 15,16
Incoming prefix 0 3 10 21 36 55 78 105
Exclusive output 0,1 3,6 10,15 21,28 36,45 55,66 78,91 105,120
Reading the stages#
Local prefixes include only a thread’s own items. The propagation stage
computes what enters each thread from preceding threads. Combining that
incoming prefix with the local sequence produces the final inclusive or
exclusive result. ∅ means there is no preceding value, as at the start
of an inclusive scan without an added prefix.
Block Scan offers raking, raking_memoize, and warp_scans.
Raking uses shared-memory segments to propagate prefixes. The memoized form
retains partials in registers to reduce shared-memory reads. Warp scans
compute local warp prefixes and propagate preceding warp aggregates. These
algorithms preserve the same sequence and result ownership; the picture
shows the mathematical dependencies, not an instruction trace. Executable
blocks selecting warp_scans must contain a multiple of 32 threads.
Block scans accept scalars or several items per thread. Physical- and
logical-warp scans accept one scalar per lane. Warp scans accept valid_items: every lane participates, but only the first
valid_items lanes have defined scan results. The explorer marks other
results with ?. The count must be uniform and between one and the group’s
width, inclusive.
Exclusive sums begin at zero. A generic exclusive scan accepts
initial_value; a non-sum operator requires it. Inclusive
scans reject initial_value. The initial value is an operand: for maximum,
an initial value of 10 keeps every output at least 10.
Scans can write aggregate_output, a separate one-item
payload containing the input aggregate at every member. It excludes the
initial value and any input lanes beyond valid_items.
Built-in scans, initial values, and aggregate outputs are supported. The kernel API also accepts compiled scalar binary operators. Prefix callbacks are unsupported.
Using Scan in a kernel#
This CuTe fragment uses the kernel-fragment
setup. Launch with 128 threads and provide at
least 128 * items_per_thread elements for each block. Each block scans its
own tile independently.
block = coop.this_block()
offset = block_index * 128 * items_per_thread
values = coop.load(
block, source, items_per_thread=items_per_thread, offset=offset
)
prefixes = coop.inclusive_sum(block, values, algorithm="raking_memoize")
coop.store(block, output, prefixes, offset=offset)
To compute an exclusive maximum with a prefix, replace the scan call with:
prefixes = coop.exclusive_scan(
block, values, scan_op="max", initial_value=10
)
In a complete CuTe kernel, this tested example scans a logical warp’s valid
prefix and writes its aggregate. operator.add selects the built-in sum;
it is not a custom device callback.
import operator
from cutlass import cute
import cuda.coop.cutlass as cutlass_coop
@cute.kernel
def scan_prefix(
source: cute.Pointer,
destination: cute.Pointer,
aggregates: cute.Pointer,
):
thread = cutlass_coop.this_block().rank()
group = cutlass_coop.this_warp().group_by(8)
inputs = cute.make_tensor(source, cute.make_layout(64))
outputs = cute.make_tensor(destination, cute.make_layout(64))
totals = cute.make_tensor(aggregates, cute.make_layout(64))
aggregate = cutlass_coop.ThreadData(items_per_thread=1)
result = cutlass_coop.exclusive_scan(
group,
inputs[thread],
scan_op=operator.add,
initial_value=7,
valid_items=5,
aggregate_output=aggregate,
)
if group.rank() < 5:
outputs[thread] = result
totals[thread] = aggregate[0]
@cute.jit
def launch(
source: cute.Pointer,
destination: cute.Pointer,
aggregates: cute.Pointer,
):
scan_prefix(source, destination, aggregates).launch(grid=1, block=64)
See cuda.coop.cutlass API Reference and the Programming Guide for initial values, aggregate outputs, and participation requirements.