文献

J-GLOBAL ID：200902201071910650   整理番号：09A1258101

LUT型FPGAの深さ最適テクノロジーマッピングに対する効率的なカット計数ヒューリスティックス

Efficient Cut Enumeration Heuristics for Depth-Optimum Technology Mapping for LUT-Based FPGAs

著者 (2件)： TAKATA Taiga (Kyushu Univ., Fukuoka-shi, JPN) ,  MATSUNAGA Yusuke (Kyushu Univ., Fukuoka-shi, JPN)
資料名： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Institute of Electronics, Information and Communication Engineers)  (IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Institute of Electronics, Information and Communication Engineers))
巻： E92-A  号： 12  ページ： 3268-3275  発行年： 2009年12月01日 
JST資料番号： F0699C  ISSN： 0916-8508  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： LUT型FPGA向けの最近のテクノロジーマッパーは,カット計数を採用している。良いネットワークを発見するには多数のカットを必要とする場合が多いものの,サイズの大きいすべてのカットの計数は多大な実行時間を消費する。既存のアルゴリズムは,各ノードのファンインカットの直積を計算するボトムアップマージを用いている。カットの数は,大部分の場合にこの直積のサイズよりは非常に小さい。従って既存のアルゴリズムは効率が悪い。さらにカットの数は,カットのサイズと共に指数的に増加し,これは実行時間をさらに大きくする。すべてのカットではなく部分的カットを計数する幾つかのアルゴリズム[8],[9]が示されているが,それらはネットワークの品質を損なう傾向がある。本論文は,カットを計数する2つのアルゴリズムとして,総当たり計数と部分計数を示す。両方とも効率は良いが,これはボトムアップマージを使用していないためである。部分計数は,深さ最小ネットワークが構築できるという保証で計数するカットの数を低減する。実験結果によれば,既存のボトムアップアルゴリズム[12]と比較して,総当たり計数はK=8,9に対しそれぞれ約5倍と13倍高速で実行される。その一方で,部分計数は,既存のボトムアップアルゴリズムよりもK=8,9に対しそれぞれ約9倍と29倍高速で実行される。部分計数により計数されるカットの集合により求めたネットワークの平均面積は,すべてのカットを使用し,深さは同じとして求めた場合よりも4%大きいだけである。(翻訳著者抄録)

シソーラス用語： *FPGA ,  ルックアップテーブル ,  ネットワーク ,  等価変換 ,  深さ ,  カットセット ,  直積 ,  時間 ,  計算機アルゴリズム ,  計数法 ,  高速度 ,  発見的方法 ,  実験 ,  最適化手法 ,  最適設計 ,  意思決定 ,  可能性
準シソーラス用語： Booleネットワーク ,  実行時間 ,  評価実験 ,  *テクノロジーマッピング ,  トップダウン ,  再構成可能性

分類 (2件)： 専用演算制御装置  (JC04030Y) ,  CAD,CAM  (JE10000A)

引用文献 (14件)：

• CONG, J. Flowmap : An optimal technology mapping algorithm for delay optimization in lookup-table based fpga designs. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 1994, 13, 1, 1-12
• CONG, J. On area/depth trade-off in lut-based fpga technology mapping. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 1994, 2, 2, 213-218
• CONG, J. Simultaneous depth and area minimization in lut-based fpga mapping. Proc. ACM 3rd Int'l Symp. on FPGA, 1995. 1995, 68-74
• CONG, J. Cut ranking and pruning : Enabling a general and efficient fpga mapping solution. Proc. FPGA'99. 1999, 29-35
• CHEN, D. Daomap : A depth-optimal area optimization mapping algorithm for fpga designs. Proc. ICCAD'04. 2004, 752-759

タイトルに関連する用語 (5件)： LUT ,  FPGA ,  テクノロジーマッピング ,  計数 ,  ヒューリスティックス