research-article

Canonicalization of Threshold Logic Representation and Its Applications

Authors:

Jie-Hong R. JiangAuthors Info & Claims

2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

Pages 1 - 8

https://doi.org/10.1145/3240765.3240785

Published: 05 November 2018 Publication History

Abstract

Threshold logic functions gain revived attention due to their connection to neural networks employed in deep learning. Despite prior endeavors in the characterization of threshold logic functions, to the best of our knowledge, the quest for a canonical representation of threshold logic functions in the form of their realizing linear inequalities remains open. In this paper we devise a procedure to canonicalize a threshold logic function such that two threshold logic functions are equivalent if and only if their canonicalized linear inequalities are the same. We further strengthen the canonicity to ensure that symmetric variables of a threshold logic function receive the same weight in the canonicalized linear inequality. The canonicalization procedure invokes <tex>$O(m)$</tex> queries to a linear programming (resp. an integer linear programming) solver when a linear inequality solution with fractional (resp. integral) weight and threshold values is to be found, where <tex>$m$</tex> is the number of symmetry groups of the given threshold logic function. The guaranteed canonicity allows direct application to the classification of NP (input negation, input permutation) and NPN (input negation, input permutation, output negation) equivalence of threshold logic functions. It may thus enable applications such as equivalence checking, Boolean matching, and library construction for threshold circuit synthesis.

References

[1]

A library of canonically represented threshold logic functions. https://github.com/NTU-ALComLab/TLCanonicalLib

[2]

M. Berkelaar, K. Eikland, and P. Notebaert. lpsolve: Open Source (Mixed-Integer) Linear Programming System. Eindhoven University of Technology, 2004.

[3]

Berkeley Logic Synthesis and Verification Group. ABC: A System for Sequential Synthesis and Verification. http://www.eecs.berkeley.edu/~alanmi/abc/

[4]

V. Beiu, J. Quintana, and M. Avedillo. VLSI Implementations of Threshold Logic– A Comprehensive Survey. IEEE Trans. Neural Netw., 14 (5): 1217–1243, 2003.

Digital Library

[5]

C.-K. Chow. On the Characterization of Threshold Functions. In Proc. SWCT, pp. 34–38, 1961.

[6]

L. Gao, F. Alibart, and D. Strukov. Programmable CMOS/Memristor Threshold Logic. IEEE Trans. on Nanotechnology, 12 (2): 115–119, 2013.

Digital Library

[7]

T. Gowda et al., Synthesis of Threshold Logic Circuits using Tree Matching. In Proc. ECCTD, pp. 850–853, 2007.

[8]

T. Gowda, S. Vrudhula, and G. Konjevod. Combinational Equivalence Checking for Threshold Logic Circuits. In Proc. GLSVLSI, pp. 102–107, 2007.

[9]

G.-B. Huang, et al. Can Threshold Networks Be Trained Directly? IEEE Trans. on Circuits and Systems II: Express Briefs, 53 (3): 187–191, 2006.

[10]

H. Hulgaard, P. Williams, and H. Andersen. Equivalence Checking of Combinational Circuits using Boolean Expression Diagrams. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst, 18 (7): 903–917, 1999.

Digital Library

[11]

A. Krizhevsky, I. Sutskever, and G. Hinton. Imagenet Classification with Deep Convolutional Neural Networks. In Proc. NIPS, pp. 1097–1105, 2012.

[12]

N.-Z. Lee, et al. Analytic Approaches to the Collapse Operation and Equivalence Verification of Threshold Logic Circuits. In Proc. ICCAD, pp 30–37, 2016.

[13]

R. Lippmann. An Introduction to Computing with Neural Nets. IEEE ASSP Magazine, 4 (2): 4–22, 1987.

[14]

P. Merolla et al., A Million Spiking-neuron Integrated Circuit with A Scalable Communication Network and Interface. Science, 345 (6197): 668–673, 2014.

[15]

S. Muroga, I. Toda, and S. Takasu. Theory of Majority Decision Elements. J. of the Franklin Institute, 271 (5): 376–418, 1961.

[16]

S. Muroga, I. Toda, and M. Kondo. Majority Decision Functions of up to Six Variables. Mathematics of Computation, 16 (80): 459–472, 1962.

[17]

S. Muroga, T. Tsuboi, and C. Baugh. Enumeration of Threshold Functions of Eight Variables. IEEE Trans. on Computers, 100 (9): 818–825, 1970.

[18]

S. Muroga. Threshold Logic and its Applications. New York: Wiley-Interscience, 1971.

[19]

A. Neutzling et al., Threshold Logic Synthesis Based on Cut Pruning. In Proc. ICCAD, pp. 494–499, 2015.

[20]

N. Nukala, N. Kulkarni, and S. Vrudhula. Spintronic Threshold Logic Array (STLA) – A Compact, Low Leakage, Non-volatile Gate Array Architecture. J. of Parallel and Distributed Computing, 74 (6): 2452–2460, 2014.

[21]

A. Palaniswamy and S. Tragoudas. Improved Threshold Logic Synthesis using Implicant-Implicit Algorithms. ACM J. on Emerging Technologies in Computing Systems, 10 (3): 21 (1)–21 (32), 2014.

[22]

S. Panda, F. Somenzi, and B. Plessier. Symmetry Detection and Dynamic Variable Ordering of Decision Diagrams. In Proc. ICCAD, pp. 628–631, 1994.

[23]

R. Schalkoff. Artificial Neural Networks, Vol. 1, New York: McGraw-Hill, 1997.

Digital Library

[24]

F. Somenzi. CUDD: CU Decision Diagram Package Release 3.0.0. University of Colorado at Boulder, 2015.

[25]

J. Subirats, J. Jerez, and L. Franco. A New Decomposition Algorithm for Threshold Synthesis and Generalization of Boolean Functions. IEEE Trans. on Circuits and Systems I: Regular Papers, 55 (10): 3188–3196, 2008.

[26]

R. Winder. Enumeration of Seven-Argument Threshold Functions. IEEE Trans. on Electronic Computers, 3: 315–325, 1965.

[27]

B. Yegnanarayana. Artificial Neural Networks, PHI Learning Pvt. Ltd, 2009.

[28]

R. Zhang et al., Synthesis and Optimization of Threshold Logic Networks with Application to Nanotechnologies. In Proc. DATE, pp. 904–909, 2004.

[29]

Y. Zheng, M. Hsiao, and C. Huang. SAT-based Equivalence Checking of Threshold Logic Designs for Nanotechnologies. In Proc. GLSVLSI, pp. 225–230, 2008.

Cited By

Bruun SLioma CMaistro M(2023)Recommending Target Actions Outside Sessions in the Data-poor Insurance DomainACM Transactions on Recommender Systems10.1145/3606950Online publication date: 30-Jun-2023
https://dl.acm.org/doi/10.1145/3606950
Dias MLopes C(2023)Optimization of Image Processing Algorithms for Character Recognition in Cultural Typewritten DocumentsJournal on Computing and Cultural Heritage 10.1145/360670516:4(1-25)Online publication date: 16-Nov-2023
https://dl.acm.org/doi/10.1145/3606705
Li MYen YLi YChen YWang C(2023)A Constructive Approach for Threshold Function IdentificationACM Transactions on Design Automation of Electronic Systems10.1145/360637128:5(1-19)Online publication date: 9-Sep-2023
https://dl.acm.org/doi/10.1145/3606371
Show More Cited By

Index Terms

Canonicalization of Threshold Logic Representation and Its Applications
1. Hardware
  1. Electronic design automation
  2. Integrated circuits
2. Theory of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

Nov 2018

939 pages

Copyright © 2018.

Publisher

IEEE Press

Publication History

Published: 05 November 2018

Permissions

Request permissions for this article.

Request Permissions

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
89
Total Downloads

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

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bruun SLioma CMaistro M(2023)Recommending Target Actions Outside Sessions in the Data-poor Insurance DomainACM Transactions on Recommender Systems10.1145/3606950Online publication date: 30-Jun-2023
https://dl.acm.org/doi/10.1145/3606950
Dias MLopes C(2023)Optimization of Image Processing Algorithms for Character Recognition in Cultural Typewritten DocumentsJournal on Computing and Cultural Heritage 10.1145/360670516:4(1-25)Online publication date: 16-Nov-2023
https://dl.acm.org/doi/10.1145/3606705
Li MYen YLi YChen YWang C(2023)A Constructive Approach for Threshold Function IdentificationACM Transactions on Design Automation of Electronic Systems10.1145/360637128:5(1-19)Online publication date: 9-Sep-2023
https://dl.acm.org/doi/10.1145/3606371
Mujahid MKanwal KRustam FAljedaani WAshraf I(2023)Arabic ChatGPT Tweets Classification Using RoBERTa and BERT Ensemble ModelACM Transactions on Asian and Low-Resource Language Information Processing10.1145/360588922:8(1-23)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.1145/3605889
Le Tolguenec PRachelson EBesse YWilson D(2023)Curiosity Creates Diversity in Policy SearchACM Transactions on Evolutionary Learning and Optimization10.1145/36057823:3(1-20)Online publication date: 20-Sep-2023
https://dl.acm.org/doi/10.1145/3605782
Sarkar MTaki GChakraborty RAgasti UGayen S(2023)Design and Performance Analysis of Dynamic and Hybrid CMOS Threshold Logic Based Full Adder Circuit2023 8th International Conference on Computers and Devices for Communication (CODEC)10.1109/CODEC60112.2023.10465873(1-2)Online publication date: 14-Dec-2023
https://doi.org/10.1109/CODEC60112.2023.10465873
Lee NJiang J(2021)Constraint Solving for Synthesis and Verification of Threshold Logic CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.301544140:5(904-917)Online publication date: May-2021
https://doi.org/10.1109/TCAD.2020.3015441
Hsu WLin CLi YChen YWang C(2021)On Reduction of Computations for Threshold Function Identification2021 IEEE 34th International System-on-Chip Conference (SOCC)10.1109/SOCC52499.2021.9739224(146-151)Online publication date: 14-Sep-2021
https://doi.org/10.1109/SOCC52499.2021.9739224
Zhang JNi LZheng SLiu HZou XWang FLuo G(2021)Enhanced Fast Boolean Matching based on Sensitivity Signatures Pruning2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD)10.1109/ICCAD51958.2021.9643587(1-9)Online publication date: 1-Nov-2021
https://doi.org/10.1109/ICCAD51958.2021.9643587
Sarkar MTaki G(2021)Performance Analysis of Full Adder Circuits Using Different Static CMOS Based Threshold Logic Gate2021 Devices for Integrated Circuit (DevIC)10.1109/DevIC50843.2021.9455809(521-524)Online publication date: 19-May-2021
https://doi.org/10.1109/DevIC50843.2021.9455809
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten