Effect of Constant One and Zero, Shared and Non-decomposed Nodes on Runtime and Graph Size of the Shannon Factor Graph (SFG)

Reddy, B K and Sabbavarapu, S and Acharyya, Amit (2014) Effect of Constant One and Zero, Shared and Non-decomposed Nodes on Runtime and Graph Size of the Shannon Factor Graph (SFG). In: Fifth International Symposium on Electronic System Design (ISED), 15-17 Dec, 2014, Surathkal.

[img]
Preview
Text
2066_raiith_ieee_07172762.pdf - Published Version

Download (183kB) | Preview

Abstract

In this paper, we propose two different algorithms for Shannon Factor Graph (SFG) construction, which can be used for cut-less mapping, to improve the runtime, graph size and required memory size. The first SFG construction algorithm does not consider the nature of the nodes (constant one and zero, non-decomposed and shared nodes) while building the SFG, whereas the second algorithm finds out the nature of the nodes on-the-fly. We observed that the constant one and zero, Shared and non-decomposed nodes can be used at the time of SFG construction to minimize the runtime and graph size significantly and to make the graph semi-canonical. The theoretical analysis and experiments performed on the standard benchmark circuits show that, by finding the constant one and zero, shared and non-decomposed nodes on-the-fly reduces the graph size by a factor of 126 and the runtime by a factor of 5.5.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Acharyya, Amithttp://orcid.org/0000-0002-5636-0676
Item Type: Conference or Workshop Item (Paper)
Additional Information: We thank Dr. Alan Mischenko, UC Berkeley for helping in harvesting the Boolean equations from the benchmark circuits.
Uncontrolled Keywords: Cut-based technology mapping, Cut-enumeration, Cut-less technology mapping, Logic Synthesis, Shannon decomposition theorem
Subjects: Others > Electricity
Others > Engineering technology
Divisions: Department of Electrical Engineering
Depositing User: Team Library
Date Deposited: 04 Dec 2015 06:17
Last Modified: 29 Aug 2017 11:08
URI: http://raiith.iith.ac.in/id/eprint/2066
Publisher URL: https://doi.org/10.1109/ISED.2014.35
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 2066 Statistics for this ePrint Item