終了検知

終了検知とは、プログラムが「停止した」ことを 検知することです。 あるプロセッサが停止したことを、そのプロセッサだけで 判断できるようなプログラムなら、自分が停止したらそれを メインのプロセッサに送信し、メインのプロセッサが 全てのプロセッサが停止したと判断したら、「プログラムは停止した」 と見なせます。
しかし、「他のプロセッサからデータが来たら処理する」というような プログラムでは、プロセッサ一台では停止を判断できないので、 この仕組みはうまく働きません。このため、以下のHuangのアルゴリズムが 考えられました。

Huangの終了検知のアルゴリズム

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