セグメントスキャン

コンピュータサイエンスにおいて、セグメントスキャンとは、スキャンを実行するセグメントの境界を示すために、プレフィックスの合計に等しいサイズのフラグビット配列を追加したものです。 ^[1]

例

以下では、「1」フラグビットは各セグメントの開始を示します。

{\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}}

グループ1

1 = 1
3 = 1 + 2
6 = 1 + 2 + 3

グループ2

4 = 4
9 = 4 + 5

グループ3

6 = 6

高性能Fortranで使用される別の方法は、フラグ値が遷移するたびに新しいセグメントを開始することです。この表現の利点は、解釈を変えることなく、プレフィックススキャンとサフィックススキャン（後方）の両方で使用できることです。HPFでは、セグメントを表すためにFortranの論理データ型が使用されます。したがって、上記の例に相当するフラグ配列は次のようになります。

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

参照

平坦化変換

参考文献

^ Blelloch, Guy E.「スキャンは基本的な並列操作である」Computers、IEEE Transactions 38.11 (1989): 1526-1538。

このコンピューティングに関する記事はスタブです。記事を拡張することでWikipediaに貢献できます。

[1] Blelloch, Guy E.「スキャンは基本的な並列操作である」Computers、IEEE Transactions 38.11 (1989): 1526-1538。