2014年6月14日土曜日

並列プログラミングに関する基礎知識

SSII2014 で並列プログラミングの良い入門を学ぶことが出来た。
まとめておこうと思う。


名工大 福嶋先生 github
https://github.com/norishigefukushima/SSII2014.git


目的:スループット、レイテンシの向上(数倍)


アムダールの法則:全体のうち並列化できる割合


並列化の単位:粒度


スループット:最大出力の維持


レイテンシ:リアルタイム性の向上


○ スループット > レイテンシ
ex) 画像1000枚を順番に渡す

○ レイテンシ > スループット
ex) 画像を分解して、画素単位で処理、1枚完了までの時間は速い。

問題によって上記のいずれを重要視するかを決定する。


フリンの分類

SISD:1つのデータと1つの命令
MIMD:複数のデータに対して、複数の命令

SIMD:複数のデータ、1つの命令
MISD:1つのデータ、複数の命令(回路を流れるイメージ)(FPGA、回路H/W = パイプライン処理)← 広がってきている

PCのマルチコアはMIMD領域

パターン

Map

1つ1つが画素、縦方向はタイムライン。
fugure の左が直列、右が並列
画素単位:閾値処理、色変換、LUT、透過

Stencil

周辺画素をまとめて処理、FIRフィルター。
エリア(パッチ)単位:平滑化、モルフォロジ

Reduction

並列化しづらい。データ同士の依存関係がある。
各命令の結果が、次の命令に依存する。
→ ブロック毎の処理を行い、最後にまとめる。(分割統治法)
探索:最大値、最小値、レジストレーション

Scan

Reductionの途中計算結果が必要な場合、途中で一度まとめる。
分解が難しい → 圧縮率悪い。
周波数変換:フーリエ、サイン・コサイン、フェーブレット(バタフライなどの分解が可能)

Fork-join

基本形。意味合いは Map。
処理単位(タスク、フロー)は全て分割する。

○Pipe-line
順次終了型。うまく繰り返せばレイテンシに効果がある。
→ TBB (局所特徴量などはTBBで並列化)

複合型:セグメンテーション、局所特徴量など


SIMD (OpenMD 4.0 からSIMDも使える) VSはまだ2.0...


SSE →最近→ AVX
レジスタの決まった領域を同時に計算。
様々な命令セットを選択出来る。(Add、Sub、Div ~)

Reductionに対しては、分割統治法を明示的に記述する。

Stencilに対しては、カーネルをあつめる作業を並列化する。

デメリットがあるので注意。


メモリ load,write のほうがボトルネック


SRAM L1キャッシュ 1CPUサイクルで済む

DRAM 100CPUサイクルかかる

→ メモリアクセスの最適化が必要
→ バイラテラルをやってみる価値はある。


後は、手を動かすことですね。

0 件のコメント:

コメントを投稿