Segmented scan

In computer science, a segmented scan is a modification of the prefix sum with an equal-sized array of flag bits to denote segment boundaries on which the scan should be performed.^[1]

Example

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

${\displaystyle {\begin{array}{|rrrrrr|l|}1&2&3&4&5&6&{\text{input}}\\\hline 1&0&0&1&0&1&{\text{flag bits}}\\\hline 1&3&6&4&9&6&{\text{segmented scan +}}\\\end{array}}}$

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 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:

${\displaystyle {\begin{array}{|rrrrrr|l|}1&2&3&4&5&6&{\text{input}}\\\hline T&T&T&F&F&T&{\text{flag values}}\\\hline 1&3&6&4&9&6&{\text{segmented scan +}}\\\end{array}}}$

See also

• Flattening transformation

References

1. Blelloch, Guy E. "Scans as primitive parallel operations." Computers, IEEE Transactions on 38.11 (1989): 1526-1538.