グリッドツールキット

さて、春学期の試験の採点が終わり、ようやくホームページを書く時間が取れた。そこで、今回はこの間少しずつやってきた事、即ち Plan 9 において N クイーンの問題を実際にグリッド流に解いてみた総括を述べる事にする。

N クイーン問題

8 クイーン問題とはチェスの盤面に 8 個のクイーンを置く問題である。どの 2 つのクイーンも互いの効き筋にあってはならない。クイーンは将棋の飛車と角を併せ持った効き筋、すなわち縦・横・斜めの効き筋を持つので、チェス盤であればせいぜい 8 個しか置く事ができない。

8 クイーン問題は古くからパズル的な興味を持たれたらしく。研究し尽くされている。筆者の手持ちの本*に依ると解は 12 個である。

* 高木茂雄「Play Puzzle -- バズルの百科」(1984, 平凡社)

N クイーン問題とは、チェス盤の代わりに N × N の盤を使って N 個のクイーンを置く問題である。この問題は昨年(2004年)電通大が PC クラスターのデモとして N=24 のケースを扱い、227514171973736 個の解の存在を確認した。

http://www.itmedia.co.jp/news/articles/0410/06/news079.html
http://www.yuba.is.uec.ac.jp/~kis/nq/index.htm

但し、この計算は 8 クイーンの問題に対して解の個数 92 を導きだしている。解が多すぎるのは本質的に同じ解が取り除かれていないからである。

1つの解が分かると、それを鏡に映したもの、90度、180度、270度回転したものも同様に解になる。電通大の解の個数にはそのような解が含まれているのである。先に述べた 12 を 8 倍すると 96 であるが、電通大の 92 にならないのは、解の中には特殊なもの、つまり対称性を持ったものが含まれているからである。

クイーンの効き筋を考えると鏡映対称なものは解にはなり得ない。しかし回転対称なものは解になり得る。実際 8 クイーン問題の 12 個の解の中には点対称なもの(180度の回転で重なるもの)が1個含まれている。

パズルの立場からすると、重複を取り除いた解の個数を知りたい。しかしそれを見つけるプログラムが存在するのか否かは筆者は知らない。

グリッドコンピューティングに適した問題

一つの大きな計算を多数の独立した計算に分割できれば、それらを他の計算機に割り振る事ができる。そうした問題はグリッドコンピューティングに適した問題であると言える。

統計的なシミュレーションはグリッドコンピューティングに適した、しかも容易な問題である。但し乱数の種の採り方に工夫が必要で、単純に計算開始時の時刻から採る訳にはいかないだろう。

N クイーン問題は難しいジャンルに含まれる。電通大が使用したプログラム(qn24b-version1.0)が http://www.yuba.is.uec.ac.jp/~kis/nq/index.htm から手に入るが、この中には 3 種のプログラム(base, mpi, omp)が含まれている。どれも N クイーン問題の解の個数を求めているが、幸いな事に omp(OpenMP版) は独立した計算に分割して問題を解く構造になっている。

以下では基の計算を「ジョブ」、ジョブを独立した計算に分割した計算を「タスク」と言う事にする。

次の表に示すのはクイーンの個数(n)、 omp による解の個数(solutions)、1個のコンピュータによる実行時間(time)、タスク分割数(tasks)の関係である。コンピュータによる実行時間は筆者の家庭の 2.4GHz Pentium/Xeon での実験であり単位は秒である。これは全てのタスクの実行に要する時間である。この時間はタスクに分割しない通常のプログラム(qn24b-version1.0/base)と殆ど変わらない。

n	solutions	time	tasks
4	2		1
5	10		7
6	4		23
7	40		78
8	92		172
9	352		401
10	724		700
11	2680		1337
12	14200		2040
13	73712		3432
14	365596		4816
15	2279184	2.5	7432
16	14772512	15	9844
17	95815104	110	14272
18	666090624	760	18132
19	4968057848	6266	25080
20	39029188884	47858	30880
21	314666222712		41176
22	2691008701644		49480
23	24233937684440		64072
24	227514171973736		75516
25	unknown		95472

OpenMP はメモリを共有する並列計算機向けの仕様である。グリッド環境はメモリを共有するシステムではない。しかし omp を少し変形すると容易にグリッド環境に適した形式に持って行ける。筆者の場合には異なるサーバで独立に実行できるように

	queen n i:j

