並列処理と遷移グラフ

こんにちは。株式会社オプティマインドで最適化チームに所属している伊豆原と申します。

最適化チームでは週1回、それぞれが興味を持った論文や書物を読んで内容を共有する勉強会を開いています。題材は当社事業である配送計画問題に関係するものが多いですが、それに限らず一般の最適化問題や計算機科学の内容を取り扱うこともあります。

この記事ではその勉強会で扱った"並列処理と遷移グラフ(transition graph)"について簡単にご紹介したいと思います。参考にした本は以下になります(以下、参考文献と呼びます)。
* Directed Algebraic Topology and Concurrency
https://www.amazon.co.jp/dp/3319153978/

## プログラムとデッドロック

プログラムを抽象化して以下のような文字列で書き表します。

$$P_a;P_b;V_a;V_b || P_b;P_a;V_b;V_a$$

各大文字の右下のアルファベット$a,b$は**リソース**を意味し、大文字のアルファベット$P$はリソースの**ロック**、$V$はリソースの**リリース**を意味します。$;$は逐次処理で$||$は並列処理であり、逐次処理は並列処理より優先されます(つまり$x;y\ ||\ z;w=(x;y)\ ||\ (z;w))$。並列処理で区切られる各サブプログラムは**プロセス**と呼ばれ、各プロセスでロックされたリリースはそのプロセス内でリリースされなければなりません。


ちなみに各リソース$a$には**キャパシティ** $\kappa_a \in \mathbb{N}$が設定されており、同時にロックできる最大数を意味しますが、今回の記事では1固定とします。

さて、この$P_a;P_b;V_a;V_b||P_b;P_a;V_b;V_a$というプログラムですが、**デッドロック**する可能性があります。左側のプロセスが$P_a$まで進み、同時に右側のプロセスが$P_b$まで進むと、どちらも次のステップでリソースをロックできずプログラムが先に進まなくなります。

実際、以下のようなPythonスクリプトを動かしますと(randomなsleepで擬似的な処理を表現)、最後まで計算が行われる時もあれば、デッドロック状態になる時もあります。

[^1]:なお、最後まで計算できたとしても、処理順によって結果が変わってしまう問題は考えられます。が、とりあえずこの記事ではデッドロック状態に陥らなければ良しとします。

```python
import time
import threading
import random

resources = { 'a', 'b' }
locks = {x : threading.Lock() for x in resources}

def randomWait(func):
    def wrapper(*args, **kwargs):
        time.sleep(0.01 * random.randint(0,10))
        func(*args, **kwargs)
        time.sleep(0.01 * random.randint(0,10))
    return wrapper

@randomWait
def lock(x, name):
    locks[x].acquire()
    print(f"{name} : lock {x}")

@randomWait
def release(x, name):
    locks[x].release()
    print(f"{name} : release {x}")

def p():
    lock('a','p')
    lock('b','p')
    release('a','p')
    release('b','p')

def q():
    lock('b','q')
    lock('a','q')
    release('b','q')
    release('a','q')

def main():
    threads = [threading.Thread(target=program) for program in [p,q]]

    print('-- Start')

    for thread in threads:
        thread.start()

    for thread in threads:
        thread.join()

    print('-- End')

main()
```

* 最後まで計算できたパターン

```
-- Start
q : lock b
q : lock a
q : release b
q : release a
p : lock a
p : lock b
p : release a
p : release b
-- End
```

* デッドロック状態

```
-- Start
p : lock a
q : lock b
```

## 遷移グラフと幾何学的セマンティック

では、こうしたデッドロックの発生を可視化する手法はあるでしょうか？この疑問に対する解答として、文字列で表されたプログラムに対する**遷移グラフ**というものがあります(参考文献では"pruned transition graph"と定義されています)。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2334028/5fe48e5e-e45e-c174-7330-413738984fd7.png)

