IPA


IPAトップ





平成15年度未踏ソフトウェア創造事業  採択案件評価書


 



1.担当PM


 紀 信邦  (日本エンジェルズ・インベストメント株式会社 取締役 )



2.採択者氏名


 代表者

番原 睦則(神戸大学 学術情報基盤センター 講師)

共同開発者

田村 直之(同大学 教授)
井上 克已(国立情報学研究所 情報学基礎研究系 認知科学研究部門 教授)
川村 尚生(鳥取大学 助教授)
玉置 久(神戸大学 助教授)



3.プロジェクト管理組織


 日本エンジェルズ・インベストメント株式会社



4.委託金支払額


 7,488,250円



5.テーマ名


 Javaによる分散協調制約解消システム



6.関連Webサイト


 http://kaminari.istc.kobe-u.ac.jp/hecs/



7.プロジェクト概要


 このプロジェクトの開発テーマは分散コンピューティング環境において、複数の制約ソルバを協調的・競争的に並列動作させることにより、効率的な問題解決を実現するシステムを開発するということである。前年度の開発に関するPMによる評価は「面白いシステムが出来たと思う。特に各種アルゴリズムに計算資源を割当てるためのスケジューラと分散並列実行の仕組みが実装できたことは重要で今後の実験の基盤が作れたと考える」であった。
 本年度は、昨年の基盤の上でさらに実装を進めていただく。
 昨年度は、目的とするシステム実現に向けて、基本的なアルゴリズムおよびフレームワークを開発した。本年度は実用に耐えるシステムの構築を目標に、以下の3点を中心に開発を進め、分散協調制約解消システムの完成に取り組む。
 1. 協調制約解消アルゴリズムの開発・改良
 2. 大規模な計算機環境での種々の問題に対する適用実験
 3. 普及のためのユーザインタフェースの開発




8.採択理由


 各種の制約解消アルゴリズムを協調的・競争的に並列動作させることにより、単一のアルゴリズムをチューニングする以上の効果を得ようという前年度の開発成果である分散協調制約解消システムの改良と大規模計算環境での実証およびユーザインタフェースの開発を進める意義は大きいので採択とした。



9.開発目標


 具体的な開発目標として、以下の目標を設定した。
  1. 複数ソルバのための高度なスケジューラ
  2. Cream上での新しい制約解消アルゴリズム
  3. SATソルバの並列分散実行処理システム
  4. 複数ソルバのための分散実行環境
  5. 大規模な計算機環境での適用実験
  6. 普及のためのユーザインタフェースの開発



10.進捗概要


 本プロジェクトでは具体的な開発目標がいくつかのパートに分かれており、それぞれ別の開発者が担当したが、アルバイトの方を含め総勢14人を数える大所帯となった(一人の開発者が複数の開発テーマを持ったケースもある)。
 複数ソルバのための高度なスケジューラは解の交換,CPU 資源の割り当て,ソルバの選択/切替えを行うことができるGBMSシステムとして実装する。実装法としてはGAが選択された。
 制約解消系であるCreamの拡張としては、性能・機能に関する拡張が行われた他、OpenOffice Calcとのインターフェースが開発された。普及のためのユーザインタフェースの開発は本プロジェクトの開発成果を世の中に送り出すための重要な構成要素である。OpenOfficeユーザ会ともコンタクトし人材の紹介をお願いしたが、技術情報を提供人物を発見することはできなかった。結果的には開発者のチームは自力でOpenOfficeとの連携に関する技術を開発することとなった。
 SATソルバの並列分散実行処理システムはmultisatシステムとして実装された。PrologCafe上の複数のSATソルバを協調させて動かすことができるが、各種の実験を行いながら有効な機能の探索を行った。
 複数ソルバのための分散実行環境であるMaglogシステムがPrologCafe上の制約ソルバを協調して動作させることができるが、エージェント間でデータを交換するための仕組みがXMLタプルスペースとして実装された。
 PrologCafeはこれらの全体を担うHecsシステムのベースとなるProlog処理系であるが、種々の機能が追加され整理された他、本システムで必要である並列実行機能と例外処理機能の強化が行われた。




11.成果


 成果は、http://kaminari.istc.kobe-u.ac.jp/hecs/ から入手できる。
 下図はジョブショップ問題について、複数ソルバを協調動作させた場合(左方の列)と単独のアルゴリズム(右5列)を比較する実験結果であるが、GBMSを用いて協調動作させることが有効であることを示している。

 

複数ソルバを協調動作させた場合と単独のアルゴリズムを比較する実験結果表

 下図はOpenOffice CalcとCreamのインターフェースのデモンストレーションであり、20-Queensパズルの解法をOpenOfficeCalcで簡単に記述できることを示している。

 

OpenOffice CalcとCreamのインターフェースのデモンストレーション図





12.プロジェクト評価


A:優れている B:期待した程度 C:もっと頑張れ D:落第
生産性・完成度は予算相対です。
先鋭性:A
生産性:A
完成度:B
波及力:A

 期待以上の各種の実装と実験が行われたが、全体のシステムの統一感という意味ではまだ作業を残しているように思う。よって完成度評価をBとするが、開発成果の内容として先鋭性、生産性、今後の波及力とも最高点をつけたい。




13.今後の課題


 各種アルゴリズムの実装結果についての実験を進め、調整を図りながら全体の統一ができるとよい。
 GBMSは複数ソルバのための高度なスケジューラとして実装実験を行った構成要素だが、この部分が自律的に進化できるメタ・スケジューラとして有効に働くかどうか評価するためには実験を重ねる必要があろう。そのためには現実の問題に適用してみるなどの試練が必要であろう。 スケジューリング問題でもそうであるが特定のベンチマークを選定して評価を実施すると、どうしてもそのベンチマークについての性能だけに目が行きやすい。現実社会で必要なシステムの多くは経時的に発生するバリエーションを持つ特定の領域の問題に対して平均的に良い解を求められるシステムであり、今回の開発で複数ソルバの協調を志向したのはその目的だった。
 この種のシステムが現場で実際に使われるようにするためには、具体的な適用業務を見つけて試作と運用実験を積み重ねることが必要であるので、各方面からの協力をお願いしたい。


  ページトップへ   






  Copyright(c) Information-technology Promotion Agency, Japan. All rights reserved 2004