CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

On solving Mincut Balanced Circuit Partitioning Problem for Digital Circuit Layout using Evolutionary Approach with Solution Archive

by Maninder Kaur, Kawaljeet Singh
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 62 - Number 14
Year of Publication: 2013
Authors: Maninder Kaur, Kawaljeet Singh
10.5120/10152-5002

Maninder Kaur, Kawaljeet Singh . On solving Mincut Balanced Circuit Partitioning Problem for Digital Circuit Layout using Evolutionary Approach with Solution Archive. International Journal of Computer Applications. 62, 14 ( January 2013), 39-42. DOI=10.5120/10152-5002

@article{ 10.5120/10152-5002,
author = { Maninder Kaur, Kawaljeet Singh },
title = { On solving Mincut Balanced Circuit Partitioning Problem for Digital Circuit Layout using Evolutionary Approach with Solution Archive },
journal = { International Journal of Computer Applications },
issue_date = { January 2013 },
volume = { 62 },
number = { 14 },
month = { January },
year = { 2013 },
issn = { 0975-8887 },
pages = { 39-42 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume62/number14/10152-5002/ },
doi = { 10.5120/10152-5002 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:11:49.811009+05:30
%A Maninder Kaur
%A Kawaljeet Singh
%T On solving Mincut Balanced Circuit Partitioning Problem for Digital Circuit Layout using Evolutionary Approach with Solution Archive
%J International Journal of Computer Applications
%@ 0975-8887
%V 62
%N 14
%P 39-42
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The interest in finding an optimal partition in the area of VLSI has been a hot issue in recent years. Circuit Partitioning Problem is one of the most studied NP complete problems notable for its broad spectrum of applicability in digital circuit layout. The balanced constraint is an important constraint that obtains an area balanced layout without compromising the mincut objective. This paper proposes a non revisited algorithm based evolutionary approach ((NRECP) for balanced circuit min cut Partitioning in VLSI physical design automation which uses binary tries to efficiently store all evaluated solutions during the heuristic search and to effectively transform the solutions into unconsidered candidate solutions in case of solution revisit.

References
  1. B. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning of electrical circuits," Bell Syst. Tech. J. , pp. 291–307, Feb. 1970
  2. C. J. Alpert, L. W. Hagen and A. B. Kahng, "A Hybrid Multilevel/Genetic Approach for Circuit Partitioning," ASPDAC, 1996, pp. 298-301
  3. C. M. Fiduccia and R. M. Mattheyses, "A linear time heuristic for improving network partitions," in Proc. ACM/IEEE Design Automation Conf. , 1982,pp. 175-181
  4. G. R. Raidl and B. Hu. Enhancing genetic algorithms by a trie-based complete solution archive. In Evolutionary Computation in Combinatorial Optimization Evolutionary Comp. 2010, volume 6022 of LNCS, pages 239-251. Springer, 2010.
  5. J. Cong, L. Hagen, and A. Kahng, "Net partitions yield better module partitions," in Proc. 29th ACM/IEEE Design Automation Conf. , 1992, pp. 47–52.
  6. J-P. Kim, Y-H. Kim, and B-R. Moon. A hybrid genetic approach for circuit bipartitioning. In Proc. Genetic and Evolutionary Computation Conference (GECCO), volume 3102 of LNCS, pages 1054–1064. Springer, 2004.
  7. L. Hagen and A. B. Kahng, "Fast spectral methods for ratio cut partitioning and clustering," in Proc. IEEE Int. Conf. Computer-Aided Design, Nov. 1991, pp. 10–13.
  8. M. R. Garey and D. S. Johnson, . Computers and Intractability: A Guide to the Theory of NP Completeness,. San Francisco, CA: Freeman, 1979
  9. Mehdi Farshbaf, Mohammad-Reza Feizi Derakhshi, Arash Roshanpoor,Multi-objective optimization using hybrid genetic algorithm and cellular learning automata applying to graph partitioning problem. HIS2011:722 727
  10. R. Chandrasekharam, S. Subhramanian and S. Chaudhury, Genetic algorithm for node partitioning problem and applications in VLSI design, lEE Proc. E (Comput. Digital Techniques) 140(5) (1993) 255-260.
  11. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing," Sci. , pp. 671–680, May 1983.
  12. Sadiq M. Sait, Aiman H. El-Maleh, Raslan H. Al-Abaji: Evolutionary algorithms for VLSI multi-objective netlist partitioning. Eng. Appl. of AI 19(3): 257-268 (2006)
  13. S. Y. Yuen and C. K. Chow. A non-revisiting genetic algorithm. In IEEE Congress on Evolutionary Computation (CEC 2007), pages 4583{4590. IEEE Press, 2007
  14. C. J. Alpert, The ISPD98Circuit Benchmark suite,in Proc. ACM Int. Symp. on Physical Design,80-85,April 1998. ,http://vlsicad. ucsd. edu/UCLAWeb/cheese /ispd98. html
Index Terms

Computer Science
Information Sciences

Keywords

Binary trie Cyclic crossover NP-complete

Powered by PhDFocusTM