マルチコア時代のLock-free入門

+45

No comments posted yet

Comments

Slide 1

マルチコア時代の Lock-free入門

Slide 2

Lock-freeアルゴリズムとは マルチコアのCPUが当たり前の時代 並列動作ができないプログラムは悪 単にマルチスレッド化するだけではダメ! アムダールの法則:並列に処理できない部分が少しでもあると、性能に大きく影響する 並列性を高め、性能をより発揮させるための手法が重要になってくる その一つが「Lock-freeアルゴリズム」

Slide 3

サンプルプログラム int alice = 100; int bob = 0; void transfer(int amount) { alice -= amount; bob += amount; } int sum() { return alice + bob; } 関数transferを何度呼び出しても、関数sumの結果は変わらないはず。 でも、transferとsumを別スレッドが同時に実行すると、それが崩れる。 つまり…スレッドセーフでない

Slide 4

スレッドセーフにするための手段 ロックによる排他制御 データ構造に対する操作を、同時には1スレッドだけに制限する ロックが競合すれば並列性は下がる Lock-freeアルゴリズム アトミックな操作の組み合わせで処理を行う 並列実行を妨げない

Slide 5

ポインタを用いたLock-freeの実現 alice = 100 bob = 0 alice = 80 bob = 20 ポインタ transfer(20) の処理 (1) 現在のデータをもとに、更新後のデータを格納したオブジェクトを作る (2) 更新後のデータオブジェクトを指し示すようにポインタを更新する sum() の処理 (1) ポインタの指し示すオブジェクトの参照を得る (2) 上記オブジェクトのaliceとbobの合計を返す この操作の前後で、データの一貫性が保たれていることが重要! *重要* ポインタの読み書きはアトミック(不可分)でなければならない どちらを指しているかはタイミング次第

Slide 6

C++0xでの実装例 struct Node { int alice; int bob; }; std::atomic<Node*> data = new Node(); // 初期値の設定については省略 void transfer(int amount) { int sum() { Node* old = data; Node* node = data; Node* node = new Node(); return node->alice + node->bob; node->alice = old->alice - amount; } node->bob = old->bob + amount; data = node; } C++0xで導入されたアトミックなポインタ型

Slide 7

同時に更新するときの問題点 alice = 100 bob = 0 alice = 80 bob = 20 ポインタ transfer(20) (1) Aのデータをもとに、更新後のオブジェクトBを作る (2) オブジェクトBを指し示すように、ポインタを更新する ポインタの指す先がAからBに変わっているのに気付かずに、Cで更新してしまったのが問題 transfer(10) alice = 90 bob = 10 A B C (1) Aのデータをもとに、更新後のオブジェクトCを作る (2) オブジェクトCを指し示すように、ポインタを更新する この変更結果が失われてしまう

Slide 8

Compare-and-swap命令 「元の値から変わっていなければ、新しい値に更新する」という操作をアトミックに行う命令 ⇒ Compare-And-Swap (CAS) if (data == old_value) { data = new_value; return true; } else { return false; } 比較が一致しなかったときはdataの現在値を返すようなバリエーションもある

Slide 9

CASを用いた実装例 void transfer(int amount) { Node* old = data; Node* node = new Node(); do { node->alice = old->alice - amount; node->bob = old->bob + amount; } while (!data.compare_exchange_strong(old, node)); } CASを使って更新を試み、失敗したらやり直す ⇒ “CAS loop” と呼ばれる基本パターン if (data == old) { data = node; return true; } else { old = data; return false; }

Slide 10

Lock-freeアルゴリズムの基本 一貫性を保持したまま、アトミック操作の組み合わせによってデータを更新していく ⇒ このアルゴリズムがLock-freeのキモ Compare-and-swap命令は超重要 とりあえず実行してみて、失敗したらやり直す ⇒ いわゆる「楽観的同時実行制御」

Slide 11

Lock-freeアルゴリズムの落とし穴 「リオーダー」の問題 「メモリ回収」の問題

Slide 12

落とし穴その1 - リオーダー 「リオーダー」とは ⇒ コンパイラ、VM、CPUなどにより命令の実行順序が変えられること 性能向上のために行うことなので、これ自体は悪いことではない マルチスレッドプログラムでは、リオーダーのために不正な実行結果となることがある ⇒ 悪影響のあるリオーダーを防ぐ仕組みが必要 それが「メモリバリア」

Slide 13

メモリバリアを正しく使うには メモリバリアが必要な場所はどこか? 基本的にはアトミック命令の前後 C++0xのstd::atomic、JavaのAtomic*型などは、メモリバリアとしての効果も持つ とりあえずは、この仕組みに任せておけばOK より深い話に興味のある方はこちら↓ 「そろそろvolatileについて一言いっておくか」 http://d.hatena.ne.jp/bsdhouse/20090720/1248085754

