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

research-article

Scalable don't-care-based logic optimization and resynthesis

Authors:

Alan Mishchenko,

Robert Brayton,

Jie-Hong R. Jiang,

Stephen JangAuthors Info & Claims

ACM Transactions on Reconfigurable Technology and Systems (TRETS), Volume 4, Issue 4

Article No.: 34, Pages 1 - 23

https://doi.org/10.1145/2068716.2068720

Published: 28 December 2011 Publication History

Abstract

We describe an optimization method for combinational and sequential logic networks, with emphasis on scalability. The proposed resynthesis (a) is capable of substantial logic restructuring, (b) is customizable to solve a variety of optimization tasks, and (c) has reasonable runtime on industrial designs. The approach uses don't-cares computed for a window surrounding a node and can take into account external don't-cares (e.g., unreachable states). It uses a SAT solver for all aspects of Boolean manipulation: computing don't-cares for a node in the window, and deriving a new Boolean function of the node after resubstitution. Experimental results on 6-input LUT networks after a high effort synthesis show substantial reductions in area and delay. When applied to 20 large academic benchmarks, the LUT counts and logic levels are reduced by 45.0% and 12.2%, respectively. The longest runtime for synthesis and mapping is about two minutes. When applied to a set of 14 industrial benchmarks ranging up to 83K 6-LUTs, the LUT counts and logic levels are reduced by 11.8% and 16.5%, respectively. The longest runtime is about 30 minutes.

References

[1]

Altera Corp. 2011. Altera Stratix IV FPGA family overview. http://www.altera.com/products/devices/stratix-fpgas/stratix-iv/overview/stxiv-overview.html.

[2]

Berkeley Verification and Synthesis Research Group (BVSRG). 2011. ABC: A system for sequential synthesis and verification, release 80802. http://www.eecs.berkeley.edu/~alanmi/abc/.

[3]

Betz, V., Rose, J., and Marquardt, A. 1999. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers.

Digital Library

[4]

