International Conference on Futuristic Trends in Computing and Communication (ICFTCC-2014)

PSO Algorithm with Self Tuned Parameter for

Efficient Routing in VLSI Design

Sudipta Ghosh Subhrapratim Nath Subir Kumar Sarkar

Dept. of Electronics & Communication Dept. of Computer Science & Dept. of Electronics &
Engineering Engineering Telecommunication Engineering
Meghnad Saha Institute of Technology Meghnad Saha Institute of Technology Jadavpur University
Kolkata, India Kolkata, India Kolkata, India
[email protected] [email protected] [email protected]

Abstract— Device size is scaled down to a large extent with the decreasing inertia weight by Shi and Eberhart [4] increases the
rapid advancement of VLSI technology. Consequently this has convergence rate of the algorithm. Innovation of a self-
become a challenging area of research to minimize the adaptive inertia weight function [5] enhances the convergence
interconnect length, which is a part of VLSI physical layer rate of the PSO algorithm for multi-dimensional problem. This
design. VLSI routing is broadly classified into 2 categories:
paper proposes further improvement of the existing PSO
Global routing and detailed routing. The Rectilinear Steiner
Minimal Tree (RMST) problem is one of the fundamental algorithm which modifies the acceleration coefficients of PSO
problems in Global routing arena. Introduction of the meta- algorithm yielding accurate results and thereby establishing
heuristic algorithms, like particle swarm optimization, for solving better and efficient exploration and exploitation in the search
RMST problem in global routing optimization field achieved a space. This motivates us to apply the algorithm suitably to
magnificent success in wire length minimization in VLSI address the RMST problem in minimization of interconnect
technology. In this paper, we propose a modified version of PSO length in the field of VLSI routing optimization. The paper is
algorithm which exhibits better performance in optimization of organized as follows. In section II brief outline of PSO
RMST problem in VLSI global routing. The modification is algorithm is given. In section III proposed algorithm of PSO is
applied in PSO algorithm for controlling acceleration coefficient
described in steps followed by experiments and results in
variables by incorporating a self tuned mechanism along with
usual optimization variables, resulting in high convergence rate section IV. Finally the paper concludes with section V.
for finding the best solution in search space.
II. BASIC PSO ALGORITHM
Keywords— Global routing, RSMT, Meta-heuristic, PSO. PSO is a kind of evolutionary computation technique. More
specifically it is a meta-heuristic algorithm, derived from the
I. INTRODUCTION collective intelligence exhibited by swarm of insects, schools
of fishes or flock of birds etc, implemented to revolve many
Advancement in IC process technology in nano-meter
kinds of optimization problems. The basic PSO model [3]
regime leads to the fabrication of billions of transistors in a
consists of a swarm ‘S’ containing ‘n’ particle (S=1, 2, 3…., n)
single chip. The number of transistors per die will still grow
in a ‘D’ – dimensional solution space. Each of the particles,
drastically in near future, which increases complexity and
having both position ‘Xi’ and velocity vector ‘Vi’ of dimension
thereby imposes enormous challenges in VLSI for physical
‘D’ respectively, are given by, Xi = (x1, x2,…..xn) ; Vi = (v1,
layer design, especially in routing. In order to handle this
v2, ……vn);
complexity, global routing followed by detailed routing is
The variable ‘i’ stands for the i-th particle. Position ‘Xi’
adopted. The primary objectives of global routing in wire
represents a possible solution to the optimization problem.
length reduction, is becoming very crucial in modern chip
Velocity vector ‘Vi’ represents the change of rate of position of
design. The only way to minimize the length of interconnects
the i-th particle in the next iteration. A particle updates its
in VLSI physical layer design technology is to address the
position and velocity through these two equations (1) and (2):
problem of Rectilinear Steiner Minimal Tree [1]. To solve this
NP complete problem, meta-heuristic algorithms [2] like V t+ 1 = Vt + c1r1 *(p i – X t) + c2r2 *(p g – X t) …(1)
particle swarm optimization is adopted. It is a robust Xt+ 1= V t +1 + X t ……………………..………...(2)
optimization technique, introduced in 1995 by Eberhert and
Kenedy [3]. The PSO approach in VLSI routing is first Here the constants ‘c1’ and ‘c2’ are responsible for the
implemented by the authors Dong et al. at 2009. Various influence of the individual particle’s own knowledge (c1) and
improvements over original PSO algorithm have been made to that of the group (c2), both usually initialized to 2. The
make this algorithm more efficient. The introduction of linearly variables ‘r1’ and ‘r2’ are uniformly distributed random
 International Conference on Futuristic Trends in Computing and Communication (ICFTCC-2014)

