再帰を含むプログラムに対するパラメトリック実行時間解析手法とツールの試作

摘要

実時間性を持つソフトウェア部品に関しては，実行時間がプロセッサなどの実行環境に依存するため，異なる環境への再利用は一般に困難である．パラメトリック実行時間解析手法を用いて，プログラムの実行時間を個々の処理の実行時間と繰り返し回数とのパラメータを用いた式の形で求めることにより，異なる実行環境においても実時間制約を満たすためのパラメータの最適化を，数理計画法を用いて容易に行うことができる．しかし，従来手法は有限オートマトンに基づいており，再帰呼び出しがあるプログラムは扱えなかった．本研究では，一般化Parikhの定理に基づき，再帰を含むプログラムを扱うことを可能にしたパラメトリック実行時間解析手法を提案する．