research-article

Exact combinational logic synthesis and non-standard circuit design

Authors:

Paul Tarau,

Brenda LudermanAuthors Info & Claims

CF '08: Proceedings of the 5th conference on Computing frontiers

Pages 179 - 188

https://doi.org/10.1145/1366230.1366263

Published: 05 May 2008 Publication History

Get Access

Abstract

Using a new exact synthesizer that automatically induces minimal universal boolean function libraries, we introduce two indicators for comparing their expressiveness: the first based on how many gates are used to synthesize all binary operators, the second based on how many N-variable truth table values are covered by combining up to M gates from the library. By applying the indicators to an exhaustive enumeration of minimal universal libraries, two dual asymmetrical operations, Logic Implication "==" and Half XOR "<" are found to consistently outperform their symmetrical counterparts, NAND and NOR. Our expressiveness metrics bring support to the conjecture that asymmetrical operators are significantly more expressive that their well studied symmetric counterparts, omnipresent in various circuit design tools.

References

[1]

Baker, R. J. CMOS Circuit Design, Layout and Simulation. John Wiley and Sons, Hoboken, NJ, USA, 2008.

Digital Library

Google Scholar

[2]

Bryant, R. E. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers 35, 8 (1986), 677--691.

Digital Library

Google Scholar

[3]

Canteaut, A., and Videau, M. Symmetric Boolean Functions. IEEE Transactions on Information Theory 51, 8 (2005), 2791--2811.

Digital Library

Google Scholar

[4]

Culliney, J. N., Young, M. H., Nakagawa, T., and Muroga, S. Results of the Synthesis of Optimal Networks of AND and OR Gates for Four-Variable Switching Functions}. IEEE Trans. Computers 28, 1 (1979), 76--85.

Digital Library

Google Scholar

[5]

Davies, D. W. Switching functions of three variables. Trans. Inst. Radio Engineers 6, 4 (1957), 265--275.

Google Scholar

[6]

Dietmeyer, D. L. Logic Design of Digital Systems. Allyn and Bacon, 1971.

Digital Library

Google Scholar

[7]

Drechsler, R. Using Synthesis Techniques in SAT Solvers. citeseer.ist.psu.edu/drechsler04using.html.

Google Scholar

[8]

Drechsler, R., and Gunther, W. Exact Circuit Synthesis. In International Workshop on Logic Synthesis\ (1998).

Google Scholar

[9]

Grosse, D., Chen, X., Dueck, G. W., and Drechsler, R. Exact sat-based toffoli network synthesis. In ACM Great Lakes Symposium on VLSI\/ (2007), H. Zhou, E. Macii, Z. Yan, and Y. Massoud, Eds., ACM, pp. 96--101.

Digital Library

Google Scholar

[10]

Hoover, H. J., Klawe, M. M., and Pippenger, N. Bounding Fan-out in Logical Networks. J. ACM 31, 1 (1984), 13--18.

Digital Library

Google Scholar

[11]

Knuth, D. The Art of Computer Programming, Volume 4, draft, 2006. http://www-cs-faculty.stanford.edu/$\sim$/knuth/taocp.html.

Digital Library

Google Scholar

[12]

Lai, H. C., and Muroga, S. Logic Networks with a Minimum Number of NOR(NAND) Gates for Parity Functions of it Variables. IEEE Trans. Computers 36, 2 (1987), 157--166.

Digital Library

Google Scholar

[13]

Maslov, D., Dueck, G. W., and Miller, D. M. Synthesis of Fredkin-Toffoli reversible networks. IEEE Trans. VLSI Syst. 13, 6 (2005), 765--769.

Digital Library

Google Scholar

[14]

Maslov, D., Dueck, G. W., and Miller, D. M. Techniques for the synthesis of reversible Toffoli networks. ACM Trans. Design Autom. Electr. Syst. 12, 4 (2007).

Digital Library

Google Scholar

[15]

Meyer, J., and Kocan, F. Sharing of SRAM Tables Among NPN-Equivalent LUTs in SRAM-Based FPGAs. IEEE Trans. VLSI Syst. 15, 2 (2007), 182--195.

Digital Library

Google Scholar

[16]

Mira, J., and Álvarez, J. R., Eds. Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach: First International Work-Conference on the Interplay Between Natural and Artificial Computation, IWINAC 2005, Las Palmas, Canary Islands, Spain, June 15-18, 2005, Proceedings, Part II (2005), vol. 3562 of Lecture Notes in Computer Science, Springer.

Digital Library

Google Scholar

[17]