numbers defined by some upper limit, ‘r max’, that is a its individual and global best position respectively. Using
parameter of the algorithm [6]. ‘p i’ and ‘p g’ are the particle’s smaller value limits the movement of the particle, while using
previous best position and the group’s previous best position. larger for the coefficient may cause the particle to diverge. For
‘Xt’ is the current position for the dimension considered .The c1 = c2 > 0, particles are attracted to the average of ‘pbest’ i.e.
particles are directed towards the previously known best points particles’ local best position and ‘gbest’ i.e. particles’ global best
in the search space. position value. A good starting point proposed to be c1= c2 =2
The balance between the movement towards the local best is used in algorithm [9] [10] for acceleration constant. Again
and that towards the global best, i.e. between exploration and c1= c2 = 1.49 generates good results for convergence as
exploitation, is considered in the above equation by Shi and proposed Shi and Eberhart [11] [12]. In our proposed
Eberhart in generating acceptable solution in the path of modification, we have introduced self tuned acceleration
particles. Therefore the inertia weight ‘w’ is introduced [4] in coefficients, linearly decreasing over time in the range of 2 to
equation (3) as follows : 1.4. This is introduced in VLSI routing optimization problem
for the first time. The pseudo code for the algorithm is given
V t+ 1 = w*Vt + c1r1 *(p i – X t) + c2r2 *(p g – X t) below.
………(3)
D. Pseudo Code
III. CONTROLLING PARAMETER OF PSO FOR OPTIMIZATION IN
 Preprocess Block
VLSI GLOBAL ROUTING
While optimizing RSMT problem for wire length - The search space for the problem is defined for a
minimization in VLSI physical layer design with the help of fixed dimension.
particle swarm optimization algorithm, we have considered - Within the search space the user defined terminal
controlling of parameters to facilitate maximum convergence node in form of coordinates are represented as ‘1’ to
and prevent an explosion of swarm. The following parameters form the required matrix.
in PSO algorithm are controlled. - The weight of the path between the nodes, including
the Steiner nodes, is calculated to form the objective
A. Selection of max velocity functions for n-particles.
Larger upsurge or diminution of particle velocities leads to - Cost of each objective function is calculated by
divergence of swarm due to un-inhibited increase the Prim’s algorithm.
magnitude of particle velocity, |Vi,j(t+1)|,especially for - Minimal cost along with the corresponding objective
enormous search space. The max velocity is limited by : function is identified amongst these results.
Vi,j(t+1) = (Xj(max) - Xj(min)) / k
 PSO Block
