Minimal Area Design of Power/Ground Nets

The value of modern layout editors is increased by by including wide set of automatic operations. Expert, a PC-NT layout editor includes many traditional automatic tools for IC layout processing: merging, hollowing, resizing, cutting, clipping out, connectivity extraction, flattening, routing, etc. However, full-custom IC design requires more specific operations. In particular, the correct width calculation for segments of Power and Ground buses could be one of the crucial points in layout design flow. Power/Ground nets are among of basic components of ICs. Total chip area is significantly influenced by the quality of P/G net design.

For full- and semi-custom design, a shape and size of IC functional elements can be arbitrary, so P/G-net layout cannot be designed in advance, and VLSI designers are faced with the problem of minimization of the area for such net. This problem is not of great importance for standard cell design approach because the layout of P/G-nets is predefined for base chip in this case.

This article deals with mathematical model and algorithmic aspects for problem of determining the optimal width of each branch in the power and ground nets for VLSI circuits. The structures of the net topologies are rooted trees. Our objective is to minimize the area of the P/G nets subject to voltage drop constraints.

A basic mathematical model was developed by S.Chowdhury and M.A.Breuer[1]:

Let T(r) be the tree for power or ground net consisting of n branches and having the root in the vertex r. Let I(j), w(j) and l(j) represents, respectively, maximum current flow, width and length, associated with branch j. V(r) is set of all vertices of the tree T(r), |V(r)|=n. L(r) is set of leaf of the tree T(r) (|L(r)|=m and L(r) is subset of V(r)).

 

Figure 1: Fragment of ground bus from full-custom IC layout.

 

The objective is to minimize:

 	    {l(j)w(j)}  	(1)
	j=1,..,|V(r)|

The voltage drop constraints can be expressed for each j:

	  {f*I(k)l(k)/w(k)} < u(j)  	(2)
	k=p(r,j)

where:

p(r,j) is the path between the root r and
leaf j of the tree T(r);
u(j) is the maximum allowable voltage drop between these two points;
is conductivity of a layer.

We ignore some other constraints considered in [1] and consider a more practical one ([2], [3]):

w(k) is in W(k), and W(k) is a subset of (3)
the positive integer.

As shown in [3], the problem (1)-(3) (we shall call it the Ordinary Problem) is NP-hard. Nevertheless, it is possible to construct efficient algorithms for its solution [2, 3], if some parameters of the problem are bounded by reasonable constants, because the problem is not strongly NP-hard.

Our investigation have shown that this model is applicable only for small P/G nets. The reason of this is the assumption that we have non-zero current I(j) in all branches of nets simultaneously. In practice, only a part of P/G net branches "works" at one time. Consider all (or some most essential) maximal subsets of branches which have non-zero current simultaneously and the list of these subsets consist of M items [4].

Let {T(r,j)}, j=1,2,...,M be the set of the corresponding subtrees of the tree T(r), and L(r,j) be the set of leaves of the subtree T(r,j).

Suppose we know the following vectors:

  • current flows

    I(j) = {i(j,1), i(j,2),..., i(j,M)},

    where i(j,k) is the value of a current in a j-th

    P/G net branch, when the subtree

    T(r,k) "works";

  • maximum allowable voltage drops

    U(j)={u(j,1),u(j,2),...,u(j,M)}

    where u(j,k) is maximum allowable voltage drop on

    the path from the root of the tree

    T(r,k) to its j-th leaf;

  • voltage drops

    X(j) = {x(j,1), x(j,2),..., x(j,M)},

    where x(j,k) is the value of a voltage drop on a

    j-th P/G net branch, when the subtree

    T(r,k) "works".

Moreover, let's introduce the following variables:

  • c(j) = fl(j)a(j),

    where a(j) = Card({k=1,M | I(j,k) is not equal 0})^-1

    (here "Card" is a cardinality of a set);

  • G(X(j))=(g(x(j,1)), g(x(j,2)), ..., g(x(j,M))),
    where g(x(j,k))=1/x(j,i), when i(j,k) is not equal 0;

    g(x(j,k))=1, when i(j,k) is equal 0.

Thus, using the vectors and the variables introduced above, we can describe the problem (1)-(3) as follows:

	 {c(j)I(j)G(J)}->min 	(4)
j=1,..,|V(r)| {X(k)} < U(j), j=1,2,...,|L(r)|, (5)

k=p(r,j)

The problem described by (4)-(5) is called Multivariant Problem of sizing P/G nets.

Note that the considered problem is also NP-hard (for M=1 it is transformed to the Ordinary Problem (1)-(3)). But since the problem is also not strongly NP-hard (just as for the Ordinary Problem) there exist algorithms which are efficient for some practical restrictions on input parameters. Several methods developed for the exact solution of the Multivariant Problem are based on the dynamic programming.

Let us have a vector Y=(y(1),y(2),...,y(M)) which is determined in the M-dimensional space. Let each the vector Y have the correspondent set G(r,Y). Each items of the set G(r,Y) are {X(j)}, j=1,2,...,|V(r)|, which satisfy the following inequality:

	{X(k)} <= U(j) - Y, 	j=1,2,...,|L(r)|,
 k=p(r,j)

Let us introduce the following function:

	F(r,Y) = min( 	 {c(j)I(j)G(X(j))} )
	 {X(j)}is in G(r,Y)  j=1,..,|V(r)|

If G(r,Y) is empty then F(r,Y) is equal to infinite number.

Since the value of F(r,0) is exactly the value of function (4) for the problem (4)-(5) in the point of minimum, therefore the function F(r,Y) will be called the determining function of the problem (4)-(5) for the vertex r.

For maximal subtree T(k) of the tree T(r) with the root in the vertex k, the determining functional of the problem (4)-(5) for vertex k is the following:

F(k,Y) = min	(  {c(j)I(j)G(X(j))} )
	 {X(j)}is in G(k,Y) 	j=1,..,|V(r)|

The determining functional of the problem (4)-(5) satisfies the following equation of dynamic programming:

	F(k,Y) = min(    {(c(j)I(j)G(X(j)) +
	{X(j)| j is in son(k)} 	j is in son(k))
	+ F(j,Y+X(j))}

Algorithms being based on an equation of dynamic programming depend on a kind of a representation of the function shown above.

Several algorithms based on the dynamic programming are developed for the exact solution of the problem (4)-(5).

The first method is pseudopolynomial. It gives polynomial solutions in the case when the number of subtrees is restricted by a constant. It is based on the fact that the cost functional of the dynamic programming formulation for the Multivariant Problem is piecewise constant, and its domain can be subdivided into hyperrectangles (k-dimensional boxes). The efficiency of the constructed algorithm is achieved by advanced techniques used for implementing of logical operations on hyperrectangles (see, in particular, [5]). The overall time complexity of considered method is

	O((Hb)^M max(|W(i)|) |V(r)| M^(M-2) log^(M-2)(bH))
 		i=1,..,|V(r)|

where:

	H = max(u(j,k));
	b is minimal integer which is divisible on each
	member of set W = union    (W(i)).
			i=1,..,|V(r)|

The second approach is based on monotonicity of the dynamical programming function. For its calculation an efficient algorithm of determining the maximal (in relation to partial order) elements of set of k-dimensional vectors is used.

The computational complexity of the second approach is

	O((bH)^(2M) max (|W(i)|) |V(r)| M^(M-2) log^(M-2)(bH))
				i=1,..,|V(r)|

Despite the better theoretical (worst-case) efficiency of the first approach, in practice the second one has some advantages, because it can be enhanced with powerful truncation methods. In addition, it requires two times less space.

Further, for the cases when both methods of exact solution become too slow due to specifics of input data , a fast heuristical algorithm for quasioptimal solutions was designed. In particular, when k is large, and there exists essential overlapping between given subtrees T(j). It calculates the value of dynamical programming function only at points of a predefined regular grid associated with the function domain.

It has computational complexity

 	O (|V(r)| H / (C^M)),

where C is a constant proportional to grid step.

So, the trade-off between efficiency and quality of problem solution must be taken into account while applying the latter method.

Sometimes, it appears a necessity to get a fast estimate (not exact) solution to the problem (4)-(5). Such solution can be obtained by using a solution of the problem (1)-(3).

Let p(i)={(z(1,i,j), z(2,i,j))}, j=1,..., k(i) be a set of P/G net segments which connect i-th functional

IC element and corresponding VLSI P/G input pad, where k(i) is a cardinality of the p(i) set; z(q,i,j), q=1,2 are planar coordinates of start and end points of j-th segment for i-th functional IC element.

Let Z(0) be a placement coordinate of VLSI P/G input pad, Z(i) - a placement coordinate of P/G input pad for i-th functional IC element.

P/G TOPOLOGY SKETCH will be called such a set PP={p(i)}, i=1,2,...,|V(r)| that each p(i) (i is in L(r)) satisfies the following relations:

a) z(2,i,j)=z(1,i,j+1), j=1,2,...k(i)-1
b) z(1,i,1)=Z(0)
c) z(2,i,k(i))=Z(1)

