狠狠撸

狠狠撸Share a Scribd company logo
経済学のための并列分散処理2
Masa Kato
August 4th, 2018 @ Ichimura-seminar
1
コンテンツ
?目的
? 経済学の研究者に並列分散処理について説明する.
? いくつかの具体的な実装例を紹介する.
? Value Function Iterationに適用できるかを検討する.
?目次
1. 並列化とは何か
2. CPUとGPU
3. 並列計算の設計方法
4. 並列計算の評価
5. 並列アルゴリズム
6. Value Function Iteration
2
第4節:並列計算の評価
3
Amdahlの法則
?プログラムの中で並列化可能部分の割合が大きくなければ意味がない.
4
パレートの法則
?「プログラムの処理にかかる時間の80%はコード全体の20%の部分が占め
る」という経験則.
?注?パレートの法則?体は世の中の様々な現象に使われる法則であり、プ
ログラムは?例.
?Amdahlの法則において、プログラム実?の80%を並列化したいとき、パ
レートの法則に則っていればコードの20%に関する並列化検討をすればよ
いことになる.
5
メニーコア向けAmdahlの法則
?並列化可能部分はメニーコア実行がよいが,並列化不可能部分は高性能な
単一コア実行が良い.
?メニーコアの3シナリオ
? 対称型:すべてのコアが同じ能力を持つ(通常のAmdahlの法則と同じ).
? 非対称型:一つの高性能コア(CPU)と複数の軽いコア(GPU).
? 動的変更型:あるときは高性能コア,あるときにはメニーコア.
?4個のコアと同じ面積で4倍性能の単一コアができるわけではない.
? Perf(r):r個のコアと同じ面積を単一コアで使ったときに出せる性能.
6
Amdahlの法則とスケーラビリティ
7
並列化不可能部分の割合を
導出するKarp–Flatt metricも
評価に使用される.
スケーラビリティと呼ばれる.
第5節:並列アルゴリズム
8
並列アルゴリズム
?代表的な並列アルゴリズム
? ソーティング
? Parallel Prefix
? 最短経路探索
? 木探索
?OpenMPを使うとマルチスレッド並列化に関する(実際に自分で書こうとす
ると)面倒な実装を自動で行ってくれる.
? どこで何を並列化するかはエンジニアが決める必要がある.
9
並列ソート
?(ここでの)ソートの定義
?ソートされていない値のリストが、プロセッサの主記憶にほぼ同数分散さ
れて記憶されている.
?ソートの完了時はすべてのプロセッサに記憶されている数のリストはソー
トされている.
? すべての? (0 ≤ ? ≤ ? ? 2) に対して??のリストの最後の値は、 ??+1のリスト
の最初の値よりも同じか?さい.
? 各プロセッサに記憶されている値の数は同数である必要はない.
10
並列Quicksort(1)
11
Pivotに選択する.
これを基準に大小に分ける
?リストは複数のスレッドに分かれて配置されている.
並列Quicksort (2)
12
Pivot = 67
新しいPivotを選択する.
並列Quicksort (3)
13
Pivot = 67
Pivot = 86Pivot = 49
その他のソーティング
?ソーティグだけでも多くの並列化手法が存在する.
14
Bellman-Ford法
?並列化は容易だがオーバーヘッド大.
15
?最短経路問題においても幾つのかの並列化
手法が考えられている.
Ex: Δ-Stepping Algorithm
木構造探索
16
木構造の探索候補
17
深さ優先探索
18
幅優先探索
19
ゲーム木探索
20
ゲーム木探索
?AND-OR?
?ノードの値: (第1プレイヤの)ゲイン?利得
?ORノード(MAXノード)
? 第1プレイヤの順番.
? 第1プレイヤはゲインを最大化したい(MAX).
? 第1プレイヤは最も良いノードを選択、すなわちすべての条件を考慮する必
要はない(OR)→勝てるパスが1つでもあれば、そこに突き進めばよい.
?ANDノード(MINノード)
? 第2プレイヤの順番.
? 第2プレイヤはゲインを最小化したい(MIN).
? 第1プレイヤはすべての可能性を考慮する必要がある(AND)→負けるパスが1
つでもあればそこに進まれるので、すべての可能性で負けないことを確認.
21
Alpha-Beta枝刈り法(1)
22
Alpha-Beta枝刈り法(2)
23
Alpha-Beta枝刈り法(3)
24
Alpha-Beta枝刈り法(4)
25
Alpha-Beta枝刈り法(5)
26
Alpha-Beta枝刈り法(6)
27
Alpha-Beta枝刈り法(7)
28
Alpha-Beta枝刈り法の並列化
29
計算結果を同期していないと,Xプロセッサでの計
算結果を反映して枝をカットすることができない.
OpenMPを使う
?先述のアルゴリズムを0から実装するのはスレッドの割り当てなどが複雑な
ので大変な作業になる.
?OpenMPを使うとスレッド管理が楽になる.
?歴史
?OpenMP以前:
?1997年:Fortran言語向けの仕様で発表
?1998年:C/C++向けに拡張
? 業界標準規格に.
? 言語ではなくAPI.
30
OpenMPの仕組み
?Fork-Join型スレッドモデルを採用
? #pragmaによるOpenMP指示文の位置に達するまではプロセスは一つのス
レッドで実行されている.
? 並列領域に達するとスレッドチームを生成する.
? 領域を過ぎるとスレッドが一つのスレッドに戻る.
31
#pragma
終了
並列化スレッド
OpenMPはどのように並列化するか
nowait節を指示文のパラメータ
として指定することで暗黙のバ
リアをなくすことができる.
32
single構文
for構文
sections構文
parallel構文
OpenMPのデータスコープと同期
?OpenMPで並列化されたコードがアクセスするデータ変数はグローバル変数
とローカル変数に分けられる.
?ローカル変数
? OpenMPの並列化領域内で宣言されている変数でスレッド固有.
?グローバル変数
? ローカル変数以外のスタティック変数やダイナミック変数はすべてグローバ
ル変数
33
グローバルデータ
スレッド1のメモリ空間
スレッド2のメモリ空間
スレッド3のメモリ空間
スレッド4のメモリ空間
? 排他制御の必要性
? 同期の必要性
? atom構文の利用
?Value Function Iterationにおい
ても問題になる.
OpenMPのデータスコープと同期
34
この二つのコードで結果が異なる!
OpenMPを使った悪いコードの例
35
OpenMPを使った悪いコードの例
?正しいコードの例.
?reductionに対して自動同期する.
? forループ内のsum += a
?しかし,これでも並列化しない場
合よりも遅い.
36
第6節:Value Function Iteration
37
Value Function Iteration
?Social Plannerの最適化問題は以下のように書き表すことができる.
? ? = ??? ?′{? ? + ?? ?′ }
?. ?. ? = ? ? + 1 ? ? ? ? ?′
? ? :現時点での総資本.
? ?′ :次時点での総資本.
? ?:代表的家計の消費.
? ?(?):ある期に得られる効用.
? ?:資本の生産に対する弾力性.
? ?:割引率.
? ?: depreciation rate
38
擬似コード
?A Practical Guide to Parallelization in Economicsに掲載されていたコード.
39
? ?個のプロセッサーを用いて並列化する.
? 各プロセッサーで分割された現時点での資
本ごとに価値関数を計算する.
? ?+1
(?1)
擬似コード
40
1期
2期
3期
4期
5期
プロセッサー1
が価値関数の値を示している.
プロセッサー2
掲載のアルゴリズムは本当に正しいのか?
?問題点
1. 範囲を分割して代入した資本ごとの価値関数の計算結果を各期ごとに同期
しないといけない(同期の問題)
2. 状況によっては排他制御が必要になる場合が生じる(参照の問題).
? メモリが同じであるために生じうる問題.
C言語もしくはFortranで書いてしまえばCPUでの並列化もGPUでの並列化も
(雑な形では)簡単に行えるためにとりあえず実装して試せばいいが,性能
が出なかった場合には上記の問題を考える必要がある.
41

More Related Content

経済学のための并列分散処理2