Total views : 164

Difficult Channel Instance Generator for VLSI Physical Design Automation using Genetic Algorithm


  • Department of Computer Science, Sammilani Mahavidyalaya, Baghajatin, Kolkata – 700075, West Bengal, India
  • Department of Computer Science and Engineering, University of Calcutta, Kolkata –700009, West Bengal, India


Objectives: The wire length minimization of Channel routing problem is NP-hard. There are several heuristic algorithms available in the literature to get the feasible routing solutions using some limited instances. Here we want to generate all possible random channel instances based on Genetic Algorithm (GA). Methods/ Statistical Analysis: The present paper is described in three phases. In the first phase, we generate fixed size initial population based on some strategies and define the fitness value of each individual by the total number of vertical and horizontal constraints present in the channel. The best individual is obtained among the population based on height fitness value. In the second phase, we select two individuals based on Roulette Wheel Selection strategies and get two offspring's using single point crossover. We continue this process until the number of offspring's reached to the size of the population. To keep the population size fixed we apply reduction methods among the initial population along with all offspring are based on minimum fitness value. In the third phase, we randomly choose some channels for mutation and we find the best individuals among current population. This methodology will be continuing until and unless we reach the goal. Findings: The proposed method works efficiently for complex problems arise in VLSI physical design automation and it gives acceptable results in terms of different channel instances. Applications/Improvement: The newly designed method for different difficult channel instances generation techniques will help to judge any newly developed algorithm in the field of VLSI physical design automation.


Channel Instance, Channel Routing Problem, Genetic Algorithm.

Full Text:

 |  (PDF views: 104)


  • Kavya G, Thulasibai V. VLSI Implementation of Telemonitoring System for High Risk Cardiac Patients. Indian Journal of Science and Technology. 2014 Jan; 7(5):1–6.
  • Malathy K, Justus RB. A Novel VLSI Based Radix-2 Single Path Delay Commutator (R2SDC) FFT Architecture Design. Indian Journal of Science and Technology. 2016 Mar; 9(11):1–9. Crossref
  • Manikandan J, Manikandan M. VLSI based Pipelined Architecture for Radix-8 Combined SDF-SDC FFT. Indian Journal of Science and Technology. 2016 Jul; 9(28):1–5. Crossref
  • Pal RK. Multi-Layer Channel Routing: Complexity and Algorithms, Narosa Publishing House, New Delhi (Also published from CRC Press, Boca Raton, USA and Alpha Science International Ltd). UK; 2000.
  • Alpert CJ, Mehta DP, Sapatnekar SS. Handbook of Algorithms for Physical Design Automation. London, New York. CRC Press; 2009.
  • Hong C, Kim Y. The Efficient Hybrid Approach to Channel Routing Problem. International Journal of Advanced Science and Technology. 2012;42:61–8.
  • Wagner MDF, Wagner F. Routing Through a Dense Channel with Minimum Total Wire Length. Proceeding of Second Annual ACM-SIAM Symposium. 1991; 15(2):475–82.
  • Sau SS, Pal RK. An Efficient High Performance Parallel Algorithm to Yield Reduced Wire Length VLSI Circuits. Proceeding of 5th International Conference on Computers and Devices for Communication (CODEC). Kolkata; 2012. Crossref
  • Sau SS, Pal RK. A Re-router for Optimizing Wire Length in Two and Four-Layer No-Dogleg Channel Routing. Proceedings of 18th International Symposium on VLSI Design and Test. VDAT. Publisher: IEEE 978-1-4799-40066/14/2014 IEEE. 2014. p. 1–6. Crossref
  • Sau SS, Pal RK. An Efficient Algorithm for Reducing Wire Length in Three-Layer Channel Routing. Applied Computation and Security Systems. Series Advances in Intelligent Systems and Computing. Springer India. 2011; 2:145–56.
  • Sau SS, Pal RK. A Re-router for Reducing Wire Length in Multi-Layer No-Dogleg Channel Routing. International Journal of Computer Trends and Technology (IJCTT). 2016; 38(2):1–17.
  • Somogyi KA, Recski A. On the Complexity of the Channel Routing Problem in the Dogleg-free Multi-layer Manhattan Model. ACTA Polytechnica Hungarica. 2004; 1(2):1–9.
  • Chao HY, Harper MP. A Difficult Channel Routing Generator. ECE Technical Reports Paper. 1995. p. 1–16.
  • Banerjee S, Dey MT, Dutta S. Difficult Channel Generation Using Genetic Algorithm. International Journal of Artificial Intelligence and Applications (IJAIA). 2010; 1(4):145–57. Crossref
  • Pal A, Mandal TN, Pal RK, Kundu D, Datta AK. Algorithms for Generating Random Channel Instances for Channel Routing Problem. International Journal of Applied Research on Information Technology and Computing. 2010; 1(1):106–29. Crossref
  • Bremiga GG, Malleswari M, Enoch S. An Improved VLSI Algorithm for Modular Operation in Cryptography. Indian Journal of Science and Technology. 2016 Aug; 9(30):1–7. Crossref
  • Ramalakshmi P, Saravanan S. Multiple Scan Base Partitioning Technique to Increase the Throughput in VLSI Testing. Indian Journal of Science and Technology. 2016 Aug; 9(29):1–5. Crossref
  • Nivedha N, Muthaiah R. A VLSI Architecture of Root Raised Cosine Filter using Efficient Algorithm. Indian Journal of Science and Technology. 2016 Aug; 9(29):1–5. Crossref
  • Premson Y, Sakthivel R. VLSI Architecture for Image Contrast Enhancement using Modified Adaptive Gamma Correction with Weighting Distribution. Indian Journal of Science and Technology. 2016 Feb; 9(5):1–7. Crossref
  • David E, Goldberg G. Genetic Algorithms. Pearson Education India. Fourth Impression. ISBN: 978-81-7758-829-3. 2009.
  • Affenzeller M, Wagner S, Winkler S, Beham A. Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications (Numerical Insights). Chapman & Hall/CRC; 2009. Crossref


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.