- 追加された行はこの色です。
- 削除された行はこの色です。
[[C]]
*概要 [#u8b2a13d]
-並列プログラミング技法のまとめ
-TODO もっと簡潔に、勉強になる問題の抽出をしたい。
*参考 [#ffe72176]
-Patterns for Parallel Programmingなるものに大量のパターンがあるらしい。
-https://deadlockempire.github.io/ スレッドセーフでないプログラムをバグらせて遊ぶゲーム
*メモ [#l20166d5]
-手順
++時間のかかっているところを特定
++プロファイラで時間計測
++独立かチェック
-バグ
--デバッガを使うと再現しない可能性
--計算順序が違うので丸め誤差で計算結果が一致しない可能性
-並列コンピューティングのチューニン＜本日大安＞BIG・totoご購入をご検討下さい
--逐次の考え方
+++キャッシュの非効率な共有
+++非効率なメモリアクセス
+++バスのオーバーロード
--並列ならではの考え方
+++同期オブジェクトの競合
+++スレッドごとの不均等な処理割り当て
+++スレッドAPIの異常なオーバヘッド
+++スレッドをそもそも使うまでもない処理量
-開発手順
--逐次のアルゴリズムを作ってから、並列化に移植すべき
--アルゴリズムのバグか並列化のバグかがわからなくなるため
--即並列を組むのは慣れてからにしましょう
-各メモリに対して以下の4パターンを割り当てる。
--並行or排他
--参照or更新
-スレッドの割り当て
--実行前に割り当てるのを静的
--実行中に割り当てるのを動的（各スレッドの実行時間が大きく違うorはじめにスレッド数が予想できない場合）
-メモリ
--分散メモリ・共有メモリという概念がある（TODO）
--TLS：スレッド固有なメモリが利用可能（とても重い！）
---変数のローカルコピーが必要で他の変数からも参照しないといけない場合
---スレッドが同じ関数を別の場所からも呼ぶ必要ある場合
--参照＞＞更新の変数には、リードライトロックを利用するといい
-''タスク分解とデータ分解''
--処理順序の独立性＝時間的独立性→タスク分解
--データのそれぞれに対しての独立性＝空間的独立性→データ分解
--OpenMPはデータ分解に特化したもの
-タスク分解の原則（トレードオフになっていることに注意）
++スレッド数<=タスク数にする
++スレッドの処理量＝''粒度''＞オーバヘッド（つまり、なるべく粒度は大きい方がいい。スレッド数増加に対してもスケーラブルになりやすい。）
--したがって、コアを全部使うと性能が下がることもある。
-依存性
--時間依存性
--空間依存性＝データ依存性（代入分だけ見ればわかりやすいが、ポインタがあると意味不明になる）
-独立性の増やし方
--漸化式を消す・帰納変数＝ループ変数をなくす・分割する
-データ分解の要件
++データチャンク分割法
---データの''形状''は、「隣接データ」と「交換＝外のチャンクのデータを使うこと」に影響
---''経験的には、ボリューム-サーフェース比を最大にするのがいい''
++チャンクを割り当てられたタスクが、更新すべきデータ全てにアクセス可能な保証
++スレッドに割り当てられたチャンクの状態
*Ben-Aliの並列化検証法 [#k9937645]
-かなり重要。
-並列プログラムの理解
--プログラムとはアトミックな処理の連続である
--並列プログラムはアトミックな処理をインターリーブする
--任意のインターリーブで期待した処理をする（この組み合わせは指数関数的に増える）
--アトミックな実行文はいつかは実行される（公平性）
-インターリーブ分析
--必要なこと：現状の定義、スレッドごとの処理の順番を考えること
--心配すること：デッドロック、スターベーション
-クリティカルリージョン
--''共有変数の参照変更''
--必ず1スレッドからしか参照されないように、排他処理が必要
--他のスレッドがクリティカルリージョンに入っているときは、自分は入れない
--いい加減にクリティカルリージョンを実装しようとするとだいたい問題が起きる（1-3段階）
-デッドロックの4条件（''これのうち一つでも不成立ならOK''）
++相互排除条件＝リソースを同時に取りうる状態が以下のどちらか「利用可能」「1スレッドのみが使用中のいずれか」
++獲得後ウェイト＝リソース獲得済みのスレッドが、新たなリソースを獲得しようとする
++プリエンプトなし＝スレッドがリソースを獲得後は、そのリソースを削除できるのは獲得したスレッドが自発的にリソースを開放した時だけ
++循環待ち＝スレッドの循環が発生し、和の中の次のスレッドがすでに獲得しているリソースを獲得しようとしている。
-スターベーション
--条件はない。''インターリーブ分析のみによって発見可能''
*性能指標 [#s43cc288]
-高速化比率
--1コア実行速度/nコア実行速度
-コア数-高速化比率曲線
--理想的には係数1の直線になるはず。
--そうならない場合は''スケーラビリティが悪い''という。
-スーパーリニア
--コア数を超える倍率の高速化
--原因はデータが小さくて、キャッシュにデータがすべて収まってしまうから。大規模データでテストしましょう。
-Amdahlの法則
--逐次ソースコードを並列化することでどれくらいの高速化が可能かを予想できる
--並列処理可能割合&mimetex($p$);、直列限定処理割合&mimetex($q$);(p+q=1)、コア数nとして、処理時間はq+p/n以下にはならない。
--これによって、''コア数-高速化比率曲線が予想可能''
-Gustafan-Barsisの法則
--並列ソースコードがどれくらいの高速化を達成しているかを測定できる
--直列限定処理時間対全部処理時間&mimetex($s$);、コア数&mimetex($n$);として、高速化率はn-(n-1)s以下である。
-実行効率
--nコア並列実行時間&mimetex($t_n$);、1コア実行時間&mimetex($t_s$);とした時、実行効率は&mimetex($t_s / (n t_n)$);
--低いとコアが使い切れていない
*具体的なライブラリ [#a2cfaadc]
-OpenMP, TBB, pthread, OpenCL(GPU)
-OpenMP
--ローカルコピーする変数の明示できる（private）
--パラレルリージョンという概念があり重要（パラレルリージョンじゃないと使えない指示子があるので）
--チャンクサイズはschedule指示節で指定
-TBB
--Lambdaが使える！
--チャンクサイズを自動調節
-pthread
--より低次な処理
*具体的なアルゴリズム [#yda47292]
-PRAMモデル
--配列を完全二分木とみなすことでアルゴリズムの高速化ができる
--並列和、プレフィックススキャンはPRAMに非常に向いている
-プレフィックススキャン(例6.8)
--使い道：セレクション＝リスト（未ソート）からk番目に大きい数値を取り出す（O(n)で可能, 例6-12）
*MapReduce [#e7819818]
-Mapデータ構造をReduceするアルゴリズム
--分割統治法、バックトラック法など
-変形例
--CountAndMarkでは1つの合計→3種類の合計を一度に算出(6.3.3)
--スキャン処理を用いてデータの値を解釈、論理バイナリのように処理
--配列を完全二分木とみなす (PRAM)
*ソート [#s20ed9b0]
-''プロセッサ時間の80%以上はソートに費やされている''
*性能解析ツール [#deb261e3]
-gdbはスレッドに対応
-スレッドチェッカ
--Intelスレッドチェッカはメモリ領域での衝突・デッドロックの可能性・スレッドのストールを検出可能
--Intel VTuneパフォーマンスアナライザをのプラグインとして使うと、動的解析可能（ストレージコンフリクトを見つけるには、スレッドのメモリアクセスをすべて監視するなど）
-プロファイリング（ホットスポットの特定）
--gprofは-pgオプションでプロファイル用にコンパイルされたプログラムを解析可能。
--Intel VTuneパフォーマンスアナライザ
*よくわからなかったところ [#ad1b9a6b]
1.3.2
1.4.2.2
2.1.1
キャッシュライン、キャッシュラインのデータの共有とは。
偽共有とは。実行効率の解析でよく出てくるので重要そう。
配列のパッキングとは
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
