- head :- (guard1 ; guard2) | body.
- の形はそのまま出力する。 ・ モジュール宣言以下のコマンド
:- xxxxx.
は、モジュール内の述語定義の一番最後にまとめて出力される。
・ モジュール宣言前のコマンドは、モジュール宣言の前に出力される。
[KLICのバージョンアップに対応するヒント]
本プログラム対応版のKLICコンパイラ(compilerディレクトリ以下の *.kl1)を、 新版のコンパイラと比較して、それに対応するプログラムを変更する。
KLICのバージョンアップに対応するために、ファイル名モジュール名等 できるだけ保存するようにしてある。
対応するオリジナルのファイルとの共通部分の比較機能% make cmp
も提供する。本プログラムの相違部分には、% IGNORE ... 等のコメントがあるが、 この比較機能はこの部分だけ無視して比較を行なうため、共通部分に変更が あれば、この機能でわかる。
[試験]
本プログラム自身を展開した結果とオリジナルプログラムに対して、 klicでコンパイルした結果で比較した。試験方法
- の形はそのまま出力する。 ・ モジュール宣言以下のコマンド
- % kl1expand XXX.kl1 > tmp.kl1
- % klic -c XXX.kl1 tmp.kl1
- % cmp XXX.c tmp.c
- % klic -c XXX.kl1 tmp.kl1
- main.kl1 ○
- write.kl1 ○
- util.kl1 △
- obj.kl1 △
- macro.kl1 △
- kl1cmp.kl1 ×
- ○は一致したもの、
- △はkl1cmp.kl1 中の tidy_clause を行なわないと一致する。
tidy_clauseは、変数名のつけかえ等を行なって 結果クローズの見栄えを良くするものである。 このため、変数の割り付け方が変わるものと思われる。
kl1cmp.kl1 のかわりに kl1cmp0.kl1を用いてコンパイルすると tidy_clauseを行わない結果が得られる。
- ×は、述語のコンパイル順序が変わることによる。
クローズ内のif-then 表記マクロの展開によって、新たに生成 される述語の順序が オリジナルのコンパイラでは逆順になっている。 このため、内部で生成するテーブル、ラベル名等の割り付けが 異る。
- △はkl1cmp.kl1 中の tidy_clause を行なわないと一致する。
- klic (limited release version 2.004) コンパイラをもとに作成。 [Version 1.0] 1996.10.25 by 杉野栄二 (sugino@jaist.ac.jp) ただし、klic (version 3.001)での動作を確認(1997.7.30) 。
- 1996.10.31 プリティプリントを変更
- orゴールの表記に段下げをつけた。
- ボディ変数と非変数のボディユニファイが 出ないようにした。（変数を非変数に置き換える）
- 1996.12.19 プリティプリントを修正 ボディで冗長なユニフィケーションが出ていたため。
- 1997.02.28 ガード組み込み述語の演算部分の表記を修正 (divide(A,B,C) -> C := A/B 等)
- KLIC klic version 2.002
- nCUBE2:nCX 5.105a 3.4.0 または
- SunOS 4.1.3
- fatpas/
- fts/
- README.j
- README-j.html
- README.e
- README-e.html
- watchdog.kl1
- copy.kl1
- ncube.kl1
- sparc.kl1
- === サンプルプログラム ===
- main.kl1
- queen.kl1
- ft_queen.kl1
- ft_queen_faulty.kl1
- main-sim.kl1
- f_sim.kl1
- f_sim_faulty.kl1
- % make sparc
- % ./dofts-s -p5 10 100d
- Leader [1]
- Leader [2]
- Backup Site Group : 2 4
- Primary Site Group : 1 3
- 30 [67,1]
- Leader [1]
- Response time is 1359 msec
- amethyst[300]% ./dofts-sf -p5 10 100d
- Leader [1]
- Leader [2]
- Primary Site Group : 1 3
- Backup Site Group : 2 4
- BOMB! 3
- Leader [1]
- 30 FAULT was detected on PRIMARY SITE!
- FAULT was informed to BACKUP!
- BACKUP change to PRIMARY !!! REBIRTH (1) [4]
- REBIRTH (2) [4]
- ... REBIRTH ndet_replay [117,1]
- BACKUP change to PRIMARY !!! REBIRTH (1) [4]
- ^Ckill tasks from io_server
- % オリジナルの述語呼び出し
- queen(N,R) :-
- % 監視プロセス生成
- watchdog:distribution(Primary,Backup),
- % 次の述語へ引数を渡す
- queen_1({N,R},Primary,Backup) @ lower_priority(10).
- % プライマリとバックアップの主プロセスへのストリームを取り
- queen_1(Args,[PTop|Primary],[BTop|Backup]) :-
- % 引数を複製し、
- copy:copy(Args,Args1,Args2,Interrupt),
- % 割り込み線をマージし、
- Interrupt = {Interrupt1,Interrupt2}, Log = ack(Log1),
- % プライマリ、バックアップそれぞれへ
- % トップのゴールをフォークする
- PTop = {primary,queen,queen,Args1,Log,Signal,Interrupt1},
- BTop = {backup ,queen,queen,Args2,Log1,Signal,Interrupt2}.
- :- module exgoal.
- call_goal(Site,Module,Predicate,Args,Log,GSig,Raise)-SC :-
- call_goal_0(Site,Module,Predicate,Args,Log,GSig,Raise)-SC @ lower_priority.
- % =-=-=-=-
- call_goal_0(primary,queen,queen,{A,B},Log,GSig,Raise)-SC :-
- queen:queen_record(A,B,Log)+GSig+Raise-SC.
- call_goal_0(backup ,queen,queen,{A,B},Log,GSig,Raise)-SC :-
- queen:queen_replay(A,B,Log)+GSig+Raise-SC.
- % =-=-=-=-
- otherwise.
- call_goal_0(Type,Module,Method,Arguments,Log,GSignal,Raise)-SC :-
- otherwise.
- klicio:klicio([stdout(normal(Out))]),
- variable:wrap((Type::Module:Method/Arguments), G),
- Out = [fwrite("Illegal goal invocation : "), putwt(G), nl,fflush(_)],
- Raise = [].
- variable:wrap((Type::Module:Method/Arguments), G),
- % Record Version
- queen_record(N,X,Log) :-
- current_node(_,All),
- queen_0_record(N,X,~(All-1),Log)@node(1).
-
- queen_0_record(4,X,A,Log) :- queen_record([1,2,3,4],[],[],X,A,Log).
- ....
- queen_record([P|U],C,L,I,PE,Log) :-
- queen_0_record(4,X,A,Log) :- queen_record([1,2,3,4],[],[],X,A,Log).
- Log = c1(Log1,Log2,Log3),
- TO:= (P mod PE)+1,
- throw_record(U,[P|C],L,I2,PE,TO,Log1),
- merge_record(I1,I2,I,Log2),
- append(U,C,N),
- c1_record(P,1,N,L,L,I1,PE,Log3).
- TO:= (P mod PE)+1,
-
- % Replay Version
- queen_replay(N,X,Log) :-
- % Replay Version
- current_node(_,All),
- queen_0_replay(N,X,~(All-1),Log)@node(1).
-
- queen_0_replay(4,X,A,Log) :- queen_replay([1,2,3,4],[],[],X,A,Log).
- ....
- queen_replay([P|U],C,L,I,PE,Log) :-
- queen_0_replay(4,X,A,Log) :- queen_replay([1,2,3,4],[],[],X,A,Log).
- Log = c1(Log1,Log2,Log3) |
- TO:= (P mod PE)+1,
- throw_replay(U,[P|C],L,I2,PE,TO,Log1),
- merge_replay(I1,I2,I,Log2),
- append(U,C,N),
- c1_replay(P,1,N,L,L,I1,PE,Log3).
- throw_replay(U,[P|C],L,I2,PE,TO,Log1),
- % Record Version
- queen_record(N,X,Log)+GSig+Raise-SC :-
- current_node(_,All),
- queen_0_record(N,X,~(All-1),Log)+GSig+Raise-SC @node(1).
-
- queen_0_record(4,X,A,Log)+GSig+Raise-SC :-
- queen_record([1,2,3,4],[],[],X,A,Log)+GSig+Raise-SC.
- ....
- queen_record([P|U],C,L,I,PE,Log)+GSig+Raise-SC :-
- Raise = {Raise1,Raise2,Raise3,Raise4},
- Log = c1(Log1,Log2,Log3),
- TO:= (P mod PE)+1,
- throw_record(U,[P|C],L,I2,PE,TO,Log1)+GSig+Raise1-SC,
- merge_record(I1,I2,I,Log2)+GSig+Raise2-SC,
- append_record(U,C,N)+GSig+Raise3-SC,
- c1_record(P,1,N,L,L,I1,PE,Log3)+GSig+Raise4-SC.
- Log = c1(Log1,Log2,Log3),
- queen_record([P|U],C,L,I,PE,ack(Log))+GSig+Raise-SC :-
- Raise = {Raise1,Raise2,Raise3,Raise4},
- Log = c1(Log1,Log2,Log3),
- TO:= (P mod PE)+1,
- throw_record(U,[P|C],L,I2,PE,TO,Log1)+GSig+Raise1-SC,
- merge_record(I1,I2,I,Log2)+GSig+Raise2-SC,
- append_record(U,C,N)+GSig+Raise3-SC,
- c1_record(P,1,N,L,L,I1,PE,Log3)+GSig+Raise4-SC.
- Log = c1(Log1,Log2,Log3),
- queen_record([],[_|_],_,I,ack(Log))+Sig+Raise-SC:-
- Raise=[],
- Log=c2(Ack),
- I=[].
- Log=c2(Ack),
- queen_record([],[_|_],_,I,ack(Log))+Sig+Raise-SC:-
- Raise=[],
- Log=c2(Ack),
- output(Ack,I, [])-SC.
- Log=c2(Ack),
-
- output(Ack,X,Y)-SC :- wait(Ack) | X = Y.
- % Replay Version
- queen_replay(A, B, Log)+GSig+Raise-SC :-
- (wait(Log) -> queen_replay_0(A, B, Log)+GSig+Raise-SC ;
- alternatively;
- GSig = [rebirth|GSig1] -> queen_record(A, B, _)+GSig1+Raise-SC).
- alternatively;
- queen_replay_0(N,X,Log)+GSig+Raise-SC :-
- current_node(_,All),
- queen_0_replay(N,X,~(All-1),Log)+GSig+Raise-SC @node(1).
-
- queen_0_replay( 4,X,A,Log)+GSig+Raise-SC :-
- queen_replay([1,2,3,4],[],[],X,A,Log)+GSig+Raise-SC.
- ....
- queen_record([P|U],C,L,I,PE,Log)+GSig+Raise-SC :-
- Log = c1(Log1,Log2,Log3) |
- Raise = {Raise1,Raise2,Raise3,Raise4},
- TO:= (P mod PE)+1,
- throw_replay(U,[P|C],L,I2,PE,TO,Log1)+GSig+Raise1-SC,
- merge_replay(I1,I2,I,Log2)+GSig+Raise2-SC,
- append_replay(U,C,N)+GSig+Raise3-SC,
- c1_replay(P,1,N,L,L,I1,PE,Log3)+GSig+Raise4-SC.
- TO:= (P mod PE)+1,
- queen_replay([],[_|_],_,I,ack(Log))+Sig+Raise-SC:-
- Log=c2(Ack) |
- Raise=[],
- I=[].
- throw_record(A,B,C,D,E,F,Log)+GSig+Raise-SC :-
- Raise = [goal(primary,queen,queen,{A,B,C,D,E},Log)].
- throw_replay(A,B,C,D,E,F,Log)+GSig+Raise-SC :-
- Raise = [goal(primary,queen,queen,{A,B,C,D,E},Log)].
- call_goal_0(primary,queen,queen,{A,B,C,D,E},Log,GSig,Raise)-SC :-
- queen:queen_record(A,B,C,D,E,Log)+GSig+Raise-SC.
- call_goal_0(backup ,queen,queen,{A,B,C,D,E},Log,GSig,Raise)-SC :-
- queen:queen_replay(A,B,C,D,E,Log)+GSig+Raise-SC.
- ....
- otherwise.
- call_goal_0(Type,Module,Method,Arguments,Log,GSignal,Raise)-SC :-
- otherwise.
- klicio:klicio([stdout(normal(Out))]),
- variable:wrap((Type::Module:Method/Arguments), G),
- Out = [fwrite("Illegal goal invocation : "), putwt(G), nl,fflush(_)],
- Raise = [].
- variable:wrap((Type::Module:Method/Arguments), G),
- プログラムとドキュメント [160KB]
試験結果
変更履歴：
【耐故障並列ソフトウェアライブラリ】
by
杉野栄二、横田治夫 at JAIST (北陸先端科学技術大学院大学)
[用途]
一般の並列計算機上で、KL1プログラムの耐故障実行を実現する。[機能]
サンプルプログラム ft_queen.kl1 のように 耐故障ソフトウェア化したKL1プログラムとリンクすることで、 耐故障実行を行う。述語 distribution(Primary,Backup) : watchdog.kl1 で提供される
は、すべてのノードを二つに分け、それぞれで監視プロセス起動する。 それぞれのプロセスへのストリームをリストにしてPrimary, Backup へ返す。述語 copy(Args,Args1,Args2,Interrupt) : copy.kl1 で提供される
は、与えられた引数（変数を含む）Argsを複製し、Args1, Args2へ返す。 変数に対してはそれぞれプロセスが生成される、Argsの変数に 動的にユニファイされる値に対しては、対応するArgs1,Args2の変数に ブロードキャストされる。 逆にArgs1, Args2へは同じ値がユニファイされる ものとし、そのいずれかをArgsの対応する変数へ送る。 変数に対して生成されているプロセスは、 ストリーム Interruptへ fault が送られると ArgsとArgs2とをユニファイして 終了する。[使い方]
ライブラリ watchdog.kl1、copy.kl1 および、 使用する環境に応じてncube.kl1 または sparc.kl1 、 それとユーザプログラム （サンプルプログラムならば main.kl1 と ft_queen.kl1 ） をKLICでコンパイル、リンクして起動する。
% klic -v -dp -o dofts watchdog.kl1 copy.kl1 sparc.kl1 main.kl1 ft_queen.kl1
注）使用可能なノード数の総数が3個以上なければならない。
[実行環境]
[ファイル構成]
- % 日本語版 README
- % 本ファイル
- % 英語版 README
- % 英語版 html
- % 監視プロセス
- % プロセス複製
- % nCUBE2向けライブラリ
- % SPARC向けライブラリ
- % サンプルプログラム 主ルーチン
- % N-Queenプログラム
- % 耐故障化 N-Queenプログラム
- % 耐故障化 N-Queenプログラム エラーあり
- % サンプルプログラム(その２）主ルーチン
- % サンプルプログラム（その２）
- % サンプルプログラム（その２）エラーあり
[実行例]
分散版KLICのトレース機能が利用できないため、バグが完全に とりきれていない。 よって現在の版では、故障に対して完全に 実行継続できない。 サンプルプログラム（その２）については、ある程度の 継続動作が見られる。1) コンパイル
2) エラー無しの実行
- <== プログラム出力 A (30), B ([67,1])
3) エラーありの実行
- <== Node 3 でexit
- <== 出力 A の後、故障検出
- <== 内部メッセージの後、出力 B
- <== 正常終了しないため ^C
耐故障化変換 プログラムは、未完成であるので、以下に耐故障化変換の指針を記す。
[耐故障化の指針]
１） 耐故障実行させたい部分を分離する。
ユーザプログラムは、main.kl1 と queen.kl1 に分離されており、 述語 queen:queen(N,Result) を耐故障実行する。注） オリジナルのプログラムは、main.kl1 queen.kl1 だけで動作する。
２）耐故障実行させたい部分を次の手順で変更する。
2-1) 呼び出される一番上の述語を次の例のように変更する。
2-2) トップゴールの呼び出し口を用意する。
呼び出し口は、モジュール exgoal に定義される。上では、モジュール queen の述語 queen は、オリジナルのアリティが2 となっているので、以下の =-=-=-=- の間の2クローズが定義される。
2-3) 2-3 で定義した トップゴール に対応する述語を用意する。
(1) もとの述語に対して Instant Replay 変換する
(2) すべてのユーザ述語について引数を追加する
引数GSigは上位からの割り込み用であり、全ゴールにブロードキャストされる ように、サブゴールにそのまま渡す。引数Raiseはゴールからの割り出し用なので、サブゴールが複数あるような 場合には、mergeされるようにサブゴールのRaiseストリームから成る ベクタをユニファイする。 サブゴールが一つだけなら、そのまま渡す。 サブゴールが存在しなければ、 [] とユニファイする。
引数組 SC は、ショートサーキットするだけのためなので、そのまま各ゴール につけるだけである。
(3) Record Versionでは、非決定的述語で Logのack待ち部分を挿入する
(4) Record Version では、非決定的述語で ボディユニファイのところに ack待ちを挿入する (出力コミット)
(5) Replay Version では各述語の前に 割り込みチェック処理用の クローズを挿入する
(6) throw goal ('goal @ node(N)')は、すべて次のような割り出しに変える
(7) throw goalするゴールに対応する入口を モジュールexgoalに追加する。
[FTP]