Skip to main content
Article
Feasible Offset and Optimal Offset for General Single-Layer Channel Routing
SIAM Journal on Discrete Mathematics
  • Ronald I. Greenberg, Loyola University Chicago
  • Jau-Der Shih
Document Type
Article
Publication Date
1-1-1995
Pages
543-554
Publisher Name
SIAM
Disciplines
Abstract

This paper provides an efficient method to find all feasible offsets for 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 nets 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 columns c is $O( n )$, the problem can be solved in time $O( n^{1.5} \lg n )$, which improves upon a “naive” $O( cn )$ approach. As a corollary of this result, 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 channel. This paper also gives improvements upon the naive approach for $c \ne O( n )$, including an algorithm with running time independent of c. An interesting algorithmic aspect of the paper is a connection to discrete convolution.

Identifier
1095-7146
Comments

Author Posting. © Society for Industrial and Applied Mathematics, 1995. This article is posted here by permission of the Society for Industrial and Applied Mathematics for personal use, not for redistribution. The article was published in SIAM Journal on Discrete Mathematics, Volume 8, Issue 4, 1995, http://dx.doi.org/10.1137/S0895480193251866

This is a revised version of the conference paper that can be found at http://ecommons.luc.edu/cs_facpubs/114 (along with presentation slides).

Creative Commons License
Creative Commons Attribution-Noncommercial-No Derivative Works 3.0
Citation Information
Greenberg, RI and J Shih. "Feasible Offset and Optimal Offset for General Single-Layer Channel Routing." SIAM Journal on Discrete Mathematics 8(4), 1995.