FEASIBLE OFFSET AND OPTIMAL OFFSET FOR GENERAL SINGLE-LAYER CHANNEL ROUTING

This paper provides an efficient method to find all feasible offsets f or a given separation in a very large-scale integration (VLSI) channel -routing problem in one layer. The previous literature considers this task only for problems with no single-sided nets. When single-sided ne ts are included, the worst-case solution time increases from theta(n) to Omega(n(2)), where n is the number of nets. But if the number of co lumns c is O(n), the problem can be solved in time O(n(1.5) Ign), whic h improves upon a ''naive'' O(cn) approach. As a corollary of this res ult, the same time bound suffices to find the optimal offset (the one that minimizes separation). Better running times result when there are no two-sided nets or all single-sided nets are on one side of the cha nnel. This paper also gives improvements upon the naive approach for c not equivalent to O(n), including an algorithm with running time inde pendent of c. An interesting algorithmic aspect of the paper is a conn ection to discrete convolution.