の形式のコマンドで n クイーン問題のタスク範囲 i:j の中にある解の個数が求まるようになっている。i:j の意味は Python に従う。すなわち m 個のタスクに 0,1,2,...,m-1 の連番を付けた時の

	i,i+1,i+2,...,j-1

のタスクの集合である。

なお OpenMP に関しては http://www.openmp.org/ に詳しい。
OpenMP のプログラミングインターフェースの仕様はこのホームページの spec25.pdf に書かれている。

Inferno blur

筆者は TIP9UG の中で山梨氏とグリッドの問題に関して議論を繰り返した。blur はその議論の中で Inferno に詳しい方から紹介された Inferno のグリッドデモプログラムである。blur のマニュアルは http://www.vitanuova.com/inferno/man/1/blur.html から手に入る。

このマニュアルによると blur は画像処理のプログラムで、画像を幾つかのブロックに分割してスレーブに処理を依頼する。マスターとスレーブは /tmp/blur を共有する。(こんな事が可能なのは Inferno は Plan 9 の血を受け継いでいるからですね)

/tmp/blur の中には次のファイルとディレクトリが存在する。

image.bit
data.dat
working
todo/

working は単なるフラグで、仕事が続行中であり、スレーブは todo の中のファイルを読み取らなければならない事を表している。todo の中には
block.0.a
block.1.a
...

などのファイルが存在する。数字はブロック番号であり、それに続く a, b, c, ... などの1文字の英字はバージョン識別子である。

スレーブはファイルを読み取ったら同名のディレクトリを作成する。例えば todo/block.1.a を読み取ったらディレクトリ block.1.a を作成する。このディレクトリはセマフォとして機能している。即ち、block.1.a を作成するのはただ1個のスレーブであり、結果を出したら block.1.a の中にファイル done を作成する。マスターはディレクトリ block.1.a が作成されたら todo/block.1.a を削除する。
スレーブがなかなか done を作成しない場合にはマスターはブロックのバージョンを上げる。例えば block.2.a を処理しているスレーブが結果を出さない場合にはマスターは todo/block.2.b を作成する。すると block.2.b は他のスレーブによって処理されるはずで、スレーブが1つでも支障なく動いていれば全てのブロックが処理される事になる。
スレーブは処理の結果を image.bit に書き込む。(そして done を作成する)
data.dat には処理に必要なパラメータが含まれている。

バージョン識別子を導入し、スレーブの不具合に対する耐久性を高めたのはなかなか旨いと思う。実際グリッド環境は不安定な環境であり、スレーブを実行しているホストが突然停止する事も十分にあり得るのである。

他方では次のような疑問も生まれてくる。

blur では todo の中のブロックを選択するのはスレーブである。スレーブは同一アルゴリズムでこの選択を行う訳であるから選択の衝突を避けるには乱数を持ち込まざるを得ない。スレーブに渡すブロックはマスター側が選択した方が良いのではないか?
バージョン識別子の更新のタイミングがマニュアルでは不明である。明確な効率の良いタイミングの採り方は無いか?
image.bit はマスターが結果を受け取るパイプである。しかし todo/block.*.* の結果はディレクトリ block.*.* の中にファイルとして書き込んだ方が良いのではないか?

なお block.*.* の中に現れる * 記号はシェルでおなじみのワイルドカードであり、任意長の文字列を表している。この記号は説明を簡略にするために以下でも多用される。

taskfs

taskfs は筆者の Grid Took Kit の中に含まれている、グリッドコンピューティングを Plan 9 で行うためのエンジンとなる基本ソフトである。筆者は taskfs を作成するにあたって Inferno の blur を参考にした。特にタスクバージョンのアイデアを取り入れた。しかしタスク実行のスケジューリングは blur 流を採用しなかった。また taskfs の作成に当たって筆者は山梨氏と議論を交わしており、彼から 2 つの贈り物をもらった。

1 つは taskfs の名称の許可である。この名称は彼が使っていたものだ。もう 1 つはマスター側の仮想ファイルをスレーブが読み取り、スレーブはそれによって実行タスクを決定する手法である。タスクのスケジューリングをマスターが行う事にすれば Plan 9 では必然的にこのようになるのであるが、山梨氏が既にこのアイデアを筆者に漏らしていたので決断が速かった。

