グリッドツールキット

• 1.0.0 N クイーン問題
• 2.0.0 グリッドコンピューティングに適した問題
• 3.0.0 Inferno blur
• 4.0.0 taskfs
• 4.1.0 処理の概要
• 4.2.0 task
• 4.3.0 スケジューリングに関する注意
• 4.4.0 最終的に生成されるファイル
• 4.5.0 中間的に生成され、最終的には消去されるファイル
• 5.0.0 グリッドホストライブラリ
• 6.0.0 グリッドツールキット
• 6.1.0 run
• 6.2.0 Q/mrun
• 6.3.0 Q/srun
• 6.4.0 Q/finish
• 6.5.0 Q/mktask
• 7.0.0 終了処理
• 7.1.0 概要
• 7.2.0 rc スクリプトによる実装
• 7.3.0 run の強制終了
• 7.4.0 メモ
• 7.4.1  プロセスグループ
• 7.4.2  ノート
• 7.4.3  子プロセスを持つプロセスへのノート
• 7.4.4  捕捉関数
• 8.0.0 N クイーン問題のグリッドコンピューティング
• 8.1.0 計算時間
• 8.2.0 ホストの内訳

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

N クイーン問題

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

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

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)と殆ど変わらない。

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

	queen n i:j

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

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

Inferno blur

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

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

• image.bit
  
• data.dat
  
• working
  
• todo/
  

などのファイルが存在する。数字はブロック番号であり、それに続く 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

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

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

処理の概要

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

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

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

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

スレーブは

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

task

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

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

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

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

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

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

taskfs はタスク番号毎に

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

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

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

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

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

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

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

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

• task.*.*/dup
  
• done
  

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

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

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

$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

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

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

グリッドツールキット

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

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 はグリッドジョブを起動する。

	run ジョブ名

	run Q

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

	bind -bc $grid /usr/none

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

	. finish
	rm done

Q/mrun

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

Q/srun

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

Q/finish

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

Q/mktask

	mktask 15 100

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

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

終了処理

概要

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

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

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

従ってマスター側は全てのタスクが終了した時点でできるだけ速やかに、タスクを実行中の全てのスレーブに対して仕事を止めさせなくてはならない。そのためには、まずマスター側の 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
}

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
        }
        ...
}
...

run の強制終了

	echo hangup >/proc/n/notepg

メモ

プロセスグループ

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

	rfork s

	/proc/n/noteid

ノート

	echo kill >/proc/n/note

	echo kill >/proc/n/notepg

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

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

	echo kill >/proc/n/note

	echo kill >/proc/n/notepg

捕捉関数

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

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

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

	echo kill >/proc/n/notepg

	echo hangup >/proc/n/notepg

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

計算時間

ホストの内訳

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