The tree T(r) will be called the REALIZATION of P/G TOPOLOGY SKETCH, if every path p(r,i)=(j(1,i), j(2,i),...,j(t(i),i)), (j(m-1,i),j(m,i)) is edge of the tree T(r); j(m,i) is in V(r); j(1,i)=r; j(t(i),i)=i, i is in L(r) satisfies the following relations:

1) t(i)=k(i);
2) l(j(m-1,i),j(m,i))=d(z(1,i,m),z(2,i,m)),

where d is a distance in some metric.

Let's introduce two additional notions:

  • GG(PP) is a set of all realizations of P/G topology sketch;
  • W={w(i)}, i is in V(r), is a set of width of all T(r) segments.

Now we assume that the realization GG(PP) of P/G topology is variable therefore we shall write V(r,T(r)), p(k,i)(T(r)). Basing on the assumption above, we can describe the problem which has the variables: W and T(r):

	FF(W,T(r)) =   {l(j)w(j)}->min (6)
				j=1,..,|V(r,T(r))|
	  {fI(k)l(k)/w(k)}<=u(j), j=1,..,|L(r,T(r))|,(7)
	k=p(r,j)(T(r))
	T(r) is in GG(PP) (8)

MAXIMAL realization of P/G topology is called such that the tree TT(r) being in GG(PP) which satisfies the following condition:

INTERSECTION (p(r,i),p(r,j)) is empty, if i is not equal to j for all i and j which are in L(r).

So maximal tree TT(r) and the set w0={w0(1),w0(2), ...,w0(n)}, where

	w0(i)= S  {fI(i)l(k)/u(j)}, i=p(r,j),j is in L(r),
 		k=p(r,j)

are the solution of the problem (6)-(8).

 

Conclusion

Implementation of the algorithm in order to provide optimal P/G nets for designers is an automatic feature that may become necessary in any sophisticated set of CAD tools.

References

[1] Chowdhury S., Breuer M.
Optimum Design of IC Power/Ground Nets Subject to Reliability Constraints.
IEEE Trans. on Computer- Aided Design. - 1988. Vol. 7. N.7. - P.787-796.

[2] Azarenok A.S., Rudenko A.G.,
Stepanec V.J. Two Methods of VLSI Power/Ground Bus Design.
Notices of the National Academy of Sciences, Minsk, Ser. Phys. And Math. Sciences, No. 5,- P.93-100, 1988.

[3] Rudenko A.G.
About Exact Integral Solution of Optimization Problem for VLSI Power/Ground Nets.
Notices of the National Academy of Sciences, Minsk, Ser. Phys. And Math. Sciences, No. 3,- P.103-108, 1990.

[4] Rudenko A.G.
Mathematical Models and Methods of Solution of the Problem of Optimization of IC Power/Ground Nets Widths.
Preprint (13(463)) of the Mathematical Institute, Belarussian Academy of Science, 1991

[5] Edelsbrunner H.
A New Approach to Rectangle Intersection. Part II.
Int. J. Comput. Math. - 1983. - Vol. 13. - P.221-229.