回路抽出による大規模論理回路へのトランスダクション法の適用
スポンサーリンク
概要
- 論文の詳細を見る
計算機を用いた自動論理回路合成において、回路変換による論理回路最適化手法は非常に重要な技術である。また、計算機能力の飛躍的向上と、効率の良い論理関数表現手法の開発(SBDD)により、ブール的手法が現実的に用いることが可能となってきた。そのような手法の中で、1970年代にイリノイ大学において開発されたトランスダクション法は、許容関数と呼ばれる回路内の冗長性を表す概念を用いて、面積や遅延など妥求に基づいて回路変換を行なうものである。開発当時は、計算機能力など様々な制約のため実用性が示されなかったが、最近ランダム論理については非常に良好な結果を得られることが分かり、日米の数社において実用化されている。しかし回路が大規模化するにつれ、回路全体を最適化の村象とする手法は、記憶容量、計算時間の両面から困難となる場含が多い。そこで、最適化の際に回路全体ではなく、部分回路に対する手法を適用するような手法が求められてきている。我々はこれまでに、ある部分回路をより段数の小さい回路へと置き換えることにより遅延最適化を行なう手法を提案してきたが、面積削減に対する手法については開発を行なってきていなかった。またの手法は、選択ざれる部分回路が比較的小さいため、大域的な回路変換が行なわれない。他では、文献[2]にこおいて、トランスダクション法のアルゴリズムの変更による大規模回路への適用法が提案されている。本発表では、遅延最適化と同時に面積減少も行なうようなトランスダクション法を、現実的な計算時間と記憶容量の範囲内において、大規模回路に対して適用する手法を提案する。本手法は、論理関数と許容関数の計算を、その関数のBDDのサイズ(ノード数)によって制限することによって計算範囲を限定し、高速に処理を行なうことを可能とするものである。また本手法による実験を行ない、かなり大規模な回路を短時問で処理することが可能であり、得られる解の品質も良好であることを示す。
- 一般社団法人情報処理学会の論文
- 1994-03-07
著者
関連論文
- Virtual Officeにおける仮想オフィス間の通信機能
- 効率の良い直列分解多段化に基づくファンイン制限付きトランスダクション法実現の一手法
- トランスダクション法の初期回路における一般化直列分割に基づくファンイン制限
- 回路抽出による大規模論理回路へのトランスダクション法の適用
- 最長経路の分解と置換による遅延最適化
- 最長経路を含む部分回路置換による論理回路の段数削減手法
- トランスダクション法のための二分決定グラフを用いた束探索に基づく3段初期回路の生成
- トランスダクション法を用いた回路の置き換えによる論理回路遅延最適化について