special section

Ernest Kuh, the 1998 Phil Kaufman Award winner This year's winner developed many of the fundamental technologies that power high-end IC physical design tools. by Jeffrey Erickson

EDAC, the Electronic Design Automation Consortium, has presented the 1998 Phil Kaufman award to Ernest Kuh, emeritus professor of engineering at the University of California at Berkeley. He's been awarded for his innovative contributions to the art of engineering in the form of physical design tool technology, enabling today's deep-submicron design capabilities.

Kuh's work and research has focused on the areas of electric circuit theory and computer-aided design for VLSI circuits and systems. In so doing, he and his predecessors made significant contributions to the state of the industry by pursuing technologies and research that transcended conventional and current modes of thinking. By applying his knowledge of technologies and research in another field--network theory--he has helped the industry move into nanometer process technology.

Richard Newton, a professor in the electrical engineering and computer sciences department at Berkeley and a member of the EDA Consortium's Phil Kaufman Award nominating committee, comments that "Kuh's work in the area of IC placement and routing is one of the driving forces behind achieving the circuit densities required for today's complex circuit designs. His research in techniques for floorplanning, partitioning, placement of standard cells and building blocks, global routing, channel routing, clock routing, timing-driven layout, and circuit simulation has proven critical for addressing the requirements of deep-submicron design."

Kuh began his research career in systems theory, a topic seemingly far removed from work in EDA tools. In systems theory, he focused on piece-wise analysis of nonlinear circuits. Between 1968 and 1980, he chaired the EECS department at Berkeley and then became Dean of Engineering. During that time, the number of graduate students decreased, and Kuh started to look into possible uses for his circuit theory and how to apply it to graph theory. His initial work in physical design investigated links between the connectivity of networks and interconnections and led to the introduction of single-row routing.

In 1978, Kuh took a sabbatical and went to Japan, where he collaborated with researchers at NEC and various Japanese universities. Together they developed and published their new theories on channel routing, the then-next level of IC layout. At that time, researchers at Bell Labs noted that solutions based on constraint graphs were among the most difficult problems in channel routing. Kuh addressed the problem by applying his knowledge of internal graphs and sequencing to develop linear placement algorithms.

After his success with linear placement algorithms, Kuh began work on block placement algorithms. Together with a graduate student at Berkeley, he developed the basic quadratic placement method as an extension to the linear placement method. By looking at the two-dimensional solution to the original linear placement, they also developed techniques for zero-skew clock tree placement. By the end of the 1980s, Kuh had started to work on timing-driven placement and routing as well as the problem of clock-tree routing. In a 1998 interview, Kuh discussed the future of EDA.

ISD: What will be needed most from tomorrow's DSM CAD tools?

EK: As deep-submicron (DSM) fabrication technology advances, the design of integrated electronic systems, whether implemented on a single chip or a multichip module, becomes drastically more complex. New CAD tools are essential and will require the evolution of present tools.

For deep submicron, both the interconnect area and signal frequency increase by an order of magnitude. It has been predicted that when the minimum feature size shrinks to 0.13 µm and below, interconnect wires will occupy 90 percent or more of the total chip area. Because you have higher frequencies and the longer wires, you have to consider the distributed circuit effects, as in a transmission line.

In addition, not only have the design rules changed, but also the area of the chips is larger. So it's the interconnects that dominate. How we deal with this complex problem in terms of circuit performance, design optimization, simulation, and testing is still not clear.

ISD: Given their importance, how do we start to characterize and simulate interconnects?

EK: Over the past eight or so years, many people have worked on different versions of simulation using different techniques. One basic contribution, made by Prof. Ron Rohrer and his students at Carnegie Mellon University, was to apply what is called the Padé approximation. It is based on the moment, the polynomial coefficients of the series expansion of the transfer function.

Ernest Kuh, emeritus professor of engineering at U.C. Berkeley, believes that evolving CAD tools are key for meeting future demands of DSM technology.

