勉強会の2回目があったのでメモ、1回目は下のリンクからどうぞ。
「第2章 並行か非並行か？それが問題だ」
◯大前提
全ての処理を並列化することは出来ない。世の中には並列化が不可能な処理があり、何がそうなのか知っておく必要がある。並行化できないアルゴリズムは以下が代表例。
- 状態を持つアルゴリズム
- 漸化式
- 帰納変数(ループの度に値が増加する、ループ変数とは1対1に対応しないインデックス)
- ループ内の処理依存
◯並行アルゴリズムの設計モデル
順序に依存しない処理を並行に実行する「タスク分解」と、大量のデータの個別の部分を並行して処理する「データ分解」がある。
どちらを選んでも基本のフレームワークは変わらない。タスクを準備し、スレッドへ処理を割り当て、次の処理へ進む前に全てのタスクが完了したことを確認する。
◯タスク分解
スレッドに割り当てるタスクを抽出する難易度はソースコードや処理内容に対する理解に反比例する。良く知っていればタスクの抽出も容易になる。タスクを簡単に見つけ出す裏技はないが、処理時間を多く占めるホットスポットにおいて、ループに着目するとそこがタスク抽出に適していることが多い。数値計算もタスク抽出のポイントとしておすすめ。
抽出したタスクの数にもポイントが有る。まずタスクの数はスレッド数(≒コア数)と同じ数以上にする。これはアイドルスレッドを避けるためである。次にタスクの粒度は出来るだけ大きい方が良い。これは並列化によるオーバーヘッドが生じることが影響している。タスクが大きい方がメモリキャッシュが効くなど性能面で有利な点がある。
タスク同士の間には2種類の依存性がある。1つ目は順序の依存で、あるタスクが他のタスクの処理結果に基づいて実行される場合が該当する。2つ目はデータ依存で、変数の使い方で問題が生じることがある。
タスクの割り当ては最初に決めてしまう静的割り当てと、動的にタスクを決める動的割り当てがある。タスクの処理時間が固定の時は静的割り当てが簡単でオーバーヘッドもなくてよい。処理時間にばらつきがある場合は動的にタスクを割り当てる必要がある。
◯データ分解
基本ルールはタスク分解と同じ。分割する数はスレッド数よりも多くする、細かすぎると並列化によるオーバーヘッドが問題になるので大きい粒度で。処理対象となる分割されたデータ領域をチャンクと呼ぶ。チャンク分割はタスクの粒度と境界長の比率が最大になるように分割すると良い。
チャンクの境界において、別チャンクのデータを参照する必要があると工夫がいる。簡単なのは境界部分を予めスレッドごとにコピーしておく方法がある(ゴーストセル)。そうでなければ処理時に必要に応じて参照させる方法があるが、参照対象のデータが未処理の場合、参照処理をまたしておく必要がある。どちらも一長一短がある。
オライリージャパン
売り上げランキング: 39727