where Vi,j(t+1) is the velocity for next iteration. Xj(max) and Xj
(min) is the max and min position value respectively, found so Initialization for First Iteration
far by the particles in the j-th dimension and K is a user defined - Each of the objective function is assigned for position
parameter that controls the particles’ steps in each dimension and velocity vector
of the search space with K=2 [7]. - Each objective function represents local-best for each
B. Inertia weight particle of ‘n’ population.
- The objective function with minimal cost is assigned
The dimension size of the search space affects the as global-best for the swarm of particles.
performance of PSO. In complex high dimensional condition,
basic PSO algorithm constricted into local optima, leading
Execution of the PSO Block
premature convergence. Hence large inertia weight is required.
Smaller inertia weight is utilized for small dimension size of While (termination criteria is not met)
search space to strengthen local search capability, assuring - Velocity and position is updated for ‘n’ number of
high rate of convergence [8]. A self adaptive inertia weight population using the equation no (3) and (2).
function is used in our algorithm, which relates inertia weight,
- Fitness values (present pi) of ‘n’ particles are
fitness, swarm size and dimension size of the search space.
evaluated by Prim’s algorithm.
W = [3 − exp ( − S / 200) + (R / 8 * D) 2] −1 - Each pi is compared with previous pi,
where S is the swarm size, D is the dimension size and R is the - If pi(present) > pi(previous),
fitness rank of the given particles [5]. In our algorithm D is then pbest pi(present);
taken as 100. Else retain the previous value.
C. Proposed Modification: Self-tuned Acceleration coefficient - New pg  minimal of all pi s (present).
The acceleration coefficient determines the scaled - If pg(present) > pg(previous),
distribution of random cognitive component vector and social then gbest pg(present);
component vector i.e. the movement of each particle towards Else retain the previous value.
 International Conference on Futuristic Trends in Computing and Communication (ICFTCC-2014)

acceleration coefficient than the existing PSO algorithm [9]

Controlling inertia constant(w) [10].
- Calculate the self-adaptive inertia weight of each
TABLE 2: Experimental Results.
particle within the pop using equation no (3) in terms
of fitness, population (swarm size) and dimension of
Minimum ‘gbest’ Mean ‘gbest’
the search space.
Value Value
Controlling acceleration constant (c1, c2) EXPERIMENT NO. 1
- Calculate self-tuned linearly decreasing acceleration
constant. PSO with c1=c2=2 308 319.81
- Check the termination criteria. If satisfied, stop
execution and get the global best value for the swarm PSO with Self 295 307.5
size. Otherwise execute the PSO block again. tuned c1,c2

IV. EXPERIMENTS AND RESULTS EXPERIMENT NO. 2

3 sets of co-ordinates for 10 terminal nodes are randomly
PSO with c1=c2=2 248 264.67
generated for connections in the defined search space of
100x100. The experiment executed 25 times for each set. The PSO with Self
population size of swarm is taken 200. The maximum no of 224 253.2
tuned c1,c2
iteration is set as 100. Experimental co-ordinates are shown in
table-1. EXPERIMENT NO. 3
TABLE 1: Coordinate set of 10 terminal nodes for 3
PSO with c1=c2=2 219 223.31
experiments.
PSO with Self 205 218.7
NO. 1 2 3 4 5 6 7 8 9 10 tuned c1,c2

COORDINATE SET 1
The comparison of the performances of existing PSO and self-
tuned PSO algorithm are shown in the bar charts. As our
X 09 17 31 20 40 49 56 72 88 93
proposed algorithm generates lower global best value as shown
Y 53 01 38 89 67 95 70 29 63 100 in figure 1, it implies that the cost of the Rectilinear Steiner
Minimal Tree (RSMT), constructed by interconnecting the
COORDINATE SET 2 terminal nodes, has been reduced. The ‘mean value’ of the
global best parameter i.e. average of the minimum cost has also
X 84 93 60 76 64 17 95 54 21 29 been improved as shown in figure 2. So this algorithm can
effectively handle the RSMT problem of graphs and thereby
Y 15 67 48 89 79 62 38 35 57 81 reduce the interconnect length to a great extent.

COORDINATE SET 3 Minimum 'gbest' value

X 44 42 97 61 89 91 80 69 31 56 350
308
295
Y 63 99 36 25 68 51 28 58 82 94 300
248
250 224
We first performed the experiment for PSO algorithm with 219
acceleration coefficient taken as c1=c2=2 and then the 205
experiment is again performed for the proposed PSO algorithm 200
with self tuned acceleration coefficient for the same three
coordinate sets. The result is tabulated in table-2. From the 150
comparative analysis it is observed that our proposed PSO Exp. No. 1 Exp. No. 2 Exp. No. 3
algorithm generates lower ‘gbest’ i.e. global best value
compared to the previous algorithm [9][10]. It is also seen from PSO with c1 = c2 = 2 PSO with self tuned c1 , c2
the results that the ‘mean value’ is also improved for our
proposed algorithm with self tuned linearly decreasing
Fig. 1. Comparison of Minimum Cost obtained by Existing and Modified
PSO algorithm
 International Conference on Futuristic Trends in Computing and Communication (ICFTCC-2014)

physical layer design. The further scope of the work can be

extended to examine the algorithm in obstacle avoiding routing
environment.
Mean 'gbest' value
350 REFERENCES
330 319.81
307.5 [1] J.-M. Ho, G. Vijayan, and C.K. Wong, “New algorithms for the
310
rectilinear Steiner tree problem”, IEEE Transactions on
290 Computer-Aided Design of Integrated Circuits and Systems,
264.67 1990, pp. 185-193.
270 253.2 [2] Xin-She Yang, Nature-Inspired Metaheuristic Algorithms.
Luniver Press, UK, 2008.
250 [3] R.C.Eberhart and J.Kennedy, “A new optimizer using particles
230 223.31 218.7 swarm theory”, Proeedings of Sixth International Symposium on
Micro Machine and Human Science, Nagoya, Japan, 1995, pp.
210 39-43.
[4] Y.H. Shi and R.C.Eberhart, “Empirical study of particle swarm
190 optimization”, Proceedings of IEEE Congress on Evolutionary
170 Computation, Washington DC, 1999, pp. 1945-1950.
[5] Dong Chen, Wang Gaofeng, Chen Zhenyi and Yu Zuqiang, “A
150 Method of Self-Adaptive Inertia Weight For PSO”, Proceedings
of IEEE International Conference on Computer Science and
Exp. No. 1 Exp. No. 2 Exp. No. 3
Software Engineering, Dec 2008, vol. 1, pp. 1195-1198
[6] A.Carlisle and G.Dozier, “An off-the-shelf PSO”, Proceedings of
PSO with c1 = c2 = 2 PSO with self tuned c1, c2 the Workshop on Particle Swarm Optimization, Indianapolis,
IN.2001
[7] A. Rezaee Jordehi, and J. Jasni, “Parameter selection in particle
Fig. 2. Comparison of Mean Cost obtained by Existing and Modified PSO
algorithm swarm optimization: a survey”, Journal of Experimental &
Theoretical Artificial Intelligence, 2013, 25(4). pp. 527-542.
[8] F.Van Den Bergh and A.P.Engelbrecht, “Effects of swarm size
V. CONCLUSION on cooperative particle swarm optimizers”, Proceedings of the
Genetic and Evolutionary Computation Conference, San
Wire length minimization in VLSI technology can be Francisco, California, 2001, pp.892-899.
achieved through global routing optimization using PSO [9] R. Eberhart, Y. Shi, and J. Kennedy, Swarm Intelligence. San
algorithm. In our proposed algorithm a modification is Mateo, CA: Morgan Kaufmann, 2001.
incorporated to the existing PSO algorithm. The technique used [10] J. Kennedy and R. Mendes. Population structure and particle
here is to modify the acceleration coefficients in such a way swarm performance. In Proceedings of the IEEE Congress on
that it can tune itself over the iteration process throughout the Evolutionary Computation , 2002, vol 2, pp. 1671–1676.
experiment. The experimental results exhibits a clear difference [11] Y.H. Shi and R.C.Eberhart, “A modified particle swarm
in the performance of the modified version from the existing optimizer”, Proceedings of IEEE World Congress on
Computational Intelligence, 1998, pp. 69-73.
one. It is seen that the convergence rate is high and also it can [12] Rania Hassan, Babak Cohanim, Olivier de Weck, and Gerhard
be applied for a large search space and having still good result Venter, “A Comparison of Particle Swarm Optimization and the
which clearly establish the robustness and stability of the Genetic Algorithm”, American Institute of Aeronautics and
optimization algorithm. Therefore this algorithm can Astronautics journal, 2005, 2055-1897.
effectively be used in global routing optimization in VLSI