終了検知とは、プログラムが「停止した」ことを
検知することです。
あるプロセッサが停止したことを、そのプロセッサだけで
判断できるようなプログラムなら、自分が停止したらそれを
メインのプロセッサに送信し、メインのプロセッサが
全てのプロセッサが停止したと判断したら、「プログラムは停止した」
と見なせます。
しかし、「他のプロセッサからデータが来たら処理する」というような
プログラムでは、プロセッサ一台では停止を判断できないので、
この仕組みはうまく働きません。このため、以下のHuangのアルゴリズムが
考えられました。
このアルゴリズムは、親プロセッサを一台决める必要があります。
一般的に並列処理では、プログラムの開始や停止を管理するのに
一台特別なマシンがあることが多いので、これを親とすればよいです。
親プロセッサはある値(ここでは1とします)を持っていて、
この値は無限に細かく分けることができます(0.3と0.7とか)。
この値を、以下のようにやり取りすることにします。
- プログラムの開始時に、親は子にこの値を配分する
- プロセッサ間でメッセージをやり取りする時は、送信者が自分の値を
一部分けて、相手に送信する。なお、分け方は共に正であれば制限はない
- 値を受信したプロセッサは、その値を自分の値に加える
- 子のプロセッサが停止したら、自分の値を親に送信する
- 親のプロセッサが値1を持つようになり、かつ親プロセッサが停止したら、
プログラムは停止した
以下に実例を挙げます。[0]が親プロセッサで、緑で書いてあるのが
「値」です。子プロセッサについては、start / stopの様子が書いてあります。
また、茶色の矢印はメッセージのやり取りを、黄色の矢印は値のみのやり取りを
表しています。
プロセッサ[1]は一度終了し、それをプロセッサ[0]に報告しているのに、
その後[2]からのメッセージで起動しています。
このHuangのアルゴリズムでは、その辺りも正確に判定が行えています。
なお、「値は無限に分けられるのか」という疑問が出てくるかと思いますが、
これに関しては、分けられなくなったら、子が親に要求し、新たな値をもらう
(その場合、合計が1ではなくなるので、終了判定も当然その値で行う)
方法が考えられると思います。
