computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

, a segmented scan is a modification of the

prefix sum In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers is a second sequence of numbers , the sums of prefixes (running totals) of the input sequence: : : : :... For instance, the prefix sums of ...

with an equal-sized array of flag bits to denote segment boundaries on which the scan should be performed.Blelloch, Guy E. "Scans as primitive parallel operations." Computers, IEEE Transactions on 38.11 (1989): 1526-1538.

Example

In the following, the '1' flag bits indicate the beginning of each segment. :

\begin
1 & 2 & 3 & 4 & 5& 6 &\text\\
\hline
1 & 0 & 0 & 1 & 0 & 1 &\text\\
\hline
1 & 3 & 6 & 4& 9 & 6 &\text\\
\end

;Group1 * 1 = 1 * 3 = 1 + 2 * 6 = 1 + 2 + 3 ;Group2 * 4 = 4 * 9 = 4 + 5 ;Group3 * 6 = 6 An alternative method used by

High Performance Fortran High Performance Fortran (HPF) is an extension of Fortran 90 with constructs that support parallel computing, published by the ''High Performance Fortran Forum'' (HPFF). The HPFF was convened and chaired by Ken Kennedy of Rice University. The f ...

is to begin a new segment at every transition of flag value. An advantage of this representation is that it is useful with both prefix and suffix (backwards) scans without changing its interpretation. In HPF, Fortran logical data type is used to represent segments. So the equivalent flag array for the above example would be as follows:

\begin
1 & 2 & 3 & 4 & 5& 6 &\text\\
\hline
T & T & T & F & F & T &\text\\
\hline
1 & 3 & 6 & 4& 9 & 6 &\text\\
\end

References

Concurrent algorithms Higher-order functions {{computer-stub

Example

See also

References