LMNtalからC言語への変換の設計と実装

Slides:



Advertisements
Similar presentations
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
Advertisements

プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
LMNtalからC言語への変換の設計と実装
班紹介 描画班一同.
データ構造とアルゴリズム 第10回 mallocとfree
LMNtalからC言語への変換の設計と実装
情報伝播によるオブジェクト指向プログラム理解支援の提案
プログラミング言語論 第6回 型 情報工学科 篠埜 功.
情報科学1(G1) 2016年度.
アルゴリズムとデータ構造 2011年6月13日
プログラムはなぜ動くのか.
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
高山建志 五十嵐健夫 テクスチャ合成の新たな応用と展開 k 情報処理 vol.53 No.6 June 2012 pp
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
第13回 ハッシュテーブルを使ったプログラム ~高速に検索するには?~.
第7回 条件による繰り返し.
プログラム実行時情報を用いたトランザクションファンクション抽出手法
細かい粒度でコードの再利用を可能とするメソッド内メソッドのJava言語への導入
ちょっとした練習問題① 配列iroを['R', 'W', 'R', 'R', 'W' , 'W' , 'W']を宣言して、「W」のときの配列の番号をprintfで表示するようなプログラムを記述しなさい。
プログラミング言語入門 手続き型言語としてのJava
高速剰余算アルゴリズムとそのハードウェア実装についての研究
暗黙的に型付けされる構造体の Java言語への導入
第10回関数 Ⅱ (ローカル変数とスコープ).
プログラミング 4 記憶の割り付け.
プログラミング入門2 第11回 情報工学科 篠埜 功.
第7回 条件による繰り返し.
東京大学人間環境学専攻 奥田・橋本研究室 修士1年 相良 光志
通信機構合わせた最適化をおこなう並列化ンパイラ
動的データ依存関係解析を用いた Javaプログラムスライス手法
Javaバイトコードの 動的依存解析情報を用いた スライシングシステムの実現
プログラミング基礎B 文字列の扱い.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
プログラミング 4 整列アルゴリズム.
バイトコードを単位とするJavaスライスシステムの試作
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語.
コンパイラ 2011年10月20日
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
プログラミング言語論 第六回 理工学部 情報システム工学科 新田直也.
JNIを利用したSLIMと他のLMNtalプロダクトとの連携の調査
JAVAバイトコードにおける データ依存解析手法の提案と実装
アルゴリズムとプログラミング (Algorithms and Programming)
参照されないリテラル 長谷川啓
静的情報と動的情報を用いた Javaプログラムスライス計算法
プログラミング言語論 第十一回 理工学部 情報システム工学科 新田直也.
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
情報基礎Ⅱ (第1回) 月曜4限 担当:北川 晃.
同期処理のモジュール化を 可能にする アスペクト指向言語
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとプログラミング (Algorithms and Programming)
サブゼミ第7回 実装編① オブジェクト型とキャスト.
アルゴリズムとデータ構造1 2009年6月15日
第6回放送授業.
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
オブジェクト指向言語論 第二回 知能情報学部 新田直也.
コンパイラ 2012年10月11日
プログラミング 4 文字列.
アルゴリズムとデータ構造 2010年6月17日
ソフトウェア工学 知能情報学部 新田直也.
プログラミング言語論 第九回 理工学部 情報システム工学科 新田直也.
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
情報処理Ⅱ 第2回 2004年10月12日(火).
オブジェクト指向言語論 第七回 知能情報学部 新田直也.
プログラミング言語論 第九回 理工学部 情報システム工学科 新田直也.
オブジェクト指向言語論 第七回 知能情報学部 新田直也.
情報処理Ⅱ 2005年11月25日(金).
プログラミング演習II 2003年12月10日(第7回) 木村巌.
C#プログラミング実習 第1回.
1.2 言語処理の諸観点 (1)言語処理の利用分野
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
Presentation transcript:

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] 変換前 1.中間変数を出力 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ソースコードに変換 変換後

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

2.中間命令に対応する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が等しくなければ次の繰り返しを行う

3.補助変数への型出力 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.