A design automation team at IBM Research is using logic optimization techniques to enhance the productivity of high-performance integrated circuits in IBM microprocessors.
In the modern semiconductor chip, which consists of millions of logic elements, logic synthesis plays a crucial role in the timely completion of electronic designs. Hardly any large-scale chip is manufactured today without also automatically translating a high-level design description into its complex interconnection of transistors. Yet rapidly evolving technologies place new expectations on synthesis to ensure on-schedule delivery of designs to the marketplace. As the result, identifying and implementing logic synthesis techniques that target design closure for high-performance integrated circuits (IC) is extremely important in the manufacture of IBM microprocessors.
As IC technologies scale down, their fabrication processes continue to have more pronounced downstream effects on circuit quality. The traditional optimization techniques applied at the early stages of a design-flow become less effective when attempting to target improved circuit timing, power dissipation, “routability” or yield. Likewise, the typical action of iterating through logic and layout synthesis – trying to fix problematic parts of a circuit using conventional point algorithms and quality estimates – tends to impede productivity.
Our design automation team addressed this problem by using novel logic restructuring techniques that transform the desired structural design change under the physical domain constraints of a circuit.
A viable approach for advancing integrated circuit technologies
The development of these techniques stems from the increasing importance of a circuit’s structural properties in its final layout. Producing high-quality, layout-friendly circuit topologies adds a new dimension to circuit optimization, as well as to the traditional synthesis measures, such as area and delay. Integrating logic synthesis in the inner loop of the physical domain optimization has become a viable approach when addressing advances in IC technologies. Although the benefits of this approach are apparent, new technological constraints occur, including spatial location of the objects, their interconnection patterns, the amount of nearby free space and available cell libraries.
Our synthesis techniques achieved design closure of high-frequency designs by:
• Focusing on the timing of critical paths.
• Iteratively fixing problematic parts by integrating logic restructuring.
• Accurately placing logical elements.
• Estimating wiring effects.
The core of the computation contains a novel functional decomposition technique that efficiently explores different implementation patterns of problematic regions. The optimizations we have introduced can analyze a chip design’s state-space to further reduce chip area.
See Figure 1 to get an idea of how we fixed a problematic region on a timing critical path.
Figure 1. Fixing a problematic region on a timing critical path.
The logic optimization algorithms we implemented reduce micro-processor chip area, meet timing constraints and improve “routability.” They are available as a Tdecomp component within IBM's placement-driven synthesis (PDS) and have been applied extensively in the server design methodology to improve cycle-time of z-series and p-series chips.
Recognition and awards
- IBM Outstanding Technical Achievement award in appreciation for contributions to design closure.
Related Publications
M. L. Case, V. N. Kravets, A. Mishchenko and R. K. Brayton. Merging nodes under sequential observability (In process). 45th ACM/IEEE Design Automation Conference. June 2008.
V.N. Kravets and K.A. Sakallah. Resynthesis of multi-level circuits under tight constraints using symbolic optimization (pdf). IEEE International Conference on Computer-Aided Design. November 2002.
V.N. Kravets and P. Kudva. Understanding metrics in logic synthesis for routability enhancement (invited talk/pdf) . International Workshop on System Level Interconnect Prediction. April 2003.
V.N. Kravets and P. Kudva. Implicit enumeration of structural changes in circuit optimization. 41st ACM/IEEE Design Automation Conference. June 2004.
Last updated April 1, 2008
Rate this article
Innovator's corner
Victor Kravets Researcher
What is the most exciting potential future use for the work you're doing?
The techniques of logic optimization are particularly exciting. They will have a critical impact on the quality of integrated circuits as complex circuits become harder to analyze. Logic optimization also will facilitate design description at a higher level of abstraction, hence shortening the time-to-market cycle.
Who or what inspired you to go into this field?
When I was beginning my graduate studies at the University of Michigan, Professor Randal Bryant from CMU gave a talk on how to verify floating-point arithmetic units by leveraging a graphical structure called binary-decision diagrams. His talk inspired me to think of how to apply binary-decision diagrams to simplify the design process and make it less error prone.
What is the most interesting part of your research?
The synthesis of circuits from a higher level of specifications is a very challenging task. It rests on the synergy of mathematical rigor, engineering skill and team-work. It is rewarding to see synthesis successes manifested in the integrated circuits of products we use every day.
What is your favorite invention of all time?
That would have to be George Boole's invention in the middle of the 19th century of binary-valued algebra. It is fundamental to circuit design and computer science in general. Boolean algebra of course is the theoretical basis for the digital age.
Research team
Victor Kravets, Prabhakar Kudva, David Kung, Ruchir Puri