2010年1月2日

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

まとめました。
1
Shinichi Tokunaga @deepneko

2章タイトル:「並行か非並行か?それが問題だ」w

2010-01-02 16:00:12
Shinichi Tokunaga @deepneko

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

2010-01-02 18:59:26
Shinichi Tokunaga @deepneko

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

2010-01-02 18:59:37
Shinichi Tokunaga @deepneko

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

2010-01-02 18:59:48
Shinichi Tokunaga @deepneko

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

2010-01-02 19:00:02
Shinichi Tokunaga @deepneko

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

2010-01-02 19:02:42
Shinichi Tokunaga @deepneko

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

2010-01-02 19:03:26
Shinichi Tokunaga @deepneko

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

2010-01-02 19:04:22
Shinichi Tokunaga @deepneko

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

2010-01-02 19:06:11
Shinichi Tokunaga @deepneko

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

2010-01-02 19:09:09
Shinichi Tokunaga @deepneko

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

2010-01-02 19:11:50
Shinichi Tokunaga @deepneko

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

2010-01-02 19:13:27
Shinichi Tokunaga @deepneko

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

2010-01-02 19:15:54
Shinichi Tokunaga @deepneko

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

2010-01-02 19:18:33
Shinichi Tokunaga @deepneko

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

2010-01-02 19:18:45
Shinichi Tokunaga @deepneko

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

2010-01-02 19:20:14
Shinichi Tokunaga @deepneko

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

2010-01-02 19:20:48
Shinichi Tokunaga @deepneko

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

2010-01-02 19:24:07
Shinichi Tokunaga @deepneko

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

2010-01-02 19:26:05
Shinichi Tokunaga @deepneko

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

2010-01-02 19:46:16
Shinichi Tokunaga @deepneko

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

2010-01-02 19:46:39
Shinichi Tokunaga @deepneko

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

2010-01-02 19:48:09
Shinichi Tokunaga @deepneko

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

2010-01-02 19:53:25
Shinichi Tokunaga @deepneko

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

2010-01-02 19:58:07
残りを読む(15)

コメント

コメントがまだありません。感想を最初に伝えてみませんか?