Comparative Study of Evolutionary Model and Clustering Methods in Circuit Partitioning Pertaining to VLSI Design

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

Abstract:

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, circuit partitioning, memetic algorithm, genetic algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1331357

References:

[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.