NorthHolland Microprocessing and Microprogramming 16 (1985) 345350
~5
Layer Assignmentby Simulated Annealing Paul Molitor Fachbereich 10, Universit~t SaarbrScken D6600 Saarbr~cken, F RG
A linear heuristic method for the via minimization problem for 2 layers, which is similar to the simulation of the process of cristallization, is introduced. The idea of this method is starting from an initial configuration, not only to accept rearrangements that lower the cost function but to allow also controlled uphill steps.
i. INTRODUCTION The layer assignment problem for interconnect is the problem of determining which layers should be used for wiring the signal nets of a circuit. The goal is to optimize the performance of the circuit and possibly to minimize its manufacturing costs [13]. This problem arises if one passes from the logictopological description of a circuit to the physical one [2].
2. FORMALIZATION OF THE CONTACT MINIMIZATION PROBLEM [13]. Given a planar circuit C in the euclidian plane, w.l.o.g, we assume a rectangular wiring, we construct in a canonical way a graph layout G c := (Vc,Ec), V c being the set of the crossovers, branches and ports, E corresponding edges
being the set of the c (see figure I).
The assignment of signal nets into layers must not change the semantics of the circuits: it must not generate short cuts; the delays of different layers must not affect the function of the circuit. The most popular version of this problem is to embed the signal nets into 2 layers such that the number of via holes is minimized [5]. The restriction to 2 layers is justified by technology: in order to avoid layers of different types, we embed the signal nets into two metal layers. In [13] this problem is reduced to the MAXCUT problem for planar graphs which can be solved in O(n 3) [12],[4],[3],[8] (n is the number of crossovers, branches and ports). Hence the algorithm introduced by Pinter would run some years for a
8
circuit C V ={1,2,3,4,5,6,7,8} c
c
={{t,6},{2,6},{3,8},{4,7},{5,7}, {6,7},{6,s},{v,s}}
signal net of size 10 5 . In this paper we introduce a heuristic method for the via minimization problem for 2 layers, which is similar to the simulation of the process of cristallization. The idea of this method is starting from an initial configuration not only to accept rearrangements that lower the cost function but to allow also controlled uphill steps. The analogy to the process of cristallization is developed in detail in [7]. In [7],[6] the method is applied to the traveling salesman problem and to several problems arising in automated design of computers like placement and global wiring.
(Figure i)
A mapping f : V
~ {red,blue} is called a c colouring of C. Such a colouring is interpreted as follows:for each port i and for each branch i the path segments of i are coloured f(i), for each crossover i the vertical path segment of i is coloured f(i) and the horizontal path segment is coloured ~  ~ (re~:= blue, blue := red). (see figure 2)
346
P. Molitor / Layer Assignmentby SimulatedAnnealing Let O
be the set of the odd faces of C, o the c c cardinality of Oc, i c the amount of odd faces f(ii) 1 2 3 4 5 6 7 8 rbrb r r r r (r_ed:~
, b_lue:
which are not adjacent to another odd face. Then the following theorem holds.
)
THEOREM
?
] Jl
zc >
oi c2~c+ i c
This lower bound can be easily improved. Definition Let f and f' be two faces of C. The distance
ILl
d (f,f') is the length of the minimum length c path connecting f and f' in the dual graph of C. (Figure 2)
Let f be a face, Uc(f, j) := { f ' 6 0 c ;
f ~ f' and
dc(f,f')
•6 
~
0(~)(f(")=
f(')) + (I 
0(k))(f(.)# f(.'))
where the predicate (f(v) = f(v'))(resp. (f(v) ~ f(v'))) has the numeric value i if it evaluates to true. So in order to minimize the amount of contacts we have to find a colouring f' of C such that zc f'= min{z~; f is a colouring of C} We denote this minimum by z . c 3. A LOWER BOUND FOR z
c
For simplicity let C be an embedding of a biconnected planar circuit in the euclidian plane. C divides the plane in regions. We call a face odd if there is an odd number of crossovers and via holes on its boundary; otherwise the face is called even. It is obvious that the boundary of an odd face can't be coloured with two colours if colour switching is not allowed. So to make C colourable one has to transform odd faces into even ones by inserting vias. Each via can transform at m o s t two odd faces in even ones (in the case that the two faces are adjacent).
is empty and Uc(f,j+l)
is nonempty
(9>__i). Then the following theorem holds THEOREM z
> c
o i c c ~ +
f>
_1
ic(J )
if G c is not bi~onnected,
~+i "L2~
z c is greater, than the
sum of the lower bounds of the biconnected components of G . c By similar considerations the via minimization problem for 2 layers can be reduced to the maximum weighted matching problem [i0) which can be solved in time O(n3). 4. A HEURISTIC METHOD FOR A VIA MINIMIZATION PROBLEM. We adapt the method of optimization by simulated annealing [7]: In order to grow a single crystal (structure of low energie state) from a melt, one has to lower the temperature a bit, then to spend a long time at this temperature to get in equilibrium. The temperature is lowered again and so on. TO simulate this process of cristallization one has to simulate a collection of atoms at a given temperature. Such a method is introduced by [ii] in 1953. In each step of the algorithm a particle is randomly chosen, just so a movement of this particle. Then the change in energy d E of the system which is caused by the above movement is computed.
If dE
movement would bring the system to a state of lower energy, we accept the movement and put the particle in its new position. If O
(k:
Boltzmannconstant). By repeating this basic step many times one simulates the thermal motion Of atoms in thermal contact with a heat Bath at temperature T.
P. Molitor / Layer Assignment by Simulated Annealing
The simulated annealing approach consists of the following series of identifications: thermal energy position of the atoms movement of a particle temperature
amount of via holes colouring redying of a vertex 'control parameter'
The probability that the configuration deteriorates is increasing with the temperature and decreasing with d . We have applied this method z among others to the following four examples: (i) (2) (3) (4)
The "simulated annealing" algorithm for solving the via minimization problem is given in figure 3.
4bit multiplier [9] easily testable 4bit multiplier 4bit conditionalsum adder [2] 8bit conditionalsum adder
[I]
Lower bound amount of via holes inserted of optimum by simulated annealing (average)
The time complexity of the algorithm is O(n+ ~ d(T  i.dT))max
(I) (2) (3) (4)
The values of Tmax,P(X,y),d T and d(Tmaxi.d T) T (i=o,.. max) have to be found by experiments. "' dT
15 72 18 49
IV ] C The values chosen by us (and confirmed by experiments) give a time complexity of O(n) for the algorithm. 5. STATISTICAL CONSIDERATIONS
347
(i) (2) (3) (4)
712 734 337 861
30 96 20.3 56
(factor 2) (factor 1.3) (factor 1.1) (factor 1.1)
CPUTime (SIEMENS 7561) 4.5 4.9 1.7 4.5
sec sec sec sec
In our program we have assigned the following values to the variables above: T = iOO, max t d T = 25, d(i) = lO. IVcl and p(dz,t) iOO.d z
Compute an initial coiourin9 f o f t ; v,,' Vc compute Zoo(¢, /) := Eh ={v, + C*temp := Tmaz; l o o p for i from 1 to d(temp) /* d(tcmp) represents the period in which this temperature doesn't "change */ loop Choose randomly a vertez v' 6 Vc; Compute Zto¢(V',f'), where f'(v)  f(v), ifv # v', and f'(v) = f(v') otherwise; d, := ZtocCv',f')  ZtocCv',/); if (d, < O) or ((0 < d,) a n d (random(O, 1) < p(d,, temp))) /* random(O, 1): random number out of CO,l). */ /* p(d,, ferap): probability that a vertex will be redyed even if 0 < dz */ t h e n f := f';
Zlo,(.,f) := Zto~(.,/'); fl; pool;
temp := temp dr; p o o l until temp < O; end; Figure 3
348
P. Molitor / Layer Assignment by SimulatedAnnealing
To determine the quality of our algorithm, we compare it with two other heuristic algorithms:
[4]
F. Hadlock: "Finding a Maximum Cut of a Planar Graph in Polynomial Time"; SIAM Journal on Computing, vol. 4, No.3 (1975), pp. 221225
C5]
A. Hashimoto, J. Stevens: "Wiring Routing by Optimizing Channel Assignment within Large Apertures"; Proc. of the Eight Design Automation Workshop, IEEE, 1971, pp. 155169
A Choose in the above method Tma x = O, d T = O, p(x,y)
= O, d(i) = 50.1V l, i.e. the redye of c a vertex must not deteriorate the configuration.
B ( iterative improvement) Compute an initial random colouring and only redye a vertex if this action really improves the (cost of the) configuration. Repeat this second step until a local minimum is reached. The following table indicates the results obtained by method A and B: the first number is the amount of via holes inserted by the respective method (average); the second number represents the factor relative to the lower bound of the optimum. Method A (1) (2) (3) (4)
37(2.5) 102(1.4) 20.5(1.1) 56.4(1.1)
[6] D°W. Jepsen, C.D. Gelatt: "Macro Placement by Monte Carlo Annealing"; [7] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi: "Optimization by Simulated Annealing"; SCIENCE, Vol. 220, No.4598, May 1983, pp. 671680 [8] E.G. Lawler: "Combinatorial Optimization Theory"; Holt Rinehart and Winston 1976, Chapter 6, pp. 217239
Method B 87.3(5.8) 178.1(2.4) 29.5(1.7) 79.8(1.6)
[9] W.K. Luk, J. Vuillemin: "Recursive Implementation of Optimal Time VLSI Integer Multiplier"; IFIP 1983, pp. 155168
6. CONCLUSION
[IO] P. Molitor: "An O(n3)Algorithm for the Via Minimization Problem for two Layers", to appear in 1985.
Our algorithm seems to be very efficient in the contact minimization problem. Compared to method B which is a current algorithm the simulated annealing method produces layer assignments with about 30%50% less contacts.
[11] N. Metropolis, W. Rosenbluth, N. Rosenbluth, A. Teller, E. Teller: "Equation of State Calculations by Fast Computing Machines"; Journal of Chemical Physics, Voi.21, No.6 (1953), pp. 10871092
The result of our algorithm seems quite useful. Unfortunately we are not able to prove the quality of our algorithm in mathematical sense. Experiments have shown that the results of our examples strongly depend on the choice of the parameters Tmax, dT, d(.) and p(.,.)° We even
[12] G.I. Orlova, YA.G. Dorfman: "Finding the Maximum Cut in a Graph"; Engineering Cybernetics, Vol. 10(1972), pp 502506
don't know if the choice of our parameters remains good for other examples. To finish we want to call the attention to the fact that the simulated annealing algorithm can be generalized to more than two layers. Furthermore one can generalize the algorithm to the layer assignment problem for 'geometrical' layouts, where there are wires on which there is not enough room to place a contact (see [13]).
[13] R.Y. Pinter: "Optimal Layer Assignment for Interconnect"; ICCC 1982, pp. 398401 [14] M.P. Vecchi, S. Kirkpatrick: "Global Wiring by Simulated Annealing"; Transactions on Computer Aided Design 1983, pp. 215222 8. APPENDIX Figure 4 shows a layer assignment of the 8bit conditionalsum adder obtained 5y the simulated annealing algorithm. In this example there are 53 contacts used. (The hatched cells represent the via holes.)
7. REFERENCES [1] B. Becker: "An Easily Testable Optimaltime VLSIMultiplier"; to appear in the proceedings of EUROMICRO 85 [2] B. Becker, G. Hotz, R. Kolla, P. Molitor: "Ein CADSystem zum Entwurf integrierter Schaltungen"; Technischer Bericht des SFB124, No. 16/1984, Universit~t des Saarlandes [3] H. Gabow: "Implementation of Algorithms for Maximum Matching on NonBipartite Graphs"; Ph.D. Dissertation, Stanford University 1973
This circuit has been constructed automatically in the design system CADIC (see [2]). CADIC is based On a calculus of nets, which allows the definition of recursive equations and controls the correctness of these equations. If the equations are given correctly, a geometrical layout (for any given size n and any set of basic cells) is produced by the system. Figure 5 shows the optimal layer assignment of the 4bit multiplier and a layer assignment of the same circuit obtained by simulated annealing.
P. Molitor / Layer Assignment by Simulated Annealing
349
( Figure 4 )
j~
I llr~il
llr~~_,'~
_ r~il
hr~il llr~il h,Anl
'
~,

~.~: ll~l
I IIr~ #'3,
p~
I llr~ I lllr&
",~,,,~
ll~,,l lJU~
11l i ~
y~ "t,
d

I
( Figure 5 )