素子数と段数に基づく回路計算量の階層性の証明と論理合成システムの評価への応用

論理最適化システムの性能は,定数個のテスト回路からなる標準ベンチマーク集合に対して,素子数や段数をどれだけ減らせるかで評価されてきた.しかし,ベンチマーク集合による評価では,「テスト回路を意識したシステム開発」という不正を防止できないという欠点があった.このような背景から本研究では,次の二つの目標を設定し,研究を進めて来た.(1)素子数や段数を増やせば計算能力が真に増加するという「回路計算量の階層性」を理論的に証明する.(2)この理論的裏付けをもとに,「素子数と段数の最適性を証明できる具体的関数」を見つけ出す.この関数を計算する回路を論理合成システムで構成し,素子数や段数が最適値にどれだけ近いかを検討することでシステムの性能を評価する.平成10年度は,以下の研究成果を公表した.1.直列計算における時間量と領域量に関する稠密な階層性を証明した.領域量階層に関しては,電子情報通信学会論文誌に採録が決定している.また,時間量階層に関しては,チェコ共和国で開催された国際会議(23rd International Symposium on Mathematical Foundations of Computer Science),および,竹原市で開催された「情報基礎理論ワークショップ」にて成果を公表した.2.回路計算量については,対数時間一様と呼ばれるある種の論理回路族の計算量階層に関する論文を,国際学術雑誌(Journal of Computer and System Sciences)に投稿中である.また,1.と2.は,電子情報通信学会第11回「回路とシステム(軽井沢)ワークショップ」にて招待講演として研究成果を公表した.

論理最適化システムの性能は,定数個のテスト回路からなる標準ベンチマーク集合に対して,素子数や段数をどれだけ減らせるかで評価されてきた.しかし,ベンチマーク集合による評価では,「テスト回路を意識したシステム開発」という不正を防止できないという欠点があった.このような背景から本研究では,次の二つの目標を設定し,研究を進めて来た.(1)素子数や段数を増やせば計算能力が真に増加するという「回路計算量の階層性」を理論的に証明する.(2)この理論的裏付けをもとに,「素子数と段数の最適性を証明できる具体的関数」を見つけ出す.この関数を計算する回路を論理合成システムで構成し,素子数や段数が最適値にどれだけ近いかを検討することでシステムの性能を評価する.平成10年度は,以下の研究成果を公表した.1.直列計算における時間量と領域量に関する稠密な階層性を証明した.領域量階層に関しては,電子情報通信学会論文誌に採録が決定している.また,時間量階層に関しては,チェコ共和国で開催された国際会議(23rd International Symposium on Mathematical Foundations of Computer Science),および,竹原市で開催された「情報基礎理論ワークショップ」にて成果を公表した.2.回路計算量については,対数時間一様と呼ばれるある種の論理回路族の計算量階層に関する論文を,国際学術雑誌(Journal of Computer and System Sciences)に投稿中である.また,1.と2.は,電子情報通信学会第11回「回路とシステム(軽井沢)ワークショップ」にて招待講演として研究成果を公表した.