最長経路の分解と置換による遅延最適化

概要

論文の詳細を見る
論理回路合成において、回路変換による論理回路最適化は非常に重要な技術である。論理回路最適化の要求には、冗長結線の削除やゲート数削減による面積最小化などがあるが、近年、半導体価格の低下に伴い、面積を犠牲にしても高速な回路が求められる状況が増し、それに従って遅延最適化技術が重要とされてきている。しかし回路の大規模化に伴い、回路全体を回路変換の対象とするような手法は、記憶容量や計算時間などの面から困難となる場合が考えられる。そこで我々は文献において、大規模回路内の部分回路を段数の少ない回路に置換することによって段数削減を行なう手法を提案した。この手法は基本的に、最長経路付近の回路を再構成するという意味では文献のアプローチと同じではあるが、遅延最適化手法はその再構成すべき部分の選択とその再構成法が問題となるため、回路変換の能力は異なったものとなっている。本稿では、文献で提案した手法をさらに発展させ、効率の良い遅延最適化を行なう手法を提案する。本手法は、目的回路における最長経路に着目、その周辺の回路を分解し、その中でもっとも効果的だと思われる回路を置換することによって段数削減を行なう手法である。また、本手法を使ってベンチマーク回路の段数削減を行なった実験結果を示す。本手法では、置き換えるための回路はその部分回路に対してのみ生成されるので、回路の大規模化に伴う計算時間や記憶容量の増大は非常に小さい。また、本手法自体は現在テクノロジー独立であるが、これに続くテクノロジーマッピングを考慮し、ファンインを制限している。また、実験で用いたプログラムはそのファンイン制限値を任意に設定することが可能である。
一般社団法人情報処理学会の論文
1993-09-27

最長経路の分解と置換による遅延最適化

スポンサーリンク

概要

著者

関連論文

スポンサーリンク