Article

Recursive bipartitioning of BDDs for performance driven synthesis of pass transistor logic circuits

Authors:

Rupesh S. Shelar,

Sachin S. SapatnekarAuthors Info & Claims

ICCAD '01: Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design

Pages 449 - 452

Published: 04 November 2001 Publication History

Get Access

Abstract

In this paper, we address the problem of performance oriented synthesis of pass transistor logic (PTL) circuits using a binary decision diagram (BDD) decomposition technique. We transform the BDD decomposition problem into a recursive bipartitioning problem and solve the latter using a max-flow min-cut technique. We use the area and delay cost of the PTL implementation of the logic function to guide the bipartitioning scheme. Using recursive bipartitioning and a one-hot multiplexer circuit, we show that our PTL implementation has logarithmic delay in the number of inputs, under certain assumptions. The experimental results on benchmark circuits are promising, since they show the significant delay reductions with small or no area overheads as compared to previous approaches.

References

[1]

K. Yano et al. A 3.8ns CMOS 16 × 16 multiplier using complementary pass transistor logic. IEEE Journal of Solid State Circuits, 25(2):388-395, Apr. 1990.

Crossref

Google Scholar

[2]

K. Yano, Y. Sasaki, and K. Rikino. Top-down pass-transistor logic design. IEEE Journal of Solid-State Circuits, 31(6):792-803, Jun. 1996.

Crossref

Google Scholar

[3]

P. Buch et al. Logic synthesis for large pass transistor circuits. In Proc. ICCAD, pages 663-670, Nov. 1997.

Digital Library

Google Scholar

[4]

R. Chaudhary et al. Area oriented synthesis for pass transistor logic. In Proc. ICCD, pages 160-167, Oct. 1998.

Digital Library

Google Scholar

[5]

T. Liu et al. Performance driven synthesis for pass transistor logic. In Proc. of the VLSI Design Conference, pages 372-377, Jan. 1999.

Digital Library

Google Scholar

[6]

C. Yang and M. Ciesielski. BDD decomposition for efficient logic synthesis. In Proc. ICCD, pages 626-631, Oct. 1999.

Digital Library

Google Scholar

[7]

C. Scholl and B. Becker. On the generation of multplexer circuits for pass transistor logic. In Proc. DATE, pages 372-378, Mar. 2000.

Digital Library

Google Scholar

[8]

T. H. Cormen et al. Introduction to Algorithms. Prentice-Hall India, New Delhi, 1998.

Digital Library

Google Scholar

[9]

F. Ferrandi et al. Symbolic algorithms for layout oriented synthesis of pass transistor logic circuits. In Proc. ICCAD, pages 235-241, Nov. 1998.

Digital Library

Google Scholar

[10]

A. Reis et al. The library free technology mapping problem. In Proc. IWLS, May 1997.

Google Scholar

[11]

Y. Jiang, S. S. Sapatnekar, and C. Bamji. A fast global gate collapsing technique for high performance designs using static cmos and pass transistor logic. In Proc. ICCD, pages 276-281, Oct. 1998.

Digital Library

Google Scholar

[12]

F. Somenzi. CUDD: CU Decision Diagram package, release 2.3.0. http://vlsi.colorado.edu/fabio/CUDD/.

Google Scholar

[13]

R. Rudell. Dynamic variable ordering for ordered binary decision diagrams. In Proc. DAC, pages 42-47, Jun. 1993.

Digital Library

Google Scholar

Cited By

View all

Beg AChandana Prasad P(2010)Prediction of area and length complexity measures for binary decision diagramsExpert Systems with Applications: An International Journal10.1016/j.eswa.2009.09.00337:4(2864-2873)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1016/j.eswa.2009.09.003
Schneider FRibas RSapatnekar SReis A(2005)Exact lower bound for the number of switches in series to implement a combinational logic cellProceedings of the 2005 International Conference on Computer Design10.1109/ICCD.2005.51(357-362)Online publication date: 2-Oct-2005
https://dl.acm.org/doi/10.1109/ICCD.2005.51
Shelar RSapatnekar S(2002)An Efficient Algorithm for Low Power Pass Transistor Logic SynthesisProceedings of the 2002 Asia and South Pacific Design Automation Conference10.5555/832284.835478Online publication date: 7-Jan-2002
https://dl.acm.org/doi/10.5555/832284.835478

Index Terms

Recursive bipartitioning of BDDs for performance driven synthesis of pass transistor logic circuits
1. Hardware
  1. Hardware validation
  2. Integrated circuits
    1. Logic circuits
      1. Combinational circuits

Recommendations

Logic synthesis for large pass transistor circuits
ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design

Pass transistor logic (PTL) can be a promising alternative to static CMOS for deep sub-micron design. In this work, we motivate the need for CAD algorithms for PTL circuit design and propose decomposed BDDs as a suitable logic level representation for ...
Implementation of Multiple-Valued Flip-Flips Using Pass Transistor Logic
DSD '04: Proceedings of the Digital System Design, EUROMICRO Systems

This paper presents the realization of multiple-valued flip-flops (MVFF) using Pass Transistor logic. Realization of MVFF has been discussed by many authors. The existing techniques are mainly extensions of binary flip-flops, based on CMOS or TTL logic. ...
BDD decomposition for delay oriented pass transistor logic synthesis

We address the problem of synthesizing pass transistor logic (PTL), with the specific objective of delay reduction, through binary decision diagram (BDD) decomposition. The decomposition is performed by mapping the BDD to a network flow graph, and then ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCAD '01: Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design

November 2001

656 pages

ISBN:0780372492

Conference Chair:
Rolf Ernst
Tech. Univ. of Braunschweig, Braunschweig, Germany

Publisher

IEEE Press

Publication History

Published: 04 November 2001

Check for updates

Qualifiers

Article

Conference

ICCAD01

Sponsor:

SIGDA

ICCAD01: International Conference on Computer Aided Design

November 4 - 8, 2001

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
105
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Beg AChandana Prasad P(2010)Prediction of area and length complexity measures for binary decision diagramsExpert Systems with Applications: An International Journal10.1016/j.eswa.2009.09.00337:4(2864-2873)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1016/j.eswa.2009.09.003
Schneider FRibas RSapatnekar SReis A(2005)Exact lower bound for the number of switches in series to implement a combinational logic cellProceedings of the 2005 International Conference on Computer Design10.1109/ICCD.2005.51(357-362)Online publication date: 2-Oct-2005
https://dl.acm.org/doi/10.1109/ICCD.2005.51
Shelar RSapatnekar S(2002)An Efficient Algorithm for Low Power Pass Transistor Logic SynthesisProceedings of the 2002 Asia and South Pacific Design Automation Conference10.5555/832284.835478Online publication date: 7-Jan-2002
https://dl.acm.org/doi/10.5555/832284.835478

View Options

Login options

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

Cited By

Index Terms

Recommendations

Logic synthesis for large pass transistor circuits

Implementation of Multiple-Valued Flip-Flips Using Pass Transistor Logic

BDD decomposition for delay oriented pass transistor logic synthesis