Slide 14

落とし穴その2 - メモリ回収 alice = 100 bob = 0 alice = 80 bob = 20 ポインタ transfer() の処理 (1) 現在のデータをもとに、更新後のデータを格納したオブジェクトを作る (2) 更新後のデータオブジェクトを指し示すようにポインタを更新する このオブジェクトが解放されていない!

Slide 15

単純にdeleteを加えてみる void transfer(int amount) { Node* old = data; Node* node = new Node(); do { node->alice = old->alice - amount; node->bob = old->bob + amount; } while (!data.compare_exchange_strong(old, node)); delete old; } ⇒ ダメ。

Slide 16

単純deleteで問題が出るケース alice = 100 bob = 0 alice = 80 bob = 20 ポインタ transfer() の処理 (1) 現在のデータをもとに、更新後のデータを格納したオブジェクトを作る (2) 更新後のデータオブジェクトを指し示すようにポインタを更新する sum() の処理 (1) ポインタの指し示すオブジェクトの参照を得る (2) 上記オブジェクトのaliceとbobの合計を返す (3) 更新前のデータオブジェクトをdeleteする deleteされたオブジェクトへアクセスしてしまう!

Slide 17

オブジェクトを再利用してみる 単純にdeleteするのはダメ。でも、そのままだとメモリリークしてしまう。 ⇒ オブジェクトを使いまわしてみては? transfer() の中で delete せずに、次回のtransfer() 呼び出しのときに再利用してみる

Slide 18

オブジェクト再利用での失敗例(1) alice = 100 bob = 0 alice = 80 bob = 20 ポインタ transfer(20) [1回目] sum() (1) ポインタの指し示すオブジェクトの参照を得る (2) 上記オブジェクトのaliceとbobの合計を返す 2回目のtransferによって書き換えられている途中の値が見えてしまう! transfer(20) [2回目・途中まで] alice = 60 bob = 0 次回再利用するために、保持しておく

Slide 19

オブジェクト再利用での失敗例(2) alice = 100 bob = 0 alice = 80 bob = 20 ポインタ ポインタの指す先が同じAなので、その内容が変化しているときでもCASが成功してしまう。 transfer(10) alice = 90 bob = 10 A B C (1) Aのデータをもとに、更新後のオブジェクトCを作る (2) CAS命令を用いて、Aを指しているポインタを、Cを指すように更新する transfer(20) [1回目] transfer(20) [2回目] alice = 60 bob = 40 「ABA問題」

Slide 20

オブジェクトを安全に再利用するには 更新回数をカウントする「タグ」をポインタに付ける ポインタを更新するたびに、タグの値もインクリメントする 操作の途中でタグやポインタの値が変化していたらやり直し ⇒ タグとポインタをまとめて一度に扱えるCAS命令が必要

Slide 21

再利用オブジェクトの管理問題 再利用するオブジェクトをどう管理するか? スレッド毎に保持するのが基本パターン ⇒ スレッド毎の管理であれば排他の必要が無い 各スレッドで、オブジェクトの生成・破棄に偏りがある場合が問題 ⇒ 再利用オブジェクトをスレッド間で共有しようとすると、そこでも排他制御が必要になってくる

Slide 22

オブジェクト再利用以外の解決方法 C++0xには参照カウンタ方式のスマートポインタ std::shared_ptr がある! しかも、マルチスレッドに対応していて、CAS命令などもある さっそく使ってみよう!

Slide 23

C++0x shared_ptr による実装 std::shared_ptr<Node> data(new Node()); void transfer(int amount) { std::shared_ptr<Node> old = std::atomic_load(&data); std::shared_ptr<Node> node(new Node()); do { node->alice = old->alice - amount; node->bob = old->bob + amount; } while (!std::atomic_compare_exchange_strong(&data, &old, node)); } int sum() { std::shared_ptr<Node> node = std::atomic_load(&data); return node->alice + node->bob; }

Slide 24

C++0x shared_ptr の効果 参照が無くなったオブジェクトは必ず解放される メモリリークの心配なし それを参照するスレッドが一つでも残っている限り、オブジェクトの再利用はされない ABA問題も発生しない これで完璧! Lock-free完成!! …とはなりません

Slide 25

マルチコアプログラミングのセオリー 複数のスレッドが同一メモリ領域に対して書き込みを行うのはコスト大 CASやアトミックな加算・減算などは数百クロックサイクルを超えることも パフォーマンスを出すためのセオリー 書き込みを行うメモリ領域はスレッド毎に分散させる CASなどのアトミック命令は必要最小限にする

