Loading...
Please wait, while we are loading the content...
Similar Documents
Single-Layer Channel Routing and Placement with Single-Sided Nets
| Content Provider | Semantic Scholar |
|---|---|
| Copyright Year | 2003 |
| Abstract | -This paper considers the optimal offset, feasible offset, and optimal placement problems for a more general form of single-layer VLSI channel routing than has usually been considered in the past. Most prior works require that every net has exactly one terminal on each side of the channel. As long as only one side of the channel contains multiple terminals of the same net, we provide linear-time solutions to all three problems. Such results are implausible, if the placement of terminals is entirely unrestricted; in fact, the size of the output for the feasible offset problem may be f2(n2). The linear-time results also hold with a ragged boundary on the side of the channel with multiple connections to the same net. K e y w o r d s v L s I , Placement, Wire routing, Channel routing, Single-layer routing, Algorithms. 1. I N T R O D U C T I O N We are given two horizontal lines, whose positions may be adjusted to form the top and bot tom boundaries (sides) of a rectilinear grid, and a set of n nets. Each net consists of terminals located at grid points on the two sides, and we refer to the region between (and including) the two sides as the channel. An acceptable routing must specify paths along grid-line segments within the channel such that terminals belonging to the same net are connected, but the wiring paths for any two different nets do not cross or have any grid-line segments in common. (See Figure 1.) We assume that there exists such a routing, a condition that can be verified in linear time [1]. The principal measure of routing quality is the number of horizontal grid lines tha t are used, or, equivalently, the separation between the sides of the channel. In seeking to minimize the separation, we allow the two rows of terminals to be shifted relative to one another by an amount referred to as the offset, as illustrated in Figure 1. (The offset may be positive or negative.) This situation models connection of VLSI modules having terminals on their boundaries. Though VLSI chips generally use more than one interconnection layer, single-layer routing actually becomes more relevant as technological advances increase the number of layers on a chip. The Supported in part by NSF Grants CCR-9109550 and CCR-9321388. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://core.ac.uk/download/pdf/81167954.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
