Run Length Decode#

Run Length Decode expands each run value by its length. Values [7, 9] with lengths [3, 2] describe the stream [7, 7, 7, 9, 9]. cuda.coop.cutlass.run_length_decode() returns one window of that stream as a fresh per-thread payload. cuda.coop.cutlass.run_length_decode_into() writes the whole stream to an array and returns its total size to every thread. Both preserve the run inputs.

The explorer uses a complete block of four teaching threads. Choose the input lengths and the number of decoded items per thread, then compare a single window with the bulk loop. Input runs and decoded outputs have independent per-thread extents. The example below uses a complete physical block.

Run values 7 and 9 with lengths 3 and 2 have exclusive starts 0 and 3 and total size 5. A four-item window at offset 2 returns 7, 9, 9, 0. The final slot is outside the stream and zero-filled.

One decoded item per teaching thread, window offset 2.#

An exclusive scan of the run lengths gives the run starts. A decoded index belongs to the last positive-length run whose start is no greater than that index.

Run values          7    9    2    5
Run lengths         3    2    0    0     (trailing padding)
Exclusive starts    0    3    5    5     total = 5
Full stream         7    7    7    9    9
Window indices      2    3    4    5     window offset = 2
Window values       7    9    9    0     last slot zero-filled

Run inputs and window ownership#

Each block owns a fixed tile of runs in blocked order. Thread t holds run t * runs_per_thread + i in its local slot i. All positive run lengths must precede any zero padding. Zeros let a fixed run tile represent fewer runs; an all-zero tile represents an empty stream. An interior zero followed by a positive length is invalid.

decoded_items_per_thread sets the returned payload’s extent. If it is D, a block of B threads returns a window of B * D positions. Thread t receives decoded indices beginning at decoded_window_offset + t * D. The window offset counts decoded items, so it can begin inside a run. It must have the same value in every thread.

For the example above, offset 2 starts at the last 7. The next two items are 9. A four-item window also includes decoded index 5, which is beyond the total of 5. The wrapper fills that value slot with zero. These tail values are defined; an empty stream or a window starting at or beyond the total produces the same fill values in every slot.

Preparing and reusing the table#

The provider checks the lengths and computes exclusive run starts, then passes the values and starts to cub::BlockRunLengthDecode. CUB holds the prepared run table in shared storage. Its decode method looks up each requested window in that table; it does not advance a hidden cursor. The explorer shows these dependencies and storage lifetime, not a sequence of compiled CUB instructions.

Each run_length_decode() call prepares its own table. The bulk run_length_decode_into() call prepares the table once and keeps it alive across an internal loop. Each iteration decodes block_threads * decoded_items_per_thread positions and stores only the valid part of its window. The final iteration can be partial. No public parent object or prepared-state token is needed for either operation.

In bulk mode, destination_offset is the index where the full stream is written. It does not skip decoded input. The destination must have room for that offset plus the entire decoded total. Select “One slot too small” to see the guard stop before any output write. An empty stream leaves the destination unchanged, provided its offset is within capacity.

Only complete one-dimensional blocks are supported. All members take part, including threads holding only zero-length padding. The API checks negative lengths, padding order, total overflow, and runtime offset ranges. The caller supplies uniform controls and nonoverlapping output arrays. See the cuda.coop.cutlass API Reference reference for dtype and size limits.

Window and bulk decoding#

This example decodes a fixed window, then reuses scratch to write the complete stream at a nonzero destination offset. Window and run extents are independent.

import cutlass
from cutlass import cute

import cuda.coop.cutlass as coop

@cute.kernel
def decode_runs(
    window_pointer: cute.Pointer,
    stream_pointer: cute.Pointer,
    totals_pointer: cute.Pointer,
    items_per_thread: cutlass.Constexpr,
):
    block = coop.this_block()
    rank = cutlass.Int32(block.rank())
    values = coop.ThreadData(items_per_thread)
    lengths = coop.ThreadData(items_per_thread)
    for item in cutlass.range_constexpr(items_per_thread):
        values[item] = rank * items_per_thread + item + 10
        lengths[item] = cutlass.Uint32(2)
    scratch = coop.TempStorage(auto_sync=True)
    window = coop.run_length_decode(
        block,
        values,
        lengths,
        decoded_items_per_thread=2,
        decoded_window_offset=3,
        temp_storage=scratch,
    )
    coop.store(block, window_pointer, window)
    destination = cute.make_tensor(
        stream_pointer, cute.make_layout(64 * items_per_thread + 16)
    )
    total = coop.run_length_decode_into(
        block,
        values,
        lengths,
        destination,
        decoded_items_per_thread=1,
        destination_offset=5,
        temp_storage=scratch,
    )
    totals = cute.make_tensor(totals_pointer, cute.make_layout(32))
    totals[rank] = total

@cute.jit
def launch(
    window_pointer: cute.Pointer,
    stream_pointer: cute.Pointer,
    totals_pointer: cute.Pointer,
    items_per_thread: cutlass.Constexpr,
):
    decode_runs(
        window_pointer, stream_pointer, totals_pointer, items_per_thread
    ).launch(
        grid=1,
        block=32,
    )

Scratch remains occupied throughout the bulk call’s internal loop. Explicit descriptors default to auto_sync=False: synchronize before the next use or request auto_sync=True. Totals use Uint32; negative lengths, misplaced padding, and overflow trap before decoding. See Why or when would I provide my own TempStorage? for reuse requirements.