Fast Detection of Node Mergers Using Logic Implications
In this paper, we propose a new node merging algorithm using logic implications. The proposed algorithm only requires two logic implications to find the substitute nodes for a given target node, and thus can efficiently detect node mergers. Furthermore, we also apply the node merger identification algorithm for area optimization in VLSI circuits. We conduct experiments on a set of IWLS 2005 benchmarks. The experimental results show that our algorithm has a competitive capability on area optimization compared to a global observability don’t care (ODC)- based node merging algorithm which is highly time-consuming. Our speedup is approximately 86 times for overall benchmarks.
Node merging is a popular and eficient logic restructuring technique. It replaces a node with another node by rewiring, and then removes the replaced node without changing the overall functionality of the circuit. A major application of the technique is to reduce the size of a logic circuit. As two nodes are merged, one of them can be removed from the circuit, and this merger may cause other redundancies in the circuit such that the resultant circuit is minimized. Circuit minimization also can be a pre-process before performing equivalence checking [3]. SAT sweeping [7] is a method that merges two functionally equivalent nodes. Firstly, it simulates the circuit by applying a set of random patterns. Next, node merger candidates are derived by searching two nodes that have the same simulation values. Finally, it uses a SAT solver to check if the nodes are actually equivalent. However, functional equivalence is not a necessary condition for node merging. In fact, if the functional differences of two nodes are never observed at any primary output (PO), these two nodes can be merged as well. Based on this observation, a node merging algorithm under local observability don’t cares (ODCs) is proposed in [16]. The algorithm can identify additional node mergers that are not functionally equivalent to each other. The local ODC-based algorithm [16] extends the SAT sweeping method by performing ODC analysis when deriving candidate node mergers. According to the simulation results, it computes the observability of each node and collects the pairs of nodes whose differences are not observable as candidates. Since full observability computation is very time-consuming, however, the method sets a k-bounded depth to extract local ODCs. With larger values of k, the method can identify more node mergers but spends more CPU time. To enhance the local ODC-based algorithm, the work in [11] proposes a node merging algorithm under global ODCs using the SAT sweeping technique as well. To reduce the complexity of full observability computation, the method computes approximate observability for each node instead of bounded-depth observability. Although the method detects certain node mergers that cannot be identified by the local ODC-based algorithm, it potentially misses some other node mergers as well. Additionally, since the approximate observability computation is global, the method expends a great amount of CPU time for large circuits. Recently, a similar algorithm that merges nodes while considering sequential ODCs is proposed in [4]. It also employs SAT sweeping to identify node mergers under sequential ODCs for sequential circuit optimization. Although both the works in [16] and [11] propose methods to decrease the complexity of observability computation, they cannot avoid performing ODC analysis in searching for a node merger. Additionally, they need to simulate a large amount of random patterns, collect candidate node mergers, and then perform SAT solving. This procedure can be very time-consuming due to a large number of SAT solving calls when the number of candidates is enormous.
Free download research paper
CSE PROJECTS