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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

use ruda_kernel::dsl as kernel_dsl;
use ruda_kernel::dsl::prelude::*;
use crate::collective::RudaSum;
use crate::collective::record::{RudaRead, RudaReadExpand, RudaWrite, RudaWriteExpand};

#[ruda]
pub fn prepare_access<T: RudaType, L: Numeric, I: RudaRead<T>, N: RudaRead<L>, S: RudaWrite<T>>(
    run_values: &I, run_lengths: &N, values: &mut S, ends: &mut SharedMemory<u64>,
    num_runs: usize, #[comptime] threads: usize, #[comptime] runs_per_thread: usize,
) -> u64 {
    let start = UNIT_POS as usize * runs_per_thread;
    let mut lengths = Array::<u64>::new(runs_per_thread);
    let mut prefixes = Array::<u64>::new(runs_per_thread);
    #[unroll]
    for item in 0..runs_per_thread {
        lengths[item] = 0;
        if start + item < num_runs {
            values.write(start + item, run_values.read(item));
            lengths[item] = u64::cast_from(run_lengths.read(item));
        }
    }
    let sum = RudaSum {};
    crate::block::inclusive_scan::<u64, RudaSum>(&lengths, &mut prefixes, ends, &sum,
        threads * runs_per_thread, threads, runs_per_thread);
    let total = ends[threads * runs_per_thread - 1];
    sync_ruda();
    total
}

#[ruda]
pub fn decode_access<T: RudaType, C: Numeric, S: RudaRead<T>, W: RudaWrite<T>, O: RudaWrite<C>>(
    values: &S, ends: &SharedMemory<u64>, output: &mut W, relative_offsets: &mut O,
    window_offset: u64, num_runs: usize, #[comptime] items_per_thread: usize,
) {
    let start = UNIT_POS as u64 * items_per_thread as u64;
    let mut total = 0u64;
    if num_runs > 0 { total = ends[num_runs - 1]; }
    #[unroll]
    for item in 0..items_per_thread {
        let relative = start + item as u64;
        if window_offset < total && relative < total - window_offset {
            let position = window_offset + relative;
            let mut low = 0usize;
            let mut high = num_runs;
            while low < high {
                let middle = low + (high - low) / 2;
                if ends[middle] <= position { low = middle + 1; } else { high = middle; }
            }
            let mut begin = 0u64;
            if low > 0 { begin = ends[low - 1]; }
            output.write(item, values.read(low));
            relative_offsets.write(item, C::cast_from(position - begin));
        }
    }
}

/// Prepare inclusive run ends once, then reuse them for any decoded window.
/// Returns the total decoded length. The run lengths' sum must fit in U64.
#[ruda]
pub fn prepare<T: RudaPrimitive>(
    run_values: &Array<T>, run_lengths: &Array<u64>,
    values: &mut SharedMemory<T>, ends: &mut SharedMemory<u64>,
    num_runs: usize, #[comptime] threads: usize, #[comptime] runs_per_thread: usize,
) -> u64 {
    let start = UNIT_POS as usize * runs_per_thread;
    let mut lengths = Array::<u64>::new(runs_per_thread);
    let mut prefixes = Array::<u64>::new(runs_per_thread);
    #[unroll]
    for item in 0..runs_per_thread {
        let mut length = 0u64;
        if start + item < num_runs {
            values[start + item] = run_values[item];
            length = run_lengths[item];
        }
        lengths[item] = length;
    }
    let sum = RudaSum {};
    crate::block::inclusive_scan::<u64, RudaSum>(&lengths, &mut prefixes, ends, &sum,
        threads * runs_per_thread, threads, runs_per_thread);
    let total = ends[threads * runs_per_thread - 1];
    sync_ruda();
    total
}

/// Decode a blocked window, also returning each item's offset within its run.
/// Entries beyond the total decoded length are left unchanged.
#[ruda]
pub fn decode_window<T: RudaPrimitive>(
    values: &SharedMemory<T>, ends: &SharedMemory<u64>,
    output: &mut Array<T>, relative_offsets: &mut Array<u64>,
    window_offset: u64, num_runs: usize,
    #[comptime] items_per_thread: usize,
) {
    let start = UNIT_POS as u64 * items_per_thread as u64;
    let mut total = 0u64;
    if num_runs > 0 { total = ends[num_runs - 1]; }
    #[unroll]
    for item in 0..items_per_thread {
        let relative = start + item as u64;
        if window_offset < total && relative < total - window_offset {
            let position = window_offset + relative;
            let mut low = 0usize;
            let mut high = num_runs;
            while low < high {
                let middle = low + (high - low) / 2;
                if ends[middle] <= position { low = middle + 1; } else { high = middle; }
            }
            let mut begin = 0u64;
            if low > 0 { begin = ends[low - 1]; }
            output[item] = values[low];
            relative_offsets[item] = position - begin;
        }
    }
}