Although the higher the order, the better the approximation, using even just the first order moment--called the Elmore delay--gives very accurate and fast simulation. The Elmore delay has already been applied to circuit simulation and many people, including our own researchers at Berkeley, have improved on it. That's a basic change, but it hasn't been adopted by industry because Spice is so entrenched. The only problem with the Padé approximation is that for very large circuits it runs into problems of stability and accuracy. Although the Padé approximation is impractical for very large deep-submicron circuits, researchers at Bell Labs, Carnegie Mellon University, IBM, Massachusetts Institute of Technology, and Berkeley have already taken the next step in using it to get very stable and accurate simulators.

To do that, we reduce the size of huge circuits to get models for a transmission line network, a process called reduced model approximation. Reduced-order modeling is an extension of the Padé approximation using just a few terms of the expansion, but it gives only a single transfer function. In reality, we must consider 10,000 to 1 million ports and nodes. You want a reduced model not for just for the function but for the whole matrix. To complicate things, not only does each transmission line have its own equations, but transmission lines are coupled as well.

What's more, these different methods do not guarantee stability. Fortunately, transmission lines are passive elements and so cannot cause instability. If you do the reduced order modeling correctly, then the reduced model should be passive, and then you are guaranteed to have stable results. That's a key area in current research: to get reduced passive models that are accurate for simulation and determining delays.

ISD: How important is parameter extraction?

EK: Extraction--determining the parameters of the actual physical implementation--is very important. Extraction tells you an interconnect's resistance, capacitance, and inductance. And in the future, with higher frequencies and narrow interconnects, we will have to worry about the skin effect. Also, the lines may not be uniform, so you have to develop techniques to handle a nonuniform interconnect. In short, you have to extract the elements accurately, and that takes very good tools.

Typically, people have used two-dimensional extraction, which considers only plane geometry to extract the resistance and capacitance. But that's not good enough for DSM designs, which require that you do three-dimensional extraction to get the elements correctly. That third dimension--the metal height--is crucial.

True, you can solve that problem by electromagnetic wave theory. But to do that you have to solve the boundary value problem in three dimensions. People use the finite-element method and that takes too long. So one area of research is necessarily focused on developing accurate, simple, and efficient techniques to do extraction.

ISD: In the future, what role will interconnect simulation play in the physical design?

EK: In the physical design of DSM chips, the goal is more than just minimizing chip area by placing the gates and then simply connecting them. Rather, it is to come up with an interconnect-based layout. Perhaps what is first needed is to estimate the total wiring space from a high-level system specification. The role of floorplanning is still crucial; however, we must keep in mind the consequences of the interconnect. What might evolve is a hierarchical design style with successive and iterative wire planning. Then, at each hierarchy, gates and modules will be placed only after the interconnect structure is determined.

Today, for physical design there are many good timing-driven tools for placement and routing. We can do the design to satisfy the requirements using a very simple model. But that's not possible with DSM when you must consider the high-frequency and fine-geometry effects. You must have better coupling between the simulation model and the physical design. It's probably not possible to design with timing-driven tools and to get it right the first time. You have to make corrections and use iterative designs to finally satisfy the requirements. Work is still needed to achieve these better models and tools, starting with simulation.

ISD: What can be done to predict signal integrity problems?

EK: Signal integrity is a key problem for future designs. The best way we have to deal with it is in terms of coupled transmission lines. To design a circuit that satisfies the minimum requirements for signal integrity, designers need some kind of rule of thumb in terms of the element values of the interconnect. For example, for simulation there is a very simple formula that calculates the Elmore delay from the resistance and capacitance values in a tree network--that is, an interconnect without loops. People can use that for designing the layout.

It would be nice to have something similar for signal integrity, some kind of error bounds or upper limits that people can use to guarantee an acceptable signal integrity. Error bounds depend on the circuit and the model. For example, if you take a simple circuit and relate the error bounds in terms of the elements, then you can design the circuit so that the bounds will not be violated. You come up with a number that guarantees that the coupling, say, will not be greater than this amount.

