ruPRIM 0.1.8

Parallel primitives, reductions, scans, and indexing for Ruda.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

use ruda_kernel::dsl as kernel_dsl;
use ruda_kernel::dsl::prelude::*;

/// Sort-based histogram without atomic counter requirements. Shared sort
/// scratch holds the entire tile. Samples are valid integral bin indices.
#[ruda]
pub fn sort_histogram<T: Numeric, C: Numeric>(
    samples: &Array<T>, histogram: &mut SharedMemory<C>,
    source: &mut SharedMemory<T>, destination: &mut SharedMemory<T>, valid: usize,
    #[comptime] bins: usize, #[comptime] threads: usize, #[comptime] items: usize,
    #[comptime] accumulate: bool,
) {
    let mut sorted = Array::<T>::new(items);
    #[unroll]
    for item in 0..items {
        if UNIT_POS as usize * items + item < valid { sorted[item] = samples[item]; }
    }
    let compare = crate::collective::RudaAscending {};
    crate::block::sort::merge_sort_keys::<T, crate::collective::RudaAscending>(
        &mut sorted, source, destination, &compare, valid, threads, items);
    let mut bin = UNIT_POS as usize;
    while bin < bins {
        let mut lower = 0usize;
        let mut upper = valid;
        while lower < upper {
            let middle = lower + (upper - lower) / 2;
            if usize::cast_from(source[middle]) < bin { lower = middle + 1; } else { upper = middle; }
        }
        let begin = lower;
        upper = valid;
        while lower < upper {
            let middle = lower + (upper - lower) / 2;
            if usize::cast_from(source[middle]) <= bin { lower = middle + 1; } else { upper = middle; }
        }
        let count = C::cast_from(lower - begin);
        if accumulate { histogram[bin] += count; } else { histogram[bin] = count; }
        bin += threads;
    }
    sync_ruda();
}

/// Initialise a shared histogram. All block threads participate.
#[ruda]
pub fn initialise<C: Numeric>(histogram: &mut SharedMemory<Atomic<C>>, #[comptime] bins: usize, #[comptime] threads: usize) {
    let mut bin = UNIT_POS as usize;
    while bin < bins {
        histogram[bin].store(C::from_int(0));
        bin += threads;
    }
    sync_ruda();
}

/// Add a blocked register tile to an existing shared histogram. Valid samples
/// are integral bin indices in range; the backend must support atomic add on C.
#[ruda]
pub fn composite<T: Numeric, C: Numeric>(
    samples: &Array<T>, histogram: &mut SharedMemory<Atomic<C>>, valid_items: usize,
    #[comptime] items_per_thread: usize,
) {
    let start = UNIT_POS as usize * items_per_thread;
    #[unroll]
    for item in 0..items_per_thread {
        if start + item < valid_items {
            histogram[usize::cast_from(samples[item])].fetch_add(C::from_int(1));
        }
    }
    sync_ruda();
}

#[ruda]
pub fn histogram<T: Numeric, C: Numeric>(
    samples: &Array<T>, histogram: &mut SharedMemory<Atomic<C>>, valid_items: usize,
    #[comptime] bins: usize, #[comptime] threads: usize, #[comptime] items_per_thread: usize,
) {
    initialise(histogram, bins, threads);
    composite(samples, histogram, valid_items, items_per_thread);
}