並行コンピューティング技法2章

Shinichi Tokunaga @deepneko

2章タイトル：「並行か非並行か？それが問題だ」ｗ

Shinichi Tokunaga @deepneko

タスク分解とデータ分解

Shinichi Tokunaga @deepneko

タスク分解で大きく考えなければならないことは3つ。1

Shinichi Tokunaga @deepneko

タスクとは何か。どのように定義するか？

Shinichi Tokunaga @deepneko

タスク間に依存性はあるのか。その条件は？

Shinichi Tokunaga @deepneko

タスクのスレッドへの割り当てはどのように行うのか？

Shinichi Tokunaga @deepneko

タスク分解の原則1. 最小でもスレッド数と同じ数のタスク数にしましょう。

Shinichi Tokunaga @deepneko

まぁ基本的にはタスク数をスレッド数より多くしたほうがいい。当たり前だけどアイドルスレッドを発生させないため。

Shinichi Tokunaga @deepneko

タスク分解の原則2. タスク内の処理量は、タスクとかスレッドを管理するオーバーヘッドより多くしましょう。

Shinichi Tokunaga @deepneko

このへんはバランスをとればいい。あんまり1タスクに使うスレッドが多すぎると1スレッドの管理オーバーヘッドが多くて損するし。

Shinichi Tokunaga @deepneko

タスク間に発生する依存性1. 順序依存。

Shinichi Tokunaga @deepneko

タスク間に発生する依存性2. データ依存。

Shinichi Tokunaga @deepneko

これはまぁ直感的にわかる場合が多い。変数の代入に複数のスレッドが関わってるかどうかを見ればいい。

Shinichi Tokunaga @deepneko

依存性がまったくないソースコードを魅惑的並列(enchantingly parallel)というらしいｗ

Shinichi Tokunaga @deepneko

データ依存の単純な解決方法：スレッドからのみアクセス可能な変数を定義する。

Shinichi Tokunaga @deepneko

つまりTLS(スレッドローカルストレージ)

Shinichi Tokunaga @deepneko

まぁ、それが無理なら素直に共有変数にmutexかなんかで単純なロックをつけて使いましょうｗ

Shinichi Tokunaga @deepneko

もちろん同期処理が追加されるからオーバーヘッドは増えるよ。

Shinichi Tokunaga @deepneko

タスクのスレッドへの割り当てをどうするか考えるときは、最初は静的スケジューリングを考えましょう。プログラミングが一番単純だから。

Shinichi Tokunaga @deepneko

もちろんタスク間の処理量にばらつきがあったり、予測不可能な場合は動的スケジューリングを使わざるを得ません。

Shinichi Tokunaga @deepneko

データ分解は大規模データを分割してスレッドで分担することですね。

Shinichi Tokunaga @deepneko

データ分解の一番一般的な対象は配列ですね。

Shinichi Tokunaga @deepneko

並列化するとアプリケーションの実行というものが、大規模データの全要素を更新する処理ばかりだということに気づく。

Shinichi Tokunaga @deepneko

チャンク(分割されたデータ)は各タスクに割り当てられる。

Shinichi Tokunaga @deepneko

つまりタスク分解でのタスク定義の原則が、データ分解でもそのまま当てはまるわけです。