ruprim/block/
histogram.rs

1use ruda_kernel::dsl as kernel_dsl;
2use ruda_kernel::dsl::prelude::*;
3
4/// Sort-based histogram without atomic counter requirements. Shared sort
5/// scratch holds the entire tile. Samples are valid integral bin indices.
6#[ruda]
7pub fn sort_histogram<T: Numeric, C: Numeric>(
8    samples: &Array<T>, histogram: &mut SharedMemory<C>,
9    source: &mut SharedMemory<T>, destination: &mut SharedMemory<T>, valid: usize,
10    #[comptime] bins: usize, #[comptime] threads: usize, #[comptime] items: usize,
11    #[comptime] accumulate: bool,
12) {
13    let mut sorted = Array::<T>::new(items);
14    #[unroll]
15    for item in 0..items {
16        if UNIT_POS as usize * items + item < valid { sorted[item] = samples[item]; }
17    }
18    let compare = crate::collective::RudaAscending {};
19    crate::block::sort::merge_sort_keys::<T, crate::collective::RudaAscending>(
20        &mut sorted, source, destination, &compare, valid, threads, items);
21    let mut bin = UNIT_POS as usize;
22    while bin < bins {
23        let mut lower = 0usize;
24        let mut upper = valid;
25        while lower < upper {
26            let middle = lower + (upper - lower) / 2;
27            if usize::cast_from(source[middle]) < bin { lower = middle + 1; } else { upper = middle; }
28        }
29        let begin = lower;
30        upper = valid;
31        while lower < upper {
32            let middle = lower + (upper - lower) / 2;
33            if usize::cast_from(source[middle]) <= bin { lower = middle + 1; } else { upper = middle; }
34        }
35        let count = C::cast_from(lower - begin);
36        if accumulate { histogram[bin] += count; } else { histogram[bin] = count; }
37        bin += threads;
38    }
39    sync_ruda();
40}
41
42/// Initialise a shared histogram. All block threads participate.
43#[ruda]
44pub fn initialise<C: Numeric>(histogram: &mut SharedMemory<Atomic<C>>, #[comptime] bins: usize, #[comptime] threads: usize) {
45    let mut bin = UNIT_POS as usize;
46    while bin < bins {
47        histogram[bin].store(C::from_int(0));
48        bin += threads;
49    }
50    sync_ruda();
51}
52
53/// Add a blocked register tile to an existing shared histogram. Valid samples
54/// are integral bin indices in range; the backend must support atomic add on C.
55#[ruda]
56pub fn composite<T: Numeric, C: Numeric>(
57    samples: &Array<T>, histogram: &mut SharedMemory<Atomic<C>>, valid_items: usize,
58    #[comptime] items_per_thread: usize,
59) {
60    let start = UNIT_POS as usize * items_per_thread;
61    #[unroll]
62    for item in 0..items_per_thread {
63        if start + item < valid_items {
64            histogram[usize::cast_from(samples[item])].fetch_add(C::from_int(1));
65        }
66    }
67    sync_ruda();
68}
69
70#[ruda]
71pub fn histogram<T: Numeric, C: Numeric>(
72    samples: &Array<T>, histogram: &mut SharedMemory<Atomic<C>>, valid_items: usize,
73    #[comptime] bins: usize, #[comptime] threads: usize, #[comptime] items_per_thread: usize,
74) {
75    initialise(histogram, bins, threads);
76    composite(samples, histogram, valid_items, items_per_thread);
77}
ruprim/block/histogram.rs

ruprim/block/
histogram.rs
