並行コンピューティング技法 6章: 並列和・プリフィックススキャン

並行コンピューティングを読んでいる。 6章では並列和、プリフィックス・スキャンを通して並列計算について書かれている。 この2つは単純で理解しやすく分析される機会も多いため、並列アルゴリズムの1つの指標になっているらしい。 キーワードについてメモする。

流れはData Parallel Algorithms(Communications of the ACM, 1986) の議論を下地にしている様子。

この論文では並列和・プリフィックススキャンを議論し、 何千ものプロセッサが存在するPRAM(Parallel Random Access Machine) で適切な並列アルゴリズムスタイルを提示しようとしている。

アブストは以下。

マルチプロセッシングで使われる操作並列スタイル(タスク分解, task decomposition)とは対照的に、 何千ものプロセッサを使った並列計算では、概してデータ並列スタイル(データ分解, data decomposition)でプログラムされる。 一見本質的に連続する様に思える問題においてもデータ並列スタイルは成功しており、 このスタイルが以前から考えられていたよりも遥かに広い適応性があることを示している。

Parallel computers with tens of thousands of processors are typically programmed in a data parallel style, as opposed to the control parallel style used in multiprocessing. The success of data parallel algorithms-even on problems that at first glance seem inherently serial-suggests that this style of programming has much wider applicability than was previously thought.

PRAM(Parallel Random Access Machine)

並列アルゴリズムを議論する時に使われる抽象機械の1つ(1章を参考にする)

並列和

ベクトル(1次元配列)の全要素を合計する問題(アウトプットは1つの値)

プレフィックス・スキャン

ベクトル(1次元配列)の全ての部分和を求める問題(アウトプットは1次元配列)

• 包含的プレフィックススキャン: n番目以前の全ての値の演算結果が各要素に格納される
• 排他的プレフィックススキャン: (n-1)番目以前の全ての値の演算結果が各要素に格納される