1Harinavi Subhasini Balika Sikshalaya, PO: Harinavi, Dist.: 24 Parganas (South), Kolkata: 700 148, West Bengal, India
2PMI Service Center Europe Sp. z o.o., al. Jana Pawla II 196, 31–982, Krakow, Poland.
3Department of Computer Science and Engineering, University of Calcutta, 92, A. P. C. Road, Kolkata: 700 009, India,
4HCL Technologies Ltd., Block: A8 & A9, Sector: 60, Noida: 201 301, Uttar Pradesh, India,
5Department of Computer and System Sciences, Visva-Bharati, Santiniketan: 731 235, Birbhum, West Bengal, India
In this paper we have developed algorithms for generating random channel instances for their use in computing channel routing solutions in VLSI physical design. Channel instances are usually of two types: simple and general, and there are usually two kinds of inherent constraints involving channel routing problem: horizontal constraint and vertical constraint. Simple channel instances do not contain any vertical constraint, whereas, general channel instances contain both horizontal as well as vertical constraints. Most of the optimization problems in two-, three-, and multi-layer channel routing are NP-hard and, in fact, very few are polynomial time computable. Hence for each of the NP-hard problems in channel routing, it is unlikely to design a polynomial time deterministic algorithm. Developing heuristic algorithm may be a probable way out that hopefully provides good solutions for most of the instances available in literature. Novelty of a heuristic algorithm is judged better if it works for a variety of large number of randomly generated instances of the problem.
Channel routing problem, VLSI design, NP-hardness, Channel specification, Random generation, Simple channel instance, General channel instance, Algorithm