並列するプロセスを格子上に配置し、各リソースのキャパシティが足りない(invalid)頂点を取り除き、残った頂点間に遷移を表した矢印を引いたグラフとなります。機械的に書けるグラフですが、DeadLockになる状態(=endに遷移しない点)が明確に確認できると思います。
なお、キャパシティ的に問題の無い点は残しますので、初期状態から到達し得ない点も遷移グラフに含まれる場合があることに注意です。そのような点はunreachableと呼ばれます。

また、遷移グラフを連続化したものとして**幾何学的セマンティック**(Geometric Semantics)と呼ばれるものがあります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2334028/e68acc18-9d5e-c04a-a6c7-479881fae7e3.png)

プロセスの並列数と等しい次元の正方形$I^n = [0,1]^n$を用意し、その中でリソースのキャパシティ的にinvalidな領域(上図の赤色領域(a由来)と青色領域(b由来))を取り除いた白い部分が幾何学的セマンティックと呼ばれます。その上のパスは実行軌跡を表し、格子を跨いだ時に処理が実行されたと見做します。
これも遷移グラフと同様にデッドロックが可視化されています。ついでにunreachableな領域も、doomed(DeadLockに到達するしかない領域)やunsafe(DeadLockに到達し得る領域)な領域なども確認することができます。

## 幾何学的セマンティックとDirected Algebraic Topology

ちょっとここで、参考文献のタイトルに含まれている"Directed Algebraic Topology"についての話を挟みます。

幾何学的セマンティックを考えると、プログラムにおけるデッドロックの存在や異なる実行軌跡の個数が"空間の不変量"と捉えられることが分かります。そして"空間の不変量"について調べるには、かねがねAlgebraic Topology(代数的位相幾何学)の分野で培われた理論や計算方法が有効です。ただしここで注意すべきなのは、一般にプログラムは"逆戻り"できないことです。その反映として幾何学的セマンティック上には不可逆な"向き"があるべきで、パスは"逆戻りできない"ものになります。

こういった空間を取り扱う分野としてDirected Algebraic Topology(有向(?)代数的位相幾何学)というものがあります。向き付けられた空間を題材に代数的位相幾何学のような不変量を見つけ出そう、という分野です(たぶん)。

https://en.wikipedia.org/wiki/Directed_algebraic_topology

私自身はこの分野に関して今回の参考文献で初めて触れているレベルなので、特に深いことを述べられないのですが、とりあえず1つの応用例を紹介します。下記の論文では有向トポロジー(ただし定義は参考文献とは異なるものを使用)にモデル構造を組み込んでホモトピー論を展開し、$\pi_{1,0}(X/X_1)=0$と書かれるある種のホモトピーの消失から2PL(下記:1)に従う並列プログラムがSerializable(下記:2)であることを示しています。
* A Hurewicz Model Structure for Directed Topology
https://arxiv.org/abs/1911.02204

結果自体は以前から知られているものですが、完全列などを用いてかなり代数的トポロジーチックに証明されている点で非常に興味深いものかと思います。これからの発展に注目したい分野ですね。

1. 2PL : 並列するプログラムがすべて、"最初に必要なリソースすべてをLockし、その後でLockしたリソースをすべてReleaseする"処理順であるもの。$P_x;P_y;L_y;L_x||P_y;P_z;P_x;L_x;L_z;L_y$など。
1. Serializable : 可能な実行軌跡がすべて、並列するプロセスを適当な順番で1つずつ実行する直列処理と同値になるもの。


## 食事する哲学者の問題

では話を戻しまして、遷移グラフの具体例を見てみます。

デッドロックに関する有名なサンプルケースとして、[食事する哲学者の問題](https://ja.wikipedia.org/wiki/%E9%A3%9F%E4%BA%8B%E3%81%99%E3%82%8B%E5%93%B2%E5%AD%A6%E8%80%85%E3%81%AE%E5%95%8F%E9%A1%8C)というものがあります。n本の箸がリソースとなり、各哲学者は左右2本の箸=リソースと必要とする問題と考えられます。

今n=3とし、各哲学者が行うプロセスを`p=右箸取る;左箸取る;右箸置く;左箸置く`と固定すると、遷移グラフは下図のようになります。左下の方で始点(黒矢印)から3矢印進んだところでデッドロックが発生していることが分かります(ついでに、食事する哲学者の問題は2PLなのでどの実行軌跡もSerializableなことも確認できます)。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2334028/143c40ab-f225-f66b-3f89-cdc7b8a53e82.png)

