Area-minimal algorithm for LUT-Based FPGA technology mapping with duplication-free restriction

被引：0
|
作者：
Kao, CC [1 ]
Lai, YT [1 ]
机构：
[1] Natl Pingtung Inst Commerce, Dept Informat Technol, Pingtung, Taiwan
来源：
ASP-DAC 2004: PROCEEDINGS OF THE ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE | 2004年
关键词：
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Minimum area is one of the important objectives in technology mapping for lookup table-based FPGAs. It has been proven that the problem is NP-complete. This paper presents a polynomial time algorithm which can run in O(n(3)) time to generate an efficient solution where n is the total number of gates in the circuit. The proposed algorithm partitions the graph representing the given circuit into subgraphs such that the solution can be obtained by merging the subgraph solutions. The greedy technique is then used to find the solution for each subgraph. It is shown that except for some cases the greedy method can find an optimal solution of a given problem. We have tested our algorithm on a set of benchmark examples. The experimental results demonstrate the effectiveness of our algorithm.
引用
收藏
页码：719 / 724
页数：6
相关论文
共 50 条
  • [1] Heuristics for area minimization in LUT-based FPGA technology mapping
    Manohararajah, Valavan
    Brown, Stephen D.
    Vranesic, Zvonko G.
    IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2006, 25 (11) : 2331 - 2340
  • [2] ALTO: An iterative area/performance tradeoff algorithm for LUT-based FPGA technology mapping
    Huang, JD
    Jou, JY
    Shen, WZ
    IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, 2000, 8 (04) : 392 - 400
  • [3] LUT-Based FPGA Technology Mapping for Reliability
    Cong, Jason
    Minkovich, Kirill
    FPGA 10, 2010, : 288 - 288
  • [4] LUT-Based FPGA Technology Mapping for Reliability
    Cong, Jason
    Minkovich, Kirill
    PROCEEDINGS OF THE 47TH DESIGN AUTOMATION CONFERENCE, 2010, : 517 - 522
  • [5] An iterative area/performance trade-off algorithm for LUT-based FPGA technology mapping
    Huang, JD
    Jou, JY
    Shen, WZ
    1996 IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN - DIGEST OF TECHNICAL PAPERS, 1996, : 13 - 17
  • [6] Technology Mapping of FSM Oriented to LUT-Based FPGA
    Kubica, Marcin
    Kania, Dariusz
    APPLIED SCIENCES-BASEL, 2020, 10 (11):
  • [7] Power minimization in LUT-based FPGA technology mapping
    Wang, ZH
    Liu, EC
    Lai, JB
    Wang, TC
    PROCEEDINGS OF THE ASP-DAC 2001: ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE 2001, 2001, : 635 - 640
  • [8] Simulated Annealing applied to LUT-based FPGA Technology Mapping
    Nachtigall, Matheus
    Ferreira, Paulo, Jr.
    Marques, Felipe
    PROCEEDINGS OF A SPECIAL SESSION 2017 SIXTEENTH MEXICAN INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (MICAI): ADVANCES IN ARTIFICIAL INTELLIGENCE, 2017, : 23 - 29
  • [9] ON NOMINAL DELAY MINIMIZATION IN LUT-BASED FPGA TECHNOLOGY MAPPING
    CONG, J
    DING, YZ
    INTEGRATION-THE VLSI JOURNAL, 1994, 18 (01) : 73 - 94
  • [10] Efficient LUT-based FPGA technology mapping for power minimization
    Hao, L
    Mak, WK
    Katkoori, S
    ASP-DAC 2003: PROCEEDINGS OF THE ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE, 2003, : 353 - 358
12345