Slide 26

C++0x shared_ptr の欠点 std::shared_ptr は参照カウンタ方式 対象オブジェクト毎に参照カウンタがあり、それをアトミックにインクリメント・デクリメントする つまり、 std::shared_ptr で管理される オブジェクトを複数スレッドから扱うのは、 とてつもなく遅い

Slide 27

参照カウンタに対する操作は? std::shared_ptr<Node> data(new Node()); void transfer(int amount) { std::shared_ptr<Node> old = std::atomic_load(&data); std::shared_ptr<Node> node(new Node()); do { node->alice = old->alice - amount; node->bob = old->bob + amount; } while (!std::atomic_compare_exchange_strong(&data, &old, node)); } int sum() { std::shared_ptr<Node> node = std::atomic_load(&data); return node->alice + node->bob; } +1 -1 -1 +1 -1 +1 -1 CAS

Slide 28

参照カウンタ方式の限界 参照カウンタ方式である std::shared_ptr の実行コストは、Lock-freeアルゴリズムのメリットを台無しにする! マルチスレッド環境において、もっと低コストでオブジェクトの安全な破棄を行なう方法は無いのか?

Slide 29

Hazard pointer 他スレッドのローカル変数内に、用済みオブジェクトへの参照が残っているときが問題 ⇒ 用済みオブジェクトの破棄を、他スレッドがそれを参照しなくなるタイミングまで遅らせればよい ⇒ でも、他スレッドのローカル変数が何を参照しているかを、直接的に調べることはできない ⇒ そこで登場するのが “Hazard pointer”

Slide 30

Hazard pointer とは スレッド毎に用意されるポインタ変数 書き込みは、それを所有するスレッドだけが可能 読み込みは、どのスレッドからも自由に行なえる

Slide 31

Hazard pointerのアルゴリズム alice = 100 bob = 0 alice = 80 bob = 20 ポインタ transfer() の処理 (1) 現在のデータをもとに、更新後のデータを格納したオブジェクトを作る (2) 更新後のデータオブジェクトを指し示すようにポインタを更新する sum() の処理 (1) ポインタの指し示すオブジェクトの参照を得る (4) 1のオブジェクトのaliceとbobの合計を計算 (3) 他スレッドのhazard pointer全てをスキャンし、更新前オブジェクトへの参照があるか調べる (2) 1のオブジェクト参照をhazard pointerに記録する (3) ポインタの値を読み取り、1の値から変わっていないことを確認する(変わっていたら1に戻る) (5) hazard pointerの内容をクリアする (6) 4の結果を返す Hazard pointer (4-a) hazard pointerに参照があれば、今回は破棄せず、後で3以降の処理を再実行するためにオブジェクトをストックしておく (4-b) hazard pointerに参照がなければ、オブジェクトを破棄する alice = 60 bob = 40

Slide 32

Hazard pointer の性能 Hazard pointer のオーバーヘッドは? 書き込みはスレッド毎に別々の変数に対して行なわれるので、コストは低い Hazard pointerのスキャンはコストの高い処理だが、破棄予定オブジェクトを1個ずつ処理するのではなく、複数個まとめて処理することで低減することが可能 書き込み順が重要なのでメモリバリアが必要 ⇒ 総合的には良好な性能を示す

Slide 33

Garbage collection (GC) の利用 GCがあれば、オブジェクト回収の問題は解決 std::shared_ptr のようにオブジェクト参照を逐一追いかけるよりも、一度にまとめてスキャンするほうが総コストは低くなる ⇒ Hazard pointer も同じコンセプト 短命なオブジェクトを使うことの多いLock-freeアルゴリズムは、GCと相性が良い

Slide 34

Lock-freeならJavaをやれ 実際、最新のJavaVMに搭載されているGCアルゴリズムは、マルチプロセッサ上で良好な性能を発揮する ⇒ Lock-freeアルゴリズムを勉強するなら、JavaVM上で動く言語にすべき!!

Slide 35

まとめ Lock-freeアルゴリズムの基本 Compare-and-swap (CAS) 実装上の注意点 リオーダー メモリバリアで対処 メモリ回収 (参照カウンタ式ではない)GCがある言語を使うべき それが無理なら「タグ付きポインタ」や「Hazard pointer」などを使う

Summary: Lock-freeアルゴリズムの基本的な考え方を説明し、実装上の注意点としてメモリバリアやメモリ回収アルゴリズムについて解説していきます。

Tags: multithreading lock-free c++

URL:
More by this User
Most Viewed
Previous Page Next Page