Scans And List Ranking
Required Readings
Summary
Prefix Sums Problem
Prefix sum for some position in the array is the sum of all elements from the beginning to that position.
A prefix sum is also called an add-scan
You cannot simply replace for loops with parfors since iterations are NOT independent.
Parallel Scans
If we can assume associativity, we can rearrange partial sums, thus allowing independent items and parallelism.
Adding consecutive pairs gives us partial sums. Doing a scan on the partial sums will give us the even indices. Then we can just add the n+1 element to get the odds.
addScan(A[1:n]) // assume n = 2^k
if n = 1 then return A[1]
let I_o[1:n/2] = odd indices
let I_e[1:n/2] = even indices
A[I_e] <- A[I_e] + A[I_o] // implicit par for
A[I_e] <- addScan(A[I_e])
A[I_o] <- A[I_e[2:]] + A[I_o[2:]] // implicit par for
Parallel Quicksort
QS(A[1:n])
if n = 1 then return A[1]
// Pick pivot
pivot <- random element
// Partition
L <- {A[i] : A[i] <= pivot }
R <- {A[i] : A[i] > pivot }
// Recurse
A_L <- spawn QS(L)
A_R <- QS(R)
sync
// Glue
return A_L + A_R
How to do partition step in parallel?
getSmallerEqual(A[1:n], pivot)
let F[1:n] = array of {0,1} flags
F[:] <- (A[:] <= pivot)
return gatherIf(A[:], F[:]) // or just A[F[:]]
gatherIf(A[1:n], F[1:n])
let K[1:n] = array of indices
K[:] <- addScan(F[:])
let L[1:K[n]] = output array
par-for i <- 1 to n do
if F[i] = 1 then L[K[i]] <- A[i]
return L[:]
Segmented Scans
Instead of doing one big scan, do a bunch of small scans
Imagine you have an array of data, then an array of flags marking when a segment begins.
segAddScan(A[1:n], F[1:n])
for i <- 1 to n do
if !F[i] then
A[i] <- A[i-1] + A[i]
let x_i = (a_i, f_i)
op(x_i, x_j)
if !f_j then
return (a_i+a_j,f_i || f_j)
return x_j
segAddScan(A[1:n], F[1:n])
let X[0:n] = array of n+1 pairs
X[0] <- (0, false)
for i <- 1 to n do
X[i] <- (A[i], F[i])
for i <- 1 to n do
X[i] <- op(A[i-1], F[i])
for i <- 1 to n do
A[i] <- left(X[i])
We need to prove op is associative
List Ranking
Imagine a linked list, how would you compute how far each node is from the head (list rank)?
We need random access in order to parallelize
ArrayPool
Place all values into an array
Replace “next” pointer with indices
// Reverse list by making it doubly-linked
reverse(V[1:m], N[1:m])
let P[1:m] = index array
P[:] <- nil
parfor i <- 1 to m do
if N[i] != nil then
P[N[i]] <- i
return P[:]
// A jump creates a pointer to my neighbor's neighbor
jumpList(N_i[1:m], N_o[1:m])
par-for i <- 1 to m do
if N_i[i] != nil then
N_o[i] <- N_i[N_i[i]]
Update and jump to create two sub lists
updateRanks(R_i[1:m], R_o[1:m], N[1:m])
par-for i <- i to m do
if N[i] != nil then
R_o[N[i]] <- R_i[i] + R_i[N[i]]
// h is index of head
rankList(V[1:m], N[1:m], h)
let R_1[1:m], R_2[1:m] = array of ranks
let N_1[1:m], N_2[1:m] = index ("Pointers")
R_1[:] <- 1 ; R_1[h] <- 0 ; N_1[:] <- N[:]
R_2[:] <- 1 ; R_2[h] <- 0 ; N_2[:] <- N[:]
for i <- 1 to ceil(log(m)) do
updateRanks(R_1[:], R_2[:], N_1[:])
jumpList(N_1[:], N_2[:])
swap(R_1, R_2)
swap(N_1, N_2)
Work is
Span is