Skip to content

Instantly share code, notes, and snippets.

@sile

sile/amp_5-6_summary.md

Last active December 10, 2015 14:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sile/4448401 to your computer and use it in GitHub Desktop.
Save sile/4448401 to your computer and use it in GitHub Desktop.
Download ZIP
The Art of Multiprocessor Programming 読書会 五章六章まとめ
Raw
amp_5-6_summary.md

[5] The Relative Power of Primitive Synchronization Operations

  • マルチプロセッサプログラミングのために必要な同期命令プリミティブを考察する章
    • 同期命令 (or 同期オブジェクト)
      • アトミックレジスタ
      • FIFO Queue
      • multiple-assignment
      • common2 RMW (Read-Modify-Write)
      • compare-and-swap
  • 諸々の同期命令はその consensus number によってレベル分けできる
    • consensus number
      • その同期命令が同時に扱えるスレッド数の上限(的な数値)
      • Nスレッドに対して、以下の条件を満たすオブジェクトを実装できるなら consensus number は N
        • 1] Nスレッドが同時に decide(value) メソッドを呼び出したとして、
        • 2] decide(value) メソッドの返り値は、
          • a) 全てのスレッドで等しい (consistent)
          • b) いずれかのスレッドの decide(value) の引数(value)の値になっている (value)
    • より低いレベルの命令をいくら組み合わせても、より高いレベルに属する問題を解決することはできない
  • 結論: compare-and-swapを備えていれば全ての問題が解決可能

個々の命令について

アトミックレジスタ

  • 複数スレッドで競合する単一の読み書き処理をアトミックに処理できるレジスタ
  • consensus number は 1
    • 他のスレッドに自分が書いた値が上書きされてしまったら、それを知るすべがない

FIFO Queue

  • 並列対応FIFOキュー
  • consensus number は 2
    • 最初の要素とそれ以降の要素の値を変えておくことで、 キューから値を取り出したスレッドが「自分が最初かどうか」は判断できるが、 「どれが最初か」を判断するための情報を持たせることはできない
    • スタック、ディーク、優先順序付きキュー等も同様

multiple-assignment

  • (m,n)-assignment とも

    • n: レジスタのフィールド数
    • m: 同時に書き込めるフィールド数

  • (n, n(n+1)/2)-assignmentなら consensus number は n

    • 全てのスレッドにアトミックに変更を通知するために、スレッド数分の同時書き込みが行える必要がある
    • 各スレッドにそれぞれ、他のスレッドの状態を保持するためのフィールドが必要になるので n(n+1)/2 のフィールドが必要

common2 RMW (Read-Modify-Write)

  • Read-Modify-Write命令

    • 以下の条件を満たすならRMW
      • a) レジスタの現在の値 v を f(v) の適用結果にアトミックに置換する
      • b) 戻り値として f を適用前の値を返す

  • RMW命令が以下のいずれかの条件を満たしている場合は Common2 クラスに属する

    • 前提: 関数 f1 および f2 があるとして、

      • a) f1 および f2 の適用順が入れ替え可能: f1(f2(v)) = f2(f1(v))
      • b) 関数が別の関数の結果を上書きする: f1(f2(v)) = f1(v) or f2(f1(v)) = f2(v)

    • get-and-set, get-and-add など

  • Common2に属するRMWの consensus number は 2

    • スレッド数が 2 の場合、自分の処理結果が、初期値に等しければ、自分が最初だと分かる
    • スレッド数が 3 以上の場合は、上の方法での判別は不可能 (FIFO Queueと同様)
      • また、定義上、複数関数を同時に適用した場合は「適用順」or「途中の適用結果」の情報が失われてしまうので、3以上は対応不可

compare-and-swap

  • RMWの一種
    • 引数に期待値と更新値を取り、現在の値が期待値と等しいなら、値を更新する
  • consensus number は 制限なし
    • cas(initial_value, thread_value)を呼び出し、
      • a) initial_value が返れば自分の値を、
      • b) thread_value が返れば、その値を使用すれば良い

[6] Universality of Consensus

  • 五章では consensus number に制限が無い consensus オブジェクトが存在することをみた

    • 本章では、それを使って任意の wait-free 並列オブジェクトが実装可能なことを説明している
    • ただし性能的に現実的な解ではないことに注意 (原理的に可能、というだけ)

  • Universal Construction

    • 任意の wait-free 並列オブジェクトを構築するための基盤部品
    • メソッド呼び出し(適用)を wait-free かつ atomic に行うための仕組み

  • まず lock-free 版から

    • オブジェクトのメソッドの呼び出し履歴を全て保持
    • 新規メソッド呼び出しの際には、履歴に新規メソッド呼び出しを追加して、履歴中の全ての呼び出しを再実行する
    • 履歴への追加の競合解決は consensus オブジェクトの decide メソッドで行う
      • 自分の呼び出し(invoc)がdecideされたら履歴に追加、そうではないなら処理を繰り返す
      • 他スレッドと競合が発生し得るのは、履歴追加時のみ
    • あるスレッドがbusyの場合は 別のスレッドが decide に失敗し続ける可能性があるので lock-free

  • 次に wait-free 版

    • 基本は lock-free 版と同じ
    • 履歴追加の際に、自分よりも優先すべきスレッドがないかを探す処理が入る点が異なる
    • 処理的には、
        1. スレッド数分の Invoc配列(announce) を用意し、履歴追加ループの前に自分のinvocを格納しておく
        1. 履歴追加ループの中で、次に履歴に追加するinvocを選択して追加する
          • a) annouce配列を見て、他に優先すべきスレッドのinvocがあるなら、そっちを採用
          • b) 無いなら自分のを採用
        1. 後は lock-free 版とほぼ同様
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment