Module parallel_scan 

Work-efficient parallel prefix sum (scan) operations

This module implements the Blelloch parallel scan algorithm, which computes prefix sums (and generalised prefix scans with arbitrary associative operators) in O(n) work and O(log n) span.

Two variants are provided:

• Exclusive scan (parallel_prefix_sum_exclusive): element i of the output is the sum of elements 0..i (the first element is identity).
• Inclusive scan (parallel_prefix_sum): element i of the output is the sum of elements 0..=i.

A generic parallel_scan function accepts any associative binary operator.

When the parallel feature is enabled, the up-sweep and down-sweep phases use rayon for parallel execution. Without parallel, all operations fall back to sequential execution.

Example

use scirs2_core::distributed::parallel_scan::{parallel_prefix_sum, parallel_scan};

// Inclusive prefix sum: [1, 3, 6, 10, 15]
let data = vec![1, 2, 3, 4, 5];
let result = parallel_prefix_sum(&data);
assert_eq!(result, vec![1, 3, 6, 10, 15]);

// Generic scan with multiplication
let data = vec![1, 2, 3, 4];
let result = parallel_scan(&data, 1, |a, b| a * b);
assert_eq!(result, vec![1, 2, 6, 24]);

Functions

parallel_prefix_max

Parallel prefix maximum — result[i] = max(data[0..=i]).

parallel_prefix_min

Parallel prefix minimum — result[i] = min(data[0..=i]).

parallel_prefix_sum

Inclusive prefix sum for a slice of values that support addition.

parallel_prefix_sum_exclusive

Exclusive prefix sum for a slice of values that support addition.

parallel_prefix_sum_f64

Fast inclusive prefix sum for f64 slices.

parallel_prefix_sum_i64

Fast inclusive prefix sum for i64 slices.

parallel_scan

Inclusive generalised parallel scan with an arbitrary associative operator.

parallel_scan_exclusive

Exclusive generalised parallel scan.

segmented_prefix_sum

Segmented prefix sum.

try_parallel_prefix_sum

Parallel prefix sum that returns a CoreResult, for ergonomic error handling at call sites.

try_parallel_scan

Parallel scan that validates the input is non-empty.