4C: Logic Synthesis


4C-1
Title Automating Logic Rectification by Approximate SPFDs
Author *Yu-Shen Yang (University of Toronto, Canada), Subarna Sinha (Synopsys, United States), Andreas Veneris (University of Toronto, Canada), Robert Brayton (University of California, United States)
Abstract In the digital VLSI cycle, a netlist is often modified to correct design errors, perform small specification changes or implement incremental rewiring-based optimization operations. Most existing automated logic rectification tools use a small set of predefined logic transformations when they perform such modifications. This paper first shows that a small set of predefined transformations may not allow rectification to exploit the full potential of the design. Then, it proposes an automated simulation-based methodology to ``approximate'' Sets of Pairs of Functions to be Distinguished (SPFDs) and avoid the memory/time explosion problem. This representation is used by a SAT-based algorithm that devises appropriate logic transformations to fix a design. The SAT method is later complemented by a greedy one that improves on run-time performance. An extensive suite of experiments documents the added potential of the proposed rectification methodology.
Slides (pdf file) 4C-1

4C-2
Title BddCut: Towards Scalable Symbolic Cut Enumeration
Author *Andrew Chaang Ling, Jianwen Zhu (University of Toronto, Canada), Stephen Dean Brown (Altera Toronto Technology Centre, Canada)
Abstract While the covering algorithm has been perfected recently by the iterative approaches, such as DAOmap and IMap, its application has been limited to technology mapping. The main factor preventing the covering problem's migration to other logic transformations, such as elimination and resynthesis region identification found in SIS and FBDD, is the exponential number of alternative cuts that have to be evaluated. Traditional methods of cut generation do not scale beyond a cut size of 6. In this paper, a symbolic method that can enumerate all cuts is proposed without any pruning, up to a cut size of 10. We show that it can outperform traditional methods by an order of magnitude and, as a result, scales to 100K gate benchmarks. As a practical driver, the covering problem applied to elimination is shown where it can not only produce competitive area, but also provide more than 6x average runtime reduction of the total runtime in FBDD, a BDD based logic synthesis tool with a reported order of magnitude faster runtime than SIS and commercial tools with negligible impact on area.
Slides (pdf file) 4C-2

4C-3
Title Node Mergers in the Presence of Don't Cares
Author *Stephen Plaza, Kai-hui Chang, Igor Markov, Valeria Bertacco (University of Michigan, United States)
Abstract SAT sweeping is the process of merging two or more functionally equivalent nodes in a circuit by selecting one of them to represent all the other equivalent nodes. This provides significant advantages in synthesis by reducing circuit size and provides additional flexibility in technology mapping, which could be crucial in post-synthesis optimizations. Furthermore, it is also critical in verification because it can reduce the complexity of the netlist to be analyzed in equivalence checking. Most algorithms available so far for this goal do not exploit observability don't cares (ODCs) for node merging since nodes equivalent up to ODCs do not form an equivalence relation. Although a few recently proposed solutions can exploit ODCs by overcoming this limitation, they constrain their analysis to just a few levels of surrounding logic to avoid prohibitive runtime. We develop an ODC-based node merging algorithm that performs efficient global ODC analysis (considering the entire netlist) through simulation and SAT. Our contributions which enable global ODC-based optimizations are: (1) a fast ODC-aware simulator and (2) an incremental verification strategy that limits computational complexity. In addition, our technique operates on arbitrarily mapped netlists, allowing for powerful post-synthesis optimizations. We show that global ODC analysis discovers on average 25% more (and up to 60%) node-merging opportunities than current state-of-the-art solutions based on local ODC analysis.
Slides (pdf file) 4C-3

4C-4
Title Synthesis of Reversible Sequential Elements
Author Min-Lung Chuang, *Chun-Yao Wang (National Tsing Hua University, Taiwan)
Abstract To construct a reversible sequential circuit, reversible sequential elements are required. This work presents novel designs of reversible sequential elements such as D latch, JK latch, and T latch. Based on these reversible latches, we also construct the designs of the corresponding flip-flops. Then, we further discuss the physical implementations of our designs based on classical MOS electronics. Comparing with previous work, the implementation cost of our new designs, including the number of gates and the number of garbage outputs is considerably reduced.
Slides (pdf file) 4C-4

4C-5
Title Recognition of Fanout-free Functions
Author Tsung-Lin Lee, *Chun-Yao Wang (National Tsing Hua University, Taiwan)
Abstract Factoring is a logic minimization technique to represent a Boolean function in an equivalent function with minimum literals. When realizing the circuit, a function represented in a more compact form has smaller area. Some Boolean functions even have equivalent forms where each variable appears exactly once, which are known as fanout-free functions. John P. Hayes had devised an algorithm to determine if a function can be fanout-free and construct the circuit if fanout-free realization exists. In this paper, we propose a property and an efficient technique to accelerate this algorithm. With our improvements, execution time of this algorithm is more competitive with the state-of-the-art method.
Slides (pdf file) 4C-5
Last Updated on: January 29, 2007