Mishchenko, A., and Brayton, R. A boolean paradigm for multivalued logic synthesis. In Proc. IgVLS'02, June, 2002, pp. 173-177. (2002).

Google Scholar

[18]

Mishchenko, A., and Sasao, T. Encoding of Boolean functions and its application to LUT cascade synthesis. In International Workshop on Logic Synthesis (2002).

Google Scholar

[19]

Muroga, S., and Lai, H. C. Minimization of Logic Networks Under a Generalized Cost Function. IEEE Trans. Computers 25, 9 (1976), 893--907.

Digital Library

Google Scholar

[20]

Oettinger, A. G., and Aiken, H. H. Retiring computer pioneer. Commun. ACM 5, 6 (1962), 298--299.

Digital Library

Google Scholar

[21]

Riedel, M. Cyclic Combinational Circuits. In Ph.D. Dissertation, Caltech. (2004).

Digital Library

Google Scholar

[22]

Sekanina, L. Evolutionary design of gate-level polymorphic digital circuits. In EvoWorkshops (2005), F. Rothlauf, J. Branke, S. Cagnoni, D. W. Corne, R. Drechsler, Y. Jin, P. Machado, E. Marchiori, J. Romero, G. D. Smith, and G. Squillero, Eds., vol. 3449 of Lecture Notes in Computer Science, Springer, pp. 185--194.

Digital Library

Google Scholar

[23]

Sekanina, L. Evolutionary design of digital circuits: Where are current limits? In Stoica et al. \cite{DBLP:conf/ahs/2006}, pp. 171--178.

Digital Library

Google Scholar

[24]

