Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 30373
Comparative Study of Evolutionary Model and Clustering Methods in Circuit Partitioning Pertaining to VLSI Design

Authors: Annamma Abraham, K. A. Sumitra Devi, N. P. Banashree


Partitioning is a critical area of VLSI CAD. In order to build complex digital logic circuits its often essential to sub-divide multi -million transistor design into manageable Pieces. This paper looks at the various partitioning techniques aspects of VLSI CAD, targeted at various applications. We proposed an evolutionary time-series model and a statistical glitch prediction system using a neural network with selection of global feature by making use of clustering method model, for partitioning a circuit. For evolutionary time-series model, we made use of genetic, memetic & neuro-memetic techniques. Our work focused in use of clustering methods - K-means & EM methodology. A comparative study is provided for all techniques to solve the problem of circuit partitioning pertaining to VLSI design. The performance of all approaches is compared using benchmark data provided by MCNC standard cell placement benchmark net lists. Analysis of the investigational results proved that the Neuro-memetic model achieves greater performance then other model in recognizing sub-circuits with minimum amount of interconnections between them.

Keywords: VLSI, Genetic Algorithm, memetic algorithm, circuit partitioning

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1327


[1] C. J. Alpert and A. B. Kahng, "Recent Directions in Net list Partitioning: A Survey,'' Integration: the VLSI Journal, 19(1-2), 1995, pp. 1 - 81.
[2] Pinaki Mazumber, Elizabeth M. Rudnick, ''Genetic Algorithms for VLSI Design, Layout &Test Automation'', Prentice Hall PTR, 1998.
[3] B. W. Kernighan and S. Lin, ''An Efficient Heuristic Procedure for Partitioning Graphs'', Bell System Tech. Journal, vol. 49, Feb.1970, pp. 291-307.
[4] C. M. Fiduccia and R. M. Mattheyses, ''A Linear-time heuristic for Improving Network partitions'', Proc. ACM/IEEE Design Automation Conf., 1982, pp 175-181.
[5] H. K. Lam, S. H. Ling, F. H. F. Leung and P. K. S. Tam, ''Tuning of the structure and parameters of neural network using an improved genetic algorithm'', in Proc. 27th Annual Conf. of the IEEE Industrial Electronics Society (IECON 01), Denver, Colorado, 29 Nov.-2 Dec. 2001, pp. 25-30.
[6] N. J. Radcliffe, and P. D. Surry, "Formal Memetic Algorithms," Evolutionary Computing, Springer- Verlag, Berlin, 1994, pp 1-16.
[7] Data Mining by Bhavani Thuraisingham
[8] Ordonez.C, Omiecinski.E ''Efficient disk-based K-Means clustering for relational databases''
[9] M. Srinivas and K. M Patnaik, ''Genetic algorithm a Survey'', IEEE comput27, 1994, 17-26.
[10] S. S. Iyehgar, L. Prasad & D. Mortan in S. S. Iyengar, ed, ''Structure of Genetic Algorithm in Biological System'' (CRC press, 1992).
[11] T.T Chow, Z. Lin, C.L song & G. Q. Zhanan Huhan, ''Applying neural network & Genetic algorithm in chiller System optimization'', IEEE Paper June1997.
[12] Prof K. A Sumithra Devi, N. P. Banashree & Dr Annamma Abraham, ''An Evolutionary time-series Model for partitiononig a Circuit pertaining to VLSI Design using Neuro-memetic Algorthim'' , in proc. 4th IASTED International Conference on Circuit, Signal & System, San Francisco, USA, 20 Nov.-22 Nov .2006, pp 325-329.