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

Article

Free access

BDS: a BDD-based logic optimization system

Authors:

Congguang Yang,

Maciej Ciesielski,

Vigyan SinghalAuthors Info & Claims

DAC '00: Proceedings of the 37th Annual Design Automation Conference

Pages 92 - 97

https://doi.org/10.1145/337292.337323

Published: 01 June 2000 Publication History

Abstract

This paper describes a new BDD-based logic optimization system, BDS. It is based on a recently developed theory for BDD-based logic decomposition, which supports both algebraic and Boolean factorization. New techniques, which are crucial to the manipulation of BDDs in a partitioned Boolean network environment, are described in detail. The experimental results show that BDS has a capability to handle very large circuits. It offers a superior runtime advantage over SIS, with comparable results in terms of circuit area and often improved delay.

References

[1]

R. Rudell, "Tutorial : Design of a logic synthesis system," in Proc. 33rd Design Automation Conference, 1996, pp. 191-196.

Digital Library

[2]

S.B. Akers, "Functional Testing with Binary Decision Diagrams," in Eighth Annual Conference on Fault- Tolerant Computing, 1978, pp. 75-82.

[3]

Randal E. Bryant, "Graph-Based Algorithms for Boolean Function Manipulation," IEEE Trans. on Computer, vol. 35, no. 8, pp. 677-691, August 1986.

Digital Library

[4]

K. Brace, R. Rudell, and R. Bryant, "Efficient Implementation of a BDD Package," in Proc. Design Automation Conference, 1990, pp. 40-45.

Digital Library

[5]

Yung-Te Lai, Kuo-Rueih Pan, and Massoud Pedram, "OBDD-Based Function Decomposition: Algorithms and Implementattion," IEEE Trans. on CAD, vol. 15, no. 8, pp. 977-990, August 1996.

Digital Library

[6]

Shih-Chieh Chang, M. Marek-Sadowska, and T. Hwang, "Technology Mapping for TLU FPGA's Based on Decomposition of Binary Decision Diagrams," IEEE Trans. on CAD, vol. 15, no. 10, pp. 1226-1235, October 1996.

Digital Library

[7]

Jason Cong and Yuzheng Ding, "Beyond the Combinational Limit in Depth Minimization for LUT- Based FPGA Designs," in IEEE International Conference on Computer-Aided Design, 1993, pp. 110-114.

Digital Library

[8]

K. Yano, Y. Sasaki, K. Rikino, and K. Seki, "Top-Down Pass Transistor Logic Design," IEEE J. Solid-State Circuits, vol. 31, no. 6, pp. 792~803, June 1996.

[9]

P. Buch, A. Narayan, R. Newton, and A. Sangiovanni-Vincentelli, "On Synthesizing Pass Transistor Logic," in Intl. Workshop on Logic Synthesis, 1997.

[10]

R. Chaudhry, T. Liu, A. Aziz, and J. Burns, "Area-Oriented Synthesis for Pass-Transistor Logic," in International Conference on Computer Design, 1998, pp. 160-167.

Digital Library

[11]

Kevin Karplus, "Using if-then-else DAGs for Multi-Level Logic Minimization," Tech. Rep. UCSC-CRL- 88-29, University of California Santa Cruz, 1988.

Digital Library

[12]

V. Bertacco and M. Damiani, "The Disjunctive Decomposition of Logic Functions," in IEEE International Conference on Computer-Aided Design, 1997, pp. 78~82.

Digital Library

[13]

Ted Stanion and Carl Sechen, "Boolean Division and Factorization Using Binary Decision Diagrams," IEEE Trans. on CAD, vol. 13, no. 9, pp. 1179-1184, September 1994.

Digital Library

[14]

S. Minato, "Fast Factorization Method for Implicit Cube Set Representation," IEEE Trans. on CAD, vol. 15, no. 4, pp. 377-384, April 1996.

Digital Library

[15]

M.A. Thornton and V. S. S. Nair, "Behavioral Synthesis of Combinational Logic Using Spectral Based Heuristics," ACM Transactions on Design Automation of Electronic Systems, vol. 4, no. 2, pp. 219-230, April 1999.

Digital Library

[16]

S. Yamashita, K. Yano, Y. Sasaki, Y. Akita, H Chikata, K. Rikino, and K Seki, "Pass-Transistor/CMOS Collaborated Logic: The Best of Both Worlds," in Symposium on VLSI Circuits Digest of Technical Papers, 1997, pp. 31-32.

[17]

C. Yang and M. Ciesielski, "Synthesis for Mixed CMOS/PTL Logic: Preliminary Results," in International Workshop on Logic Synthesis, 1999.

[18]

C. Yang, V. Singhal, and M. Ciesielski, "BDD Decomposition for Efficient Logic Synthesis," in International Conference on Computer Design, 1999, pp. 626-631.

Digital Library

[19]

E. Sentovich et al., "SIS: A System for Sequential Circuit Synthesis," Tech. Rep. UCB/ERL M92/41, ERL, Dept. of EECS, Univ. of California, Berkeley., 1992.

[20]

http: //www. ecs. umass, edu/ece/labs/vlsicad/ciesielski, html.

Cited By

