High Performance Computing 7 | Scan and Rank List

1. Prefix Sum

The prefix sum is defined as the sum of the previous item before the input index. For example, if we have an array A,

A = [1, 2, 3, 4, 5]

Then the prefix of the index i = 3 (i starts from 1) should be,

prefix sum = 1 + 2 + 3 = 6

2. Scans

Scans generalize prefix sum to other operations. To use scan in an algorithm, what we have to do is to say we are scanning and what is the operator. The “Add-scan” is the “prefix sum” we have mentioned and there are some other scans,

max-scan: max value to the current position
product-scan: or prefix-products refers to the products to the current position
and-scan: refers to the cumulative logical AND to the current position

3. Parallel Scans?

Let’s think of a problem. Suppose we have the following algorithm,

input: A[n]

for i = 2 to n do:
    A[i] += A[i-1]

In this case, we can not replace the for loop with a parallelized for loop because the iterations are not independent. This is because the prefix A[i] depends on the last prefix A[i-1].

Note that this algorithm at the best case has O(n) operations.

4. Parallel Scan in a Naive Way

To change it to a parallel scan, we have to detach the dependency of the current prefix and the last prefix. A naive solution is to simply reduce the first i item based on our operation. The pseudo code should be,

input: A[n]
output: B[n]

for i = 1 to n do:
    B[i] = reduce(A[:i])

The work here would be O(n^2) and this is much worse than the sequenial solution. How can we improve?

5. Advanced Parallel Scan

Let’s see how we can improve it. Suppose we have an array A of 8 items. The first step is to Create a partial scan array which will scan every two items in this array. So,

Scan_partial = [reduce(A[1:2]), 
                reduce(A[3:4]), 
                reduce(A[5:6]), 
                reduce(A[7:8])]

Then the scan of this partial scan array would be the scan of all the even items in the array,

Scan_even = [reduce(A[1:2]), 
             reduce(A[1:4]), 
             reduce(A[1:6]), 
             reduce(A[1:8])]

Now we have all the even scans and the odd scans can be retrieved by using the last even scan by and reduce with itself,

Scan = [A[1], 
        reduce(A[1:2]), 
        reduce(A[1:2])+A[3], 
        reduce(A[1:4]), 
        reduce(A[1:4])+A[5], 
        reduce(A[1:6]), 
        reduce(A[1:6])+A[7], 
        reduce(A[1:8])]

Now here are some pseudo codes,

function addScan(A[n]):
    if n == 1 do:
        return A[:n]
    Let:
        I_odd[1:n/2] = 1, 3, 5, ...
        I_even[1:n/2] = 2, 4, 6, ...
        
    for i in I_odd do:
        A[i+1] = A[i] + A[i+1]       // partial scan
    
    A[I_even] = addScan(A[I_even])   // even scan
    
    for i in I_odd[2:] do:
        A[i] += A[i-1]               // odd scan

Then let’s see the cost,

partial scan: n/2 additions
odd scan: (n/2 - 1) additions
even scan: W(n/2) additions assume the work is W(n)

Then we have,

W(n) = n - 1 + W(n/2),     when n >= 2
W(n) = 0,                  when n = 1

This is to say that,

W(n) = O(n)

6. Sequential Segmented Scan

Now let’s see another problem. If we don’t want to scan the whole array all along, but we would like to scan it in segments. For example, with array,

A = [1, 2, 3, 4, 5, 6]

We want to add-scan for the first three items and another add-scan for the next three. So the segmented add scan of A would be,

A = [1, 3, 6, 4, 9, 15]

Given the flag defined as another array F as follows,

F = [1, 0, 0, 1, 0, 0]

Then the pseudo code for a sequential solution would be,

function segAddScan(A[n], F[n]):
    for i = 1 to n do:
        if not i do:
            A[i] += A[i-1]

Note that it basically means we keep the value of A[i] when the flag shows the position i has a new start (aka. F[i] = 1).

7. Rank List Sequential Solution

Suppose we have a linked list with a head pointer and then we have to rank all the nodes. Sequentially, the pseudo code should be very easy, as

function rankList(head):
    r = 0
    cur = head
    
    while cur != NULL do:
        cur.rank = r
        cur = cur.next
        r++
        
node.rank = distance of node to head

If we want to solve this problem as a scan, then what can we do? Think about it before we move on.

8. Rank List As a Scan

So let’s see if we want to make the rank a scan, we have to assign each node an initial value so that the add scan would in principle produce the desired ranks. For a simple ordered rank,

0 should be assigned to the node head
1 should be assigned to the rest of the nodes

