AlgorithmsIntermediate~75 min

Parallel Prefix Scan

Implement the fundamental parallel scan primitive — first a work-inefficient Hillis-Steele scan, then a work-efficient Blelloch scan, then scale to multi-block arrays.

scanprefix-sumBlellochshared-memoryatomicsreduction

// PREREQUISITES

// PROJECT PHASES

  1. 1

    Hillis-Steele scan (single block)

    Inclusive scan using log₂(N) parallel steps.

  2. 2

    Blelloch scan (single block)

    Work-efficient two-phase (reduce + downsweep) exclusive scan.

  3. 3

    Multi-block scan

    Scan blocks independently, collect per-block sums, then add prefix back.

  4. 4

    Stream compaction

    Use your scan to implement stream compaction.

// SANDBOX

GPU execution
main.cu
loading editor…

// EXPECTED OUTPUT

Hillis-Steele: PASS
Blelloch: PASS

// YOUR PROGRESS

Log in to save progress

// DETAILS

Category
Algorithms
Difficulty
Intermediate
Est. time
~75 min
Prerequisites
1

// LEARN THE THEORY

Algorithms concepts