Statistical models for the VLSI route problem: Estimating the efficiency of collaborative problem-solving, with applications to chip design

Project Description

In complex processes such as ultra large scale integration (ULSI) of chips, computer-aided design tools are treated as black boxes in the typical chip design process. In most cases, the automated design tools operate on designs and successfully complete a specified task to create designs that satisfy specified design criteria. In other cases involving complex designs, however, the tools are unable to create designs that satisfy the specified criteria. In both situations, the performance of the tools can be enhanced with systematic external intervention that is implemented with some supplemental algorithm. This algorithm can either be fully automated or can rely on formally describable human expertise. In this intervention, the supplmental algorithm and the automated design tool take turns to move the design from one configuration to anohter until either the task is complete or until further improvements are not possible or necessary. In such as setting, a number of questions arise about how to measure the effectiveness of the external intervenion. One question, for example, is whether the external intervention is consistently able to assist the automated program to make progress. This situation is an instance of a general problem involving collaboration of several contributors who strive to achieve a certain goal, and we have developed a statistical framework to address questions that arise in the context of such problems. As an example, we apply this framework to the problem of routing a functional unit of the IBM POWER4 microprocessor.

Introduction

Physics tells us that there are limits for shrinking wires and devices. So better design techniques are more important as these physical limits are reached, and better design can help achieve more with available technology. Currently, assistance is provided by individual designers in an ad hoc way described as "carefully managed engineered wires and custom routes" that are costly to implement.

In chip design, success is a chip that operates at the project frequency and meets a set of other constraints specified by current engineering requirements. Examples of such constraints are the chip real estate (that is, chip area) and power dissipation limits. Within this set of traditional constraints, many possible designs exist that simultaneously enhance the design with respect to other parameters such as critical area, total wire length, via count, or parasitic coupling.

Statistical Model of Effectivness

For a particular chip architecture, success is achieved by feeding a device layout to an automated route algorithm, which fails on complex designs. In this project, we developed a set of equations to identify poor routes for routing by a supplemental algorithm, with the route algorithm completing the remaining routes. Each iteration of this loop is a trial, and the sequence of trials is continued until either success is achieved or one decides to obtain a better design. Our statistical models will help with such decisions, as illustrated in the diamond box in the figure below. To start, we locate the most poorly-routed signals within the chip area. The region occupied by these wires defines a "region of influence" of the supplementary algorithm and divides the wires into three sets, namely:

For each group, we define effectiveness variables for wirelengths and vias. Our assumptions about these variables are based on how we believe the supplemental algorithm will interact with the automated router, and we find no evidence in the data to contradict our assumptions. First, we postulate that the effectiveness variables are random variables following a multivariate normal distribution; that the variables observed in different trials are mutually independent; that the means and correlation structure within a trial are invariant from trial to trial; and that the variances are inversely proportional to domain size. Here, we use the term "domain size" to describe the amount of wire or via count in each of the three sets of routes.

Next, we evaluate the effectiveness of the supplemental algorithm, and whether progress is being made. We evaluate a weighted average of each effectiveness based on a series of trials, evaluate the standard errors and correlation structure, and establish the significance of the observed effects by calculating p-values and confidence bounds. If we succeed to obtain a legal route solution after a series of trials, we can stop or we can try to improve the design further. To assist in making this decision, we forecast the effectiveness of the supplemental algorithm in a subsequent step and establish its significance.

We applied these statistical frameworks to the wire routes in the POWER4 Instruction Fetch Unit. The immediate problem is that an automated vendor router tries but fails to wire this section. A supplemental algorithm (human intervention) commits to six trials to help the router succeed, and in the process reduced via count by 20 percent with no negative impact on wirelength, where the division of labor between human intervention and the vendor router is 1/3:2/3. The human intervention had significant positive effect on both wirelength and via count, with only slight negative impact on the router in the regions of influence, and with no impact on the vendor router outside the region of influence. To decide whether it is worthwhile to continue additional trials, we use our statistical model of forecasting and find strong evidence for negative impact on wirelength with no impact on via count; this reduces the cumulative wirelength effectiveness at trial 7. We see that it is not profitable to continue, so we stop.

The ability to make these types of decisions provides a method for designers to make efficient use of their design efforts. For example, if there are two weeks remaining in a design schedule, the ability to make the decision to stop then frees the designers to focus their efforts elsewhere.

Journal Publications

• "Estimating the efficiency of collaborative problem-solving, with applications to chip design," M. Y. L. Wisniewski, E. Yashchin, R. L. Franch, G. Fiorenza, I. C. Noyan, in IBM Journal of Research and Development, January 2003, pp. 77-88.

• "The physical design of on-chip interconnections," M. Y. L. Wisniewski, E. Yashchin, R. L. Franch, D. P. Conrady, D. N. Maynard, G. Fiorenza, I. C. Noyan, in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, March 2003, vol. 22, no. 3.

Project Members

• Emmanuel Yashchin

• Mary Y. L. Wisniewski

• Robert L. Franch

• Giovanni Fiorenza

• Cevdet Noyan

IBM T. J. Watson Research Center
Route 134
1101 Kitchawan Road
Yorktown Heights, New York 10598 USA