VLSI設計における全解探索アルゴリズムの開発に関する研究

点击翻译按钮获取中文摘要

1.まえがきVLSIの設計では、回路網を記述する非線形方程式をコンピュータで解くことが行なわれる。回路方程式は一般に複数の解をもち、それらすべての解を設計段階で検証することが要求されるが、実用的な全解探索アルゴリズムはまだ開発されていない。本研究は、VLSIを記述する非線形方程式のすべての解を求める、高速で実用的なアルゴリズムを開発することを目的として行なわれたものである。2.研究成果本研究は当初の計画通り順調に行なわれ、その成果のほとんどは学会論文誌、国際会議等で発表されている。研究成果の概要は次の通りである。1)VLSIを記述する非線形方程式は、セパラビリティと呼ばれる特殊な構造的性質をもつ。本研究ではまず、この性質を活用した非線形回路方程式のすべての解を求める高速アルゴリズムを開発した。本手法は既存のどの方法よりも遥かに高速であることが確認された。(2)次に“超球面"の概念を用いた新しい解曲線追跡法を開発し、これを複数個の解の高速探索法として拡張した。この方法は“実現容易性"に優れ、広く実用に供することができる。(3)アルゴリズムの適用範囲をMOS系VLSIに拡張するため、セパラブルでない非線形関数をセパラブルな関数に変形させるアルゴリズムを開発した。この研究は、有名なヒルベルトの第13問題に対するコルモゴロフの存在証明に、具体的な構成アルゴリズムを与える形となり、学会からの注目度は非常に高かった。補助金は補助金の補助条件に従って大体当初の予定通り使用された。また補助金により購入した設備品(コンピュータ端末)は数値実験などにおいて十分に活用された。