Reference Capabilities for Safe Parallel Array Programming
Here&#x27;s a common GPU &#x2F; SIMD trick for parallel programming, which also happens to be my favorite array trick I&#x27;ve ever learned about. Since SIMD is implemented on Intel x86, AMD x86, ARM, and POWER9... as well as NVidia GPUs and AMD GPUs... I think anyone who is into parallel processing of arrays should learn the SIMD trick. This is truly universal on modern hardware (although the precise instructions are different).<p>First, a helper function called &quot;active_lane&quot;:<p><pre><code>    active_lane():
       exclusive_parallel_prefix_sum(current_lane_is_active);
</code></pre>
This &quot;parallel_prefix_sum&quot; operation is a GPU-intrinsic. On AMD, it is &quot;__ockl_activelane_u32()&quot;, which compiles into 2-assembly language statements with throughput 1-instruction per clocktick. I assume NVidia&#x27;s __active_lane() function is similarly very efficient<p>AVX can implement active_lane by performing parallel-prefix-sum over the execution mask: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Prefix_sum" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Prefix_sum</a><p>Imagine the following execution mask in AVX: 0 1 0 1 0 1 1 1. The exclusive parallel prefix sum is 0 0 1 1 2 2 3 4. Thread#1 gets index0. Thread#3 gets index1. Thread#7 gets index4.<p>Intel 128-bit SIMD can implement this for 8-bit ints as follows:<p><pre><code>    ; Conceptual purposes only, untested. Using AVX-style &quot;dest, src0, src1...&quot; methodology here
    ; Assume xmm0 is the execution-mask &#x2F; input
    psrldq xmm1, xmm0, 1 ; Byteshift right 1-byte
    paddb xmm0, xmm1, xmm0 ; 8-bit integer add
    psrldq xmm1, xmm0, 2 ; 2-byte shift
    paddb xmm0, xmm1, xmm0
    psrldq xmm1, xmm0, 4 ; 4-byte shift
    paddb xmm0, xmm1, xmm0
    psrldq xmm1, xmm0, 8 ; 8-byte shift
    paddb xmm0, xmm1, xmm0
    ; xmm0 contains prefix-sum 
</code></pre>
Extending it beyond 128-bits requires vpbroadcastd due to the AVX2 128 &quot;lane&quot; split, but otherwise continues to follow the pattern. In any case, &quot;active lane&quot; is still a very efficient operation in AVX, as it doesn&#x27;t even touch L1 cache (register space only).<p>------<p>Once Active-lane is figured out, treating an array as a 16-way parallel SIMD-stack (or bigger) is actually quite simple:<p><pre><code>    SIMD-Push(X)
        array[tail + __active_lane()] = X
        toAdd = popcount(exec_mask);
        if(__active_lane() == 0){ &#x2F;&#x2F; Tail is shared. Only have one lane update &quot;tail&quot;.
            tail += toAdd;
        }

    SIMD-Pop()
        toRemove = popcount(exec_mask);
        if(__active_lane() == 0){
            tail -= toRemove;
        }
        return array[tail + 1 + __active_lane()];
</code></pre>
The above is GPU-style (ipsc, ROCm, OpenCL, or CUDA). While all threads read &quot;tail&quot; together you only want one thread updating the &quot;tail&quot; variable at a time.<p>----------<p>With that being said: the work in the paper is interesting. &quot;Split&quot; and &quot;Merge&quot; (especially &quot;interleaved&quot; forms) are an interesting way to formally specify Array of Structs &#x2F; Structure of Arrays, which is one of the problems you will commonly deal with in SIMD or parallel-compute.<p>The &quot;split&quot; and &quot;merge&quot; primitives were also used as a cute mergesort implementation at the end.<p>Arrays are surprisingly efficient and effective data-structures today, even more so now that CPUs rely upon pre-fetchers to fill cache fast enough.