Browse Prior Art Database

Optimal Placement for River Routing

IP.com Disclosure Number: IPCOM000128140D
Original Publication Date: 1981-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 44K

Publishing Venue

Software Patent Institute

Related People

Charles E. Leiserson: AUTHOR [+4]

Abstract

Programs for integrated circuit layout typically have two phases: placement and routing. The router should produce as efficient a layout as possible, but of course the quality of the routing depends heavily on the quality of the placement. On the other hand, the placement procedure ideally should know the quality of a routing before it routes the wires. In this talk we present an optimal solution for a practical, *common version of this placement and routing problem. . River routing is the problem of connecting in order a set of terminals a,,.. ., a, on a line to another set bl,... , bn across a rectangular channel. Since the terminals are located on modules, the modules must be placed relative to one another before rout-ing. This placement problem arises frequently in design sys-tems like bristle-blocks where stretch lines through a module can effectively break it into several chunks, each of which must be placed separately. In this talk we shall present concise neces-sary and sufficient conditions for wirability which are applied to reduce the optimal placement problem to the graph-theoretic single - source- longes t-paths problem. By exploiting the special structure of graphs that arise from the placement problem for rectilinear wiring, an optimal solution may be determined in linear time.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Optimal Placement for River Routing

Charles E. Leiserson Ron Y. Pinter

Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, Massachusetts 02139-1986

Abstract

Programs for integrated circuit layout typically have two phases: placement and routing. The router should produce as efficient a layout as possible, but of course the quality of the routing depends heavily on the quality of the placement. On the other hand, the placement procedure ideally should know the quality of a routing before it routes the wires. In this talk we present an optimal solution for a practical, *common version of this placement and routing problem. . River routing is the problem of connecting in order a set of terminals a,,.. ., a, on a line to another set bl,... , bn across a rectangular channel. Since the terminals are located on modules, the modules must be placed relative to one another before rout-ing. This placement problem arises frequently in design sys-tems like bristle-blocks where stretch lines through a module can effectively break it into several chunks, each of which must be placed separately. In this talk we shall present concise neces-sary and sufficient conditions for wirability which are applied to reduce the optimal placement problem to the graph-theoretic single - source- longes t-paths problem. By exploiting the special structure of graphs that arise from the placement problem for rectilinear wiring, an optimal solution may be determined in linear time.

Key words and phrases: analysis of algorithms, graph theory, longest paths, placement and routing, river routing, VLSI layout.

1

Introduction River routing is a special routing problem which arises often in the design of integrated circuits, and it has been shown to be optimally solvable in polynomial-time for many wiring models (see in particular [Tompa] and [Dolev et al.1). In this paper we demonstrate that the placement problem for river routing is also polynomial-time solvable.

The general character of the placement problem for river routing is illustrated in Figure 1. Two sets of terminals a 1, . . . , a,, and bl, . . . , b, are to be connected by wires across a rectangular channel so. that wire i is routed from ai to bi. The terminals on each side of the channel are grouped into chunks which must be placed as a unit. The quality of a legal placement-one for which the channel can be routed-can be measured in terms of the dimensions of the channel. The separation is the vertical distance between the two lines of terminals, and the spread is the horizontal dimensioil of the channel.

1 This research was supported in part by the Defense Advanced Research Projects Agency under Contract No. N00014-80-C-0622,

Massachusetts Institute of Technology Page 1 Dec 31, 1981

Page 2 of 12

Optimal Placement for River Routing

(Image Omitted: Figure 1: Two sets of chunks on either side of a rectangular channel....