t1 = `a`_1

LMNtalからC言語への変換の設計と実
装
2007年度卒業論文発表
2008/2/5
1G04R013-7
石川力
1
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]}}.
2
LMNtal実行までの処理の流れ
3
中間命令列
中間命令列とは、グラフを操作するための粒度の小さい命令セット
以下の例は概念を示すため実際の中間命令列とは異なっている
(1)
(2)
(3)
(4)
(5)
(6)
findatom
deref
func
[1, 0, 'a'_1]
[2, 1, 0, 0]
[2, 'b'_1]
グラフの始点を選
ぶ
リンクをたどる
newatom
newlink
freeatom
[3, 0, 'c'_1]
[1, 0, 3, 0]
[2]
新しいアトムを生成する
リンクを張る
アトムを消す
アトムの種類を確認する
4
研究の動機・目的
SLIMをより高速化すること
SLIMは軽量・高速な実行時処理系を目指し多くの改良が施されている
・
リンクオブジェクトの排除
・
ポインタメンバへのデータの埋め込み
・
内部データ構造の絞込み
＊ SLIMはJava版実行時処理系と比較して数十倍高速
ここにJava版で得られた高速化の手法を持ち込むことで更なる高速化
＊ Java版実行時処理系において、Javaへの変換を行うと
インタープリット実行に比べ数倍高速
↓
SLIM上においてCへの変換を行う
5
変換の流れ
char *trans_symbols[] = {
"lmn",
"tal",
＊使用される文字列、型等の静的な情報を
それぞれ配列として出力
＊各ルールを関数として出力
＋ルール内で使用される中間変数を出力
・変数の使用目的に合わせた型で宣言
＋各中間命令に対応するC言語コードを出
力
・その際に変数の型を補助変数に出
力
"slim"
};
int trans_rule_0_0()
{
int v0d, v0a;
・・・
}
int trans_rule_1_0()
{
・・・
}
6
中間変数の出力
各中間命令が使用する変数を関数の先頭で宣言する
Javaへの変換機では中間変数を基底クラスのポインタ配列で管理し、
使用する際にはその要素に静的なキャストを行っていた
Object[] v = new Object[100];
SLIMでのインタプリタでも汎用の変数によって同様の方法を用いて
いた
LmnWord v = malloc(100*sizeof(LmnWord));
Cへの変換機では、最適化の効きやすいよう変数をばらばらに
し、最終的には各変数に静的な型を持たせられるようにした。
現在は汎用型ポインタと整数データのみが利用可能である。
Atom *v1, *v2, *v4; Membrane *v3; int v5;
この方法を用いることで、doubleのようにサイズの大きな一時データ
を
扱うことも期待できる
7
中間命令に対応するC言語コードを出力
補助ツールの話とか
8
補助変数への型出力
LMN_ATTR_IS_DATA(LMN_ATTR_INT)とか
LMN_ATOM_TYPED_GET_LINKとか
9
C言語への変換の効果
10
まとめと今後の課題
11
参考
[1]
乾敦行，工藤晋太郎，原耕司，水野謙，加藤紀夫，上田和紀 :
``階層グラフ書換えモデルに基づく統合プログラミング言語LMNtal''
コンピュータソフトウェア，Vol.~25, No.~1, pp.124--150,
2008.
[2]
石川力, 堀泰祐, 村山敬, 岡部亮, 上田和紀 :
``軽量なLMNtal実行時処理系SLIMの設計と実装''
情報処理学会第70回全国大会(発表予定), pp.??--??, 2008.
12
おわり
13
この中間命令列は次のように
機械的に変換が可能である
以下のソースコードも
説明のための概念的なもの
(1)
(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]
foreach(v1 in 'a'_1){
(2)
if( v1.attr[0] != 0 ){ continue; } else { v2 = v2.link[0]; }
(3)
if( v2.func != 'b'_1){ continue; }
(4)
v3 = newatom('c'_1);
(5)
newlink(v1, 0, v3, 0);
(6)
freeatom(v2);
/* success */
}
/* failure */
14
中間変数の出力
Javaへの変換機では中間変数を基底クラスのポインタ配列で管理し、
使用する際にはその要素に静的なキャストを行っていた
Object[] v = new Object[100];
Cへの変換機では、最適化の効きやすいよう変数をばらばらに
し、最終的には各変数に静的な型を持たせられるようにした。
現在は汎用型ポインタと整数データのみが利用可能である。
Atom *v1, *v2, *v4; Membrane *v3; int v5;
この方法を用いることで、doubleのようにサイズの大きな一時データ
を
扱うことも期待できる
15
研究の動機・目的
SLIMの開発目的は軽量、高速な実行時処理系を得ること
・
リンクオブジェクトの排除
・ポインタメンバへのデータの埋め込み
・
一部拡張機能の削除
Java版で得られた高速化の手法を活かせる部分が残っている
・
オーダーの改善
→
別アプローチから上田研メンバが研究中
・トランスレータ
＊ SLIMはJava版実行時処理系と比較して数十倍高速(参考文献よ
り)
＊ Java版実行時処理系において、Javaへの変換を行うと
インタープリット実行に比べ数倍高速
↓
更なる高速化として、SLIM上においてCへの変換
16
SLIMにおいてはデータ構造の設計上
アトムの種類(型)が分からないとそのアトムのリンクを参照できない
しかし機械的な変換では各命令にアトムの種類の情報が
含まれていないため動的に型を調べるしかなかった
⇒型を解析して静的に種類が分かっている場合は無駄を回避したい
型を表す補助変数を用意する
newatom [1, 0, 'a'_1]
⇒
v1 = newatom('a'_1); t1 =
'a'_1;
種類が予測できる時は型を表す変数の中身が一意に決まるはずなので、
型検査をC言語コンパイラが最適化してくれる
↓
自前で型解析を行わないでもC言語コンパイラの最適化を利用できる
17
C言語への変換の効果
ルール実行の失敗が多い場合や、各ルールの長さが短い場合
ボトルネックが最適化の範囲の外のためあまり効果がえられない
例) 単純なアトムの確保/開放を繰り返す場合
インタープリット実
行
C言語変換
3.775 (s)
2.414
それに対し、ルールが複雑になると最適化の効く範
囲が実行時間に占める割合が増えるため効果が高く
なる
例) lambda計算(Church数の例題)
インタープリット実
行
C言語変換
13.098
4.827
18
まとめと今後の課題
C言語コンパイラの最適化を利用することでルール内の最適化を行
い
ある程度実用的な例では3倍程度の高速化を得られた
C言語に変換できたのはルール内のみで、実行方式につ
いては自然なC言語とはかけ離れている
LMNtalプログラムにおいてC言語に近い記述をしていれば
それに似た実行方式をとる自然なC言語コードを出力できるように
したい
19

Download Report