2.ＫＬ１のスレッド実行の高速化

［目次］

1. 研究テーマ
2. 研究体制／研究方法
3. 想定されるソフトウェア成果

［研究テーマ］

1) 研究テーマ名：

ＫＬ１のスレッド実行の高速化

2) 研究の背景

現在提供されている並列論理型言語 KL1 の処理系は， 動的な並列／並行実行の機構が大きなオーバヘッドの要因となり，充分な実行性能を得られていない。そこで我々は，モード解析 [1]などの静的解析技術を用いることによってこの問題を解決できると考え，研究を行ってきた。

本研究では，静的解析によりプログラムの挙動を予測し，この情報を利用してコードを生成することによって，実行時のオーバヘッドを削減するというアプローチをとる。 この方針に基づき，プロセッサ間通信の最適化手法 [2] や，ゴール・スケジューリングの最適化手法 [3,4]を確立し，それぞれ大幅な性能向上が得られることを示してきた。これらはいずれも変数の型解析に基づくものであり，一つの解析技術を様々な局面で応用できることを示したものでもある。

昨年度までの研究で，我々は既存の KLIC 上に前記の最適化手法を実装し，性能評価を行ってきた。しかし，これらの実装はまだ制限事項が多く，実プログラムに適用することは難しい。したがって，これらの最適化手法の成果を利用するには，実用的な処理系の設計・実装が欠かせない。

また我々が開発した型解析手法は，上記の手法以外の最適化にも利用でき，これによってさらに実行性能の向上が可能と考えられる。この方面の研究も，引き続き行っていく必要がある。

3) 研究の目的

平成７・８年度の研究成果を元に，我々は昨年度の研究でより高速なスレッド化手法を確立し，最適化 KL1 処理系として実装した。

しかし現在の手法には，次のような課題が残っている。

(a)完全なプログラム情報が得られない場合への対応

現在の解析系で用いている解析アルゴリズムは，すべての述語について完全な型情報が得られることを前提に，ゴール間の依存関係を求めている。したがって，対象プログラムについてなんらかの理由で不完全な情報しか得られない場合には，安全なスレッド化を行うことができない。

現在の実装では，組込述語については，あらかじめ述語ごとの型情報を解析系内に組み込むことで対処している。しかし，入出力やメタ機能など複雑なものについては，現状では対応できていない。また，将来ライブラリの形で組込述語が追加されることを想定すると，現在の方式では，そのつど述語の型情報を解析系に追加しなければならない。

さらに， KLIC ではジェネリック・オブジェクトによりユーザが新たな型を定義できるが，これについてもユーザが定義した型の情報を解析系に与える必要があり，ユーザの負担を増加させる。

このように，完全な解析情報を得る現在の方式は，一般の実プログラムを対象とする場合には制限事項が多く，処理系として実用性に欠ける。

また，ユーザ定義述語についても，定義節がすべてプログラム中で与えられている必要がある。このため，ユーザプログラムを分割コンパイルすることができない。この点も，大規模な実プログラムを対象とする場合に大きな欠点となる。

(b)解析情報を利用した，スレッド化以外のプログラム最適化

昨年度は， 平成７・８年度に行った KL1 のスレッド化手法を元に，これをより高速化する手法について研究を行った。これらの研究で得られた静的解析手法とその解析結果は，スレッド化以外のプログラム最適化手法にも応用できる。

たとえば，現在の KLIC の実行方式では，節内の最初のユーザ定義ボディゴールについてはゴールレコードを作らず， 引数を C の局所変数として保持したまま対応するコードに分岐する。このことを利用し，節内にユーザ定義ボディゴールをたかだか一つしか書かないようにコーディングすることによって，それらのゴールの中断が起きなければ高速な実行が可能であることが知られている。

節内のボディゴール呼び出しを複数の節に展開する変換を自動的に行うことによって，ユーザが特に意識しなくともプログラムの高速化が可能である。しかしそのためには，プログラムの意味を変えずに書き換え可能な範囲を，判別する必要がある。

これらの課題を解決することが，本年度の研究の目的である。

4) 研究の内容

(a)不完全な情報を扱える解析系の実現

