AlgorandSIMULATION v1.0
Sequential Engines(17)
Parallel Engines

Parallel Prefix Sum (Scan)

parallelPRAM-CREW

Computes all prefix sums (cumulative running totals) of a sequence. Uses the Hillis-Steele algorithm to aggregate elements in O(log N) steps using N processors.

SIMULATION STEP PROGRESSStep 1 / 1
SPEED (50%)
SIZE (8)
CORES (8)
NETWORK TOPOLOGY
💡 Tip: Enter integers between 1 and 99. Max size is 16.
Code Workspace
1procedure ParallelPrefixSum(A: array of size N)
2 allocate temp[N]
3 for d := 1 to ceil(log2(N)) do
4 step := 2^(d-1)
5 for each processor P_i in parallel do
6 if i >= step then
7 temp[i] := A[i] + A[i - step]
8 else
9 temp[i] := A[i]
10 end if
11 end parallel-for
12 A := copy(temp) // barrier synchronization
13 end for
14end procedure
Currently highlights executing branch
RUNTIME COST METRICS
Comparisons0
Memory Writes0
Memory Reads0
Elements Swapped0
Core Capacity:8 Cores
Total Work Done:5 operations
Critical Path Span:2 levels
Observed Speedup:2.5x
Efficiency Bound:31%
PROCESSOR ALLOCATION EFFICIENCY
THEORETICAL ANALYSIS & RESEARCH

Conceptual Focus: Computes all prefix sums (cumulative running totals) of a sequence. Uses the Hillis-Steele algorithm to aggregate elements in O(log N) steps using N processors.

Real-world Industrial Applications:
  • Parallel stream compaction and filtering
  • Parallel Radix Sort partition calculation
  • Evaluating polynomials in parallel