FPGA向けテクノロジ·マッピングにおける深さ最小ネットワーク生成のための効率的なカット列挙手法

摘要

本稿では，LUT型FPGA向けテクノロジ·マッピングにおいて，深さ最小なネットワークの生成を目的とした効率的なカット列挙手法を提案する．カットの数はカットのサイズに対して指数的に増加するため，サイズが大きいカットの全列挙には時間がかかる．提案手法は，深さ最小なネットワークの生成を保証しつつ限られたカットのみを列挙することによって，既存手法よりも高速にカットの列挙を行う．カットのサイズを8および9とした実験の結果，提案手法はボトムアップ型の全列挙手法と比べてそれぞれ6倍および16倍，トップダウン型の全列挙手法と比べて2倍の早さでカットを列挙した．全てのカットを用いて生成したネットワークの段数と提案手法で列挙したカットを用いて生成したネットワークの段数は等しい．また，全てのカットを用いて生成したネットワークのLUT数と比較して，提案手法で列挙したカットを用いて生成したネットワークのLUT数はわずかに4％ほど大きかった．