以下に taskfs で使用されるファイルを説明する。これらは全てではない。taskfs は特定のアプリケーションに限定していないので、後に紹介する一般的なツールを含んでいる。ここでは Inferno の blur に相当する部分だけを採り上げる。

処理の概要

実行前に必要な基本ファイル

data/task.*
finish
task
tasks/task.*

task.* は

	task.n (n=0,1,2,...)

の形式のファイルで、この内容は

tasks/task.* はプログラム
data/task.* は tasks/task.* のためのデータ、

である。これらの内容は問題毎に与えられ、処理の途中で変化しない。
finish は全てのタスクが完了した後に実行される終了スクリプトである。task は空のファイルであるが、taskfs が立ち上がるとパイプのような働きをする仮想ファイルとなる。マスターは task を通じてスレーブに実行すべきファイル名 task.*.* を与える。ここに task.*.* は task.* にバージョン識別子を付加した名前である。

	task.n.v (n=0,1,2,..., v=a,b,c,...)

スレーブに渡す名前の衝突が発生しないようにするのはマスターの責任である。

スレーブは

マスターから受け取った名前と同名のディレクトリ task.*.* を作成し、
tasks/task.* を実行し、
結果を task.*.*/result に書き込み、
スレーブのホスト名を task.*.*/hostname に書き込み
task.*.*/done を作成する

もちろん、このような事が可能なのは、Plan 9 のスレーブはマスターのファイルシステムをマウントできるからである。

`task`

task は重要な役割を果たす。マスターは task を通じてスレーブに次のタスクを教える。スレーブは task を通じてタスクを要求する。タスク名にはバージョン識別子が付加されるが task.1.a も task.1.b も同一のプログラム tasks/task.1 を実行するので同じタスクと言える。バージョン識別子は処理の高速化と安定性のために導入されているだけである。taskfs は task.*.*/done の生成を監視し、スレーブが task を読み取る時にその内容を与えるファイルシステムである。この taskfs がマスターとして働いている。

我々は以下の事を taskfs の仕様として要求する。

バージョン識別子を含めたタスク名には重複があってはならない
完了したタスク、即ち task.*.*/done が作成されたタスクの実行をスレーブに指示してはならない
未完了のタスクが存在する限りタスクを要求するスレーブにタスク名を渡す
同一のタスクを複数のスレーブが実行する場合には、1つのタスクを実行するスレーブ数の均一化を図る

最後の「1つのタスクを実行するスレーブ数の均一化」について補足しよう。処理が進むにつれて残りタスクは減少する。

	残りタスク数 ≧ スレーブ数

である限りスレーブにはバージョン識別子が "a" のタスク名が渡される。しかし

	残りタスク数 < スレーブ数

になった場合には (上記の仕様 3 に従えば) 同一のタスクが2つのスレーブによって実行されだす。その場合には (上記の仕様 1 と 2 に従って) 後から始めたスレーブにはバージョン識別子が "b" のタスク名が渡される。さらに

	残りタスク数 < スレーブ数/2

になったら今度は後から始めたスレーブにはバージョン識別子が "c" のタスク名が渡される。以下同様である。

このような動作をするタスクのスケジューリングはどのようにすれば可能であるか?

taskfs はタスク番号毎に

タスク名
バージョン番号
完了フラグ

の3つのセットを内部テーブルとして保管している。タスク名は "task.0" のような文字列である。この部分はディレクトリ tasks のファイルの名前そのものである。バージョン識別子とは言わないでバージョン番号と言っているのは、内部では 0,1,2,... のような数字でバージョンが管理されているからである。そして taskfs は

スレーブが task.*.*/done を生成したら内部テーブルの相当するタスクに完了を示すフラグを立てる。
スレーブから task の読み取りがあった場合、未処理のタスクの中からバージョン番号の最小なものをスレーブに教える。それとともにtaskfs はそのタスクのバージョン番号を更新する。

バージョン番号の最小なものを探すアルゴリズムでは最小のタスク番号のものが選ばれている。従って、処理はタスク番号が小さいタスクから進んで行くことになる。

スケジューリングに関する注意

