Particle Swarm Optimization Approach for MST Problem in VLSI Routing

Particle Swarm Optimization Approach for MST Problem in VLSI Routing

Vandana Mahanthi * G.Anantha Rao

M.Tech Student Asst.Professor

Avanthi Institute of Engineering and Technology Avanthi Institute of Engineering and Technology Visakhapatnam

Visakhapatnam

Abstract – The performance of very large scale integration (VLSI) circuits predominantly depends on routing of interconnected circuits. The major problems in the design of VLSI layouts are wire sizing, buffer sizing and buffer insertion. These are the techniques to improve power dissipation, area usage, noise and time delay. The interconnect delay can be optimized by choosing proper buffer locations along the routing path. A stochastic based Particle Swarm Optimization algorithm is used here to optimize buffer locations to find the shortest path and also simultaneously minimize the congestion. The performance is compared with Particle Swarm Optimization based VLSI routing. The results obtained shows the proposed approach has a good potential in VLSI routing and can be further extended in future.

Index Terms – Buffer insertion, Minimal Spanning Tree (MST),Routing, Particle Swarm Optimization (PSO).

1. INTRODUCTION

   With rapid advancement of Very Large Scale Integrated (VLSI) circuit fabrication technology, size of the deep submicron and nanometer design has become a predominant factor in circuit performance and reliability. Numerous techniques are developed to reduce interconnect delay buffer insertion has been proven methodology among them. Therefore the performance of VLSI circuit is largely depending upon wire routing and buffer insertion through the path. The routing is a complex problem. Thus optimization algorithms give best solutions for the given routing problem with buffer insertion.

   To solve this multifaceted problem, Hai Zhou [12] proposed novel algorithms to solve this problem comprehensively. An evolutionary computation technique, Particle Swarm Optimization (PSO) is used by Chen Dong [13] and his only shortest path without buffer insertion. Nasir Ayob etal [8] attempted the same problem including buffer insertion along with routing optimization using PSO.

2. PARTICLE SWARM OPTIMIZATION (PSO)

   Kennedy and Eberhant [8] proposed an approach called Particle Swarm Optimization which was inspired on the choreography of bird flock. It is a population based search algorithm that exploits a population of individuals to probe promising regions of the search space. In the

   context, the population is called a swarm, and individuals are called particles. Each particle moves with an adaptable velocity with in the search space and retains in its memory the best position it ever encountered.

   Considering an-dimensional search space, and particle is associated with the position attribute and velocity attribute. The best position encountered by the particle is denoted as. Assume to be index of the particle that attained the best position found by all particles in the swarm. The swarm is manipulated in the same form resembling the following equations

   V t 1 w.V t c .rand.p

   t X t c .rand.p

   t X

   t

   (1)

   id id 1

   id id 2

   gd id

   X id t 1 X id t Vid t 1 (2)

   Where = 1,2, is the particles index, = 1,2, , is the dimension index and

   = 1,2, .. indicates the iteration number. The variable 1 2are positive constants, which are referred to as cognitive and social parameters, respectively and is a function which generates a random number that is uniformly distributed within the interval {0,1}. The variable

   is a parameter called inertia weight, which plays the role of balancing the global and local searches. It is positive linear function of iteration, given as

   wlast wstart * iteration

   w wlast

   max imum

   iteration

   (3)

3. MODELING IN PSO

   Initialize the Particle Swarm. Initialize m particles with random position and velocity inside the search space. Calculate the Fitness Value of each particle. Each particle represents a minimal spanning tree (MST), and the cost of the MST is the fitness value of this particle. The fitness value is calculated by Prim algorithm [11]. Compare the calculation of each particle with the particles previous best values pi: if the current value is better than the previous best values, then set the current value to be the best value. Compare the calculation of each particle with the global best previous values among the population pg: if the current value is better than the previous global best values, then set the current value to be the global best value. Compare the calculation of each particle with the global best previous values among the population pg: if the current value is better than the previous global best values, then set the current value to be the global best value. Calculate the self-adaptive Inertia weight for every particle: Put a particle Fitness Value and its swarm population into equation (3), the particles Inertia Weight wk

   would be get. Update the velocity and position of particles by using equation (1) and (2). Check the termination condition (a good enough position or the maximum number of iterations is reached). If fulfilled, the run is terminated. Otherwise the fitness value is calculated and process continues till the termination.

