一般部分計算(GPC)における制御構造と停止条件

Report
ソフトウェア開発アルゴリズム
プログラム自動超高速化実験
システムの開発
二村良彦
早稲田大学 理工学部 情報学科
一般部分計算法(GPC)
一般部分計算は,PEPMC’87 (1987)にお
いて二村等により提案された.
 推論機能(定理証明器)を利用した強力な
プログラム変換法で,コンパイラやコンパイ
ラ・コンパイラの自動生成も可能.

自動高速化の効果(理論値)
ハノイ問題の場合,素朴なプログラムでは
n=64の時,
264-1=1844京6744兆737億955万1615単
位時間以上を要する.
 早稲田システムにより最適化されたプログ
ラムで計算すると,n=64の時,約64単位時
間で計算できる.
 これは理論的には約28京倍の高速化

自動高速化の効果(観測値)
枚数(n) 素朴なプログラ
ム計算時間
(PenIII 650M)
22
3分3秒
最適化プロ 高速化
グラム計算 比率
時間
23
0.00043秒 140万倍
9分44秒
0.00042秒 45万倍
24以上 メモリ不足のた 0.00044秒 無限大の
差
め計算不能
(OSストール
WWW公開ソフトウェア
(1) ランダムデーターサーバ(RDS):
プログラムの性能および信頼性評価の
ためのデストデータ自動生成ソフトウェア
(2) T(n)ソルバー :分割統治法で作成された
プログラムの計算量,線形再帰方程式の解
等の自動評価ソフトウェア
(特許出願準備中)
2001年度以降の実現計画
早稲田大学「ソフトウェア生産技術研究
所」において本プロジェクトの成果の実用
化を図る.
 自己適用化を可能とし,第2,第3二村射影
を実現する(コンパイラおよびコンパイラ・コ
ンパイラの自動生成).

明日のデモの内容
実際に1分以内で,プログラムが約1万倍
以上に高速化されるという事実を体感して
いただく.
 特許,新聞発表,国際学会における招待
論文,招待講演等の説明


similar documents