Padmavathy NJhansi KOrmila KValarmathi B(2023)Information Theoretic Heuristics to Find the Minimal SOP Expression Considering Don’t Care Using Binary Decision DiagramsCognitive Computing and Cyber Physical Systems10.1007/978-3-031-28975-0_8(86-111)Online publication date: 25-Mar-2023
https://doi.org/10.1007/978-3-031-28975-0_8
Scarabottolo IAnsaloni GConstantinides GPozzi LReda S(2020)Approximate Logic Synthesis: A SurveyProceedings of the IEEE10.1109/JPROC.2020.3014430108:12(2195-2213)Online publication date: Dec-2020
https://doi.org/10.1109/JPROC.2020.3014430
Ubar RJurimagi LAdekoya AJenihhin M(2019)True Path Tracing in Structurally Synthesized BDDs for Testability Analysis of Digital Circuits2019 22nd Euromicro Conference on Digital System Design (DSD)10.1109/DSD.2019.00077(492-499)Online publication date: Aug-2019
https://doi.org/10.1109/DSD.2019.00077
Show More Cited By

Index Terms

BDS: a BDD-based logic optimization system
1. Applied computing
  1. Physical sciences and engineering
    1. Engineering
2. Hardware

Recommendations

BDS-MAJ: a BDD-based logic synthesis tool exploiting majority logic decomposition
DAC '13: Proceedings of the 50th Annual Design Automation Conference

Despite the impressive advance of logic synthesis during the past decades, a general methodology capable of efficiently synthesizing both control and datapath logic is still missing. Indeed, while synthesis techniques for random control logic (AND/OR-...
BDS: a BDD-based logic optimization system

This paper describes a novel logic decomposition theory and a practical logic synthesis system, BDS. It is based on a new binary decision diagrams (BDD) decomposition technique which supports all types of decomposition structures, including AND, OR, XOR,...
Performance of BDS-3: satellite visibility and dilution of precision

We describe a method to assess the performance of the third-generation BeiDou navigation satellite system (BDS-3), in terms of satellite visibility and dilution of precision (DOP), on global and regional scales. Different from traditional methods, this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '00: Proceedings of the 37th Annual Design Automation Conference

June 2000

819 pages

ISBN:1581131879

DOI:10.1145/337292

Chairman:
Giovanni De Micheli
Stanford Univ., Stanford, CA

Copyright © 2000 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

EDAC: Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC00

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC00: ACM/IEEE-CAS/EDAC Design Automation Conference

June 5 - 9, 2000

California, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
939
Total Downloads

Downloads (Last 12 months)272
Downloads (Last 6 weeks)60

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Padmavathy NJhansi KOrmila KValarmathi B(2023)Information Theoretic Heuristics to Find the Minimal SOP Expression Considering Don’t Care Using Binary Decision DiagramsCognitive Computing and Cyber Physical Systems10.1007/978-3-031-28975-0_8(86-111)Online publication date: 25-Mar-2023
https://doi.org/10.1007/978-3-031-28975-0_8
Scarabottolo IAnsaloni GConstantinides GPozzi LReda S(2020)Approximate Logic Synthesis: A SurveyProceedings of the IEEE10.1109/JPROC.2020.3014430108:12(2195-2213)Online publication date: Dec-2020
https://doi.org/10.1109/JPROC.2020.3014430
Ubar RJurimagi LAdekoya AJenihhin M(2019)True Path Tracing in Structurally Synthesized BDDs for Testability Analysis of Digital Circuits2019 22nd Euromicro Conference on Digital System Design (DSD)10.1109/DSD.2019.00077(492-499)Online publication date: Aug-2019
https://doi.org/10.1109/DSD.2019.00077
Hutton MBetz VAnderson J(2016)FPGA Synthesis and Physical DesignElectronic Design Automation for IC Implementation, Circuit Design, and Process Technology10.1201/b19714-18(373-413)Online publication date: 14-Apr-2016
https://doi.org/10.1201/b19714-18
Monor C(2015)Logic synthesis method for combinatorial blocks using a FPGA-like basic cell structure2015 19th International Conference on System Theory, Control and Computing (ICSTCC)10.1109/ICSTCC.2015.7321347(526-532)Online publication date: Oct-2015
https://doi.org/10.1109/ICSTCC.2015.7321347
Arora HBanerjee AJidge R(2013)A novel algorithmic approach for logic synthesis engine design2013 International Mutli-Conference on Automation, Computing, Communication, Control and Compressed Sensing (iMac4s)10.1109/iMac4s.2013.6526513(785-790)Online publication date: Mar-2013
https://doi.org/10.1109/iMac4s.2013.6526513
Condrat CKalla PBlair SAtienza DXie YAyala JStevens K(2011)Logic synthesis for integrated opticsProceedings of the 21st edition of the great lakes symposium on Great lakes symposium on VLSI10.1145/1973009.1973013(13-18)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.1145/1973009.1973013
Fiser PSchmidt JVasicek ZSekanina L(2010)On logic synthesis of conventionally hard to synthesize circuits using genetic programming13th IEEE Symposium on Design and Diagnostics of Electronic Circuits and Systems10.1109/DDECS.2010.5491755(346-351)Online publication date: Apr-2010
https://doi.org/10.1109/DDECS.2010.5491755
Brayton RMishchenko A(2010)ABCProceedings of the 22nd international conference on Computer Aided Verification10.1007/978-3-642-14295-6_5(24-40)Online publication date: 15-Jul-2010
https://dl.acm.org/doi/10.1007/978-3-642-14295-6_5
Kravets VMishchenko A(2010)Sequential Logic Synthesis Using Symbolic Bi-decompositionAdvanced Techniques in Logic Synthesis, Optimizations and Applications10.1007/978-1-4419-7518-8_3(31-45)Online publication date: 11-Nov-2010
https://doi.org/10.1007/978-1-4419-7518-8_3
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents