Area Recovery under Depth Constraint by Cut Substitution for Technology Mapping for LUT-based FPGAs

DAシンポジウム2008-システムLSI設計技術とDA : 2008年8月26日-27日 : 静岡県浜松市深さ（最長パスの長さ）制約下で信号遷移確率の総和が小さいネットワークを生成するテクノロジ・マッピング問題はNP 困難なクラスと同等に難しいと考えられ，ヒューリスティックな手法で解かざるを得ない．本稿では，深さ最小な初期解からLUT を取り除く反復改善によって局所的な最適解を生成するアルゴリズムを考える．The problem to generate a network comprised by LUTs whose total swithcing activity is minimum for technology mapping for LUT-based FPGAs is as difficult as NP-hard class problem, and the problem to generate a network under depth-minimum constraint seems to be difficult. So we must take a heuristic approach to generate a solution for this problem. In this paper, we study the algorithm to generate a local optimum solution by eliminating redundant LUTs while the depth of the network is maintained