最長経路を含む部分回路置換による論理回路の段数削減手法

概要

論文の詳細を見る
論理回路合成において、回路変換による論理回路最適化は非常に重要な技術であるといえる。論理回路最適化の要求には、冗長結線の削除やゲート数削減による面積最小化などがあるが、回路の段数削減による遅延最適化技術が重要とされてきている。しかし回路の大規模化に伴い、回路全体を回路変換の対象とするような手法は、記憶容量や計算時間などの面から因難となる場合が考えられる。我々は文献において、あるゲート集合を置き換えることにより段数を削減する手法を提案した。しかしこの手法はもとの回路の外部入力の一部より置き換える回路を生成するので、やはり大きな回路においては計算時間や記憶容量が増大する傾向があった。そこで本稿では、目的回路における最長経路に着目し、それを含んだ部分回路を回路変換の対象とすることによって段数削減を行なうような手法を提案し、その実験結果を示す。本手法では、置き換えるための回路はその部分回路に対してのみ生成されので、回路の大規模化に伴う計算時間や記憶容量の増大は非常に小さい。また、プログラムはファンイン数を任意に設定することができる。
一般社団法人情報処理学会の論文
1993-03-01