More Web Proxy on the site http://driver.im/

research-article

On area/depth trade-off in LUT-based FPGA technology mapping

Authors:

Yuzheng DingAuthors Info & Claims

IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Volume 2, Issue 2

Pages 137 - 148

https://doi.org/10.1109/92.285741

Published: 01 June 1994 Publication History

Abstract

In this paper, we study the area and depth trade-off in lookup-table (LUT) based FPGA technology mapping. Starting from a depth-optimal mapping solution, we perform a sequence of depth relaxation operations and area-minimizing mapping procedures to produce a set of mapping solutions for a given design with smooth area and depth trade-off. As the core of the area minimization step, we have developed a polynomial time optimal algorithm for computing an area-minimum mapping solution without node duplication for a K-bounded general Boolean network, which makes a significant step towards complete understanding of the general area minimization problem in FPGA technology mapping. The experimental results on MCNC benchmark circuits show that our solution sets outperform the solutions produced by most existing mapping algorithms in terms of both area and depth minimization.

References

[1]

N. Bhat and D. Hill, "Routable technology mapping for FPGA's," 1st Int. ACM/SIGDA Wkshp. on FieM Programm. Gate Arrays, pp. 143-148, Feb. 1992.

[2]

R. K. Brayton, R. Rudell, and A. L. Sangiovanni-Vincentelli, "MIS: A multiple-level logic optimization," IEEE Trans. CAD, pp. 1062-1081, Nov. 1987.

Digital Library

[3]

K. C. Chen, J. Cong, Y. Ding, A. B. Kahng, and P. Trajmar, "DAG-Map: Graph-based FPGA technology mapping for delay optimization," IEEE Design and Test of Comput., pp. 7-20, Sept. 1992.

[4]

J. Cong and Y. Ding, "An optimal technology mapping fo delay optimization in lookup-table based FPGA designs," Proc. IEEE Int. Conf. on Computer-Aided Design, pp. 48-53, Nov. 1992.

[5]

J. Cong and Y. Ding, "Beyond the combinational limit in depth minimization for LUT-based FPGA designs," Proc. IEEE Int. Conf. on Computer-Aided Design, pp. 110-114, 1993.

[6]

J. Cong, Y. Ding, T. Gao, and K. Chen, "An optimal performance-driven technology mapping algorithm for LUT based FPGA's under arbitrary net-delay models," Proc. 1993 Int. Conf. on CAD and Computer Graphics, pp. 599-603, Aug. 1993.

[7]

T. Cormen, C. Leiserson, and R. Rivest, Algorithms. Cambridge, MA: MIT Press, 1990.

[8]

A. Farrahi and M. Sarrafzadeh, "On the lookup-table minimization problem for FPGA technology mapping," in Tech. Rep. 93-AC-102, Dept. of EECS, Northwestern Univ. (July 1993).

[9]

R. J. Francis, J. Rose, and Z. Vranesic, "Ghortle-crf: Fast technology mapping for lookup table-based FPGA's," Proc. 28th ACM/IEEE Design Automat. Conf., pp. 613-619, June, 1991.

Digital Library

[10]

R. J. Francis, J. Rose, and Z. Vranesic, "Technology mapping for lookup table-based FPGA's for performance," Proc. IEEE Int. Conf. on Computer-Aided Design, pp. 568-571, Nov. 1991.

[11]

D. Hill, "A CAD system for the design of field programmable gate arrays," Proc. 28th ACM/IEEE Design Automation Conf., pp. 187-192, June, 1991.

Digital Library

[12]

K. Karplus, "Xmap: A technology mapper for table-lookup field-programmable gate arrays," Proc. 28th ACM/IEEE Design Automat. Conf., pp. 240-243, June, 1991.

Digital Library

[13]

R. Murgai, Y. Nishizaki, N. Shenoy, R. Brayton, and A. Sangiovanni-Vincentelli, "Logic synthesis algorithms for programmable gate arrays," Proc. 27th ACM/IEEE Design Automation Conf., pp. 620-625, 1990.

Digital Library

[14]

R. Murgai, N. Shenoy, R. K. Brayton and A. Sangiovanni-Vincentelli, "Performance directed synthesis for table look up programmable gate arrays," Proc. IEEE Int. Conf. on Compuer-Aided Design, pp. 572-575, Nov. 1991.

[15]

R. Murgai, N. Shenoy, R. K. Brayton, and A. Sangiovanni-Vincentelli, "Improved logic synthesis algorithms for table look up architectures," Proc. IEEE Int. Conf. on Computer-Aided Design, pp. 564-567, Nov. 1991.

[16]

P. Sawkar and D. Thomas, "Technology mapping for table-look-up based field programmable gate arrays," 1st Int. ACM/SIGDA Wkshp. on Field Programm. Gate Arrays, pp. 83-88, Feb. 1992.

[17]