ではこの哲学者らのうち、1人だけ左箸から取る、つまり`q=左箸取る;右箸取る;左箸置く;右箸置く`というプログラムを採用したらどうなるでしょうか？この時、遷移グラフは以下のようになり、デッドロックは発生しないことが分かります。さらによく見ると、こちらの遷移グラフではunreachableな点が存在しないことが分かります。つまりリソース的に問題のない(=1つのフォークを2人以上が取ったりしない)任意の状態は、初期状態から常に到達しうることが分かります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2334028/56ace28b-3c6a-23f8-3707-aaa697bfb8f6.png)

このように、遷移グラフを書くことでプログラムの色々な性質が見えてきます。

##  Lipski/Papadimitriouの例

最後にもう少し複雑で面白い例を見てみます。LipskiとPapadimitriousによる並列数=3のプログラムがあります。
```math
p \  | \ q \ | \ r \\
p = P_a;P_b;P_c;V_a;P_f;V_c;V_b;V_f \\
q = P_d;P_e;P_a;V_d;P_c;V_e;V_a;V_c \\
r = P_b;P_f;V_b;P_d;V_f;P_e;V_d;V_e
```

見た目かなり複雑ですが、このプログラムの何が特殊かを見る前にデッドロックについて改めて考えてみます。

まず、リソースをLockしたら次にすぐReleaseするようなプログラムではデッドロックは起きないことが分かります。なのでデッドロックが起きるとすれば、複数のリソースを同時に確保する必要がある場合に限ります。
そこで、次の方法で構築される**リクエストグラフ**(Request Graph)と呼ばれるものを考えます。
* 各リソースを頂点に持ち、2つのノード$a,b$について"$a$をLockした後、$a$をReleaseする前に$b$をLockする"プロセスが存在する時に辺$a \to b$を追加する。

例えば本記事冒頭で出てきた$P_a;P_b;V_a;V_b || P_b;P_a;V_b;V_a$のリクエストグラフを書いてみますと、2頂点によるサイクルになっていることが分かります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2334028/1d2342b9-4865-18e4-95e2-b05ccdea274e.png)

さて、リクエストグラフにサイクルが存在しない場合は、トポロジカルソートなど考えればデッドロックが発生しないことが分かります(∵末尾の方からリリースされていくため)。では、サイクルがある場合は常にデッドロックが発生しうるのでしょうか？実は、LipskiとParadimitriousによる先のプログラムはその反例になっています！つまり、リクエストグラフにサイクルがあるにも関わらずデッドロックが発生しないプログラムなのです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2334028/926410c5-8415-9775-e581-8d11af30ae11.png)

デッドロックが発生しないことは遷移グラフから確認できます(見辛いですが)。目視でなくても適当なグラフ探索により"始点からたどり着けて終点からたどり着けない"状態が無いことを確認しても良いですし、あるいは参考文献ではデッドロックを見つけるアルゴリズムが紹介されてます(Algorithm 5.13)。
特にこの例では、Serializableでない実行軌跡が存在します。つまり各プロセス$p,q,r$を適当な順番で直列に実行した結果の**どれとも異なる**結果が並列処理によって発生し得ます。デバッグしずらそうですね。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2334028/dd279c03-8472-97c1-72b6-c678b5b488fb.png)

## 結び

並列処理とその遷移グラフについて書かせて頂きました。この辺の話についてはネット上にも専門家による解説やスライドが色々とありますので、興味を抱いた方がいらっしゃいましたら是非調べてみてください。
読んで頂きありがとうございました。