Hybrid Algorithm PSO and SA in Achieving Partitioning Optimization for VLSI Applications

	International Journal of P2P Network Trends and Technology (IJPTT)
	© 2012 by IJPTT Journal
	Volume-2 Issue-1
	Year of Publication : 2012
	Authors : Shikha Arora,Neeru malhotra,Rajan Vohra,Rajdeep Singh

Citation

Shikha Arora,Neeru malhotra,Rajan Vohra,Rajdeep Singh."Hybrid Algorithm PSO and SA in Achieving Partitioning Optimization for VLSI Applications". International Journal of P2P Network Trends and Technology (IJPTT), V2(1):1-4  Jan - Feb 2012, ISSN:2249-2615, www.ijpttjournal.org. Published by Seventh Sense Research Group.

Abstract

This paper includes a new partitioning algorithm for circuit bi-partitioning, used for the reduction of the number of interconnections between elements of VLSI circuit. In this paper, the hybrid PSO and SA algorithm for the bi-partitioning problem is proposed. PSO employs a collaborative population-based search, which is inspired by the social behavior of bird flocking. It combines local search (by self experience) and global search (by neighboring experience), possessing high search efficiency. SA employs certain probability to avoid becoming trapped in a local optimum and the search process can be controlled by the cooling schedule. Experimental result shows that the developed hybrid PSO and SA algorithm can consistently produce the better fitness value and the time required is less than the other algorithms of optimization.[1-10]

References

[1] Eugene L. Lawler, Karl N. Levitt, and James Turner, “ Module Clustering to minimize delay in Digital Networks”, IEEE Transactions on Computers, Vol. C-18 , No.1,pp47-57,Jan, 1969.
[2] B.W. Kerhinghan , S. Lin, “An efficient heuristic procedure for partitioning graphs”,Bell System Tech. Journal , Vol. 49, pp 291 – 307, Feb,1970..
[3] D.G. Schweikert and B.W. Kernighan, “A proper model for the partitioning of electrical circuits,” Proc. ACM/IEEE Design Automation Workshop, pp. 57- 62, 1972
[4] C.M. Fiduccia and Mattheyses, “A Linear time heuristic for improving network partitions” , Proc. 19th IEEE Design and Automation Conference, IEEE Press, Piscataway, NJ, USA , pp 175-182, 1982..
[5] Shawki Areibi and Anthony Vannelli, “Circuit partitioning using a tabu search approach”, IEEE International Symposium on Circuits and Systems , Chicago, Illinois,pp 1643-1646, March,1993
[6]S. Areibi, “Recursive and flat partitioning for VLSI circuit design,” The 13th International Conference on microelectronics, Rabat, Morocco, pp. 237-240, 2001.
[7] Sandeep Singh Gill, Dr. Rajeevan Chandel, Dr. Ashwani Chandel (2010) ‘Genetic Algorithm Based Approach to Circuit Partitioning’ IEEE Vol. 2, No. 2, April, 2010
[8] R. Poli, J. Kennedy, and T. Blackwell, “Particle swarm optimization :An Overview,” Swarm Intelligence Journal, vol.1, No.1, pp. 33-57, 2007
[9] G. Wang, W. Gang, and R. Kastner, “Application Partitioning on programmable platforms using Ant Colony Optimization,” Journal of Embedded Computing, vol. 2, Issue 1, pp.119-136, 2006
[10]Sandeep Singh Gill, Rajeevan Chandel, and Ashwani Chandel (2009) ‘Comparative study of Ant Colony and Genetic Algorithms for VLSI circuit partitioning’

Keywords

Partitioning, Simulated Annealing Algorithm, Particle Swarm Optimization Algorithm, Netlist.