現在の静的解析手法では，次のような手順によって型情報を求めている[3]。

(1)あらかじめ解析系に与えてある組込述語の引数型情報を元に， 対象プログラム中の組込述語の引数について，依存ゴールつき型集合を求める。

(2)同一化述語や，ユーザ定義述語によるヘッド・ボディ間同一化によって，型集合の伝搬を行う。

(3)伝搬が収束した時点で， 値参照を行うゴールの引数の型情報から，依存ゴールを求める。

このため，組込述語の具体化引数について (1)の段階で正しい型集合を求めることができなければ，(3) で正確な依存を得られず，安全にスレッド化を行うことが出来ない。 この結果，現在のスレッド化 KL1 処理系は，対象プログラム中で使用可能な述語がかなり限定されたものになっている。

この問題は，組込述語について充分な情報を解析系に組み込むことで，ある程度まで改善可能である。しかし，ジェネリック・オブジェクトによるユーザ定義型については，本質的に対応が不可能である。さらに，プログラムを分割コンパイルする場合を考えると，一部のユーザ定義述語については定義節，または呼出側のボディゴールが解析プログラム中に現れないことになる。この結果，型集合の伝搬がそこで途切れてしまう。

こうした，不完全な情報しか得られない場合には，依存の有無が判別できない部分については依存があるとみなすことによって，粒度は小さくなるものの安全なスレッド化を行うことが出来る。

そこで，本年度の研究では，不完全な解析結果しか得られない場合にも安全なスレッド化を行えるように，解析手法を修正する。これによって，一般のプログラムについてスレッド化可能な処理系を実現できる。

(b)ループ展開による実行高速化

たとえば，

p :- q, r, p. (p, q, r はユーザ定義ゴール，ai, bj は組込述語)

q :- a1, ... al.

r :- b1, ... bm.

という節があった場合， 従来の KLIC では r, p のゴールレコードを生成しゴールキューに繋いだ後，q に対応するコードにジャンプする。このため，節内で 2 番目以降のゴール r, p と比べると， q はゴールレコード生成のオーバヘッドを伴わない分，効率良く実行できる。

これを利用し，上記の節を次のように，各節にユーザ定義ボディゴールをたかだか 1 個しか含まないように書き換えることによって， プログラムを高速化することができる。

p :- q.

q :- a1, ..., al, r.

r :- b1, ..., bm, p.

本研究では，このループ展開をコンパイラが自動的に行うことによって，生成される実行コードの高速化を目指す。

このループ展開を行う上で，以下の点に注意する必要がある。

1.どのような場合にも q, r, p がこの順番で実行可能でなければならない。

2.プログラム中に現れる p, q, r のすべての呼び出しについて， 変形の前後 で意味が変わってはならない。たとえば，q が p の他にユーザ定義述語 sの定義節から呼び出されている場合，この定義節が

s :- ..., q, r, p.

となっていれば，上記の p,q,r の変形に加え，

s :- ..., q.

とすればよい。しかし，

s :- ..., q, s.

となっていれば， q を上のように変形してしまうと s からの呼び出しでは 不要な r, p が実行されてしまうから，q についての変形はできない。

1 については，スレッド化されたプログラムについて，各スレッド内についてのみ本手法を適用すればよい。

2 については，スレッド化されたプログラムについてゴール間の呼び出しグラフを作り，変形を適用可能な条件を求める必要がある。本研究では，この適用可能条件を求める手法を確立することによって，誤ったコードを生成することなくこの最適化を行う処理系を実現する。

［研究体制／研究方法］

1) 研究体制

	氏名	所属
研究代表者	中島　浩	豊橋技術科学大学
研究協力者	大野　和彦	豊橋技術科学大学
研究協力者	杉山　奈美代	豊橋技術科学大学(修2)

2) 研究の方法

昨年度の成果である「ゴール・スケジューリング最適化 KLIC（スレッド高速化版）」を元に，解析系／実行系を拡張・改良する形で行う。研究は２年計画で実施しており，本年度は初年度に行ったスレッド高速化手法の成果とプロトタイプの実装を元に，解析系・実行系の改良と並列実行への対応を行う。

