Pointer Jumping (List Ranking) Visualizer

Pointer Jumping (List Ranking)

parallelPRAM-EREW

A parallel technique for finding the distance of every node in a linked list to the end of the list. By updating pointers to parent of parent, it shrinks path lengths logarithmically.

SIMULATION STEP PROGRESSStep 1 / 1

SPEED (50%)

SIZE (8)

CORES (8)

💡 Tip: Enter integers between 1 and 99. Max size is 12.

Code Workspace

1procedure PointerJumping(next: array of pointers, d: array of distances)

2 for each processor P_i in parallel do

3 if next[i] == null then d[i] := 0 else d[i] := 1

4 end parallel-for

5 for step := 1 to ceil(log2(N)) do

6 for each processor P_i in parallel do

7 if next[i] != null then

8 d[i] := d[i] + d[next[i]]

9 next[i] := next[next[i]]

10 end if

11 end parallel-for

12 barrier()

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: A parallel technique for finding the distance of every node in a linked list to the end of the list. By updating pointers to parent of parent, it shrinks path lengths logarithmically.

Real-world Industrial Applications:

Finding roots of forests in parallel graph components
Evaluating parallel expression trees
List ranking algorithms