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.

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: