sile/amp1-2.md

## amp1-2.md

      
    Raw
  

              amp1-2.md
            
          
    | 一章 Introduction - 導入

1.5 The Harsh Realities of Parallelization - 並列化の厳しい現実


理想化された世界で並列化について考えるのは楽しい

N倍多くのプロセッサが使えれば、N倍プログラムが早くなる！


現実にはそうはならない
例: 五人の友人が協力して家の壁を塗る話

各々の作業スピードやそれぞれの部屋の広さが異なる場合、部屋数が5で割り切れない場合にどうなるか


並列化することで全体をどの程度効率化できるかといった分析は重要


Amdahl's Low:


タスク全体を並列実行可能な部分と、直列的にしか実行できない部分に分け、


その並列実行可能な部分をプロセッサの数で割ることで、全体のスピードアップ率を見積もる
[例1] 小部屋四つ、大部屋一つ、作業者五名とした場合:  ※ 大部屋は小部屋の二倍の作業量

　S = 1 / (1/6 + 1/6) = 3倍  (一人でやる場合に比べて)
[例2] 小部屋九つ、大部屋一つ、作業者十名とした場合:

　S = 1 / (1/11 + 1/11) = 5.5倍
直列にしか処理できない部分が少しあるだけで、プロセッサ(作業者)が増えた場合の並列化の度合いが大幅に下がってしまう

=> 利用可能なプロセッサ数が多くなればなるほど問題に


科学計算領域や画像処理の分野では、時たま簡単に並列タスクに分割可能な問題に出くわすこともある

ただし通常のシステムでは Amdahl's low が示すような、全体に占める僅かな直列部分が、並列化によるスピードアップの度合いを大幅に制限してしまうようなケースが大半


その僅かな直列部分を頑張って並列化することはできないか？

例えば、早く終わった作業者が残りの人の作業を手伝えば、もっと効率が上がるのでは？
可能だが、その場合、作業者間の調整のためのコストが追加で必要となる

上手くやれば、全体の性能(スケールアップ)に大きく貢献できる
この部分を(効率的に)並列化するには、大抵、極めて難解な通信・調整処理が必要となってくる
この本は、それを達成するためのツールやテクニックを提供する


例: 素数計算

コードのどの部分をアトミックに実行するか


1.6 Parallel Programming - 並列プログラミング

この本のテーマ、進め方についての要約的な節。

アプリケーションを並列化したくなった時

大抵の場合、通信/調整が不要で簡単に並列化できる(全体に占める割合の大きな)部分を簡単に見つけることができる
残りの簡単に並列化できない部分をどう扱うかが難しい問題であり、この本のテーマ


読者に現代的な調整パラダイムや並列データ構造を提示するのが目的
マルチプロセッサプログラムには様々な挑戦が伴う

理想化されたモデルから実践的なモデルへと、漸進的な改良を通して進んでいく
例えば、最初は相互排除(mutual exclusion)に取り組む

数学的な知見や計算可能性の問題、理想化されたアーキテクチャ上での多数のアルゴリズムの正確性プロパティの分析、から始める


ここで扱うアルゴリズム自体は古典的であり、実践的ではないが、現実の問題について推測する仕方を

特に生存問題(飢餓やデッドロック)についての推測の仕方を学ぶのは大事


そういったアルゴリズムについて推測する一般的な方法を身につけたら、次はより現実的な文脈に注意を払っていく


多様なマルチプロセッサアーキテクチャ上での多岐に渡るアルゴリズムやデータ構造を探検する

1.7 Chapter Notes

省略
1.8 Exercises

省略
【PRINCIPLES - 原理】

| 二章 Mutual Exclustion - 相互排除


相互排除は、マルチプロセッサプログラミングで最も普及している調整手段
この章は、共有メモリを用いた古典的な相互排除アルゴリズムを取り扱う

現実では使われていない。しかし、

相互排除アルゴリズムや正確性問題、同期について考える際の入り口としては理想的


不可能性の証明も導入する

共有メモリを用いた相互排除では何が実現できないか、を教えてくれる


アルゴリズムの証明を行っているまれな章でもある

2.1 Time - 時間


並列プログラミングについて推論する、ということは、ほとんど時間について推論する、ということ

複数の物事が同時に起こったり、あるいは別々に起こったり
複数の時間が重なることができたり、あるいはできなかったり


自然言語では、曖昧すぎて、このような複雑な条件のもとでの推論を行うには弱い

並列スレッド群が時間時間でどのように振る舞うかを記述するための、独自の語彙と記法を導入する


語彙と記法:

スレッド群は同じ(外部からは独立した独自の)時間を共有する
スレッドは__ステートマシン__であり、そのステート(状態)の遷移は__イベント__と呼ばれる
イベントは瞬間的

時間軸の一つの瞬間に発生する
同じ瞬間には複数のイベントが同時に発生することはない (その方が思考の際に便利)

