LMNtalからC言語への変換の設計と実装 2007年度卒業論文発表 2008/2/5 1G04R013-7 石川 力

LMNtalとは → ルールによる階層グラフ構造の書き換えで計算が進む言語 ルールの実行順序は自由 →可能なところから計算が進む並行計算のモデル X=[a,a,a], {p(X,[])}. X=[], {p(X,[a,a,a])}. → X=[a|T], {p(X,Y), $p[Y]} :- {p(T,M), {M=[a|Y],$p[Y]}}.

LMNtal実行までの処理の流れ 中間命令列が各処理の中心にある

中間命令列 中間命令列とは、グラフを操作するための粒度の小さい命令セットである 以下の例は概念を示すためのもので実際の中間命令列とは異なっている (1)‏ findatom [1, 0, 'a'_1] グラフの始点を選ぶ (2)‏ deref [2, 1, 0, 0] リンクをたどる (3)‏ func [2, 'b'_1] アトムの種類を確認する (4)‏ newatom [3, 0, 'c'_1] 新しいアトムを生成する (5)‏ newlink [1, 0, 3, 0] リンクを張る (6)‏ freeatom [2] アトムを消す

研究の動機・目的 より速いLMNtal実行環境を得ること ↓ SLIM上においてCへの変換を行う ・　リンクオブジェクトの排除 ・　ポインタメンバへのデータの埋め込み ・　内部データ構造の絞込み ＊　SLIMはJava版実行時処理系と比較して数十倍高速 ここにJava版で得られた高速化の手法を持ち込むことで更なる高速化 ＊　Java版実行時処理系において、Javaへの変換を行うと 　　 インタープリット実行に比べ数倍高速 ↓ SLIM上においてCへの変換を行う

変換の流れ 変換前 変換後 findatom [1, 0, 'a'_1] deref [2, 1, 0, 0] func i？ = lmn_mem_get_atomlist (？, ？); t？ = ？ for ( ？ = atomlist_head(i？); ？ != atomlist_end(i？); ？ = atom_next(？) )‏ { 繰り返す内容 } 失敗時命令 findatom [1, 0, 'a'_1] deref [2, 1, 0, 0] func [2, 'b'_1] newatom [3, 0, 'c'_1] newlink [1, 0, 3, 0] freeatom [2] 変換前 １．中間変数を出力 long v1, a1; /* アトムが入る */ long v2, a2; /* アトムが入る */ ・・・ 3．補助変数に 型情報を出力 i1 = lmn_mem_get_atomlist (v0, 'a'_1); t1 = 'a'_1; for ( v1 = atomlist_head(i1); v1 != atomlist_end(i1); v1 = atom_next(v1) )‏ { if(LMN_ATOM_GET_ATTR(v1,0) != 0)‏ continue; ・・・ } return 0; 2．各中間命令を対応する Cソースコードに変換 変換後

１．中間変数の出力 各中間命令が使用する中間変数を関数の先頭で宣言する ・ Javaへの変換機では中間変数を基底クラスのポインタ配列で管理し、 使用する際にはその要素に静的なキャストを行っていた Object[] v = new Object[100]; ・ SLIMでのインタプリタでも汎用の変数によって同様の方法を用いていた LmnWord *v = malloc(100*sizeof(LmnWord)); ○ Cへの変換機では、最適化が効きやすいよう変数を個別に宣言し、最終的には各変数に静的な型を持たせられるようにした。 現在は汎用型ポインタと整数データのみが利用可能である。 Atom *v1, *v2, *v4; Membrane *v3; int v5; この方法を用いることで、doubleのようにサイズの大きな一時データを 扱うことも期待できる

２．中間命令に対応するC言語コードを出力 各中間命令を実行するためのC言語コードを出力する freemem [ 1 ] 　　　　　　　⇒　　　　　　　lmn_mem_free(v1); loadruleset [ 0, 3 ] 　　⇒　　lmn_mem_add_ruleset(v0, (void*)&trans_ruleset_3); しかしSLIMで設計変更した影響により、 中間命令と実行コードが単純に対応しない場合が発生した そのような場合出力処理が煩雑になりがちである if ( リンクの先がデータなら ) { 代入によるデータコピー } else { 専用関数によるデータコピー } この問題を解決するため、「中間命令に対応するC言語コードを出力する関数」 を出力する補助ツールを作成した #ieq v v if(! (TRANS_DATA($$0) == TRANS_DATA($$1))) $$f; この記述は、中間命令ieqに対して出力するコードを表現しており、 変数0と変数1が等しくなければ次の繰り返しを行う

３．補助変数への型出力 SLIMにおいてはデータ構造の設計上 アトムの種類(型)が分からないとそのアトムのリンクを参照できない しかし機械的な変換では各命令にアトムの種類の情報が 含まれていないため動的に型を調べるしかなかった ⇒型を解析して静的に種類が分かっている場合は無駄を回避したい そこで型を表す補助変数を用意した newatom [1, 0, 'a'_1]　　　　　　⇒　　　　　v1 = newatom('a'_1); t1 = 'a'_1; 中間命令列において、ある中間変数の型が予測できる時があれば、 その時補助変数の内容は定数性を持っているはずである ↓ 自前で型解析を行わないでも C言語コンパイラの定数の畳み込み最適化を利用することで 型に関する最適化を行える

C言語への変換の効果 例題 インタープリット実行(s) 変換実行(s) 性能比 アトムの生成削除を繰り返す 8.402 4.457 1.885 リンクの繋ぎ替えを繰り返す 5.538 2.173 2.549 Josephus問題 16.243 6.719 2.417 Collaz算法 40.318 7.330 5.500 Lambda計算(Church数) 7.761 2.534 3.063 1つのルール内で複雑な計算や書き換えを行っている場合性能が向上しやすい

まとめと今後の課題 LMNtalからC言語への変換機能を設計、実装した。 まとめ ある程度実用的な例ではSLIMでのインタープリット実行に比べ 3倍程度の高速化を得られた。 今後の課題 今回C言語に変換したのはルール内のみで、 実行方式については自然なC言語とはかけ離れている。 LMNtalプログラムにおいてC言語に近い記述をしていれば それに似た実行方式をとる自然なC言語コードを出力できるようにしたい。

参考 [1] 乾敦行，工藤晋太郎，原耕司，水野謙，加藤紀夫，上田和紀 : [1]　乾敦行，工藤晋太郎，原耕司，水野謙，加藤紀夫，上田和紀 : 　　　``階層グラフ書換えモデルに基づく統合プログラミング言語LMNtal'' 　　　　　　コンピュータソフトウェア，Vol.~25, No.~1, pp.124--150, 2008. [2]　石川力, 堀泰祐, 村山敬, 岡部亮, 上田　和紀 : 　　　``軽量なLMNtal実行時処理系SLIMの設計と実装'' 　　　　　　情報処理学会第70回全国大会(発表予定), pp.??--??, 2008.