Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/1366230.1366263acmconferencesArticle/Chapter ViewAbstractPublication PagescfConference Proceedingsconference-collections
research-article

Exact combinational logic synthesis and non-standard circuit design

Published: 05 May 2008 Publication History

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.
[2]
Bryant, R. E. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers 35, 8 (1986), 677--691.
[3]
Canteaut, A., and Videau, M. Symmetric Boolean Functions. IEEE Transactions on Information Theory 51, 8 (2005), 2791--2811.
[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.
[5]
Davies, D. W. Switching functions of three variables. Trans. Inst. Radio Engineers 6, 4 (1957), 265--275.
[6]
Dietmeyer, D. L. Logic Design of Digital Systems. Allyn and Bacon, 1971.
[7]
Drechsler, R. Using Synthesis Techniques in SAT Solvers. citeseer.ist.psu.edu/drechsler04using.html.
[8]
Drechsler, R., and Gunther, W. Exact Circuit Synthesis. In International Workshop on Logic Synthesis\ (1998).
[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.
[10]
Hoover, H. J., Klawe, M. M., and Pippenger, N. Bounding Fan-out in Logical Networks. J. ACM 31, 1 (1984), 13--18.
[11]
Knuth, D. The Art of Computer Programming, Volume 4, draft, 2006. http://www-cs-faculty.stanford.edu/$\sim$/knuth/taocp.html.
[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.
[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.
[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).
[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.
[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.
[17]
Mishchenko, A., and Brayton, R. A boolean paradigm for multivalued logic synthesis. In Proc. IgVLS'02, June, 2002, pp. 173-177. (2002).
[18]
Mishchenko, A., and Sasao, T. Encoding of Boolean functions and its application to LUT cascade synthesis. In International Workshop on Logic Synthesis (2002).
[19]
Muroga, S., and Lai, H. C. Minimization of Logic Networks Under a Generalized Cost Function. IEEE Trans. Computers 25, 9 (1976), 893--907.
[20]
Oettinger, A. G., and Aiken, H. H. Retiring computer pioneer. Commun. ACM 5, 6 (1962), 298--299.
[21]
Riedel, M. Cyclic Combinational Circuits. In Ph.D. Dissertation, Caltech. (2004).
[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.
[23]
Sekanina, L. Evolutionary design of digital circuits: Where are current limits? In Stoica et al. \cite{DBLP:conf/ahs/2006}, pp. 171--178.
[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.
[25]
Shannon, C. E. Claude Elwood Shannon: collected papers. IEEE Press, Piscataway, NJ, USA, 1993.
[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).
[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.
[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.
[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.
[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.
[31]
Tarau, P., and Luderman, B. Revisiting Exact Combinational Circuit Synthesis. In Proceedings of ACM SAC'08 (Fortalezza, Brazil, Mar. 2008). to appear.
[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.

Cited By

View all
  • (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
  • (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
  • (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

Index Terms

  1. Exact combinational logic synthesis and non-standard circuit design

    Recommendations

    Reviews

    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

    cover image ACM Conferences
    CF '08: Proceedings of the 5th conference on Computing frontiers
    May 2008
    334 pages
    ISBN:9781605580777
    DOI:10.1145/1366230
    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: 05 May 2008

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. asymmetrical logic operators
    2. exact combinational circuit synthesis
    3. minimal transistor-count circuits
    4. minimal universal boolean logic libraries

    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

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)9
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (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
    • (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
    • (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

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media