 Optimum Standard Cell Layout Using Weighted Cycle Linear Placement

Introduction

Placement and routing problems for integrated circuits are inherently interrelated and extremely complex from the algorithmic point of view. This complexity grows exponentially as the scale of integration increases. To cope with their complexity within fully automated design methodologies, a common approach is to restrict the design framework both in terms of the structure of the target circuit and design algorithms.

A widely used approach is standard cell design (Fig. 1), in which almost all layout cells are of the same height, so it is convenient to arrange them in rows. If there some cells can be grouped in such a way that interconnects between the groups may be ignored or accounted for in some hierarchical way, then a locally-optimal placement of cells within each group may be approximated by the model of linear placement as shown in Figure 2. The quality of placement is estimated by some measure of interconnectivity provided that all wires run horizontally. 1. A standard-cell design (wiring hidden) in Expert. 2. Standard cell linear placement model.

In many cases the latter problem may be reduced to a problem of optimal placement of a weighted graph on a line. This problem is known to be NP-hard for many common optimality criteria [GJ]; therefore to handle this problem, a common approach is to consider its special cases affording a polynomial-time solution.

This paper proves NP hardness of a refined special case of linear placement and proposes a polynomial-time algorithm for some classes of placement, based on dynamic programming approach.

Weighted Cycle Linear Placement Problem

Let G(V,E) be a graph with vertex set V = V(G) and edge set E=E(G) and let n be the number of its vertices, n = |V|. A graph G is said to be edge-weighted if a weighting function

W: E(G) --> R+

is defined upon its edge set. A one-to-one correspondence

F: V(G) --> {1,2,,n}

is called linear placement, or numbering, of G. If we assume that V(G) = {1,2,,n}, then f is a permutation from the symmetric group Sn over the set {1,2,,n}; therefore in this paper the set of all numberings (linear placements) of an n-vertex graph will also be denoted by Sn.

This paper will consider the following criteria for placement:

Bw(G,f) = max{w(u,v)|f(u)-f(v)| : (u,v) \in E},

Tw(g,f) = max(1<=I<n) Sum(w(v,u)),

where the sum is over (v, u) \in E, such that f(v)<=I<f(u).

