(21) CMGTP による並列チャネルルータの開発

［目次］

1. 研究の背景
2. 研究の目的
3. 研究内容
4. 研究体制／研究方法
5. 想定されるソフトウェア成果

［研究の背景］

チャネルルーチイング問題は,VLSIレイアウト設計の中の一つ重要な問題である。これは,チャネルのターミナル間の接続要求を与え,それらを満たす配線方法を決める制約充足問題である。私たちは,すでに制約論理型言語CLPを用いてこの問題を解くためのプログラムを書いた。しかし,このプログラムは,次に上げる二つの理由で満足にいく結果が得られなかった。(1)チャネルが多層になる場合に,一本の配線に対してチャネルの層と層の中のトラックを決めなければならないため,問題を簡単にCLPで記述できない。(2)大規模な問題を解く時に効率が悪い。

MGTPはKLICで書かれた一階述語論理のための証明系である。これは,非ホーン節が書けることや並列を意識せずに並列探索プログラムが書けるなどの魅力がある。また制約MGTPであるCMGTPは,制約解消によく用いられている制約伝搬法をルールを用いて柔軟に記述できる利点を持っている。しかし,CMGTPの応用は決して多いとは言えない。また,CMGTPは開発者以外の人によって徹底的に評価されたことはまだない。

［研究の目的］

本研究の目的は二つある.第一に,CMGTPを用いて高速なチャネルルータを構築する。この目的に達するためには,並列を生かすようなプログラミング技法を採用しなければならない。第二に,第五世代コンピュータ研究の基盤技術の一つであるCMGTPを評価し,CMGTPの応用範囲を広げる。また,このプロジェクトから得られた経験をCMGTPの機能拡張及び利用技術向上に役立てるように整理する。

［研究内容］

本研究は,特定型のチャネルと配線に対してルータを構築するのではなく,汎用性のあるチャネルルータを構築する。ルータは,チャネルと配線の型及び具体的な接続要求を入力として受けとり,配線位置を出力として表示する。具体的な研究内容は以下の通りである。

(a) 問題をCMGTPで記述しやすい形に定式化する。CMGTPは基本的に既存の関係を組み合わせることによって新しい関係を構築するというボトムアップ的な証明方法を取っている。チャネルルーチイング問題は制約充足問題であるが,変数の定義域が整数の集合ではなく,タプルの集合になっているため,変数及びそれの定義域を一つの多項関係として記述する。また,制約も関係として記述する。プログラムの実行は,既存の関係から制約を満たす新しい関係を生成することになる。

(b) プログラムの効率を改善するために,中間関係の生成を抑制する方法を採用する。具体的には,否定情報を積極的に伝搬して解の生成に貢献できない中間事実をできるだけ早く削除する。また,問題に特有な制御知識を用いて中間事実の生成を抑制する。さらに,目標に関連したサブゴールの証明を行なうトップダウン証明法の良さを取り入れたマジック法がこの問題に対して有効であるかどうかについても検討を行なう。

(c) プログラムの効率を改善するために,並列性を活用する.CMGTPで書かれたプログラムは,KLICに変換してから実行するため,CMGTPの有効なプログラミング技法を採用しなければならない。また実験を進めるとともに,新しいプログラミング技法を見つける必要があるかもしれない。

(d) ルータの性能を評価する.チャネルルーチイング問題に関して大規模なベンチマークが多く公開されている。これらのベンチマークを用いてCMGTPで書かれたルータの性能を評価し,また他のルータの性能との比較を行なう。

(e) KLICの視覚インタフェースを用いて配線の位置を表示するプログラムを作成し,本ルータを使いやすいソフトウエアにして公開する。

［研究体制／研究方法］