Reaves.dev

v0.1.0

built using

Phoenix v1.7.12

Scans And List Ranking

Stephen M. Reaves

::

2024-09-10

Notes about Lecture 5 for CS-6220

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.

GComponent i 1 2 3 4 5 6 7 8 A[1:8] 3 4 -2 -1 7 -5 6 4 PSum 3 7 5 4 11 6 12 16

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.

GComponent i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 A[1:16] 3 4 -2 -1 7 -5 6 4 3 4 -2 -1 7 -5 6 4 Flags 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0
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

G1218812->81319913->932332->1382883882->837783->7headhead11head->1661->66->12008->0330->33->329->82557->5
GComponent i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 V[1:14] 3 9 8 5 6 8 7 8 3 1 ? 1 0 ? N[1:14] 2 3 6 0 10 7 4 13 1 8 0 5 9 0
// 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

Gaa: 0bb: 1a->bcc: 1b->cdd: 1c->dee: 1d->eff: 1e->f
Gaa: 0cc: 2a->cbb: 1dd: 2b->dee: 2c->eff: 2d->f
Gaa: 0ee: 4a->ebb: 1ff: 4b->fcc: 2dd: 3
Gaa: 0bb: 1cc: 2dd: 3ee: 4ff: 5
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 O(m×log(m)) O(m \times log(m))

Span is O(log2(m)) O(log^2(m))