taskfs は個々のタスクに関してスレーブを選ぶ仕組みは持たない。すなわち task を読み取るスレーブを選ぶ事はできない。

この制限は本質的なものであるが、仮に可能であるとしても、それによってどの程度処理速度を改善できるか疑わしい。CPU の能力が高いからと言って、それが実際のスレーブの能力を表しているとは限らない。また経済学的視点から言えばユーザが非常に多くなると高性能な CPU は多くの人が使用し、そして均衡の方向へ向かう。

こうした事を考えると、仕事を細かく分割し、よってたかって片っ端から片付ける taskfs のアルゴリズムは悪くはないはずである。このやり方をとれば、ひ弱なスレーブもそれなりに計算に寄与し、その存在は邪魔にはならないのである。

注意: task.*.*/done が生成された時に、同じタスクを実行している全てのスレーブにメッセージを送り、次の仕事を行うように指示するのは実行速度を高めるはずである。しかし taskfs は現在の版ではそれを行っていない。

最終的に生成されるファイル

既に述べたようにスレーブは

task.*.*/done
task.*.*/result
task.*.*/hostname

を作成する。

中間的に生成され、最終的には消去されるファイル

以下のファイルは taskfs によって生成され、マスター側の終了に伴って削除される。

task.*.*/dup
done

複数のスレーブが同一のタスクを処理し、その結果を task.*.*/ の中に書き込む。我々はその内の1つだけが必要なのであり、残りを削除しなくてはならない。これを容易にするために、遅れて完了したタスクには印が必要である。task.*.*/dup がそのための印である。task.*.*/dup は taskfs によって作成される。

また taskfs は全てのタスクが終了した時に finish が置かれているディレクトリにファイル done を作成する。このファイルはスレーブプロセス全体の強制終了を安全に行うために使用される。

グリッドホストライブラリ

グリッドホストとホスト毎の factotum の一覧を $home/lib/grid に持つ。

$home/lib/grid/bell-labs/factotum
$home/lib/grid/bell-labs/names
$home/lib/grid/co/factotum
$home/lib/grid/co/names
...

names はホストの名前の一覧であり bell-labs の場合には

b.grid.bell-labs.com
c.grid.bell-labs.com
d.grid.bell-labs.com
#e.grid.bell-labs.com
f.grid.bell-labs.com
g.grid.bell-labs.com
#h.grid.bell-labs.com
#i.grid.bell-labs.com

のように書く。使用していないホストは # 記号によってコメントアウトできる。

factotum はこれらのホストの共通の認証データである。例えば bell-labs が提供する grid 環境の factotum は

key dom=grid.bell-labs.com proto=p9sk1 user=arisawa !password=XXXXXXXX

である。ここに XXXXXXXX はパスワードである。

Plan 9 ユーザのためにボランティア的に提供されている殆どのコンピュータでは Bell-labs の Plan 9 ソースのアップデートアカウントの factotum が使用されている。

これらのデータは次に述べる run の中で使用される。

グリッドツールキット

筆者のサーバ

	http://plan9.aichi-u.ac.jp/netlib/

には Plan 9 用のグリッドツールキットである grid.tgz が置かれている。このグリッドツールキットには N クイーン問題に関連して、以下のファイルが含まれている。

run
pattern
src/*
bin/386/taskfs
bin/386/alarm
bin/rc/
readme
Q/mrun
Q/srun
Q/data/*
Q/task
Q/tasks/
Q/mktask
Q/readme
Q/finish
Q/src/*
Q/bin/386/queen
Q/bin/rc

以上の他にグリッドホストに関する情報を取得するためのツールも含まれているが、ここでは採り上げない。

run

以下では run の置かれているディレクトリを $grid とする。

run はグリッドジョブを起動する。

	run ジョブ名

例えば N クイーン問題であれば

	run Q

run の内部で行われている主な仕事は、
$home/lib/grid/* を読み取り、名前空間を再構成し

	bind -bc $grid /usr/none

そしてホスト毎に mrun を起動する。

	for (host in $hosts)
		mrun $host &
	wait

そして全てが終了すると

	. finish
	rm done

Q/mrun

Q/mrun は run によって起動される。mrun の主たる仕事は cpu コマンドを起動することである。

	cpu -P pattern -h $host -c /mnt/term/usr/none/srun

Q/srun

Q/srun は cpu コマンドによってグリッドホストの中で起動される。
srun は taskfs が提供する task を読み取り、タスク名が与えられ続ける限り、そのタスクを実行する。srun は次の3つのファイルを生成する。

task.*.*/result
task.*.*/hostname
task.*.*/done

