Widths of Channel Routing in VLSI Design
Abstract
In VLSI design, one of the most important detailed routings is the channel routing. Given a channel with length n in 2-layer Manhattan model, Szeszler proved that the width (number of tracks required for routing) of the channel is at most 7/4 n, and this upper bound can be achieved by a linear time algorithm. In this note, we improve the upper bound 7/4 n to 3/2 n, which also can be achieved by a linear time algorithm.
Keywords
Download Options
Introduction
In VLSI design, One of the most important detailed routings is the channel routing [2,5,6]. A channel is defined by a rectangular grid of size (w +2)× n , insisting of horizontal tracks (numbered from 0 to w+1) and vertical columns (numbered from 1 to n), where w is the width and n is the length of the channel. The horizontal tracks numbered 0 and w + 1 are called the top and bottom of the channel, respectively. Points on the top or bottom are called terminals. A net is a set of terminals. The channel routing problem (CRP) is to interconnect all the terminals in the same nets, using minimum possible routing area, that is, minimizing the width w with the length n fixed. If all the terminals of each net are situated on one side, top or bottom, of the channel, we speak of single row routing problem. An instance of the CRP is a set N = {N1 ,…, Nt } of pair wise disjoint nets, each containing at least two terminals. The instance is called bipartite if each net N1 contains exactly two terminals, one on the top and the other on the bottom of the channel. The instance is dense if each terminal belongs to some net. A net is trivial if it consists of two terminals which are situated in the same column of the channel.