Lw(G,f) = Sum(w(u,v) |f(u)-f(v)|

where the sum is over (v, u) \in E.

The values Fw(G) = min{Fw(G,f) : f \in Sn}, where F is one of B, T, L, will be called the width, thickness, and length of G, respectively.

The problems of finding Bw(G), Tw(G), Lw(G) are known to be NP-hard, see [GJ], where the problems of finding B, L and T are called bandwidth minimization, optimal linear arrangement and min-cut linear arrangement, respectively. Polynomial-time algorithms for finding the length of an unweighted tree are known , . On the other hand, the problem of finding the width of an unweighted tree is NP-hard even for the case when vertex degrees of a tree do not exceed 3, see . An NP-hard problem is the one of finding the thickness of the weighted star graph K(1,n) (the PARTITION problem [1J] is easily reduced to it). Therefore polynomial algorithms are sought for narrower classes of graphs: special subclasses of trees ,  and weighted trees . This paper is devoted to the evaluation of computational complexity of linear placement of weighted cycle graphs.

Let Cn be a cycle graph with vertex set {1,2,..,n} and edge set {(1,2), (2,3),,(n-1,n), (n,1)}.Without loss of generality, assume that the edge (n,1) of Cn has minimal weight. Then it is immediately seen that the placement f(i)=i, i=1,2,..,n, is minimal both with respect to its length and thickness. However this is not the case with respect to width.

Theorem 1. The problem of finding a minimum width linear placement of a weighted cycle is strongly NP-hard.

See the book  for the notion of strong NP-hardness.

Proof. We shall make use of the following strongly NP-complete recognition problem 3-PARTITION from .

3-PARTITION: Given a set A of size 3m, a positive integer threshold B and positive integer sizes s(a_i) for all elements a_i from A, such that

B/4 < s(a_i) < B and Sum (s(a_i)) = mB,

is it possible to partition A into m disjoint subsets A_1,.., A_m such that S(s(a_j)) =B, where the S is over all a_j in A_j for all j, 1< j<m?

We shall demonstrate that this problem is pseudopolynomially reducible to the following problem of recognition of the width of a weighted cycle under linear placement:

WEIGHTED CYCLE LINEAR WIDTH: Given a cycle Cn, weights (w_1,, w_n) of its edges (1,2),(n,1), and a positive integer K, does there exist a linear placement of this weighted cycle of width at most K?

It will be convenient to use the following intuitive casting of this problem. The cycle is considered as nonexpandable thread with knots which correspond to the vertices of the cycle graph. The length of the thread between knots j and j+1 (edge (j,j+1)) is equal to L_j = K/w_j for all j=1,,n. The question is whether it is possible to place this thread along the line in such a way that the knots populate all points 1,2,,n, see Figure 3. Notice again that our thread can bend, but cannot expand. 3. Linear placement of C_6

The required reduction will be constructed as follows. For each instance of the 3-PARTITION problem we shall take the thread with 3mB+3m+3 = 3M knots with the following edge lengths:

L_j =1 for j in intervals [1, M-1], [M+1, M+s(a_1) -1],

[M+s(a_1)+1, M+s(a_1)+s(a_2)-1],,[M+mB+1, 2M+mB-1] .

L_j = mB+m for j = M, M+s(a_1), M+s(a_1)+s(a_2),

L_j = mB+m+1 for j = 2M+mB and j = 3M.

The chains of knots [1,,M], [M+1,, M+s(a_1)],, [M+mB+1,, 2M+mB] (i.e., the chains of edges of length 1) will be called rigid, because in any feasible placement they must occupy consecutive positions. Further, the first and the last rigid chain may occupy only the starting and the ending segments of the segment [1, 3M], i.e., all positions [1,,M] and [2M+1,, 3M], because our thread has only two sufficiently large edges that may pass over these chains. As a result, the subchain of m edges of lengths B+1 may be placed in the unique way, leaving m groups of consecutive positions unoccupied. Each of the remaining rigid chains with lengths s_j, j=1,, 3m, may be placed in any of these groups, thanks to the sufficiently long edges between them. Now it is easily seen that an instance of 3-PARTITION problem is solvable if and only if the corresponding thread has a linear placement.

The remaining three conditions for a reduction to be pseudopolyniomial [1J] are readily verified. It is also easily seen that WEIGHTED CYCLE LINEAR WIDTH problem belongs to class NP, hence the theorem is proved.

Polynomial Time Solvable Special Case

A placement f of a graph G is said to be k-layer, if

T_1(G,f) = k.

It is easy to see that

T_1(G,f) = max |{(v,u) \in E(G) :

f(v)< j < f(u)}|,

where maximum is taken over all j, 1< j < n. For example, a placement at Fig. 3 is a 4-layer one. Notice that the mentioned earlier minimum-length and minimum-thickness placements of a weighted cycle is two-layer. Let us consider the problem of finding the minimum-width two-layer placement of a weighted cycle.

The following statement is evident.

Lemma. Let f be a two-layer placement of a cycle C_n. Then for any number k, 1 < k < n, the vertices with numbers 1, 2, , k (and similarly, k+1, n) generate a chain and and the vertex placed at k (at k+1, respectively) is the endpoint of the chain.

In what follows, "+" and "-" will denote addition and subtraction modulo n, respectively.

Let (v-1,v) and (u, u+1) be edges of C_n (v = u is a possible case). After the deletion of these two edges the cycle is decomposed into two chains, denoted by c1 = (v, -u) and c2 = (u+1, -v-1). Let the first one has k vertices. Let further

S((v,a)(u,b)(u+1, c)(v-1, d))

Denote the set of all two-layer numberings (i.e., linear placements) of C_n in which the vertices of the chain (v, -u) are numbered by 1,2,, k, and the vertices v, u, u+1, v-1 are numbered by a,b,c,d, respectively. The Lemma above implies that there are only 2(k-1) admissible pairs of numbers (a,b) and 2(n-k-1) admissible pairs (c,d).

Let S((v,a)(u,b)) and S((u+1, c)(v-1, d)) denote the sets of numberings of chains c1 and c2 such that for any

h \in S((v,a)(u,b)) and g \in S((u+1, c)(v-1, d))

the numeration f of C_n such that f(j) = h(j) if j is in c1 and f(j) = n-g(j) + 1, if j is in c2 belongs to S((v,a)(u,b)(u+1, c)(v-1, d)).

Denote

B2_w((v,a)(u,b)) = min max w(j, j+1) |f(j)-f(j+1)|,

where the minimum is over all f from S((v,a)(u,b)) and the maximum is over v< j<u. We can derive recurrent formulae for the functional B2_w by unfolding the max expression at point a. then the width of minimum-width two-layer placement of a weighted cycle is

B2_w(C_n) = min_{(v, -u)}

min_{a,b,c,d} max{n1, n2,n3,n4},

where n_1 = B2_w((v,a)(u,b)), n_2 = B2_w((u+1,c)(v-1,d)), n_3= w(u,u+1)(c-b+floor(n/2)), n_4= w(v-1,v)(d-a+floor(n/2)), and the minimum is sought over all chains (v,-u) with the number of vertices floor(n/2) and over all quadruples a,b,c,d. Given the boundary conditions B2_w((j, 1)(j, 1)) = 0, the value B_2(w(C_n) may be found by the dynamic programming approach. Time complexity of the evaluation of the table of values B(()()) using recurrent relations is O(n4). It is necessary to enumerate n chains and n2 admissible quadruples in order to evaluate B2_s(C_n) by the formula above, so its time complexity is O(n3). In total the time complexity of the dynamic programming algorithm for finding minimum-width linear two-layer placement of a weighted cycle is O(n4).

Finally, notice that there are cycles for which minimum-width linear placement is not two-layer. An example is the 14-cycle:

(12, 14, 84,84, 84,84, 21, 84, 42, 21, 84,84, 84,84).

Its minimum-width linear placement is (1, 8, 14, 13, 12, 11, 10, 6, 7, 9, 5, 4, 3, 2) of width 84.

References

1. [GJ] M. R. Garey, D. S. Johnson
Computers and Intractability, 1978.
2. [GK] M. Goldberg, I.Klipker
Notices of Acad. Sci. of Georgian SSR, 1976
Vol. 81, No. 3, 553--556.
3. [C84] Chung F.R.K.
Computers and Math., with Appl., 1984
Vol.10, No.1, 43--60.
4. [GGJK] M.R. Garey, R.L. Graham, D.S.Johnson, D.E.Knuth, SIAM J.
Appl.Math., 1978
Vol. 34, No.3, 477-495.
5. [L85] Lepin V.V.
Notices of Belarusan Acad. Sci., Ser. Match Phys. 1985
No.2, 16--21.
6. [SZ82] M.M.Syslo, J.Zak, Ann.
Descrete Math., 1982
Vol.16, 281--286.