Article

Improvements to technology mapping for LUT-based FPGAs

Authors:

Alan Mishchenko,

Satrajit Chatterjee,

Robert BraytonAuthors Info & Claims

FPGA '06: Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays

Pages 41 - 49

https://doi.org/10.1145/1117201.1117208

Published: 22 February 2006 Publication History

Abstract

The paper presents several improvements to state-of-the-art in FPGA technology mapping exemplified by a recent advanced technology mapper DAOmap [Chen and Cong, ICCAD '04]. Improved cut enumeration computes all K-feasible cuts without pruning for up to 7 inputs for the largest MCNC benchmarks. A new technique for on-the-fly cut dropping reduces by orders of magnitude memory needed to represent cuts for large designs. Improved area recovery leads to mappings with area on average 7% smaller than DAOmap, while preserving delay optimality when starting from the same optimized netlists. Applying mapping with structural choices derived by a synthesis flow on average reduces delay by 7% and area by 14%, compared to DAOmap.

References

[1]

B. Bloom. "Space/time tradeoffs in hash coding with allowable errors," Comm. of the ACM 13:7 (1970), pp. 422--426.

Digital Library

[2]

D. Chen, J. Cong. "DAOmap: A depth-optimal area optimization mapping algorithm for FPGA designs," Proc. ICCAD'04, pp. 752--757.

Digital Library

[3]

S. Chatterjee, A. Mishchenko, R. Brayton, X. Wang, and T. Kam, "Reducing structural bias in technology mapping", Proc. ICCAD '05, pp. 519--526. http://www.eecs.berkeley.edu/~alanmi/ publications/2005/iccad05_map.pdf

Digital Library

[4]

G. Chen and J. Cong, "Simultaneous logic decomposition with technology mapping in FPGA designs," Proc. FPGA'01, pp 48--55.

Digital Library

[5]

J. Cong and Y. Ding, "FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs", IEEE Trans. CAD, Vol.13(1), Jan. 1994, pp. 1--12.

Digital Library

[6]

J. Cong and Y. Ding, "On area/depth trade-off in LUT-based FPGA technology mapping," IEEE Trans. VLSI, Vol 2(2), Jun. 1994, pp 137--148.

Digital Library

[7]

J. Cong, C. Wu and Y. Ding, "Cut ranking and pruning: Enabling a general and efficient FPGA mapping solution," Proc. FPGA '99, pp. 29--36.

Digital Library

[8]

J. Cong et al, RASP: FPGA/CPLD Technology Mapping and Synthesis Package. http://ballade.cs.ucla.edu/software_release/rasp/htdocs/

[9]

N. Eén, A. Biere "Effective preprocessing in SAT through variable and clause elimination," Proc. SAT'05.

[10]

A. Farrahi and M. Sarrafzadeh, "Complexity of lookup-table minimization problem for FPGA technology mapping," IEEE Trans. CAD, vol. 13 (11), 1994, pp. 1319--1332.

Digital Library

[11]

IWLS 2005 Benchmarks. http://iwls.org/iwls2005/benchmarks.html

[12]

C.-C. Kao, Y.-T. Lai, "An efficient algorithm for finding minimum-area FPGA technology mapping". ACM TODAES, vol. 10(1), Jan. 2005, pp. 168--186.

Digital Library

[13]

A. Kuehlmann, V. Paruthi, F. Krohm, and M. K. Ganai, "Robust boolean reasoning for equivalence checking and functional property verification," IEEE Trans. CAD, Vol. 21(12), 2002, pp. 1377--1394.

Digital Library

[14]

E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness, "Logic decomposition during technology mapping," IEEE Trans. CAD, vol. 16(8), 1997, pp. 813--833.

Digital Library

[15]

F. Lu, L. Wang, K. Cheng, J. Moondanos and Z. Hanna, "A signal correlation guided ATPG solver and its applications for solving difficult industrial cases," Proc. DAC'03, pp. 668--673.

Digital Library

[16]

V. Manohara-rajah, S. D. Brown, Z. G. Vranesic, "Heuristics for area minimization in LUT-based FPGA technology mapping," Proc. IWLS'04, pp. 14--21.

[17]

A. Mishchenko, S. Chatterjee, R. Jiang, R. Brayton, "FRAIGs: A unifying representation for logic synthesis and verification," ERL Technical Report, EECS Dept., UC Berkeley, March 2005.

[18]

A. Mishchenko, S. Chatterjee, R. Brayton, and M. Ciesielski, "An integrated technology mapping environment," Proc. IWLS'05, pp. 383--390. http://www.eecs.berkeley.edu/~alanmi/publications/2005/ iwls05_env.pdf

[19]

A. Mishchenko, S. Chatterjee, R. Brayton, and P. Pan, "Integrating logic synthesis, technology mapping, and retiming", Proc. IWLS'05, pp. 383--390. Also, submitted to DAC '06. http://www.eecs.berkeley. edu/~alanmi/publications/2006/dac06_int.pdf

[20]

MVSIS Group. MVSIS: Multi-Valued Logic Synthesis System. UC Berkeley. http://www?cad.eecs.berkeley.edu/mvsis/

[21]

Berkeley Logic Synthesis and Verification Group, ABC: A System for Sequential Synthesis and Verification, Release 50905. http://www.eecs.berkeley.edu/~alanmi/abc/

[22]

P. Pan and C.-C. Lin, "A new retiming-based technology mapping algorithm for LUT-based FPGAs," Proc. FPGA'98, pp. 35--42.

Digital Library

[23]

M. Teslenko and E. Dubrova, "Hermes: LUT FPGA technology mapping algorithm for area minimization with optimum depth," Proc. ICCAD'04, pp. 748--751.

Digital Library

Cited By

Liu JZhao Q(2024)AiMap+: Guiding Technology Mapping for ASICs via Learning Delay PredictionElectronics10.3390/electronics1318361413:18(3614)Online publication date: 11-Sep-2024
https://doi.org/10.3390/electronics13183614
Guan ZMao RZhang QZhang ZZhao ZBian S(2024)AutoHoG: Automating Homomorphic Gate Design for Large-Scale Logic Circuit EvaluationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.335759843:7(1971-1983)Online publication date: Jul-2024
https://doi.org/10.1109/TCAD.2024.3357598
Pan HXia YWang LChu Z(2024)Semi-Tensor Product-Based Exact Synthesis for Logic RewritingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.333727943:4(1093-1106)Online publication date: Apr-2024
https://doi.org/10.1109/TCAD.2023.3337279
Show More Cited By

Index Terms

Improvements to technology mapping for LUT-based FPGAs
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware
  1. Electronic design automation
    1. Logic synthesis
      1. Circuit optimization
  2. Very large scale integration design
    1. Application-specific VLSI designs

Recommendations

Improvements to Technology Mapping for LUT-Based FPGAs

This paper presents several orthogonal improvements to the state-of-the-art lookup table (LUT)-based field-programmable gate array (FPGA) technology mapping. The improvements target the delay and area of technology mapping as well as the runtime and ...
WireMap: FPGA Technology Mapping for Improved Routability and Enhanced LUT Merging

This article presents a new technology mapper, WireMap. The mapper uses an edge flow heuristic to improve the routability of a mapped design. The heuristic is applied during the iterative mapping optimization to reduce the total number of pin-to-pin ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FPGA '06: Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays

February 2006

248 pages

ISBN:1595932925

DOI:10.1145/1117201

General Chair:
Steve Wilton
University of British Columbia, Canada
,
Program Chair:
André DeHon
California Institute of Technology, USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 February 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

FPGA06

Sponsor:

FPGA06: ACM/SIGDA International Symposium on Field Programmable Gate Arrays

February 22 - 24, 2006

California, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
702
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu JZhao Q(2024)AiMap+: Guiding Technology Mapping for ASICs via Learning Delay PredictionElectronics10.3390/electronics1318361413:18(3614)Online publication date: 11-Sep-2024
https://doi.org/10.3390/electronics13183614
Guan ZMao RZhang QZhang ZZhao ZBian S(2024)AutoHoG: Automating Homomorphic Gate Design for Large-Scale Logic Circuit EvaluationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.335759843:7(1971-1983)Online publication date: Jul-2024
https://doi.org/10.1109/TCAD.2024.3357598
Pan HXia YWang LChu Z(2024)Semi-Tensor Product-Based Exact Synthesis for Logic RewritingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.333727943:4(1093-1106)Online publication date: Apr-2024
https://doi.org/10.1109/TCAD.2023.3337279
Hu ZMa CChu Z(2024)A Novel Structural Choices Generation Method for Logic Restructuring2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617691(306-311)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617691
Tu KTang XYu CJosipović LChu ZTu KTang XYu CJosipović LChu Z(2024)Logic SynthesisFPGA EDA10.1007/978-981-99-7755-0_9(135-164)Online publication date: 1-Feb-2024
https://doi.org/10.1007/978-981-99-7755-0_9
Fan LWu CIenne PZhang Z(2023)FPGA Technology Mapping with Adaptive Gate DecompositionProceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays10.1145/3543622.3573048(135-140)Online publication date: 12-Feb-2023
https://dl.acm.org/doi/10.1145/3543622.3573048
Yu MDe Micheli G(2023)Striving for Both Quality and Speed: Logic Synthesis for Practical Garbled Circuits2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)10.1109/ICCAD57390.2023.10323660(01-09)Online publication date: 28-Oct-2023
https://doi.org/10.1109/ICCAD57390.2023.10323660
Wang HRizzi CJosipović L(2023)MapBuf: Simultaneous Technology Mapping and Buffer Insertion for HLS Performance Optimization2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)10.1109/ICCAD57390.2023.10323639(1-9)Online publication date: 28-Oct-2023
https://doi.org/10.1109/ICCAD57390.2023.10323639
Grosnit AZimmer MTutunov RLi XChen LYang FYuan MBou-Ammar H(2023)Lightweight Structural Choices Operator for Technology Mapping2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247838(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247838
Ruzicka RSimek V(2022)Technology Mapping for PAIG Optimised Polymorphic Circuits2022 25th Euromicro Conference on Digital System Design (DSD)10.1109/DSD57027.2022.00112(801-808)Online publication date: Aug-2022
https://doi.org/10.1109/DSD57027.2022.00112
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents