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

平成８年度委託研究中間報告

１　研究テーマ、研究代表者：
　（１）研究テーマ: CMGTPによる並列チャネルルータの開発
　（２）研究代表者
        ［氏名］周 能法 (しゅう のうほう)
        ［組織名］九州工業大学情報工学部
        ［役職］助教授

２　記述項目：
　（１）研究進捗状況
まず,比較の対象としてCLP(FD)で多層チャンネルルーチイング問題を解くプ
ログラムを書いた.多層チャネルルーチイング問題は制約充足問題であるが,変
数の定義域が整数の集合ではなく,タプルの集合になっているため,そのままの
形では記述できない.そこで,変数の定義域が整数集合となるように,問題を定
式化し直した. また,制約伝搬をできるだけ早い時期に行なわせるために,遅延
機構を用いて条件付き制約を記述した.このプログラム(500行位)は,VLSI設計
の分野で有名なDeutsch問題を解くことができた.

そして,チャンネルルーチイング問題をCMGTPでの定式化を検討した.CMGTPは基
本的に既存の関係を組み合わせることによって新しい関係を構築するというボ
トムアップ的な証明方法を取っている.制約充足問題における変数と変数の定
義域及び制約は,全部関係として記述できる. この考えに基づいて書いたプロ
グラムは非常に簡潔であるが,組合せ爆発を簡単に引き起こしてしまう問題が 
ある.実際にCMGTPで書かれたプログラムは単純なバックトラックを用いた
Prologプログラムよりも遥かに遅い. 

そこで,研究方針を変え,直接並列版のKLICでプログラムを構築することを検討
した. KLICはcommitted-choice型の言語であるが,並行性を利用して非決定性
を真似ることができる.並行性を利用して探索問題を解く場合に,以下の二点が
非常に重要となる.一点目は,プロセスに適切な優先度を与えることである.
CLP(FD)でのプログラムでは,変数の具象化順序は制約グラフに基づいて決めら
れている.これに似たような考えがプロセスの優先度の指定に適用できると考
えられる.二点目は探索空間を縮めることである.探索木のすべての枝でプロセ
スを生成してしまうと,大量の粒度の低いプロセスが生成され,システム全体の
効率が低下してしまいがちである.そこで,最適解に導ける可能性の低い枝を刈
り取って,プロセスの数を減らす.

　（２）現在までの主な成果
``CROUTER in CLP(FD)''を開発した.このルータは,nHV型のチャネルと接続要
求を入力として受けとり,dogleg-free型の配線位置を出力として表示する.表
示は,LaTexを用いて行なわれているが,将来Tcl/Tkで書く予定である. このプ
ログラムはftp.kyutech.ac.jp:/pub/Language/prolog/benchmarks.tar.gzから
入手できる.  

``CROUTER in KLIC''の設計を行なった.特に探索木をKLICのどのようなプロセ
ス構造にマッピするかについて検討した.

　（３）今後の研究概要
``CROUTER in KLIC''を完成し,本学のネットワーク上で実験を行なう.そして,
``CROUTER in CLP(FD)''及び従来のルータと性能比較を行なう.

非nHV型チャネル及びdogleg型の配線に対応できるようにルータを拡張する.

　（４）今年度目標成果ソフトウェアイメージ
それぞれKLICとCLP(FD)で書かれた二つのルータを成果ソフトウエアとして提
供する.接続要求はデータファイルの形で,チャネルに関する情報は質問のパラ
メータとしてルータに与える.得られた結果はTcl/Tkを用いて表示する.