burn-msa 0.2.4

MiniMax Sparse Attention (MSA) - block-sparse attention with per-GQA-group top-k block selection for Burn
Documentation
use cubecl::prelude::*;

#[cube(launch_unchecked)]
fn exp_free_topk_kernel<F: Float>(
    scores: &Array<F>,
    indices_out: &mut Array<u32>,
    n_blocks: u32,
    topk: u32,
) {
    let row = CUBE_POS_X;
    let lane = UNIT_POS_X;
    let step = CUBE_DIM_X;

    let mut heap_scores = Array::<F>::new(shared, topk);
    let mut heap_indices = Array::<u32>::new(shared, topk);

    for i in 0..topk {
        heap_scores[i] = F::neg_infinity();
        heap_indices[i] = u32::MAX;
    }

    let row_base = row * n_blocks;
    let mut j = lane;
    while j < n_blocks {
        let score = scores[row_base + j];
        if score > heap_scores[0] {
            heap_scores[0] = score;
            heap_indices[0] = j;
            let mut idx = 0;
            loop {
                let mut smallest = idx;
                let left = 2 * idx + 1;
                let right = 2 * idx + 2;
                if left < topk && heap_scores[left] < heap_scores[smallest] {
                    smallest = left;
                }
                if right < topk && heap_scores[right] < heap_scores[smallest] {
                    smallest = right;
                }
                if smallest == idx {
                    break;
                }
                let tmp_s = heap_scores[idx];
                let tmp_i = heap_indices[idx];
                heap_scores[idx] = heap_scores[smallest];
                heap_indices[idx] = heap_indices[smallest];
                heap_scores[smallest] = tmp_s;
                heap_indices[smallest] = tmp_i;
                idx = smallest;
            }
        }
        j += step;
    }

    for k in 0..topk {
        let mut best_score = heap_scores[0];
        let mut best_index = heap_indices[0];
        for offset in 0..5u32 {
            let mask = 1u32 << offset;
            let peer_score = F::shuffle_down(best_score, mask);
            let peer_index = u32::shuffle_down(best_index, mask);
            if peer_score > best_score {
                best_score = peer_score;
                best_index = peer_index;
            }
        }
        best_score = F::shuffle(best_score, 0u32);
        best_index = u32::shuffle(best_index, 0u32);
        if lane == 0 {
            indices_out[row * topk + k] = best_index;
        }
        for i in 0..topk {
            if heap_indices[i] == best_index {
                heap_scores[i] = F::neg_infinity();
                heap_indices[i] = u32::MAX;
            }
        }
        let mut idx = 0;
        loop {
            let mut smallest = idx;
            let left = 2 * idx + 1;
            let right = 2 * idx + 2;
            if left < topk && heap_scores[left] < heap_scores[smallest] {
                smallest = left;
            }
            if right < topk && heap_scores[right] < heap_scores[smallest] {
                smallest = right;
            }
            if smallest == idx {
                break;
            }
            let tmp_s = heap_scores[idx];
            let tmp_i = heap_indices[idx];
            heap_scores[idx] = heap_scores[smallest];
            heap_indices[idx] = heap_indices[smallest];
            heap_scores[smallest] = tmp_s;
            heap_indices[smallest] = tmp_i;
            idx = smallest;
        }
    }
}

pub unsafe fn launch_exp_free_topk<R: CubeRuntime>(
    client: &ComputeClient<R>,
    scores_handle: &Handle,
    indices_handle: &Handle,
    n_rows: u32,
    n_blocks: u32,
    topk: u32,
) {
    let cube_dim = CubeDim::new(32, 1, 1);
    let cube_count = CubeCount::Static(n_rows, 1, 1);
    exp_free_topk_kernel::launch_unchecked::<F32, R>(
        client,
        cube_count,
        cube_dim,
        ArrayArg::from_raw_parts(scores_handle.clone(), (n_rows * n_blocks) as usize),
        ArrayArg::from_raw_parts(indices_handle.clone(), (n_rows * topk) as usize),
        n_blocks,
        topk,
    );
}