もし複数のイベントの発生時間が近すぎて、どれが先かが分からないようなケースでは、任意の順序が起こりうる、と考える


スレッド_A_ は、イベント列   a₀,a₁,...  を生成する
イベント a_i の j 番目の出現は a_i^j と記述する
イベント_b_ に先行するイベント_a_ は a→b と表記する (total order)
二つのイベント_a₀_ と a₁ は a₀→a₁ という関係を持つ
区間_(a₀,a₁)_ は a₀ から a₁ までの期間を表す
区間_I_B = (b₀,b₁)_ に先行する 区間_I_A = (a₀,a₁)_ は a₁→b₀ が成り立つなら I_A→I_B と表記する

区間に対する_→_ 関係は、二つの区間同士のpartial orderを定義する
→ 関係を持たない区間同士は、並列である、と云われる


区間_I_A_ の_j_ 番目の実行は_I_A^j_ と表記する

2.2 Critical Sections - クリティカルセクション


クリティカルセクション

一度に一つのスレッドのみが実行可能なコードブロック
相互排除プロパティを備える
相互排除を達成する標準的な方法はロックを使うこと

__Lock__オブジェクト(Figure 2.2): lock と unlock メソッド備える


__Lock__を使用するスレッドは一定の形式に従う必要がある

各クリティカルセクションは、ユニークな__Lock__オブジェクトに結びついている
スレッドはクリティカルセクションに入る(入るのを試みる)前に__lock()__を呼び出す
スレッドはクリティカルセクションを出るときには__unlock()__を呼び出す


良いロックアルゴリズムが満たすべき性質:

※ CS_A^j  はスレッド__A__による、__j__回目のクリティカルセクション(区間)の実行を表す

Mutual Exclusion(相互排除):

異なるスレッド間のクリティカルセクションはオーバラップしない
スレッド A 及び B、任意の整数 j 及び k に対して、__CS_A^k→__CS_B^j あるいは __CS_B^j→__CS_A^k が成り立つ


Freedom from Deadlock(デッドロックフリー):

ロック獲得を試みたスレッドが一つ以上ある場合、その内のどれかは(いつかは)獲得できる
もしあるスレッドがいつまでもロックを獲得できないとしたら、それは別のスレッドが延々とロックの獲得・解放およびクリティカルセクションの実行を繰り返している場合のみ


Freedom from Starvation(飢餓フリー):   ※ aka. lockout freedom

ロック獲得を試みたスレッドは全て、いつかロックを獲得できる
deadlock freedom を包含する


__相互排除__は safety property。これを備えていないと、計算の正しさが保証できない
__デッドロックフリー__は liveness property。システムが(全体として)フリーズしないために重要

特定のスレッドがフリーズする可能性はある(starvation)
複数のロックを使用する場合、それぞれがデッドロックフリーの性質を備えている場合でもデッドロックが発生する可能性がある (『食事する哲学者』が有名)


__飢餓フリー__は望ましいのは明らかだけど、三つの中で一番実現されることが少ない

後続の章で飢餓フリーを備えることができなかった実用の相互排除アルゴリズムを見ていく

それらの大抵は、飢餓が理論的には発生しうるけど、通常の用途ではほとんど起こらない環境で用いられる


飢餓フリー属性は、クリティカルセクションに入るまでの待ち時間の長さを保証しない

後続の章で、スレッドの最大待ち時間に上限を設けたアルゴリズムについても見ていく


2.3 2-Thread Solutions - 二スレッドの排他方法

まず、二つの能力不足ではあるが興味深いロックアルゴリズムについて見ていく。
スレッド数は二つに限定する。
新たな記法:

write_A(x = v): スレッド__A__が__x__フィールドに、値__v__を割り当てるイベント
read_A(v == x): スレッド__A__が__x__フィールドから、値__v__を読み取るイベント
値が重要ではないときは__v__は省略するかも


2.3.1 The LockOne Class


図 2.4
相手がロック獲得を試みている(or クリティカルセクションにいる間)は待機する

一人の時だけ使用する
両方が(ドアの前に)居合わせた場合はデッドロックに!


命題 2.3.1:  LockOneアルゴリズムは相互排除プロパティを満たす
証明(背理法):

前提

クリティカルセクションに入るには「自分のフラグをonにした」後に「相手のフラグがoff」であることを確認する必要がある
クリティカルセクションに入る前に一度onになったフラグがoffに戻ることはない


両方のスレッドがクリティカルセクションに入るには以下のイベントの遷移をたどる必要がある

__A__がフラグをonにする
__A__が__B__のフラグがoffであることを確認する => __A__はクリティカルセクションに
__B__がフラグをonにする
__B__が__A__のフラグがoffであることを確認する => __B__がクリティカルセクションに

ここで矛盾発生! (__A__のフラグが on かつ off に)


面白い性質:

二つのスレッドが別々に走って入れば上手く行く


2.3.2 The LockTwo Class


図 2.5
別のスレッドが来るまで待ち続け、来たら交代する

