coarse parallel running sum

gistfile1.cpp

blockdist = BlockDistribution[P partitions, N elements]

global int localsum[P] (blockdist); // for per-partition sums (alternatively represented as partition-private storage)
global int A[N] (blockdist); // input
global int B[N] (blockdist); // intermediate
global int C[N] (blockdist); // result

// compute running sum, within each partition
// we can only break dependences between groups of iterations with knowledge of how blockdist works
forall i in 0..N {
    p = blockdist(i).blocknum;
    localsum[p] += A[i];
    B[i] = localsum[p];
}

// for each partition, compute the running sum up to the end of it
forall p in 1..P {
    localsum[p] = localsum[p-1] + localsum[p]
}

// update running sum to reflect partition sums
forall i in blockdist(c).left .. N {
    p = blockdist(i).blocknum
    C[i] = B[i] + localsum[p-1]
}


//////////////////////////////////////////////////
// Suppose the above is a TV-UDF in a SQL query
// If there were a filter predicate on C[], then it could be pipelined onto the last loop
// update running sum to reflect partition sums
forall i in blockdist(c).left .. N {
    p = blockdist(i).blocknum
    auto res = B[i] + localsum[p-1]
    if (predicate(res)) {
        C.unordered_append(B[i] + localsum[p-1]);
    }
}