Sekanina, L., Starecek, L., Gajda, Z., and Kotásek, Z. Evolution of multifunctional combinational modules controlled by the power supply voltage. In Stoica et al. \cite{DBLP:conf/ahs/2006, pp. 186--193.

Digital Library

Google Scholar

[25]

Shannon, C. E. Claude Elwood Shannon: collected papers. IEEE Press, Piscataway, NJ, USA, 1993.

Digital Library

Google Scholar

[26]

Shende, V., Prasad, A., Markov, I., and Hayes, J. Synthesis of reversible logic circuits. In IEEE Trans. on CAD 22, pp. 710--722 (June 2003).

Digital Library

Google Scholar

[27]

Stoica, A., Arslan, T., Suess, M., Yalçin, S., Keymeulen, D., Higuchi, T., Zebulum, R. S., and Aydin, N., Eds. First NASA/ESA Conference on Adaptive Hardware and Systems (AHS 2006), 15-18 June 2006, Istanbul, Turkey (2006), IEEE Computer Society.

Google Scholar

[28]

Stoica, A., Zebulum, R. S., Keymeulen, D., and Daud, T. Transistor-level circuit experiments using evolvable hardware. In Mira and Álvarez \cite{DBLP:conf/iwinac/2005-2, pp. 366--375.

Digital Library

Google Scholar

[29]

Stoica, A., Zebulum, R. S., Keymeulen, D., Ramesham, R., Neff, J., and Katkoori, S. Temperature-adaptive circuits on reconfigurable analog arrays. In Stoica et al. \cite{DBLP:conf/ahs/2006}, pp. 28--31.

Digital Library

Google Scholar

[30]

Tarau, P., and Luderman, B. A Logic Programming Framework for Combinational Circuit Synthesis. In 23rd International Conference on Logic Programming (ICLP), LNCS 4670 (Porto, Portugal, Sept. 2007), Springer, pp. 180--194.

Digital Library

Google Scholar

[31]

Tarau, P., and Luderman, B. Revisiting Exact Combinational Circuit Synthesis. In Proceedings of ACM SAC'08 (Fortalezza, Brazil, Mar. 2008). to appear.

Digital Library

Google Scholar

[32]

Young, M. H., and Muroga, S. Symmetric Minimal Covering Problem and Minimal PLA's with Symmetric Variables. IEEE Trans. Computers 34, 6 (1985), 523--541.

Google Scholar

Cited By

View all

Tarau PLuderman BCho YGantenbein RKuo TTarokh V(2012)Symbolic modeling of a universal reconfigurable logic gate and its applications to circuit synthesisProceedings of the 2012 ACM Research in Applied Computation Symposium10.1145/2401603.2401688(389-394)Online publication date: 23-Oct-2012
https://dl.acm.org/doi/10.1145/2401603.2401688
Tarau PLuderman B(2012)Boolean Evaluation with a Pairing and Unpairing FunctionProceedings of the 2012 14th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing10.1109/SYNASC.2012.20(384-390)Online publication date: 26-Sep-2012
https://dl.acm.org/doi/10.1109/SYNASC.2012.20
Chen WRoa ELoke WJung B(2012)A 14.1-GHz dual-modulus prescaler in 130nm CMOS technology using sequential implication logic cells2012 IEEE Radio Frequency Integrated Circuits Symposium10.1109/RFIC.2012.6242295(341-344)Online publication date: Jun-2012
https://doi.org/10.1109/RFIC.2012.6242295

Index Terms

Exact combinational logic synthesis and non-standard circuit design
1. Hardware
  1. Integrated circuits
    1. Logic circuits
      1. Combinational circuits

Recommendations

Revisiting exact combinational circuit synthesis
SAC '08: Proceedings of the 2008 ACM symposium on Applied computing

The paper revisits exact combinational circuit synthesis with logic programming tools. Our focus is finding a minimal cost circuit that matches a specification - a notoriously hard nondeterministic search problem. After an exhaustive expressiveness ...
A logic programming framework for combinational circuit synthesis
ICLP'07: Proceedings of the 23rd international conference on Logic programming

Logic Programming languages and combinational circuit synthesis tools share a common "combinatorial search over logic formulae" background. This paper attempts to reconnect the two fields with a fresh look at Prolog encodings for the combinatorial ...
Reconvergence-based circuit partitioning technique for combinational and sequential logic synthesis

Reviews

Reviewer: Paparao S Kavalipati

It is a common belief among engineers that symmetric operations are better for combinational logic synthesis. The authors here suggest that asymmetrical operators {<, =>} have better expressiveness, based on experimental results using an exact algorithm. Two metrics of expressiveness are described in the paper. The first one uses the total gates required to express all 16 Boolean operations on two variables, where the set {<, =>} outperforms traditional favorites NAND/NOR. It is not clear if this metric can be generalized for the case of n variables, and whether asymmetrical operators continue to be better when the number of variables increases. The second metric takes a given number of gates and measures the number of functions expressible by them. Results presented show that libraries with a mixture of symmetric and asymmetric operations like {<, =} and {=>, ^} do better, and the conjecture on circuits built exclusively with asymmetrical operators is not obvious. NAND and NOR seem to be better for implementation, as reducing the transistor counts for {<, =>} requires pass transistor logic. More extensive validation of the models presented is required to determine if asymmetrical operators will become viable. The conclusions reached here are interesting, but the chosen metrics need better justification. The ideas presented here show promising directions for future research. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CF '08: Proceedings of the 5th conference on Computing frontiers

May 2008

334 pages

ISBN:9781605580777

DOI:10.1145/1366230

General Chair:
Alex Ramirez
UPC, Spain
,
Program Chairs:
Gianfranco Biliardi
University of Padova, Italy
,
Michael Gschwind
IBM TJ Watson Research Center, USA

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: 05 May 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CF '08

Sponsor:

CF '08: Computing Frontiers Conference

May 5 - 7, 2008

Ischia, Italy

Acceptance Rates

Overall Acceptance Rate 273 of 785 submissions, 35%

Upcoming Conference

CF '25

Sponsor:
sigmicro

22nd ACM International Conference on Computing Frontiers

May 28 - 30, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
246
Total Downloads

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

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tarau PLuderman BCho YGantenbein RKuo TTarokh V(2012)Symbolic modeling of a universal reconfigurable logic gate and its applications to circuit synthesisProceedings of the 2012 ACM Research in Applied Computation Symposium10.1145/2401603.2401688(389-394)Online publication date: 23-Oct-2012
https://dl.acm.org/doi/10.1145/2401603.2401688
Tarau PLuderman B(2012)Boolean Evaluation with a Pairing and Unpairing FunctionProceedings of the 2012 14th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing10.1109/SYNASC.2012.20(384-390)Online publication date: 26-Sep-2012
https://dl.acm.org/doi/10.1109/SYNASC.2012.20
Chen WRoa ELoke WJung B(2012)A 14.1-GHz dual-modulus prescaler in 130nm CMOS technology using sequential implication logic cells2012 IEEE Radio Frequency Integrated Circuits Symposium10.1109/RFIC.2012.6242295(341-344)Online publication date: Jun-2012
https://doi.org/10.1109/RFIC.2012.6242295

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

Revisiting exact combinational circuit synthesis

A logic programming framework for combinational circuit synthesis

Reconvergence-based circuit partitioning technique for combinational and sequential logic synthesis

Reviews

Access critical reviews of Computing literature here