バトンタッチ方式
一つのスレッドしか動いていなかった場合はデッドロックに!


命題 2.3.2: LockTwo アルゴリズムは相互排除プロパティを満たす
証明(背理法):

__A__が自分を犠牲者に設定
__B__が自分を(__A__の代わりに)犠牲者に設定
__A__は__B__が犠牲者になっているのを確認 => クリティカルセクションに
__B__は__A__が犠牲者になっているのを確認 => クリティカルセクションに

ここで矛盾発生! (__A__を犠牲者に設定するイベントが存在しない)


面白い性質:

二つスレッドが並列に走っていると上手く行く
LockOneとLockTwoは相補的

片方がデッドロックになる状況が、もう片方には好ましい


2.3.3 The Peterson Lock

LockOneとLockTwoを組み合わせた__飢餓フリー__なロックアルゴリズム。
おそらく二つのスレッドでの相互排除アルゴリズムの中では、最も簡潔でエレガント。

図 2.6
一人しかいないなら勝手に使って(LockOne)、競合時はバトンタッチ方式(LockTwo)で所有者を決める

命題 2.3.3: Peterson ロックアルゴリズムは相互排除プロパティを満たす
証明(背理法):


命題 2.3.4: Peterson ロックアルゴリズムは飢餓フリー
証明:

一言で云ってしまえば、競合解消にバトンタッチ方式を採用しているので、片方のスレッドが毎回所有権を得つづけることはない

帰結 2.3.1: Peterson ロックアルゴリズムはデッドロックフリー

2.4 The Filter Lock - フィルターロック

二個以上のスレッドに対応するロックアルゴリズムを二つ取り上げる。

Filterロック: Petersonロックをそのまま一般化したもの
Bakeryロック: おそらく最も簡単で一番良く知られている複数スレッドロックアルゴリズム

Filterロック:

図2.7
Levels

クリティカルセクションに通る前に通過しなければならないn-1個の待ち部屋 (nはスレッド数)
あるレベル(部屋)に入ろうとするスレッドがある場合、

少なくとも一つは入ることに成功する
複数スレッドが入ろうとした場合は、最低一つはブロックされる


スレッドは最初はレベル0に居て、レベルn-1に到達したらクリティカルセクションに入る

レベル_j_ にいるスレッドは、それより下の全てのスレッドにもいるものとみなされる


各レベルごとに犠牲者が一人いる
スレッドは、以下の上限を満たした場合に、目的のレベルに入れる

自分と同じかより上のレベルにいる(or 入ろうとしている)スレッドがいない  (LockOne)
自分が目的のレベルでの犠牲者になっていない (LockTwo)


全nスレッドが一度にクリティカルセクションに入ろうとした場合は、各レベルに付き一人が犠牲者となって留まるので、最後のレベル(クリティカルセクション)まで残るのは一スレッドだけ、となる


命題 2.4.1: 0からn-1の数値jに対して、レベルjには多くてもn-jのスレッドしかいない
証明:

要はレベルが一つ上がると、そこに同時に居られるスレッド数が一つ減ることを示したい
背理法

複数スレッドがレベル_j_ に入ろうとしている
__A__を最後に来たスレッドとする

レベル_j_ の犠牲者は__A__ に設定される


_A__以外のスレッドは__A__が犠牲者になっているのでレベル_j に入れる

ということは__A__がいるところ以上のレベルにいるスレッドが最低一つはあることになる


犠牲者__A__は同等以上のレベルにいるスレッドが存在しないため、スレッド_j_ に入れる

ここで矛盾発生！


クリティカルセクションに入るということは、レベルn-1に入る、ということに等しい。
帰結: Filterロックアルゴリズムは相互排除プロパティを満たす
命題 2.4.2: Filterロックアルゴリズムは飢餓フリー
証明(背理法):

レベル_j_ の前にスレッド__A__ が留まり続ける(ブロックされ続ける)ケースがあることを示す
帰納的仮定

レベル_j_ == レベル_n-1_ のケース: __A__が留まり続けることはありえない(既にクリティカルセクション)
レベル_j_ < レベル_n-1_ のケース: レベル_j+1_ かそれ以上にいるスレッドは、いつかはクリティカルセクションに到達する (仮定)


以下、

仮定により、__A__より上のレベルにいるスレッドはいつかはいなくなる

レベル_j_ に入ろうとしているスレッドが__A__ しかいないなら、A はレベル_j+1_ へと進めてしまう


A__より後にレベル_j に入ろうとする全てのスレッドは、既に__A_ がいるため、そこに留まることになる(留まる瞬間が発生し得る)

この時点で犠牲者の値は__A__以外になる (その後 -一周せずに- __A__に戻ることはない)


犠牲者以外のスレッドは、レベル_j+1_ へと進む

__A__も進むことになってしまうので、最初の条件が成り立たない！


帰結 2.4.2: Filterロックアルゴリズムはデッドロックフリー