OPTIMIZATION OF INTEGRATED CIRCUITS BY MEANS OF SIMULATED ANNEALING Jernej Olenšek, Janez Puhan, Ärpäd Bürmen, Sašo Tomažič, Tadej Turna University of Ljubljana, Faculty of Electrical Engineering, Ljubljana, Slovenia Key words: parametric optimization, simulated anneaiing, design of integrated circuits. Abstract: Ttie purpose of this paper is to test the efficiency of the modified orthogonal simulated annealing algorithm. The method is compared with the COMPLEX method on a set of mathematical functions. The method is then used on three real-world cases of integrated circuits and compared with a modified COMPLEX method that uses intelligent initial points selection. Optimizacija integriranih vezij z algoritmom simuliranega ohlajanja Kjučne besede: parametrična optimizacija, simulirano ohlajanje, načrtovanje integriranih vezij. Izvleček: Namen prispevka je preizkusiti učinkovitost modificiranega ortogonalnega simuliranega ohlajanja. Primerjamo ga z metodo COMPLEX na skupini matematičnih funkcij. Metoda je nato uporabljena na treh realnih primerih integriranih vezij in primerjana z modificirano metodo COMPLEX, ki uporablja pametno izbiranje začetnih točk. 1 Introduction Optinnization problems arise in virtually every field of engineering, science, and business. The parametric optimization problems are usually presented in the following form: min fix) xeR" xe \L,U_ (1) where / is the so-called cost function (CF) and x is a vector of parameter values. L and U are vectors of lower and upper parameter bounds, respectively. Unfortunately analytical solutions to (1) can only be obtained for some very simple and small problems. Most practical problems are complex and often include simulations and measurements, which are very expensive and time consuming. The complexity of the optimization problem depends on the dimensionality (i.e. the number of optimization parameters) and on the shape of the CF. The size of the solution space increases exponentially with the problem dimensionality, so locating good solutions becomes increasingly more difficult. But the real challenge arises from the CF itself. In most real-world applications the CF is nonlinear and has many local minima. Often the value of the CF is a result of numerical simulations or measurements that introduce noise to the CF. Noise makes the fast deterministic gradient based methods useless and derivative free direct methods become more attractive. Direct methods are usually divided in two major groups. Deterministic methods always produce the same final solution when they start with the same initial guess. One method from this group is the simplex method which is well known and popular due to its simplicity and speed. But the simplex method is a local downhill search method and its solution greatly depends on the initial guess. Stochastic methods, on the other hand, introduce randomness to the search process and are capable of escaping from the local minima in order to find better solutions. Simulated annealing is a stochastic method. In this paper we describe a recent version of simulated annealing referred to as Orthogonal Simulated Annealing (OSA)/1/ and compare it with a modified simplex method also known as Constrained SIMPLEX (COMPLEX) /2/. The comparison is done on a set of mathematical test functions. OSA and modified COMPLEX methods are then used on three real-world integrated circuit (iC) design problems. The purpose of comparison is to establish the feasibility of circuit optimization with OSA. The paper is organized as follows. In section 2 a brief description of the basic simulated annealing algorithm is given and in section 3 the OSA algorithm is described in detail. Section 4 compares the algorithm with the COMPLEX method on a set of mathematical test functions. In section 5 OSA is compared with a modifed COMPLEX methods on three cases of IC design. Section 6 gives the conclusions. 2 Simulated annealing algorithm Downhill methods can easally get trapped in local minima. To escape from a local minimum uphill moves must be allowed from time to time to give the algorithm a chance to move to unexplored parts of the solution space. Simulated annealing /3/ was developed for this purpose. It always accepts downhill moves but occasionally uphill moves are also accepted. The basic features of the algorithm come from the analogy with the movement of atoms in metal. When metal is heated up to a very high temperature, atoms can move freely even to a state with higher energy. When the material is cooled down slowly, atoms are more likely to move to low energy states. If the annealing is slow enough, the resulting metal has an uniform structure with very few defects and minimal free energy. The simulated annealing method mimics this process by introducing an artifical parameter to the search process often referred to as the temperature (T) which controlls the acceptance probability for the uphill moves. At the beginning of the search it is set to a high value and most transitions to higher CF values are accepted. As the search progresses, the temperature is slowly decreased so that the uphill moves become less frequent. If the annealing is done in a sufficiently slow manner, the final solutions reached by the algorithm are near the global minimum of the CF. The CF is an analogy of the free energy of the atoms in a metal. The basic steps of the simulated annealing algorithm are: 1. initialize - set algorithm parameters, inital point 2. generate new point - generation mechanism 3. acceptance criterion - transition 4. continue with 2 until end of temperature stage 5. annealing - cooling schedule (decrease temperature) 6. continue with 2 until stopping condition is met These steps must be chosen carefully in order to ensure the probabilistic convergence to the global optimum. The obtained algorithms, however, are not very efficient in practice because the required cooling schedules are too slow or the generation mechanisms are too inefficient to get any useful result in a reasonable amount of time. That is why most practical versions of the algorithm use modified generation mechanisms and cooling schedules. This way the convergence proofs (i.e. /5/) no longer apply but good solutions can still be obtained in a reasonable amount of time. 3 Orthogonal simulated annealing algorithm (OSA) Recently a new version of the simulated annealing algorithm was developed /1/, taking advantage of a carefully designed set of experiments at every iteration that helps to choose a good point for the next iteration. Since the results reported in /1/ were encouraging, this method was chosen for implementation and testing. All steps of the algorithm are described in this section. 3.1. Initialization In the initialization step basic algorithm parameters are set. For this purpose several points (in our case 100) are randomly chosen and evaluated. The best of these points is set as the starting point for the algorithm. The initial value of the temperature parameter T is set to the standard deviation of CF values at these points. Our method differs slightly from the original one /1/. Instead of using the same parameter (temperature) for the acceptance criterion and the generation meachanism we use a separate parameter for generation of random moves. The allowed intervals /Z, U/ for different optimization variables can vary considerably so the generation mechanism must use a separate parameter for each variable. For this reason we introduce another vector parameter referred to as the range {R). The initial values of the components of R are set to allowed interval widths of optimization variables. Another parameter that needs to be set is the number of moves at each temperature stage Nt. In theory it must be large enough for the algorithm to reach thermal equlibrium in every temperature stage. In our case Nt is set to 10. 3.2. Generation mechanism The algorithm uses orthogonal experimental design (OED) to choose good candidates for the next iteration. A carefully designed set of experiments allows for an efficient factor analysis. The main idea is to evaluate a small number of points in order to estimate factor effects on the given CF The selection of these points is done with the help of orthogonal arrays. In this context orthogonal means statistically independent so that the estimation of the effect of one factor does not affect the estimation of the effects of others. An example of such an experimental design for three factors and three levels per factor is given in table 1, which contains the generated orthogonal array and figure 1, which shows the distribution of the corresponding experimental points. Table 1: Orthogonal array for 3 factors and 3 levels per factor. experiment factor 1 factor 2 factor 3 number level level level 1 1 1 1 2 1 2 2 3 1 3 3 4 2 1 2 5 2 2 3 6 2 3 1 7 3 1 3 8 3 2 1 9 3 3 2 There is a total of ß"' = = 27 combinations of factor levels for this example, where Q is the number of levels per factor and Nf is the number of factors. In our case only nine experimental points have to be evaluated and the use of the orthogonal array assures that these points are evenly spread around the search space. The algorithm for generation of orthogonal arrays can be found in /4/. level 3 level 2 --level 1 level 3 level 2 level 1 level 1 level 2 _' foatQLJLZ: level 3 Fig. 1: Distribution of experimental points when the orthogonai array from Tabie 1 is used. The use of orthogonal arrays also has drawbacks. The method works very well when there are no interactions between different factors. Unfortunately this is usually not the case. Furthermore optimization problems often include many optimization variables so the number of required experiments for an efficient factor analysis is large. Therefore the A/v variables are randomly grouped into A/f factors. The two most extreme cases are when Nf = Nv and Nf = 1. In the former case there are many factors but because of the interaction effects between factors, the estimation of factor effects is less accurate. In the latter case there is only one factor and the estimated effect is accurate, but the optimization requires more iterations. A compromise is needed. The formula for determining the number of factors for a given problem is: N (2) At the beginning of every iteration the variables are randomly divided into Nf groups and every group is considered as one factor. Then a random perturbation vector is generated according to a specified probability distribution (in our case the Cauchy distribution). For every optimization parameter x/ the probability distribution of perturbation dxi is: p(dx.) = R: n(Rf+dxf} /■ = 1,2,...TV, (3) where Ri is the range parameter of the /-th variable in the current temperature stage. To generate a random variable from this distribution the inversion method is used: dx.=R.-tan(K-{U-l/2)} i = \,2,-N, (4) where U is an uniformly distributed random number from the interval /0,1 /. After generating the perturbation vector dx, the three levels for every optimization variable are determined as: xj = xf - dx, (5) where x' is the current value of the /-th variable. If x] or x^ violates box-constraints /U Ui/, its value is chosen randomly from this interval. Since variables are grouped into factors, setting one factor to some level means setting all the variables x,- from that factor to the corresponding level {x°, x'. or xf). This way the orthogonal array is converted into experimental points, which are then evaluated. The main effects of all factor levels are obtained by the following formula: (6) where Sj,k denotes the effect of the /c-th level of the /-th factor and yt is the value of the CF from the t-th experiment. Ft has only two possible values. It is 1 if in the f-th experiment the y-th factor has /(-th level. Otherwise F( is 0. The new candidate solution can now be generated. For every factor (J) the level {!<) with the minimum Sj,k is chosen. The CF of the new candidate solution is then evaluated. The best of all the experimental points and the candidate solution is then submitted to the acceptance criterion as a potential solution for the next iteration. This process is repeated Nt times in every temperature stage. 3.3. Acceptance criterion Most versions of the simulated annealing algorithm use the same transition acceptance criterion which is known as the Metropolis criterion. Downhill transitions are allways accepted. Uphill transitions are accepted with the probability: P = e y-y t (7) where y' and y are the CF values at the new and the current point, respectively, and T is the value of the temperature parameter. At high temperatures almost all transitions are accepted but when the temperature is close to zero most of the uphill moves are rejected and the algorithm acts as a downhill method. 3.4. Annealing The next step of the algorithm is the cooling schedule. Several schedules have been developed but the best known and also very popular is the original schedule of Kirkpatrick /3/. The temperature decreases exponentially: T{k)=T{k-\)-a, ae[0,i; (8) where k is the temperature stage index. Large values of a mean slow convergence but more reliable search for the global optimum whereas smaller values mean fast convergence with the increased risk of getting trapped in a local minimum. The empirically chosen value for awas 0.99. At the end of every temperature stage the number of moves Nt in a temperature stage is also decreased by a: NXk)=NXk-l}a (9) The probaility distribution for random moves must also be adapted. The range parameter fl is reduced at the end of every temperature stage: (10) 3.5. Stopping criterion Several stopping criteria can be used. In our case the algorithm stops when the temperature reaches user specified minimal value Tmin (in ourcase10"®)orwhen the number of CF evaluations exceeds the maximum allowed number of evaluations. 4 Optimization of mathematical test functions Orthogonal simulated annealing was compared with the COMPLEX method /2/ on a set of mathematical functions. The set includes unimodal functions, functions with a small number of local minima (considered as moderatelly difficult problems) and difficult problems with many local minima, noise, nonlinearity and strong interactions between variables. All of the tested functions can be found in /4/. The optimization was repeated 50 times for every function with randomly chosen initial points. Both methods had the same limited number of CF evaluations (50000 and 70000 for problems with Nv = 30 and Nv = 100, respectively). The optimization results are given in table 2. The results show that the OSA method is promising when compared to COMPLEX. The COMPLEX method exhibits very fast convergence but gets stuck in a local minimum in almost every tested case. It outperforms the OSA method in some cases of unimodal functions and functions with strong noise. The latter is not unexpected since the method maintains a population of points between iterations. Simulated annealing, on the other hand, starts every iteration from a single point. On multimodal functions OSA outperformed the COMPLEX method in terms of global search capabilities. Due to the modified generation mechanism and cooling schedule the algorithm was not able to locate the global minimum in all optimization runs, but the solutions that were found were still fairly good when compared to the global minimum. 5 Optimization of integrated circuits Since the OSA performance on mathematical functions was very promising, the next step was to test it on real-world COMPLEX OSA global minimum /l 30 -9596.2 -12569.5 -12569.5 -3012.3 -12569.5 /2 30 6.9709 3.5527-10"" 0 224.67 1.9899 /3 30 1.6714-10-2 1.5234-10-' 0 3.93447 2.7337-10"' /4 30 2.2362 TO"^ 1.7375-10-'^ 0 3.04840 1.6971-10"' /5 30 2.1584-10-' 1.6672-10"'^ 0 1.59433 2.0732-10"' fe 30 1.955M0-^ 6.99148 3.1601-10"" 1.0987-10"' 0 /7 100 -61.124 -98.861 -99.2784 -29.261 -97.860 /s 100 -70.408 -78.332 -78.33236 -63.311 -78.331 /,0 100 113.13 283.59 0 196.95 795.04 /n 30 2.598M0"'' 5.4955-10"" 0 5.3587-10'^ 8.2124-10"'^ fu 30 4.1618-10"^ 2.4360-10"' 0 2.0489-10"^ 1.5660-10"' fn 30 1.9705-10-' 1.8169-10"' 0 3.6034 8.2303-10"' fu 30 8.9943-10"' 39.777 102,83 1928.0 0 /,5 30 1.8026 1.2809-10"^ 0 9.4910 1 8.4080-10"' Table 2. Table shows the best and the worst solution found In 50 optimization runs. The functions used are defined in [41. electronic circuit design problems and compare its performance with the COMPLEX method. For this purpose SPICE OPUS circuit simulator was used /6/. In SPICE OPUS a modified COMPLEX method is already integrated as one of the available optimization methods. Since the original method has very fast convergence, restart with intelligent initial points selection is conducted every time the basic method reaches its stopping criterion /7/. This process is repeated untill the given limit of CF evaluations is reached. The final result is the best solution of all the runs. The OSA method had to be implemented in C langu-nage and added as one of the available optimization methods in SPICE OPUS. Three cases of electronic circuit design were considered. The first circuit was a simple delay element, the second an operational amplifier, and the third a rather complex amplifier circuit. Circuit topologies for all three cases are given in figures 2, 3, and 4, The key properties of all three optimization problems are given in table 3. Optimization parameters were resistances, capacitances and transistor channel lengths, widths, and multiplier factors. For every circuit several design goals were set. A single CF is constructed as a combination of all the design goals /8/. Optimization is conducted across several cor- ivddd m Ivssd ............ ........_ out —o Fig. 2: Topology of the first circuit. ipd bn Inn Inp ysp ic:r>= out J) Fig 3: Topology of the second circuit. .....v^d....... Hvdds i Inni Inpl Inns Inp2 (;^l ! qM .i::........ OLrtp -o -CU-J- Fig. 4: Topology of the third circuit. Table 3: Summary of the optimization cases: number of optimization parameters, number of design goals, and number of corner points. case K design goals comer points 1 12 7 1 2 15 14 14 3 17 32 17 ner points to account for different envirenmental conditions (supply voltage, temperature, process parameter variations, ...). Since every OF evaluation requires a separate circuit simulation for each corner point, a large number of simula- tions is expected resulting in very long run times. Therefore every circuit was optimized only once. The results of the optimization are given in table 4. Table 4: Optimization results: number of function evaluations (FE) to find a solution of the given quality, and final solutions. For modified COMPLEX method the number of the run In which a solution was found, is also given in brackets. mdified case COMPLEX OSA FE until cost< 100'10^ 253 (1) 1011 FE until cost <20'10' 660 (1) 12758 1 best cost 6.39-10' 11.3-10' FE until best cost 21409 (28) 14703 final FE > 100 000 16122 FE until cost < 50 124(1) 58 FE until cost < 10 2483 (2) 33595 2 best cost 8.07 7.37 FE until best cost 96912 (69) 47605 final FE > 100 000 47768 FE until cost< 10 3672 (3) 32014 FE until cost < 1 26688 (21) 34248 3 best cost 0.282 0.088 FE until best cost 41131 (32) 43877 final FE > 45 000 44164 Since the modified COMPLEX method uses restarts and can explore several local solutions within the given number of CF evaluations, the number of the run in which a solution was found is given in brackets. The number of CF evaluations after which the COMPLEX method was manually stopped, is also given. The OSA method stopped automatically when the temperature reached its final value. Both tested methods were compared in terms of the solution quality and the number of CF evaluations (FE). The first case is the most simple of the three cases considered. It only has a few design goals and does not include corner points. It also has the least optimization variables. All this makes the solution space smaller and the CF less complex. For this case the modified COMPLEX method performed considerably better than OSA. It did however require more CF evaluations and several restarts to reach a good solution. In the second case multiple corner points and more design goals were considered. OSA outperformed the modified COMPLEX method in terms of solution quality and number of required CF evaluations. The third case has the largest number of optimization variables, design goals, and corner points. In this case OSA was also more successfull than the modified COMPLEX method. These results show that for simpler cases the modified COMPLEX method clearly is a better choice. But when it comes to complex circuits, many design goals, and, above all, a large number of corner points, it does not perform as good as OSA. Not even restarts helped the COMPLEX method to find a better solutions than the one OSA found in a single run. 6 Conclusions A recently developed optimization method called Orthogonal Simulated Annealing (OSA) is described and compared against a version of the simplex algorithm (COMPLEX method). Both methods are first tested on a set of mathematical test functions. The results showed that OSA performs better when the CF has many local minima. On the other hand, the COMPLEX method is a good choice when finding a local minimum quickly is more important than finding a global minimum. OSA and modified COMPLEX method were then tested on three IC design cases. The results showed that on the simpler case the modified COMPLEX method using restarts outperformed the OSA method. As the problem complexity increased, the ability of the OSA to explore the search space more thoroughly resulted in better performance (compared to the modified COMPLEX method). But in order to obtain a good solution in a reasonable amount of time, probabilistic global convergence of the algorithm had to be sacrificed (modified generation mechanism and cooling schedule). Therefore there is no guarantee as to when and if the global minimum will actually be found. Nevertheless OSA is well suited to IC optimization and design, particularly for problems with many variables and corner points. 7 Acknowledgment The research has been supported by the Ministry of Higher Education, Science and Technology of Republic of the Slovenia within programme P2-0246 - Algorithms and optimization methods in telecommunications. 8 References /1/ Li-Sun Shu, Shinn-YIng Ho, A Novel Orthogonal Simulated Annealing Algorithm for Optimization of Electromagnetic Problems, IEEE transactions on magnetics, Vol. 40, No. 4, pp. 1790-1795, July 2004. /2/ M.J. Box, A new method of constrained optimization and a comparison with of^er methods. Computer Journal, Vol. 8, pp. 42-52, 1965. /3/ S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, Optimization by simulated annealing, Science, Vol. 220, pp. 1277-1292,1983. /4/ Yiu-Wing Leung, An orthogonal Genetic Algorithm with Quantization for Global Numerical Optlmlzaion, IEEE transactions on evolutionary computation. Vol. 5, No. 1, pp. 41-53, 2001. /5/ R.L.Yang, Convergence of simulated annealing algorithm for continuous global optimization, Journal of optimization theory and applications, Vol. 104, No. 3, pp. 691-716, 2000. /6/ SPICE OPUS circuit simulator homepage: URL: http://www.fe.uni-lj.si/spice/ , Faculty of Electrical Engineering, Electronic Design Automation Laboratory: URL: http://www.fe.uni-y.si/edalab/\hspace{1 mm). /7/ PuhanJ, Bürmen A, TumaT. Analogue Integrated circuit sizing with several optimization runs using heuristics for setting initial points, Canadian journal of electrical and computer engineering, Vol. 28 (3-4): pp. 105-111 JUL-OCT 2003. /8/ Bürmen A, Strle D, Bratkovlč F, Puhan J, Fajfar I, Tuma T. Automated robust design and optimization of integrated circuits by means of penalty functions, AEU- International journal of electronics and communications, Vol.57 (1), pp. 47-56,2003. univ. dipl. ing. el. Jernej Olenšek Univerza v Ljubljani, Fakulteta za elektrotehniko Tržaška 25, SI-1000 Ljubljana E-mail: jernej.olensek@fe.uni-lj.si Tel: (01) 4768 724 doc. dr. Janez Puhan Univerza v Ljubljani, Fakulteta za elektrotehniko Tržaška 25, SI-1000 Ljubljana E-mail: janež.puhan@fe. uni-lj. si Tel: (01) 4768 322 doc. dr. Ärpäd Bürmen Univerza v Ljubljani, Fakulteta za elektrotehniko Tržaška 25, SI-1000 Ljubljana E-mail: arpadb@fides. fe. uni-lj. si Tel: (01) 4768 322 prof. dr. Sašo Tomažič Univerza v Ljubljani, Fakulteta za elektrotehniko Tržaška 25, SI-1000 Ljubljana E-mail: saso.tomazic@fe.uni-lj.si Tel: (01) 4768 432 izr. prof. dr. Tadej Tuma Univerza v Ljubljani, Fakulteta za elektrotehniko Tržaška 25, SI-1000 Ljubljana E-mail: tadej.tuma@fe.uni-lj.si Tel: (01) 4768 329 Prispelo (Arrived): 20. 02. 2006; Sprejeto (Accepted): 29. 05. 2006