Jump to content

Segmented scan

From Wikipedia, the free encyclopedia

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

[edit]

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

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:

See also

[edit]

References

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