［想定されるソフトウェア成果］

1) ソフトウェア名称

スレッド化 KLIC 改良版

2) そのソフトウェアの機能／役割／特徴

スレッド化 KLIC 改良版は， 昨年度のプロトタイプ版と同様に， ゴール間のデータ依存解析を行なってスケジューリング戦略を定める解析系と，解析系が求めた戦略にしたがってゴールのスケジューリングを行なう実行系に分かれる。また解析系／実行系ともにオリジナルの KLIC に組み込まれ，ユーザのプログラム変更が不要であることも，同様である。

解析系は，解析結果が不完全であっても，得られた範囲内で安全なスレッド化を行うように変更される。この結果，従来は内部的に型情報を与えていない組込述語を使用すると，誤ったスレッド化を行う可能性があったのに対し，今回の版では一般の実プログラムについて，正しいコード生成を行うことができる。

また，プログラム変形による最適化を行うために，ゴール間の呼び出し関係を解析する機能と，その解析結果を利用して，安全な場合のみ変形を行う機能を追加する。

実行系については，並列実行への対応を行う。

3) ソフトウェアの構成／構造

解析系は，既存の KLIC コンパイラに対し，マクロ展開後に依存解析などを行う解析部を追加する。また，解析部の結果を利用してコードを最適化するよう，コード生成部に追加・変更を加える。 既存の KLIC との連続性や，KLIC の今後の改良に対応するため，解析系は既存部分とは最大限に独立した形で実装する。また，今後さらに最適化手法を追加可能なように，解析部にできるだけ汎用性を持たせる。

実行系は，既存の KLIC ランタイムシステムの一部として追加・変更を行う。本年度に新たに追加するループ展開による最適化は，プログラムを変形してからコード生成を行うことで実現され，ランタイムシステムの変更は不要である。したがって，昨年度の版と同様，スレッド化されたゴールの実行・スレッドの動的スケジューリングなどの機構を組み込む。また，組込述語については既存のランタイムをそのまま使用する。本年度版は解析系の改良により，これらの組込述語のほとんどが使用可能になる。

4)ブラッシュアップ項目

ソフトウェアの操作性の向上

昨年度に作成した最適化 KLIC では，解析系の設計・実装上の制約により以下のような制限事項があり，実用的な使用は困難であった。

1. 組込述語は一部しか使用できない
2. ジェネリック・オブジェクトによるユーザ定義型は使用できない
3. ソースプログラムは 1 ファイルとして与えなければならず， 分割コンパイルはできない

これらの制約は，解析により完全な型情報が得られることを前提として，スレッド化を行っているためである。

これに対し本年度の版では，解析アルゴリズムを見直し，プログラムの一部が欠けていたり，引数の型が不明な組込述語が存在しても，安全な範囲でスレッド化を行うように設計し直す。この結果，上記の制限事項がなくなり，一般のプログラムに対して最適化 KLIC を利用することができるようになる。

(5) もし，ＩＦＳとの関連があれば，どのソフトウェアと関連があるのか

本研究で作成するソフトウェアは， 既に IFS として提供している「ゴール・スケジューリング最適化 KLIC 改良版」を改良する形で実装される。

(6) 使用予定言語および動作環境／必要とされるソフトウェア・パッケージ／ポータビリティなど

解析系は KL1 で，実行系は C で作成する。動作環境などは KLIC と全く同一で良い。

(7) ソフトウェアの予想サイズ（新規作成分の行数）

解析系 1500 行。実行系 1000 行。

(8)ソフトウェアの利用形態

KLIC の改良版として提供されるので， KL1 プログラムは勿論，ユーザ定義のジェネリック・オブジェクトを変更する必要は一切ない。

また本研究での最適化は，ほとんど全てのプログラムに効果があると予想されるが，特にプロセスを指向したプログラミング・パラダイムを採用したプログラムについて，大きな効果を発揮するものと期待できる。また今後のプログラム開発において，従来のように処理系の性質を過度に考慮することなく，自然なプログラミングで十分に高い性能を得ることができると期待される。

(9) 添付予定資料

ソフトウェア仕様書，ユーザマニュアル等