So if we continue to scan along this array, we will get the 1s accumulated and these will create a rank for us. Because the head in our case should be ranked as 0, so we have 0 assigned to it.

The problem is that if we have a scan like this, the rank is still sequential and a better one should be a random access. This brings us to to the method of array pools.

9. Array Pools Representation of Linked List

Array pools is just another way to represent a linked list. Suppose we have the following linked list,

ll = [1, 6, 1, 8, 0, 3, 3, 9, 8, 8, 7, 5]

Then the array pools representation takes two steps.

First, put values in an array V of length n
Then, replace the concept of pointer to the index and place to another array N of length n

Let’s see ll as an example. Let’s assign a unique integer i (n = 14 and i < n) for each of the nodes in ll randomly,

[1, 6, 1, 8, 0, 3, 3, 9, 8, 8, 7, 5] = ll
[12,5,10, 8,13, 9, 1, 2, 3, 6, 7, 4] = I

Then use i as the index, we can put the nodes of ll to an array V of length n = 14,

V[14] = [3, 9, 8, 5, 6, 8, 7, 8, 3, 1, ?, 1, 0, ?]

where ? means the value is not assigned.

Then for the pointers, we put the assigned integer (index) of the next node of the current node to the array N. Note that 0 should be used for not NULLs or not assigned nodes.

N[14] = [2, 3, 6, 0, 10, 7, 4, 13, 1, 8, 0, 5, 9, 0]

10. Primitive Jump Pseudocode

Now we have a taste of the array pools representation, the other knowledge we have to know about is called a jump for a linked list.

The jump means to move the next pointer so that it points to the neighbor’s neighor,

curr.next = curr.next.next

If we do this to all the nodes in a linked list, we can split it into two linked list. And we can continue to split for more of them. This is very helpful for divide-and-conquer. Also, note that this can be performed in parallel.

When considering the array pools representation, the pseudo code should be as follows,

function jumpList(N_in[1:m], N_out[1:m]):
    parallel for i = 1 to m do:
        if N_in[i] do:
            N_out[i] = N_in[N_in[i]]

11. Rank Update

So the ideas we have so far is,

represent linked list as array pool
use add scan for list ranking
jump to divide-and-conquer

But how can we tread the list rank as an add scan? Remeber we have use 0 for the head and 1 for the others, and we can also use jumps to get sublists. And if we jump repeatedly, we can get shorter and shorter sublists.

So in order to keep the position when we jump, we have to add the integer of the current node to its successor. This is what we called “update” and it can also be parallelized. Let’s see an example, suppose we have

0 -> 1 -> 1 -> 1 -> 1 -> 1 -> NULL

So in an update, every node pushes its value to its successor,

0 -> 1+0 -> 1+1 -> 1+1 -> 1+1 -> 1+1 -> NULL

for,

0 -> 1 -> 2 -> 2 -> 2 -> 2 -> NULL

Then we call jump to split the linked list,

0 -> 2 -> 2 -> NULL
1 -> 2 -> 2 -> NULL

Then another update,

0 -> 2 -> 4 -> NULL
1 -> 3 -> 4 -> NULL

Then jump,

-> 4 -> NULL
-> NULL
-> 4 -> NULL
-> NULL

Then update,

-> 4 -> NULL
-> NULL
-> 5 -> NULL
-> NULL

And a final jump,

-> NULL
-> NULL
-> NULL
-> NULL
-> NULL
-> NULL

Now we have all the individual nodes each with a rank and then we are done.

Here’s an algorithm for the update step with the array pool representation,

initial R_in = [0, 1, 1, ...]

function updateRanks(R_in[1:m], R_out[1:m], N[1:m]):
    parallel for i = 1 to n do:
        if N[i] do:
            R_out[N[i]] = R_in[i] + R_in[N[i]]

12. Parallel List Rank

So finally let’s wrap up the parallel list ranker using pseudocode. Suppose we have an input V[m] which is the array holding the values, and we also have an input N[m] which holds the next node indexes. The index of head is also given as h so we can assign the rank of it to 0.

function rankList(V, N, h):
    R_in[m], R_out[m]    // array of ranks
    N_in[m], N_out[m]    // pointer index arrays
    
    // init
    R_in[:], R_out[:] = [1]
    R_in[h], R_out[h] = 0
    N_in[:], N_out[:] = N[:]
    
    // compute
    for i = 1 to (# of jumps) do:
        updateRanks(R_in, R_out, N_in)
        jumpList(N_in, N_out)
        // swap to continue the loop
        R_in, R_out = R_out, R_in
        N_in, N_out = N_out, N_in

Note that here the # of jumps should be the ceiling of log(m). This algorithm is called Wyllie’s algorithm and we should meet it in our project.