Blelloch scan is a (exclusive) scan algorithm for parallel computers. A common example of scan is prefix sum.



def exclusive_scan(a, op):
    b = [0] # Identity of the op, (for sum and max, it is 0).
    for x in a[:-1]:
        b.append(op(x, b[-1]))
    return b

exclusive_scan([1, 2, 3, 4], lambda x, y: x+y) == [0, 1, 3, 6]

exclusive_scan([1, 2, 3, 4], max) == [0, 1, 2, 3]

This vlog is complementary to the excellent video description from now archived Udacity CS344 course. The video explains the “how” of the algorithm very well, but I couldn’t easily find “why” of the algorithm, neither in that video nor in any other videos on the Internet. So here is my attempt to explain it.