Simulated Annealing Approach onto VLSI Circuit Partitioning

March 3, 2014

Simulated Annealing Approach onto VLSI Circuit Partitioning

Abstract:

Decompositions of inter-connected components, to achieve modular independence, poses the major problem in VLSI circuit partitioning. This problem is intractable in nature, Solutions of these problems in computational science is possible through appropriate heuristics. Reduction of the cost that occurs due to interconnectivity between several VLSI components is referred to in this paper. Modification of results derived by classical iterative procedures with probabilistic methods is attempted. Verification has been done on ISCAS-85 benchmark circuits. The proposed design tool shows remarkable improvement results in comparison to the traditional one when applied to the standard benchmark circuits like ISCAS-85.

Author(s):

Arijit Bhattacharya, Department of Computer Science, APC College, New Barrackpore, West Bengal
Sayantan Ghatak, Department of CSE, University of Calcutta, Kolkata – 700009, West Bengal
Satrajit Ghosh, Department of Computer Science, APC College, New Barrackpore, West Bengal
Rajib Das, Department of CSE, University of Calcutta, Kolkata – 700009, West Bengal

DOI:

https://doi.org/10.15415/mjis.2014.22010

Keywords:

Circuit Partitioning, Intractability, Metaheuristics, Randomized search, Simulated Annealing

References:

Bertsimas D; Tsitsiklis J (1993) Simulated Annealing, Statistical Science, 1993, Vol. 8 No. 1, 10-15 http://dx.doi.org/10.1214/ss/1177011077

Chibante R (2010) Simulated Annealing Theory with Applications, Sciyo Publishers. http://dx.doi.org/10.5772/252

Dasgupta P (1996), PhD.(tech) thesis, Studies on the application of AI techniques to VLSI design, University of Calcutta.

Fiduccia-Mattheyses, RM (1982), “A Linear-Time Heuristic for Improving Network Partitions”; 19th ACM IEEE Design Automation Conference, 1982. pp 175-181. http://dx.doi.org/10.1109/DAC.1982.1585498

Ghatak S and Ghosh S (2012) VLSI circuit partitioning: an efficient approach. Proc. of RHECSIT, India 50-56.

Ghatak S and Ghosh S (2011) Hybrid approach onto VLSI circuit partitioning Proc. of CCSN. ISC AS High-Level Models http://web. eecs .umich. edu/~jhayes/iscas.restore/benchmarkhtml Kernighan, B.W., Lin S (1970), An Efficient Heuristic Procedure for Partitioning Graphs, The Bell Sys. Tech. Journal, pp 291-307. http://dx.doi.org/10.1002/j.1538-7305.1970.tb01770.x

Kirkpatrick S; Gelatt CD.; Vecchi M.P., Optimization by Simulated Annealing, Science New Series, Vol. 220, No. 4598, pp 671-680. http://dx.doi.org/10.1126/science.220.4598.671

Sherwani N (1995), Algorithm for VLSI Physical Design Automation, Kluwer Academic Publishers. http://dx.doi.org/10.1007/978-1-4615-2351-2

Chitkara University Publications