Recently, a professor at the University of California at Santa Barbara published a paper dealing with this subject [Ashok Vittal and Malgorzata Marek-Sadowska, "Crosstalk Reduction for VLSI," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 16, no. 3, pp. 290-297, March 1997]. But that work still used the lumped-equivalent circuit to estimate the bounds. In the future, we would like to have bounds based on the distributed-circuit elements and to determine the bounds for crosstalk violations.

If those bounds could be obtained easily, that would be a big contribution to layout designers. You would determine the per-unit-length values of transmission parameters like resistance, capacitance, ground resistance, and inductance, which would become bigger factors in the future. The goal is to get the bounds in terms of those parameters and also in terms of the drive resistance, which is nonlinear and depends on the input voltage. That nonlinearity, by the way, is yet another complication to consider.

ISD: Are there ways to reduce design iterations when signal integrity problems are found

EK: Suppose you finish a design and find that the signal integrity requirements are not satisfied. The question becomes, "How do you redo the routing to satisfy the signal integrity requirements?" We claim that if you have already done the detailed routing, it may be too late. Although you can make some improvements--for example, you can change the order of the tracks in a channel to separate sensitive nets--at that stage, the channels are fixed. You don't have that much freedom.

A better approach is to check for violations after you do the global, but not the detailed, routing. Then, if you find that crosstalk is too high, you have more room to do the rerouting. In other words, once you do the global routing, you use simulators to check for crosstalk violations. If there are violations, you rip up and reroute the interconnections to correct them before you do the detail routing. To do this, you first formulate a region in terms of a graph model connecting the other regions. Then you can change the graph to modify the global routing.

Most layout problems can be specified by a graph, which makes graph theory a very important part of layout design. The graph is a representation of the netlist. It represents the connections among modules, shown as nodes. Each interconnect or group of interconnects is represented by an edge and in this way you form a graph. To graph the global routing, each connector has a weight, which indicates the concentration of the wires. Once you represent global routing, placement, and partitioning on a graph, you can use graph theory algorithms to solve the problem.

Then, when you calculate which region is sensitive to signal crosstalk, you can modify that region to reduce its sensitivity. The way to do that through global rerouting is to rip up some nets and do the rerouting. Then you are sure that when you do the detailed routing you won't have that problem. But how to retrieve the layout and introduce physical design tools into the process remains a research problem.

ISD: What additional complications does DSM process technology pose?

EK: With DSM technology, 8, 10, even 12 layers of metal are possible. How do you do the routing to take into account all these metal layers? It's not easy because existing tools are based on two or three metal layers. In a multichip module or printed circuit board, you might also use that many layers. But those cases cannot be translated to chip design very easily. One reason is that in DSM technology, the design rules for each layer are different. For example, the spacing at the top layer is different from that at the bottom layer.

Other complications of multilayer routing on the chip are the vias. Vias are not easily characterized. The problem is to design a router that can take advantage of the many layers that are available and yet is consistent with the process design rules. That's a challenge.

ISD: Could you say more about the idea of interconnect-based chip planning and architectures?

EK: Interconnects should play a role in the architecture of the chip. In the past, you placed the gates to minimize the area. In the future, you will want to place the interconnects so that you know how much delay there is. That calls for something revolutionary: interconnect-based chip planning. This is something that we don't know how to do yet, but it emphasizes the importance of interconnects.

Interconnect-based chip planning is beyond the idea of interconnect-based floorplanning. You design a chip or a system and ask what kind of architecture you will have. That's a revolutionary idea. We are saying that you need to think of new architectures that lend themselves to efficient interconnections and then, using that, connect the modules to provide the function. If you make the architecture interconnect-based, you make sure that the interconnects will not create all the problems.

To voice an opinion on this or any Integrated System Design article, please email your message to jeff@isdmag.com.

integrated system design  June 1999