Department of Electrical and Computer Engineering

The Computer Engineering and Systems Group

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