Open Access Open Access  Restricted Access Subscription or Fee Access

Particle Swarm Optimization Approach for MST Problem in VLSI Routing

K. Madhavi, K.V. Ramana Rao

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.


Keywords


Buffer Insertion, Minimal Spanning Tree (MST), Routing, Particle Swarm Optimization (PSO)

Full Text:

PDF

References


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

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

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. 259–262.

Blum C, Sampels M. An ant colony optimization algorithm for shop scheduling problems. J Math Modeling Algorithms 2004;3(3):285–308.

Corry P, Kozan E. Ant colony optimization for machine layout problems. Compute Optim Appl 2004;28(3):287–310.

Kennedy and R. C. Eberhart, “Swarm Intelligence”. San Mateo, CA: Morgan Kaufmann, 2001.

Dorigo M, Blum C. Ant colony optimization theory: A survey. Theoret Compute Sci 2005;344(2–3):243–78.

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

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.

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.

PRIM R.C. Shortest connection networks and some generalization [J], B STJ, 1957, 36(6):1389-1401.

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.

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.

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


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.