第 9 章
まとめと今後の課題
9.1 まとめ
本研究はLMNtal実行時処理系SLIMにおいて,ルール適用時におけるグラフパターン
マッチングの改善を行った. その結果,複数の例題において従来よりも高速にグラフパター ンマッチングが行えるようになった. 具体的には, アトムの動的操作によって想定する時 間計算量より悪く動作したプログラムの計算量を改善し,並列グラフパターンマッチング によって逐次実行と比較して10コアを使用したときに最大5倍の速度向上を達成した.
を変化させることは今後の課題である.
9.2.2 LMNtal ルール記述による計算量悪化の阻止
プログラムの実行性能を悪化させないために,本論文では内部実装を意識してルール記 述を行っている. 今後の課題として,ユーザーが内部事情をを知らなくても実行性能を悪 化させないよう, LMNtalコンパイラが最良な中間命令列を出力することが挙げられる. す なわち,同じ意味を持つルールは同じ中間命令列を出力するようにしなければならない.
一方で,静的にコンパイルされるLMNtalルールは扱うLMNtalグラフ上に存在してい るアトムを意識せずにコンパイルされる. 扱うLMNtalグラフによって最適な中間命令列 は異なるもとであると筆者は考える. LMNtalグラフの書換えに応じて最適な中間命令列 を動的に作成・適用させることも今後の課題である.
9.2.3 同時グラフ書換えの実現
本論文ではルール適用時におけるグラフパターンマッチングの並列化を行ったが, グラ フの書換えは逐次実行で行っている. しかし, 扱う例題によってグラフパターンマッチン グではなくグラフ書換えが実行のボトルネックとなることが十分考えられる.
本研究においてグラフ書換えを並列化しなかった理由として, SLIM 内においてグラフ を所持するデータ構造とルール適用のアルゴリズムが同時書換えに向いていなことが挙げ られる. 現在SLIM上のアトムは同じファンクタ同士を1つの連結リストで管理している ため,同時書換えを行う際は同時に複数のスレッドが同じアトムを書き換えないよう,処理 系の排他制御を徹底しなければならないと考える. しかし,性能向上を考えるにはなるべ く排他制御による遅延を抑えなければならない. したがってSLIM内部のアトムの管理方 法を含めて,同時書換えに適したデータ構造,同時書換えアルゴリズムを考えていく必要が ある.
9.2.4 同一プロセス内における複数ルールの管理
今回の評価実験は同一プロセス内に存在するルールは1つのみであることを条件に例題 の作成と計測を行った. しかし一般的にモデルを記述する際は複数のルールを使用してモ デリングすると考えられる. 現状の SLIMにおいて複数ルールを記述した場合, ルール適 用はプログラム中で上部に記述されているルールから行われる. したがってプログラム中 で下部に記述したルールの計算量は上部に記述されたルールの計算量の影響を受けてしま
う. 同一プロセス内において複数ルールを扱う際に, あるルールが他のルールの計算量の 影響を受けずに実行することが今後の課題の1つである.
謝辞
本研究を進めるにあたり,研究室の様々な方と日々議論を行い,指導・助言をいただきま した.
最初に本論文の研究に発展したきっかけとなるshortestpathall2all.lmnのプログラムを 提供して頂き, 修士論文完成まで日々全般的なご指導を賜わった上田和紀教授に深く感謝 致します.
次に研究室生活やゼミにおいて様々な先輩方から技術的な助言・アドバイスを頂きまし た. 特に学部時代にSLIM内部の構造を賜った目黒学氏，LMNtalコンパイラやLaViTに 関する私の要求に快く答えて下さった信夫裕貴氏,独自の世界に引き込む宮原和大氏,研究 室宴会に様々な絶品料理を提供して下さった谷口直輝氏,常日頃修行に励む松本翔太氏に 深く感謝致します.
さらに 3年間という長い期間, くだらない話をしたり励ましあったり, 時には夜が明け るまで遊んでくれた同期の皆さんには大変お世話になりました. 常に何かに追われている が着実に乗り越える小沼氏,影の努力が半端でない河野氏, 推しメンに一途な小林氏, いつ も不気味なくらい手牌が良い吉田氏,もりもりお仕事を頑張っている安田氏に感謝の意を 表します.
他にもいろいろな状況でお世話になった全ての人に感謝致します. 最後に，今までずっと影で支えてくれた家族に特に深く感謝致します．
2015年1月 青山龍一
参考文献
[1] T. Fr¨uhwirth: Theory and practice of constraint handling rules, Journal of Logic Pro-gramming, Special Issue on Constraint Logic ProPro-gramming, 37(1-3):95-138, 1998.
[2] Edmund S.L. Lam, Martin Sulzmann: A Concurrent Constraint Handling Rules Seman-tics and its Implementation with Software Transactional Memory, In DAMP ’07: Proc.
ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming, 2007.
[3] Christos H. Papadimitriou and Kenneth Steiglitz: Combinatorial Optimization Algo-rithm and Complexity, Dover Publications Inc., 1982.
[4] Dick Buttlar, Jacqueline Farrell, Bradford Nichols : Pthreads Programming, O’Reilly, 1996
[5] A.Grama, A.Gupta, G.Karypis, V.Kumar：Introduction to Parallel Computing (2nd ed.), Cambridge Univ. Press, 2003.
[6] Kazunori Ueda : LMNtal as a hierarchical logic programming language, Theoretical Computer Science, Vol.410, No.46, pp4784–4800, 2009.
[7] 水野謙，加藤紀夫，原耕司，上田和紀: 階層グラフ書換え言語LMNtal処理系におけ る非同期実行の実現,日本ソフトウェア科学会第22回大会論文集, 2005.
[8] 乾敦行， 工藤晋太郎， 原耕司， 水野謙， 加藤紀夫， 上田和紀： 階層グラフ書換 えモデルに基づく統合プログラミング言語LMNtal， コンピュータソフトウェア，
Vol.25，No.1，2008.
[9] 村山敬， 工藤晋太郎， 櫻井健， 水野謙， 加藤紀夫， 上田和紀：階層グラフ書換え
言語LMNtalの処理系， コンピュータソフトウェア，Vol.25，No.2，2008.
[10] 後町将人, 堀泰祐, 上田和紀: LMNtal実行時処理系の並列モデル検査器への発展, コ
ンピュータソフトウェア, Vol.28, No.4(2011), pp.137 157
[11] 中原紀, 長澤一之: 情報社会の原動力としての「ムーアの法則」とその終焉を巡る論 考,足利工業大学研究集録42, 117-124, 2008
[12] 石川力， 堀泰祐， 村山敬， 岡部亮， 上田和紀： 軽量なLMNtal実行時処理系SLIM の設計と実装，情報処理学会第70回全国大会，2008.
[13] 小川誠司,目黒学,上田和紀: 階層グラフ書換えモデルを拡張したHyperLMNtalの実 現, 2011年度人工知能学会全国大会, 2011
[14] 信夫裕貴,田辺良則,上田和紀: LMNtalにおけるグラフ書換え操作のCoqによる形式
化, 2013年度日本ソフトウェア科学会第30回大会, 2013
[15] 村山敬:計算量が予測可能なLMNtalシステムの設計と実装,修士論文, 2008.
[16] 岩澤宏希: LMNtalプログラムによるLMNtal中間命令列の最適化,修士論文, 2011.
[17] 小川誠司:階層グラフ書換えモデルを拡張したHyperLMNtalの実現,修士論文, 2011.
[18] 村山敬: LMNtalにおけるデータ並列処理環境の設計と実装,卒業論文, 2006.
[19] 青山龍一: LMNtal処理系SLIMのマルチスレッド化による最短経路問題のデータ並
列求解,卒業論文, 2013.
発表文献
[1] 青山龍一,上田和紀: LMNtal処理系SLIMのマルチスレッド化による最短経路問題
のデータ並列求解,先進的計算基盤システムシンポジウム(SACSIS2013), 2013,ポ スター発表．
[2] 青山龍一, 上田和紀: LMNtal 実行時処理系 SLIM におけるグラフ構造探索の計
算量改善, 第 16 回プログラミングおよびプログラミング言語ワークショップ (PPL2014), 2014,ポスター発表．
[3] 青山龍一,上田和紀: LMNtal処理系SLIMのマルチスレッド化による最短経路問題
のデータ並列求解,第15回プログラミングおよびプログラミング言語ワークショッ プ(PPL2013), 2013,ポスター発表．
付録 A
グラフ構造探索例題の応用
A.1 1 本のエッジしか接続されていないノード
1本のエッジしか接続されていないノード（つまりunaryノード）を抽出するルール例 を図A.1に示す. このルールは抽出したノードとエッジ,ノードの属性情報を消去する.
main @@
n(!H,$x),p(!H1,B),p(!H1,B) :-num(!H) == 1, hlground($x)|.
図A.1 グラフ中のunaryノードを消去するルール