M. Schlag, J. Kong, and P. K. Chan, "Routability-driven technology mapping for lookup table-based FPGA's," Proc. 1992 IEEE Int. Conf. on Computer Design, pp. 86-90, Oct. 1992.

[18]

N.-S. Woo, "A heuristic method for FPGA technology mapping based on the edge visibility," Proc. 28th ACM/IEEE Design Automat. Conf., pp. 248-251, June, 1991.

Digital Library

[19]

Xilinx, The Programmable Gate Array Data Book. Xilinx: San Jose, 1992.

Cited By

Lee SMicheli G(2023)Heuristic Logic Resynthesis Algorithms at the Core of Peephole OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.325634142:11(3958-3971)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3256341
Hu HHu JZhang FTian BBustany IBadaroglu MDutt S(2022)Machine-Learning Based Delay Prediction for FPGA Technology MappingProceedings of the 24th ACM/IEEE Workshop on System Level Interconnect Pathfinding10.1145/3557988.3569713(1-6)Online publication date: 3-Nov-2022
https://dl.acm.org/doi/10.1145/3557988.3569713
Lee SRiener HMishchenko ABrayton RDe Micheli G(2022)A Simulation-Guided Paradigm for Logic Synthesis and VerificationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.310870441:8(2573-2586)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1109/TCAD.2021.3108704
Show More Cited By

Recommendations

Dual-output LUT merging during FPGA technology mapping
ICCAD '20: Proceedings of the 39th International Conference on Computer-Aided Design

Modern commercial Field-Programmable Gate Array (FPGA) architectures support dual-output look-up tables (LUTs). If the number of total inputs in two small LUTs do not exceed the constraint, e.g., 5 in Xilinx UltraScale+ series, we can pack them into one ...
Complexity issues and algorithms for LUT-based FPGA technology mapping
Heuristics for Area Minimization in LUT-Based FPGA Technology Mapping

In this paper, an iterative technology-mapping tool called IMap is presented. It supports depth-oriented (area is a secondary objective), area-oriented (depth is a secondary objective), and duplication-free mapping modes. The edge-delay model (as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Very Large Scale Integration (VLSI) Systems

IEEE Transactions on Very Large Scale Integration (VLSI) Systems Volume 2, Issue 2

June 1994

135 pages

ISSN:1063-8210

Issue’s Table of Contents

Copyright © 1994.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 June 1994

Revised: 01 December 1993

Received: 13 April 1993

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee SMicheli G(2023)Heuristic Logic Resynthesis Algorithms at the Core of Peephole OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.325634142:11(3958-3971)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3256341
Hu HHu JZhang FTian BBustany IBadaroglu MDutt S(2022)Machine-Learning Based Delay Prediction for FPGA Technology MappingProceedings of the 24th ACM/IEEE Workshop on System Level Interconnect Pathfinding10.1145/3557988.3569713(1-6)Online publication date: 3-Nov-2022
https://dl.acm.org/doi/10.1145/3557988.3569713
Lee SRiener HMishchenko ABrayton RDe Micheli G(2022)A Simulation-Guided Paradigm for Logic Synthesis and VerificationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.310870441:8(2573-2586)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1109/TCAD.2021.3108704
Riener HLee SMishchenko ADe Micheli GWang T(2022)Boolean Rewriting Strikes Back: Reconvergence-Driven Windowing Meets ResynthesisProceedings of the 27th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC52403.2022.9712526(395-402)Online publication date: 17-Jan-2022
https://dl.acm.org/doi/10.1109/ASP-DAC52403.2022.9712526
Echavarria JWildermann SKeszöcze OTeich JLi Z(2020)Probabilistic error propagation through approximated boolean networksProceedings of the 57th ACM/EDAC/IEEE Design Automation Conference10.5555/3437539.3437727(1-6)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.5555/3437539.3437727
Wang FZhu LZhang JLi LZhang YLuo GXie Y(2020)Dual-output LUT merging during FPGA technology mappingProceedings of the 39th International Conference on Computer-Aided Design10.1145/3400302.3415617(1-9)Online publication date: 2-Nov-2020
https://dl.acm.org/doi/10.1145/3400302.3415617
Juretus KSavidis I(2020)Characterization of In-Cone Logic Locking Resiliency Against the SAT AttackIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.292538739:8(1607-1620)Online publication date: 16-Jul-2020
https://dl.acm.org/doi/10.1109/TCAD.2019.2925387
Soeken MRoetteler MWiebe NMicheli G(2019)LUT-Based Hierarchical Reversible Logic SynthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.285925138:9(1675-1688)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1109/TCAD.2018.2859251
Haaswijk WSoeken MAmarù LGaillardon PDe Micheli G(2017)A novel basis for logic rewriting2017 22nd Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2017.7858312(151-156)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.1109/ASPDAC.2017.7858312
Khurshid B(2017)LUT based realization of fixed-point multipliers targeting state-of-art FPGAsDesign Automation for Embedded Systems10.1007/s10617-017-9184-x21:2(89-115)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s10617-017-9184-x
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents