Data structure manipulation for NNIG and PTNNIG: Towards a unified power and timing analysis

Rashmi Mehrotra; Ka Lok Man; Emanuel Popovici; Michel Schellekens

doi:10.1109/ICSCS.2009.5414179

Data structure manipulation for NNIG and PTNNIG: Towards a unified power and timing analysis

Rashmi Mehrotra^*, Ka Lok Man, Emanuel Popovici, Michel Schellekens

^*Corresponding author for this work

University College Cork

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

3 Citations (Scopus)

Abstract

Structural representation and technology mapping of a Boolean function is an important issue in the design of digital circuits. Various data structures such as Binary Decision Diagrams (BDDs), And Inverter Graphs (AIGs) and Nand Nor Inverter Graphs (NNIGs) have been widely used for structural representation, logic synthesis and technology mapping of digital circuits. The tool ABC has been developed for the logic synthesis and manipulation of AIGs. This paper presents a tool which builds and manipulates NNIGs as a sub-package in ABC. To the best of our understanding, it is the first tool developed for the manipulation of NNIGs. Experimental results illustrate the applicability and efficiency of the tool. The paper also presents a new data structure Probabilistic Timed Nand-Nor-Inverter Graph (PTNNIG) that can be used for accurate power estimation and timing analysis of digital circuits. Such data structures are incorporated with probability and timing as parameters and will lead to a better and combined power and timing analysis.

Original language	English
Title of host publication	3rd International Conference on Signals, Circuits and Systems, SCS 2009
DOIs	https://doi.org/10.1109/ICSCS.2009.5414179
Publication status	Published - 2009
Externally published	Yes
Event	3rd International Conference on Signals, Circuits and Systems, SCS 2009 - Medenine, Tunisia Duration: 6 Nov 2009 → 8 Nov 2009

Publication series

Name	3rd International Conference on Signals, Circuits and Systems, SCS 2009

Conference

Conference	3rd International Conference on Signals, Circuits and Systems, SCS 2009
Country/Territory	Tunisia
City	Medenine
Period	6/11/09 → 8/11/09

Keywords

ABC
AIGs
Algebraic factorisation
NNIGs
SOP

Access to Document

10.1109/ICSCS.2009.5414179

Cite this

@inproceedings{86c006c5f480414bbca0806b15d80b0a,

title = "Data structure manipulation for NNIG and PTNNIG: Towards a unified power and timing analysis",

abstract = "Structural representation and technology mapping of a Boolean function is an important issue in the design of digital circuits. Various data structures such as Binary Decision Diagrams (BDDs), And Inverter Graphs (AIGs) and Nand Nor Inverter Graphs (NNIGs) have been widely used for structural representation, logic synthesis and technology mapping of digital circuits. The tool ABC has been developed for the logic synthesis and manipulation of AIGs. This paper presents a tool which builds and manipulates NNIGs as a sub-package in ABC. To the best of our understanding, it is the first tool developed for the manipulation of NNIGs. Experimental results illustrate the applicability and efficiency of the tool. The paper also presents a new data structure Probabilistic Timed Nand-Nor-Inverter Graph (PTNNIG) that can be used for accurate power estimation and timing analysis of digital circuits. Such data structures are incorporated with probability and timing as parameters and will lead to a better and combined power and timing analysis.",

keywords = "ABC, AIGs, Algebraic factorisation, NNIGs, SOP",

author = "Rashmi Mehrotra and Man, {Ka Lok} and Emanuel Popovici and Michel Schellekens",

year = "2009",

doi = "10.1109/ICSCS.2009.5414179",

language = "English",

isbn = "9781424443987",

series = "3rd International Conference on Signals, Circuits and Systems, SCS 2009",

booktitle = "3rd International Conference on Signals, Circuits and Systems, SCS 2009",

note = "3rd International Conference on Signals, Circuits and Systems, SCS 2009 ; Conference date: 06-11-2009 Through 08-11-2009",

}

Mehrotra, R, Man, KL, Popovici, E & Schellekens, M 2009, Data structure manipulation for NNIG and PTNNIG: Towards a unified power and timing analysis. in 3rd International Conference on Signals, Circuits and Systems, SCS 2009., 5414179, 3rd International Conference on Signals, Circuits and Systems, SCS 2009, 3rd International Conference on Signals, Circuits and Systems, SCS 2009, Medenine, Tunisia, 6/11/09. https://doi.org/10.1109/ICSCS.2009.5414179

Data structure manipulation for NNIG and PTNNIG: Towards a unified power and timing analysis. / Mehrotra, Rashmi; Man, Ka Lok; Popovici, Emanuel et al.
3rd International Conference on Signals, Circuits and Systems, SCS 2009. 2009. 5414179 (3rd International Conference on Signals, Circuits and Systems, SCS 2009).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Data structure manipulation for NNIG and PTNNIG

T2 - 3rd International Conference on Signals, Circuits and Systems, SCS 2009

AU - Mehrotra, Rashmi

AU - Man, Ka Lok

AU - Popovici, Emanuel

AU - Schellekens, Michel

PY - 2009

Y1 - 2009

N2 - Structural representation and technology mapping of a Boolean function is an important issue in the design of digital circuits. Various data structures such as Binary Decision Diagrams (BDDs), And Inverter Graphs (AIGs) and Nand Nor Inverter Graphs (NNIGs) have been widely used for structural representation, logic synthesis and technology mapping of digital circuits. The tool ABC has been developed for the logic synthesis and manipulation of AIGs. This paper presents a tool which builds and manipulates NNIGs as a sub-package in ABC. To the best of our understanding, it is the first tool developed for the manipulation of NNIGs. Experimental results illustrate the applicability and efficiency of the tool. The paper also presents a new data structure Probabilistic Timed Nand-Nor-Inverter Graph (PTNNIG) that can be used for accurate power estimation and timing analysis of digital circuits. Such data structures are incorporated with probability and timing as parameters and will lead to a better and combined power and timing analysis.

AB - Structural representation and technology mapping of a Boolean function is an important issue in the design of digital circuits. Various data structures such as Binary Decision Diagrams (BDDs), And Inverter Graphs (AIGs) and Nand Nor Inverter Graphs (NNIGs) have been widely used for structural representation, logic synthesis and technology mapping of digital circuits. The tool ABC has been developed for the logic synthesis and manipulation of AIGs. This paper presents a tool which builds and manipulates NNIGs as a sub-package in ABC. To the best of our understanding, it is the first tool developed for the manipulation of NNIGs. Experimental results illustrate the applicability and efficiency of the tool. The paper also presents a new data structure Probabilistic Timed Nand-Nor-Inverter Graph (PTNNIG) that can be used for accurate power estimation and timing analysis of digital circuits. Such data structures are incorporated with probability and timing as parameters and will lead to a better and combined power and timing analysis.

KW - ABC

KW - AIGs

KW - Algebraic factorisation

KW - NNIGs

KW - SOP

UR - http://www.scopus.com/inward/record.url?scp=77951453273&partnerID=8YFLogxK

U2 - 10.1109/ICSCS.2009.5414179

DO - 10.1109/ICSCS.2009.5414179

M3 - Conference Proceeding

AN - SCOPUS:77951453273

SN - 9781424443987

T3 - 3rd International Conference on Signals, Circuits and Systems, SCS 2009

BT - 3rd International Conference on Signals, Circuits and Systems, SCS 2009

Y2 - 6 November 2009 through 8 November 2009

ER -

Data structure manipulation for NNIG and PTNNIG: Towards a unified power and timing analysis

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this