4. RESULTS

   Swarm size is taken of 200 is used. The maximum number of iterations is set as 100. The acceleration constants are set as: c1 =c2=2. r1 and r2 are random numbers, their value are between 0 and 1. The inertia weight should be set in the range of [0.4 to 0.95] from Shi and Eberhart [14] for PSOs good performance. We set the inertia weight by equation (3) applying to VLSI problem.

   Experiment 1: There are 12 cells generated randomly in this experiment, and the coordinates are shown in Table 1.

   NO.	1	2	3	4	5	6
   X	36.99	36.99	53.66	68.56	67.55	63.22
   Y	75.88	52.88	57.67	72.36	52.24	41.05
   NO	7	8	9	10	11	12
   X	81.69	36.24	20.08	43.31	30.93	59.97
   Y	37.86	39.46	42.97	33.39	16.45	18.05

   Table 1: Coordinates of 12 cells

   Figure 1: Optimal solution found by PSO for Experiment 1.

   Experiment II. There are 21 cells generated randomly in this experiment, and the coordinates are shown in Table 2.

   No	1	2	3	4	5	6	7
   X	13.89	13.6	15.06	25.29	21.49	31.43	48.39
   Y	14.77	32.6	48.68	55.99	74.12	84.36	85.53
   No	8		10	11	12	13	14
   X	66.81	78.22	92.84	79.39	67.69	88.16	56.58
   Y	87.87	85.23	88.74	68.86	54.24	47.81	53.07
   No	15	16	17	18	19	20	21
   X	42.25	51.32	40.79	38.74	68.27	61.84	93.13
   Y	65.35	35.23	29.39	41.67	32.6	17.69	8.04

   Table 2: Coordinates of 21 cells.

   Figure 2: Optimal solution found by PSO for 21 cells.

   Experiment III. There are 25 cells generated randomly in this experiment, and the coordinates are shown in Table 3.

   No	1	2	3	4	5	6	7
   X	10.38	11.55	25.88	42.25	39.04	37.87	19.74
   Y	68.27	89.91	86.7	85.23	75.29	58.92	47.51
   No	8	9	10	11	12	13	14
   X	10.96	47.81	67.11	71.78	66.81	61.26	82.6
   Y	35.23	53.95	53.07	72.37	84.65	94.3	92.84
   No	15	16	17	18	19	20	21
   X	91.08	84.36	76.75	82.89	84.06	68.27	50.15
   Y	79.68	53.07	34.06	29.97	10.09	13.3	11.26
   No	22	23	24	25

   X	53.36	32.89	28.51	8.04
   Y	31.43	29.09	14.47	9.8

   Table3: Coordinates of 25 cells.

   Figure 3: Optimal solution found by PSO for 25 cells.

5. CONCLUSION

The complex routing problem in VLSI has been solved using bio-inspired computing techniques. Particle Swarm Optimization algorithm is successfully applied to obtain optimum paths in VLSI routing. This paper presents an application of PSO for VLSI routing. The experiments have been carried out to demonstrate the feasibility of PSO implement VLSI routing. And algorithm also shows good results in VLSI routing optimization.

REFERENCES

[1]. Simultaneous Routing and Buffer Insertion with Restrictions on Buffer Locations. Hai Zhou, D. F. Wong, I-Min Liu, and Adnan Aziz,2000.

[2]. T. H. Cormen, C. E. Leiserson, and R. H. Rivest, Introduction to Algorithms Cambridge, MA: MIT Press, 1989.

[3]. J. Lillis, C. K. Cheng, and T. T. Lin, Optimal and efficient buffer insertion and wire sizing, in Proc.

Custom Integrated Circuits Conf., 1995, pp. 259262.

[4]. Blum C, Sampels M. An ant colony optimization algorithm for shop scheduling problems. J Math Modeling Algorithms 2004;3(3):285308.

[5]. Corry P, Kozan E. Ant colony optimization for machine layout problems. Compute Optim Appl 2004;28(3):287310.

[6]. Kennedy and R. C. Eberhart, Swarm Intelligence. San Mateo, CA: Morgan Kaufmann, 2001.

[7]. Dorigo M, Blum C. Ant colony optimization theory: A survey. Theoret Compute Sci 2005;344(23):243 78.

[8]. A Particle Swarm Optimization approach for routing in VLSI by Nasir Ayob et al.

[9]. Eberhart, R.C., and Kennedy, J. A new optimizer using particles swarm theory, Proc. In: Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan: IEEE Service Center, Piscataway, NJ, 1995. 39-43.

[10]. Kennedy, J and Eberhart, R.C. A discrete binary version of the particle swarm algorithm. In: Proceedings of the World Multiconference on Systematics, Cybernetics and Informatics 1997. IEEE Service Center, Piscataway, NJ.,1997: 4101-4109.

[11].PRIM R.C. Shortest connection networks and some generalization [J], B STJ, 1957, 36(6):1389-1401. [12]. Zhou. H et al. 2000. Simultaneous Routing and Buffer Insertion with Restrictions on Buffer Location.

IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems 19:819-824.

[13]. Chen Dong, Gaofeng Wang, Zhenyi Chen, Shilei Sum, and Dingwan Wang, A VLSI Routing Algorithm based on Improved DPSO, Proceeding of IEEE International Conference on Intelligent Computing and Intelligent Systems, 20-22 November, Vol. 4, pp.802-805, 2009.

[14].Shi, Y.H., Eberhart, R.C. A Modified Particle Swarm Optimizer. In: IEEE International conference of EvolutionaryComputation, Piscataway, NJ: IEEE, 1998. 68-73.