Q/finish

finish はスレーブが作成したディレクトリ task.*.* の最終整理を行っている。finish は次の場合に task.*.* を削除する。

task.*.*/done が存在しない場合
task.*.*/dup が存在する場合

これらは一般的な作業であるが、問題に応じた終了処理を含める事が出来る。

Q/mktask

ディレクトリ Q の中の mktask は N-Queens 問題のタスク名をディレクトリ tasks の中に作成するツールである。ディレクトリ Q で例えば

	mktask 15 100

を実行すると 100 個のファイル

	task.0
	task.1
	...
	task.99

が tasks の中に作成される。そしてファイル task.0, task.1,task.2,.. の内容は各々、クイーンが 15 の問題で生成される 7432 個のタスクを 100 個のタスクに分割したもの

	queen 15 0:74
	queen 15 74:148
	queen 15 148:222
	...

になっている。

終了処理

概要

苦労したのは終了の方法である。全てのタスクが終わった段階でできるだけ速やかに終了したい。どうすれば良いか?

最初のアイデアから紹介する。taskfs はタスクの終了を捉えているので、内部テーブルの全てのタスクに完了フラグが立てられたら taskfs を終える。

しかしこれは乱暴なやり方で、終了時にスレーブからエラーメッセージがでてくる。スレーブが依拠していたファイルが突然無くなったわけでスレーブはパニック状態に陥るのである。

他方、マスターの Q/task から仕事を読み取れなくなったらスレーブが順次終了して行くやり方は別の問題を引き起こす。この方法は最も品の良い終了法ではあるが、マスターは全てのスレーブの自然終了を待つ事になり、非力なスレーブの存在が足を引っ張るばかりか、1つのスレーブが何かの原因でいつまでも終了しない場合にはマスターは永久に終了できないことになる。

従ってマスター側は全てのタスクが終了した時点でできるだけ速やかに、タスクを実行中の全てのスレーブに対して仕事を止めさせなくてはならない。そのためには、まずマスター側の cpu コマンドを強制終了させなければならない。これも乱暴なように思えるが、cpu コマンドは、マスター側を強制的に終了させれば、スレーブ側のプロセスは遅かれ速かれ終了するように作られているはずである*。

* でないと cpu コマンドのバグである。なおスレーブ側での実際の終了は実行中のタスクが終了してからである。

taskfs の終了は cpu コマンドの終了を確認してから行う。

rc スクリプトによる実装

やりたい事は上の「概要」の通りであるが、実際にはどようにすればよいだろうか?

1つの mrun が終了すると(done が作成されている事を確認して) mrun は run に終了を通知する。
mrun

...
rfork ens
...
if(test -e done && test -e /proc/$ppid){
        echo killing run
        echo hangup>/proc/$ppid/notepg
}

ここに $ppid は run のプロセス ID である。

run の中では 2 つのノートハンドラが定義されている。

...
rfork ens
...
fn sighup{echo run: sighup}
fn sigexit{
        ...
        for(p in $mpids){
                if(test -e /proc/$p)
                        echo kill >/proc/$p/notepg
        }
        ...
}
...

$mpids は mrun のプロセス ID のリストである。
fn sighup のお陰で run は hangup ノートを受け流す。(これが無いと run が落ちる)
そして run は wait を抜け出し、終了するが、その際に sigexit を実行する。そして全ての mrun を、その子プロセスもろとも殺しに行く。

run の強制終了

run のプロセス ID を n とすると

	echo hangup >/proc/n/notepg

メモ

プロセスグループ

rc スクリプトでは rfork の s フラグがプロセスグループの境界を定義する。

	rfork s

どのプロセスがどのグループに属するかは

	/proc/n/noteid

をみる事で確認できる。

ノート

Plan 9 ではシグナルは数字ではなく文字列である。これをノートと言う。

	echo kill >/proc/n/note

はプロセス ID が n のプロセスだけに kill ノートを送るが

	echo kill >/proc/n/notepg

