Julia High Performance - Second Edition

Parallel prefix sum with shared arrays

In Chapter 9, Threads, we discussed an algorithm for calculating the prefix sum (or cumulative sum) of an array. We can implement a similar algorithm with SharedArrays, which operates on multiple processes, accessing a commonly shared array:

function prefix_shared!(y::SharedArray)    l=length(y)    k=ceil(Int, log2(l))    for j=1:k        @sync @distributed for i=2^j:2^j:min(l, 2^k)             @inbounds y[i] = y[i-2^(j-1)] + y[i]        end    end    for j=(k-1):-1:1        @sync @distributed for i=3*2^(j-1):2^j:min(l, 2^k)             @inbounds y[i] = y[i-2^(j-1)] + y[i]        end    end    yend

I hope you will agree that Julia makes it easy to express an algorithm in many different ways. Whatever mechanism we choose for parallelism, the essence of the algorithm is still ...