Logic Synthesis
In the logic synthesis domain, we have developed improved two-level logic
minimization techniques, efficient approximate Compatible Observability Don't Care computation
approaches, multi-node logic optimization techniques and a hierarchical don't
care computation methodology. We have also worked on a logic synthesis
approach that preserves "toggles" in a design. In addition, we have several
instances of research efforts where logic synthesis is used in
non-conventional areas such as optical networking, IP routing table
compression and Pass Transistor Logic (PTL) network synthesis.
In recent times, the cost function of logic synthesis needs to be
revisited, due to the significant impact of wiring delays.
To address this, we have have developed techniques to merge
synthesis and placement, to address the timing closure problem. In
addition, we have developed Sets of Pairs of Functions to be Distinguished
(SPFD) techniques for wire removal and wire planning in a circuit.
Publications, patents and artefacts:
- Invited chapter "Logic Synthesis" in the CRC EDA handbook "EDA
for IC Implementation, Circuit Design and Process Technology". Editors
L. Lavagno, L. Scheffer, G. Martin. ISBN 0849379245, 9780849379246,
571pp, published 2006. Chapter co-authored by Narendra Shenoy of Synopsys
Inc. The wikipedia entry on "Logic Synthesis" is based on the material in
this chapter.
- Invited paper "Multi-valued Logic Synthesis", Brayton, Khatri. 12th
International Conference on VLSI Design (VLSI-99), pp 196-205, Goa, India,
pp. 196-205. This paper presents a review of the state of the art in
multi-valued logic synthesis
approaches. Presentation slides.
- "SPFD-based Wire Removal in
Standard-cell and Network-of-PLA Circuits", Khatri, Sinha, Brayton, Sangiovanni-Vincentelli. IEEE Transactions on
Computer-Aided Design of Circuits and Systems, vol 23, number 7, June 2004,
pp 1020-1030. In this paper, we present approaches
to perform wire removal using Sets of Pairs of Functions to be
Distinguished (SPFDs), achieving a 11-20% reduction in placed-and routed
area for a network-of-PLA design (insignificant for a standard cell
based design).
- "SPFD-based Wire Removal in a Network of PLAs", Khatri, Sinha, Kuehlmann,
Brayton, Sangiovanni-Vincentelli. International Workshop on Logic
Synthesis, Tahoe City, CA. May 1999. In this paper, we present approaches
to perform wire removal using Sets of Pairs of Functions to be
Distinguished (SPFDs), achieving a 20% reduction in wiring in a
network-of-PLA based design. Presentation slides.
- "Don't Care Wires in Logical/Physical Design",
Chong, Jiang, Khatri, Sinha, Brayton. IWLS-2000. In this paper, given an
initial decomposition of a network, we find a set of alternate wires, and
select the most favorable wire (based on wirelength and congestion),
followed by a determination of the logic function. The wirelength reduction
obtained is between 5% and 8%.
- "Addressing The Timing Closure Problem By Integrating Logic Optimization
And Placement," Gosti, Khatri, Sangiovanni-Vincentelli. IEEE/ACM
International Conference on Computer-Aided Design (ICCAD-2001). Nov 2001,
Santa Clara, CA, pp. 224-231. This paper attempts to address the timing
closure by combining logic optimization and placement. Logic optimization
choices are made based on a companion placement, and an evaluation of
wirelengths of the choices based on this companion placement. The approach
realizes a reduction in circuit delay (18%) as well as area (18%).
- "A Robust Algorithm For Approximate Compatible Observability Don't Care
(CODC) Computation", Saluja, Khatri. Design Automation Conference (DAC),
June 2004, pp. 422-427. This paper presents an efficient, scalable approach
for approximate CODC computation, achieving 80% of the literal count
reduction of the full CODC computation, with a 25X reduction in runtime and
a 33X reduction in memory compared to the full CODC computation. It Presentation slides.
- "An Iterative Technique for Improved Two-level Logic Minimization", Shenoy,
Saluja, Khatri. International Workshop on Logic Synthesis, June 2004,
pp. 119-126. This paper performs two-level minimization by running ESPRESSO
iteratively. After each iteration, a subset of cubes are put aside, and
considered as don't cares for further iterations. With a small number of
iterations, a cube count reduction of up to 18% is achieved over a single
run of ESPRESSO, with 2X increase in runtime.
Presentation slides.
- "A Highly Testable Pass Transistor Based Design Methodology", Gulati,
Jayakumar, Khatri. IEEE International Test Synthesis Workshop (ITSW) 2006,
April 9-12, Santa Barbara, CA. This paper presents a pass transistor logic
(PTL) based design approach which utilizes partitioned ROBDD construction
as the synthesis backbone. With scan techniques, test generation for this
structure can be done in linear time in the size of each BDD partition. Presentation slides.
- "Generalized Buffering of PTL Logic Stages using Boolean Division", Garg,
Khatri. IEEE International Symposium on Circuits and Systems (ISCAS), May
21-24 2006, Kos, Greece, pp. 5615-5618. This paper presents a PTL
synthesis approach in which the design is realized in a decomposed
manner. The signals at the outputs of blocks are buffered using generalized
gates, which are found by Boolean Division. A 26% improvement in delay is
achieved over a traditional buffered PTL design approach.
- "Efficient Don't Care Computation for Hierarchical Designs", Gulati,
Lovell, Khatri. IEEE International Symposium on Circuits and Systems
(ISCAS), May 21-24 2006, Kos, Greece, pp. 3037-3040. Logic synthesis is
traditionally performed in a flat manner, limiting scalability. This paper
presents a hierarchical approach to do logic synthesis, which achieves a
36% literal count reduction over a flattened approach. The method can
complete several large examples which flattened optimization
fails on.
Presentation slides.
- "Gate-based Buffering of PTL Logic using Don't Cares", Garg,
Khatri. International Workshop on Logic & Synthesis (IWLS) 2006, June 7-9,
Vail, CO, pp. 23-30. This paper presents a PTL
synthesis approach which uses generalized repeaters (logic gates) to buffer
the signal between PTL stages. The generalized buffers are found by Boolean
Division as well as logical don't cares. A 5% improvement in delay and a 2%
improvement in area is achieved over a generalized buffering approach which
does not utilize don't cares. Presentation slides.
- "Toggle Equivalence Preserving (TEP) Logic Optimization", Goldberg, Gulati,
Khatri. 10th Euromicro Conference on Digital System Design (Architectures,
Methods and Tools), Aug 29-31, 2007, Lubeck, Germany, pp. 271-279. This
paper presents a new bottom-up logic synthesis approach which produces
circuits which toggle when a specification toggles. We demonstrate an
improvement of up to 50% in gate count over traditional logic optimization
techniques.
- "Noise-based Logic Hyperspace with the Superposition of 2^N States in a
Single Wire". Kish, Khatri, Sethuraman. Accepted for publications by
Physics Letters A. In this paper, we build on a previous paper which
proposes designing gates using uncorrelated noise signals. In this paper,
we show how this can be generalized to create a noise hyperspace, which can
convey up to 2^N states in a single wire. The resulting formalism is
competitive with quantum logic, and can solve string search O(sqrt(M))
times faster than Grover's quantum algorithm where M is the number of
strings being searched.
- "Robust Window-based Multi-node Technology-Independent Logic Minimization",
Cobb, Gulati, Khatri. IEEE/ACM Great Lakes Symposium on VLSI (GLSVLSI)
2009, Boston, MA. May 10-12, 2009. This paper reports our results on our
technique to perform logic optimization on 2 nodes simultaneously. We show
that this can improve the literal count of the state-of-the-art single node
approach by 15%. Presentation slides.
This paper also appears as a book chapter "Robust Window-Based Multi-node
Minimization Technique Using Boolean
Relations", Cobb, Gulati, Khatri. pp 309-333, In “Advanced Techniques in
Logic Synthesis Optimizations and Applications”, Khatri, Gulati,
ed. Springer Publishers.
- "A Boolean Satisfiability based Solution to the Routing and Wavelength
Assignment Problem in Optical Telecommunication Networks", Valavi, Saluja,
Khatri. International Conference on Communications (ICC), May 16 - 20 2005,
Seoul, pp. 1802-1806. In this paper, we utilize SAT to solve the Routing
and Wavelength Assignment (RWA) problem in dense wavelength division
multiplexed optical networks. A 3-4 order of magnitude speedup is achieved
over existing approaches. Presentation slides.
- "An Algebraic Decision Diagram (ADD) Based Technique to find Leakage
Histograms of Combinational Designs", Gulati, Jayakumar,
Khatri. International Symposium on Low Power Electronic Design
(ISLPED). This is also listed in the "Leakage Reduction and Modeling in VLSI" section.
2005, August 8-10, San Diego, CA, pp. 111-114. In this paper, we present an<
ADD based technique to generate the leakage histogram of a design. This
technique can be used to find the maximum and minimum leakage as well.
- "Advanced Techniques in Logic Synthesis, Optimizations and Applications",
Khatri, Gulati, editors. Springer Publishers, 1st ed, 2011. 240p. ISBN
978-1-4419-7517-1