ではプロセス ID が n のプロセスと同じグループの全てのプロセスに kill ノートが送られる。但し送信元のプロセスには送られない。kill の他に alarm、hangup などがよく使用される。

ノートを受けたプロセスが、それによって何かの処理を行いたい場合には kill は使わずに alarm あるいは hangup を使う。通常は hangup を使う。hangup は実行を停止させている要因を(1つだけ)スキップさせる。

子プロセスを持つプロセスへのノート

子プロセスを持つプロセスに

	echo kill >/proc/n/note

としても、そのプロセスは死なない。alarm や hangup も同様である。これらのノートの効果を得るには子プロセスが先に死ぬ必要がある。

	echo kill >/proc/n/notepg

が子プロセスもろとも殺すには効果的である。

捕捉関数

Plan 9 のノートの捕捉関数は C でコーディングすれば任意のノートの捕捉が可能である。そして捕捉されないノートを受け取れば、そのプロセスは(子プロセスを持たなければ)終了する。

rc スクリプトでもノートの捕捉が可能である。但し

	fn sigalrm {...}
	fn sighup {...}
	fn sigexit { ...}

だけが定義されている。このうち sigexit はスクリプトの終了処理関数で正しくは捕捉関数ではない。

これらが rc スクリプト foo で定義されているとし foo のプロセス ID を n としよう。

	echo kill >/proc/n/notepg

で sigexit は実行されない。直ちに死んでしまうからである。sigexit を実行させたい場合には

	echo hangup >/proc/n/notepg

を使用する。但し関数 sighup は形式的にせよ定義しておかなくてはならない。(でないと foo は hangup を受け取っても sigexit を実行しないまま死ぬ。)

N クイーン問題のグリッドコンピューティング

計算時間

以下に 10 個のグリッドホストで実測した計算時間を示す。

n	slaves	tasks	time(秒)
19	10	100	1520
20	10	100	11384
21	10	500	99331

slave はグリッドホストの個数、tasks はタスクの個数、time は計算に要した時間である。n=20 の例を、1個のホスト (io.home) で計算した結果と比較すると 1/4 の時間で計算が終わっている。1/10 にならないのは次の表で分かるように、io.home は 10 ホストの中でも計算能力が高いのに対して、10 個のグリッドホストの多くは計算能力が低いからである。

ホストの内訳

次に 10 個のグリッドホストの内訳と、n=19 および n=20 において、各ホストがこなしたタスク数、それと CPU の能力を示す。

ホスト	tasks (n=19)	tasks (n=20)	tasks (n=21)	CPU
al.aichi-u.ac.jp	7	6	33	665MHz PentiumIII/Xeon
ar.aichi-u.ac.jp	9	10	45	868MHz PentiumIII/Xeon
b.grid.bell-labs.com	4	3	13	?
co.aichi-u.ac.jp	4	5	22	998MHz C3
f.grid.bell-labs.com	4	4	21	?
g.grid.bell-labs.com	5	4	26	?
hera.aichi-u.ac.jp	18	20	100	1808MHz AMD-Athlon
io.home	24	21	108	2392MHz PentiumIV/Xeon
isengard.tip9ug.jp	22	24	116	2.4GHz AMD64
lugosi (9grid.us)	3	3	16	?

C3 がクロック数から想像される程には良くない。

ここに上げたホスト毎の task 数は1つの実験の結果であって、もう一度繰り返せば、異なる数字になるであろう。小さな数字の違いにこだわってはならない。どのホストがどれだけの処理能力を持ちうるかは、その時のホストの負荷状態に依存する。

検事の鏡 A mirror of Kenji Arisawa's site

グリッドツールキット

N クイーン問題

グリッドコンピューティングに適した問題

Inferno blur

taskfs

処理の概要

task

スケジューリングに関する注意

最終的に生成されるファイル

中間的に生成され、最終的には消去されるファイル

グリッドホストライブラリ

グリッドツールキット

run

Q/mrun

Q/srun

Q/finish

Q/mktask

終了処理

概要

rc スクリプトによる実装

run の強制終了

メモ

プロセスグループ

ノート

子プロセスを持つプロセスへのノート

捕捉関数

N クイーン問題のグリッドコンピューティング

計算時間

ホストの内訳

`task`