Bjesse, P. and Claessen, K. 2000. SAT-Based verification without state space traversal. In Proceedings of the International Conference on Formal Methods in Computer-Aided Design (FMCAD'00). Lecture Notes in Computer Science, vol. 1954, Springer, 372--389.

Digital Library

[5]

Case, M. L., Mishchenko, A., and Brayton, R. K. 2006. Inductively finding a reachable state space over-approximation. In Proceedings of the International Workshop on Logic and Synthesis (IWLS'06). 172--179. http://www.eecs.berkeley.edu/~alanmi/publications/2006/iwls06_inv.pdf.

[6]

Case, M. L., Mishchenko, A., and Brayton, R. K. 2008. Cut-Based inductive invariant computation. In Proceedings of the International Workshop on Logic and Synthesis (IWLS'08). 253--258. http://www.eecs. berkeley.edu/~alanmi/publications/2008/iwls08_ind.pdf.

[7]

Chang, K.-H., Markov, I. L., and Bertacco, V. 2007. Fixing design errors with counterexamples and resynthesis. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC'07). 944--949.

Digital Library

[8]

Chen, K.-C. and Cong, J. 1992. Maximal reduction of lookup-table-based FPGAs. In Proceedings of the Design Automation and Test in Europe Conference (DATE'92). 224--229.

Digital Library

[9]

Chen, D. and Cong, J. 2004. DAOmap: A depth-optimal area optimization mapping algorithm for FPGA designs. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'04). 752--757.

Digital Library

[10]

Cong, J., Lin, Y., and Long, W. 2002. SPFD-Based global rewiring. In Proceedings of the International Symposium on Field Programmable Gate Arrays (FPGA'02). 77--84.

Digital Library

[11]

Een, E. and Sörensson, N. 2003. An extensible SAT-solver. In Proceedings of the SAT'03 Conference. http://www.cs.chalmers.se/Cs/Research/FormalMethods/MiniSat/.

[12]

Goldberg, E. and Novikov, Y. 2003. Verification of proofs of unsatisfiability for CNF formulas. In Proceedings of the Design Automation and Test in Europe Conference (DATE'03). 886--891.

Digital Library

[13]

Kravets, V. N. and Kudva, P. 2004. Implicit enumeration of structural changes in circuit Optimization. In Proceedings of the Design Automation Conference (DAC'04). 438--441.

Digital Library

[14]

Lee, C.-C., Jiang, J.-H. R., Huang, C.-Y., and Mishchenko, A. 2007. Scalable exploration of functional dependency by interpolation and incremental SAT solving. In Proceedings of the International Conference on Computer Aided Design (ICCAD'07). 227--233. http://www.eecs.berkeley.edu/~alanmi/publications/2007/iccad07_fd.pdf.

Digital Library

[15]

McMillan, K. L. 2003. Interpolation and SAT-based model checking. In Proceedings of the International Conference on Computer-Aided Verification (CAV'03). Lecture Notes in Computer Science, vol. 2725, Springer, 1--13.

[16]

McMillan, K. 2005. Don't-Care computation using k-clause approximation. In Proceedings of the International Workshop on Logic and Synthesis (IWLS'05). 153--160.

[17]

Mishchenko, A., Steinbach, B., and Perkowski, M. A. 2001. An algorithm for bi-decomposition of logic functions. In Proceedings of the Design Automation Conference (DAC'01). 103--108.

Digital Library

[18]

Mishchenko, A. and Brayton, R. 2005. SAT-Based complete don't-care computation for network optimization. In Proceedings of the Design Automation and Test in Europe Conference (DATE'05). 418--423. http://www.eecs.berkeley.edu/~alanmi/publications/2005/date05_satdc.pdf.

Digital Library

[19]

Mishchenko, A. and Brayton, R. 2006. Scalable logic synthesis using a simple circuit structure. In Proceedings of the International Workshop on Logic and Synthesis (IWLS'06). 15--22. http://www.eecs. berkeley.edu/~alanmi/publications/2006/iwls06_sls.pdf.

[20]

Mishchenko, A., Chatterjee, S., and Brayton, R. 2006a. DAG-Aware AIG rewriting: A fresh look at combinational logic synthesis. In Proceedings of the Design Automation Conference (DAC'06). 532--536. http://www.eecs.berkeley.edu/~alanmi/publications/2006/dac06_rwr.pdf.

Digital Library

[21]

Mishchenko, A., Zhang, J. S., Sinha, S., Burch, J. R., Brayton, R., and Chrzanowska-Jeske, M. 2006b. Using simulation and satisfiability to compute flexibilities in Boolean networks. IEEE Trans. Comput. Aid. Des. 25, 5, 743--755. http://www.eecs.berkeley.edu/~alanmi/publications/2005/tcad05_s&s.pdf.

Digital Library

[22]

Mishchenko, A., Chatterjee, S., Brayton, R., and Een, E. 2006c. Improvements to combinational equivalence checking. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'06). 836--843. http://www.eecs.berkeley.edu/~alanmi/publications/2006/iccad06_cec.pdf.

Digital Library

[23]

Mishchenko, A., Chatterjee, S., and Brayton, R. 2007a. Improvements to technology mapping for LUT-based FPGAs. IEEE Trans. Comput. Aid. Des. 26, 2, 240--253. http://www.eecs.berkeley.edu/~alanmi/publications/2006/tcad06_map.pdf.

Digital Library

[24]

Mishchenko, A., Cho, S., Chatterjee, S., and Brayton, R. 2007b. Combinational and sequential mapping with priority cuts. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'07). http://www.eecs.berkeley.edu/~alanmi/publications/2007/iccad07_map.pdf.

Digital Library

[25]

Mishchenko, A., Brayton, R., and Chatterjee, S. 2008a. Boolean factoring and decomposition of logic networks. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'08). 38--44. http://www.eecs.berkeley.edu/~alanmi/publications/2008/iccad08_lp.pdf.

Digital Library

[26]

Mishchenko, A., Brayton, R., Jiang, J.-H. R., and Jang, S. 2009. Scalable don't care based logic optimization and resynthesis. In Proceedings of the International Symposium on Field Programmable Gate Arrays (FPGA'09). 151--160. http://www.eecs.berkeley.edu/~alanmi/publications/2009/fpga09_mfs.pdf.

Digital Library

[27]

Mishchenko, A., Case, M. L., Brayton, R., and Jang, S. 2008b. Scalable and scalably-verifiable sequential synthesis. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'08). 234--241.

Digital Library

[28]

Muroga, S., Kambayashi, Y., Lai, H. C., and Culliney, J. N. 1989. The transduction method- Design of logic networks based on permissible functions. IEEE Trans. Comput. 38, 10, 1404--1424.

Digital Library

[29]

Pan, P. and Lin, C.-C. 1998. A new retiming-based technology mapping algorithm for LUT- based FPGAs. In Proceedings of the International Symposium on Field Programmable Gate Arrays (FPGA'98). 35--42.

Digital Library

[30]

Plaza, S., Chang, K.-H., Markov, I. L., and Bertacco, V. 2007. Node mergers in the presence of don't cares. In Proceedings of the Asia South Pacific Design Automation Conference (ASP-DAC'07). 414--419.

Digital Library

[31]

Saluja, N. and Khatri, S. P. 2004. A robust algorithm for approximate compatible observability don't care (CODC) computation. In Proceedings of the Design Automation Conference (DAC'04). 422--427.

Digital Library

[32]

Savoj, H. 1992. Don't cares in multi-level network optimization. Ph.D. dissertation, University of California, Berkeley.

Digital Library

[33]

Sentovich, E., Singh, K. J., Lavagno, L., Moon, C., Murgai, R., et al. 1992. SIS: A system for sequential circuit synthesis. Tech. rep. UCB/ERI, M92/41, ERL, Department of EECS, University of California, Berkeley.

[34]

Xilinx Corp. 2011. Xilinx Virtex-5 product table. http://www.xilinx.com/products/silicon_solutions/fpgas/virtex/virtex5/v5product_table.pdf.

[35]

Yang, Y.-S., Sinha, S., Veneris, A., and Brayton, R. 2007. Automating logic rectification by approximate SPFDs. In Proceedings of the Asia South Pacific Design Automation Conference (ASP-DAC'07).

Digital Library

[36]

Zhu, Q., Kitchen, N., Kuehlmann, A., and Sangiovanni-Vincentelli, A. L. 2006. SAT sweeping with local observability don't-cares. In Proceedings of the Design Automation Conference (DAC'06). 229--234.

Digital Library

Cited By

Barkalov ATitarenko LBieganowski JKrzywicki K(2024)Basic Approaches for Reducing Power Consumption in Finite State Machine Circuits—A ReviewApplied Sciences10.3390/app1407269314:7(2693)Online publication date: 22-Mar-2024
https://doi.org/10.3390/app14072693
Sun YLiu TWong MYoung EDe V(2024)Massively Parallel AIG ResubstitutionProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3655987(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3655987
Hien BWalter MWille R(2024)Reducing Wire Crossings in Field-Coupled Nanotechnologies2024 IEEE 24th International Conference on Nanotechnology (NANO)10.1109/NANO61778.2024.10628717(155-160)Online publication date: 8-Jul-2024
https://doi.org/10.1109/NANO61778.2024.10628717
Show More Cited By

Index Terms

Scalable don't-care-based logic optimization and resynthesis
1. Hardware
  1. Electronic design automation
    1. Logic synthesis
      1. Circuit optimization
  2. Very large scale integration design
    1. Application-specific VLSI designs

Recommendations

Scalable don't-care-based logic optimization and resynthesis
FPGA '09: Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays

We describe an optimization method for combinational and sequential logic networks, with emphasis on scalability and the scope of optimization. The proposed resynthesis (a) is capable of substantial logic restructuring, (b) is customizable to solve a ...
Technology Mapping of Speed-Independent Circuits Based on Combinational Decomposition and Resynthesis
EDTC '97: Proceedings of the 1997 European conference on Design and Test

This paper presents a solution to the problem of sequential multi-level logic synthesis of asynchronous speed-independent circuits. The starting point is a technology-independent speed-independent circuit obtained using, e.g., the monotonous cover ...
FPGA area reduction by multi-output function based sequential resynthesis
DAC '08: Proceedings of the 45th annual Design Automation Conference

We propose a new resynthesis algorithm for FPGA area reduction. In contrast to existing resynthesis techniques, which consider only single-output Boolean functions and the combinational portion of a circuit, we consider multi-output functions and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Reconfigurable Technology and Systems

ACM Transactions on Reconfigurable Technology and Systems Volume 4, Issue 4

December 2011

179 pages

ISSN:1936-7406

EISSN:1936-7414

DOI:10.1145/2068716

Issue’s Table of Contents

Copyright © 2011 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 December 2011

Accepted: 01 November 2010

Revised: 01 August 2009

Received: 01 May 2009

Published in TRETS Volume 4, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
562
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)14

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Barkalov ATitarenko LBieganowski JKrzywicki K(2024)Basic Approaches for Reducing Power Consumption in Finite State Machine Circuits—A ReviewApplied Sciences10.3390/app1407269314:7(2693)Online publication date: 22-Mar-2024
https://doi.org/10.3390/app14072693
Sun YLiu TWong MYoung EDe V(2024)Massively Parallel AIG ResubstitutionProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3655987(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3655987
Hien BWalter MWille R(2024)Reducing Wire Crossings in Field-Coupled Nanotechnologies2024 IEEE 24th International Conference on Nanotechnology (NANO)10.1109/NANO61778.2024.10628717(155-160)Online publication date: 8-Jul-2024
https://doi.org/10.1109/NANO61778.2024.10628717
Zhu JPan HChu Z(2024)Multiplication Complexity Optimization based on Quantified Boolean Formulas2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617946(332-336)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617946
Cai YYang ZNi LLiu JXie BLi X(2024)Parallel AIG Refactoring via Conflict Breaking2024 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS58744.2024.10558523(1-5)Online publication date: 19-May-2024
https://doi.org/10.1109/ISCAS58744.2024.10558523
Barkalov ATitarenko LMazurkiewicz MKrzywicki K(2023)Improving the Spatial Characteristics of Three-Level LUT-Based Mealy FSM CircuitsElectronics10.3390/electronics1205113312:5(1133)Online publication date: 26-Feb-2023
https://doi.org/10.3390/electronics12051133
Barkalov ATitarenko LKrzywicki KSaburova S(2023)Improving Characteristics of FPGA-Based FSMs Representing Sequential Blocks of Cyber-Physical SystemsApplied Sciences10.3390/app13181020013:18(10200)Online publication date: 11-Sep-2023
https://doi.org/10.3390/app131810200
Reichl FSlivovsky FSzeider SWilliams BChen YNeville J(2023)Circuit minimization with QBF-based exact synthesisProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i4.25524(4087-4094)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i4.25524
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: Nov-2023
https://doi.org/10.1109/TCAD.2023.3256341
Rai SCalvino ARiener HDe Micheli GKumar A(2023)Utilizing XMG-Based Synthesis to Preserve Self-Duality for RFET-Based CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.318463342:3(914-927)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1109/TCAD.2022.3184633
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents