# 並列プレフィックス演算 ## 定義 並列プレフィックス演算(スキャン)は、i 番目のプロセッサに、直前 i-1 個のプロセッサの値へ結合演算を適用した結果を返す集団演算である。逆向きの並列サフィックス演算(後方スキャン)もある。[[Connection Machine CM-5]] の制御網はこれをハードウェアで持つ。演算子は 32 ビットワードに対するビット単位の OR、ビット単位の XOR、符号付き最大値、符号付き加算、符号なし加算の 5 種類である。例として、ベクトル (3, 2, 0, 4, 2, 6, 5, 8) を加算で前方スキャンすると (0, 3, 5, 5, 9, 11, 17, 22) となる。(Source: [[@1992__SPAA__The Network Architecture of the Connection Machine CM-5]]) 「セグメント開始」ビットを立てるとそこからスキャンをやり直す、セグメント化スキャンも使える。セグメント化リダクションは、セグメント化スキャンを前方と後方で 2 回行うことで作れ、網がパイプライン化されているので追加の負担は小さい。著者らは、CM-2 の経験から、組み合わせ論的・数値的を問わず多くの高性能データ並列アルゴリズムがスキャンを多用することを、ハードウェア実装の動機に挙げる。演算子は「ハードウェアを速く単純に保つ」ことと「他の演算を作る部品として十分」であることの折衷で選び、たとえば AND は OR からド・モルガンの法則で作れるので両方を実装しない。(Source: [[@1992__SPAA__The Network Architecture of the Connection Machine CM-5]]) ここでのスキャンは、JTAG のバウンダリスキャンとは無関係である。 ## 未解決の問い - ハードウェアのスキャン演算は、現代の網内集約(スイッチ側の集団演算)とどう位置づくか。 ## 未編纂の観察 ## 関連 - 概念: [[データ並列プログラミング]] / [[バリア同期]] / [[インネットワーク集約]] / [[集合通信]] - ソース: [[@1992__SPAA__The Network Architecture of the Connection Machine CM-5]] - エンティティ: [[Connection Machine CM-5]] ## 出典 - [[@1992__SPAA__The Network Architecture of the Connection Machine CM-5]]