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

作成者
本文言語
出版者
発行日
収録物名
収録物名
開始ページ
終了ページ
出版タイプ
アクセス権
概要 本稿では,LUT 型 FPGA 向けテクノロジ・マッピングにおいて,深さ最小なネットワークの生成を目的とした効率的なカット列挙手法を提案する.カットの数はカットのサイズに対して指数的に増加するため,サイズが大きいカットの全列挙には時間がかかる.提案手法は,深さ最小なネットワークの生成を保証しつつ,限られたカットのみを列挙することによって,既存手法よりも高速にカットの列挙を行う.カットのサイズを$8...$および$9$とした実験の結果,提案手法はボトムアップ型の全列挙手法と比べてそれぞれ$6$倍および$16$倍,トップダウン型の全列挙手法と比べて$2$倍の早さでカットを列挙した.全てのカットを用いて生成したネットワークの段数と提案手法で列挙したカットを用いて生成したネットワークの段数は等しい.また,全てのカットを用いて生成したネットワークのLUT数と比較して,提案手法で列挙したカットを用いて生成したネットワークのLUT数はわずかに$4$%ほど大きかった.
This paper presents a top-down cut enumeration for depth-minimum technology mapping for LUT-based FPGAs. Enumerating all cuts with large size consumes long run-time because the number of cuts increases with the size of cuts. The proposed algorithm enumerates partial cuts with a guarantee that a depth-minimum network can be constructed, and runs faster than enumerating all cuts. The experimental results show that the proposed algorithm runs about $6$ times and $16$ times faster than bottom-up exhaustive enumeration for $K=8, 9$, respectively. The proposed algorithm also runs about $2$ times faster than top-down exhaustive enumeration for $K=8, 9$, respectively. Area of network derived by the set of cuts enumerated by the proposed algorithm is only $4$ % larger than that derived by exhaustive enumeration on average, and the depth is the same.
続きを見る

本文情報を非表示

taiga08_2 pdf 229 KB 97  

詳細

レコードID
査読有無
関連情報
主題
注記
タイプ
登録日 2009.06.02
更新日 2017.12.08

この資料を見た人はこんな資料も見ています