intrinsics for scan (prefix sum)

[brandongc]

A scan operation takes a sequence of n elements [a_0, a1, …, a{n-1}] and a binary associative operator op as input and produces a second sequence containing the sums of prefixes. ie

b(1) = 0
do i = 1, n-1
    a(i+1) = a(i) + b(i)
end do

Scans are important components of many use cases including sparse data structures, histograms, sorting. Parallel algorithms are available to exploit multiple levels of parallelism: SIMD, SIMT, Device, distributed. However efficient implementation of these algorithms is non-trivial and typically not portable between different levels or even devices from the same vendor.

An important generalization is the segmented scan which is the collective application of M scan operations to a single array with M segments.

Similar to #224, but instead of modification to do concurrent add intrinsic routines.

In HPF there are:

<op>_PREFIX(ARRAY, DIM, MASK, SEGMENT, EXCLUSIVE)
<op>_SUFFIX(ARRAY, DIM, MASK, SEGMENT, EXCLUSIVE)

• can be all, any, count, in which case you really just pass a mask.
• can be sum, maxval, minval for real and integer data

HPF APIs

[brandongc]

Listing a few use cases

Converting counts to offsets

  do concurrent (i=1:n_tiles)
     nonzeros(i) = count_tile_nonzeros(i)
  end do

  offsets = exclusive_prefix_sum(nonzeros)

  do concurrent (i=1:n_tiles)
     A(offset(i)+1:offset(i)) = compute_tile_elements(i)
  end do

Sparse Linear Algebra

• Load-balancing Sparse Matrix Vector Product Kernels on GPUs
• spmv kernel from ginkgo

https://en.wikipedia.org/wiki/Prefix_sum#Applications

• Counting Sort
• List Ranking
• List Ranking + Euler Tours for Efficient parallel tree / graph algorithms (https://doi.org/10.1137/0214061)
• Decoding a Gray coded value into a binary number
• Polynomial interpolation

Prefix Sums and Their Applications - G. Blelloch

Lists and goes in detail for several of

• lexicographical comparison of strings
• addition of multi-precision numbers
• polynomial evaluation
• solving recurrences
• radix sort
• quicksort
• solve tridiagonal linear systems
• delete marked elements from an array
• dynamic allocation
• lexical analysis
• regular expressions
• tree operations
• component labeling in 2d images

pack intrinsic

PACK intrinsic can be implemented with a scan operation on the mask

Prior Art

• HPF
• C++ STL (exclusive_scan, inclusive_scan)
• Boost (same as above)
• CUB example
• Thrust
• OpenMP (scan directive)
• Kokkos parallel scan

[w6ws]

More prior art:

• The APL language and its descendants have had scan operators since the 1960s.
• The MPI library has scan operations. (E.g., MPI_SCAN, MPI_EXSCAN, and friends) MPI_SCAN has been in the MPI library since MPI 1.0 and MPI_EXSCAN since MPI 2.0. Various variants have been added since then.
• Various vendor scientific programming libraries (e.g., Cray scilib/libsci, OpenVMS MTH$) have contained "FOLR" (First Order Linear Recurrence) routines.

[klausler]

More prior art: classic Cray vector machines descended from later X-MPs had a "compressed index" instruction that returned a vector of the positions of the bits that were set in a mask, and (on a much later machine) an instruction that was a true exclusive prefix scan over the bits of a mask. Both were handy for vectorizing if/then/else constructs (in different ways).