Segmented scan

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}}}$

• Flattening transformation