Abstract: The main aim of present study is to predict the interconnect length and width and we have proposed a novel approach to the prediction of the interconnect geometries without applying constraints on the circuit or the architecture model. Also, the study includes a probabilistic prediction of the area of the chip at the pre-placement stage. This predicted area would serve as a termination condition for the simulated annealing run to optimize the area during routing. This would yield a shorter physical design cycle.
INTRODUCTION
As technology pushes forward, feature sizes continue to decrease, but chip sizes tend to stay the same or grow even larger. As a consequence, the length of semi global and global wires increases, relative to the feature size and the relative cost of interconnect in the cost of VLSI chips is becoming ever more important (Sherwani, 1995). This causes large problems for designers; because most interconnect properties relate to their geometries and only become known during physical design. Hence, they are very difficult to optimize before at least some part of physical design has been executed. Moreover, since modern CAD flows require repetitive cycles of placement and routing to converge on a solution, interconnect prediction is gaining more and more relevance.
There are four different design styles. They are the full-custom, standard cell, gate array and also the Field Programmable Gate Arrays (FPGAs). During the physical design cycle, these design styles have decreasing degrees of freedom. Hence, layout of a full custom design style with no constraints, is the most difficult to complete. Hence, prediction is helpful but challenging.
The study of the link between the interconnect topology of a circuit net list and the cost of its physical implementation has been the main subject of System Level Interconnect Prediction (SLIP) since the 1970s introduction of Rent`s Rule. The earliest contributions to SLIP research provided models for the average wire length and the distribution of wire lengths in a circuit implementation (Dambre et al., 2004; Christie and Stroobandt, 2000).
To be useful for speeding up the design process, interconnect prediction techniques should be applicable as early in the design cycle as possible. Hence, it must be possible to abstract them for use in earlier design stages, e.g., by quickly estimating characteristic parameters of the interconnect topology or by replacing them by typical values. Since the prediction quality unavoidably decreases toward higher abstraction levels, it is important that the predictors are as accurate and reliable as possible. The prediction should be reliable across implementations in different layout substrates as well as across net list alternatives. This paper attempts a prediction independent of the process technology.
Most current prediction techniques focus on predicting placement wire length distributions from a logic-level net list (Davis et al., 1998; Dambre et al., 2004; Amakawa et al., 2007). This research takes a probabilistic approach for prediction, the work done on predicting the average width is a relatively less visited area of SLIP by researchers. There are 3 ways of planning width identified and correspondingly estimated. They are continuous width, discrete width sizing and wire tapering (Lee et al., 2002; Cong and Pan, 2002; Bamal et al., 2004; Alpert et al., 2001). We propose a method of predicting the width based on the typical current in the net list.
CIRCUIT AND SIMULATION MODEL
The circuit is modeled as a set of modules with varied area. Each module has a set of pins. The modules are in rectangular shape. The pins are assumed to be on only two sides of the module.The internal net comprises of pins from various modules.
The external net comprises of pins from the modules and terminals of the chip. All the lengths are in terms of λ, which depends on the process technology.
The simulation model for analysis is setup by generating random benchmark circuits that resembles a realistic circuit (Wan and Jeske, 2004, 2007). The module areas are generated by normal distribution. The internal and external net degree distributions follow a power law. The Rent`s exponent is taken as 0.85 and the internal net fraction factor is taken as 0.85. The circuits generated by the chosen net list generation method are verified to be realistic.
LENGTH PREDICTION
We adopt a probabilistic method for length prediction. The approach is as follows:
| • | Model a net as a tree. The tree would have, at the maximum, (netdegree-1) number of levels. Since the levels range over a small number of values, the number of levels for each net is taken randomly. The 6 terminal net in Fig. 1 has got three levels |
| • | Each line between the dots is taken as a segment. In a particular level, where there are no recursive levels, the length of the segment taken to reach the actual pin is negligible as compared to the length of the other segments and hence is neglected. Thus, in the net of Fig. 1, the number of segments under consideration is 9 |
| • | For as large as 1000 modules, the number of nets would grow close to 10,000. Hence, the number of such segments would be as high as 20,000 or more. Hence taking the segment lengths to be independent random variables, they will follow normal distribution as normal distribution is an approximation of any other distribution. Hence, these segment lengths are taken to be in normal distribution |
| Fig. 1: | Six terminal net modeled as tree |
| • | A normal distribution is determined by its mean and standard deviation. To begin with, the mean and standard deviation is obtained as follows: |
| LPV | = | Largest Possible Value |
| SPV | = | Smallest Possible Value |
| Mean | = | LPV+SPV/2 |
| SD | = | LPV-SPV/4 |
| • | To find LPV and SPV |
Consider modules of area (mean length mean length) to be placed in a grid of square root of the number of modules. The sum of all the module areas is calculated. Study reveals that 80% of the chip area is occupied by the interconnect. Hence, 4 times the module area is added to the module area to obtain the grid area. Assuming the grid to be a square, the length of the grid is determined. The total free space along a row between blocks is obtained by dividing the length of the grid by the sum of the mean lengths of the modules in a single row. The total free space is divided into (No of modules in a grid row+1) parts. The length of a single unit is the horizontal and vertical space between modules.
Hence SPV is obtained as:
| SPV | = | space + mean Length (Fig. 2) |
| LPV | = | (gridSize-2)2(space+meanLength)+2*(space+meanLength/2) (Fig. 3). |
| • | The expected length of every segment is then obtained as follows: |
Expected length = Σli*pi |
| li | = | Segment length |
| pi | = | Probability of obtaining that length |
| Fig. 2: | Determining SPV in 4* 4 grid |
| Fig. 3: | Determining LPV in 4*4 grid |
Probability of a particular value li is taken to be a ratio of the frequency of that value by the total number of segment lengths. Hence, frequency distribution is taken to obtain pi. Hence, expected length is the predicted length of a segment.
INTERCONNECT WIDTH PREDICTION
Greater the length, greater is the current drawn. Hence, current drawn is directly proportional to the length. But the current also depends on the branching. The length distribution obtained as discussed earlier, takes into consideration both the length and the branching. Hence, the current distribution can be considered to follow the length distribution with probable scaling factors that depend on the technology. Mean current/mean length is taken to be factor, KCl. KCl is obtained as a ratio of the current in the interconnect of expected length with a typical 0width of the technology. Hence, we propose to find the expected current first to lead us to the expected width.
Expected current in a segment is determined as follows. First, find the effective length in each branch. Then, current in that branch or segment will be equal to the effective length. For example, consider the Fig. 4, the effective length in s1branchislen(s1)+len(s2)+len(s3)+ len(s4)+len(s5). Here, len(seg) stands for the length of the segment. Expected current is then obtained as a product of effective length and factor KCl.
The expected current is then obtained, similarly as expected length by drawing a frequency distribution.
Expected Current = Σci*pi. |
The effective length is calculated by modeling the interconnect as a resistance, inductance and capacitance, the driver as a voltage pulse source, a driver resistance and a parasitic capacitance and sink as a load capacitance.
| Fig. 4: | Effective current illustration |
| Fig. 5: | Modeling of source, interconnect and sink |
The effective impedance of two branching interconnects can be obtained by complex method. The real part of the impedance (resistance) is proportional to the effective length and thus obtained. Modeling can be obtained from Fig. 5.
The width of every interconnect segment depends on the current that it has to carry. Greater the current, greater is the width. So width is directly proportional to the current. So, expected width can be determined directly as a product of the expected current and a technology dependant factor kwc. To obtain kwc, an approximation is made that a wire of 3 times the typical width (for a technology) is nothing but 3 wires of typical width in parallel. Expected area of a segment is the product of the expected length and expected width. The total interconnect area is the product of the expected area of a single segment and the total number of segments in the net list.
RESULTS
The prediction model is applied to varied input net lists varying from 5000 to 10,000 nets. Only the internal nets are taken for analysis. The prediction is compared with the results of a global routing tool, Labyrinth. The parameters considered are average net length and total wire length.
| Table 1: | Predicted vs routed average net length |
| Table 2: | Predicted vs. routed total wire length. |
The verification flow is to apply random placement, map the net list to a grid graph, obtain varying capacities to the grid edges and run the Labyrinth tool. The predicted and the routed average net length and total wire length and the corresponding error percentage are shown in Table 1 and 2, respectively. It shows that the model gives the average net length with an average error rate of 18.4% and total wire length with an average error rate of 19.19% with respect to the global routed length.
The width predicted for the five input test net lists are shown in Fig 6. The widths vary only in a small margin (μm). As per Cong and Pan (2002), there are only a few typical widths for a given technology. Accordingly, we get some typical width for the technology 0.18 UM.
CONCLUSION AND FUTURE WORK
The prediction model is for a full custom design assuming no circuit model or architecture model. The prediction model gives the average net length with an average error rate of 18.4% and total wire length with an average error rate of 19.19% with respect to the global routed length. This model can be used for the feasibility analysis prior to the design cycle. There are only a few typical widths for a given technology. As the technology dictates, the prediction model also gives almost the same width for varied inputs.
The prediction model has been verified by an academic global routing tool. We hope to verify this model with the results of a detailed router. To further continue, we expect to verify this model with commercial placement and routing tools. We expect it to predict the output of various tools to validate the prediction model to its entirety. The current routing algorithms disregard the width. With the width predicted, the wire width can be incorporated into routing algorithm. Simulated annealing is the most commonly used evolutionary algorithm for placement and routing.
| Fig. 6: | Width prediction |
The predicted length can be taken as a termination condition for the simulated annealing algorithm in order to minimize the number of iterations.
The width prediction can be further refined to obtain a more converging width with respect to the typical width for a technology.