効率の良い直列分解多段化に基づくファンイン制限付きトランスダクション法実現の一手法

概要

論文の詳細を見る
近年のVLSI技術、および、論理回路の自動設計技術の進歩に伴い、計算機による論理回路設計が実用の域に入ってきている。特に、BOD(Binary Decision Diagrams)を利用することにより、これまで膨大な記憶容量を必要としてきたプール的手法による論理回路段適化が、広く利用されるようになった。1970年代前半にイリノイ大学において開発されたトランスダクション法は、許容関数と呼ばれる論理関数の変更の自由度を利用して回路を変形し、面積コスト、遅延時間などの点から最適化を行なう手法である。最近になって、規則性の少ない回路においては非常に良い結果を得ることができることが示され、BDDとの結合により、日米の数社で実用化されている。また、変数を時間シフトすることによる順序回路の最適化や、大規模回路向きのアルゴリズムの改良、並列計算機上での実現などの研究も行われ論理回路最適化の手法としての標準になりつつある。トランスダクション法では、初期回路として与えられた回路をもとに最適化を行なう手法であるため、初期回路の性質によって最適化後の結果が大きく左右され、局所解に落ち込んでしまうことも稀ではない。特に、テクノロジマッピングを考慮し、ファンイン制限を行なった上でのトランスダクション法の適用は、さらに回路変換の可能性を狭め、最適化結果が局所解に陥る要因となっていると考えられる。そこで本稿では、ファンイン制限を満たした初期回路に対し、ファンイン制限を満たした上でトランスダクション法を適用する際に、面積コストの点での最適化能力の向上を図るための改良を行なった結果を報告する。本手法は、回路変形の自由度を変化させながら局所解からなるべく抜け出せるように工夫をしたものであり、ファンイン制限をしたまま回路変換をする際の最適化能力の減少をなるべく小さくすることが可能である。実験の結果従来一般的にとられてきたファンイン制限のもとでのトランスダクション法に比べ、65%程度の回路で面積コストの改善が見られ、また回路によっては、劇的に面積コストの改善が実現できる場合があることが分かり、本手法が有効であることが示された。
一般社団法人情報処理学会の論文
1993-03-01

効率の良い直列分解多段化に基づくファンイン制限付きトランスダクション法実現の一手法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク