Browse Prior Art Database

# Optimal Algorithm for Determining Channel Structure Placement of Circuit Chips

IP.com Disclosure Number: IPCOM000039482D
Original Publication Date: 1987-Jun-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 4 page(s) / 61K

IBM

## Related People

Luk, WK: AUTHOR [+5]

## Abstract

A technique is described whereby an algorithm is used to optimally determine the structural placement of channels for the automation of very large-scale integration (VLSI) circuit chip design. Methodology, based on slicing structures, is emphasized so as to efficiently utilize the empty space for channels and chip placement. The algorithm is used as a first step when determining the slicing structure of the placement, but is also applicable to arbitrary placements that are not slicing structures. (Image Omitted) In the physical design of a circuit chip, three elemental structural procedures are generally followed: 1) floorplanning, 2) global wiring, and 3) detailed wiring and layout of the macros.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 46% of the total text.

Page 1 of 4

Optimal Algorithm for Determining Channel Structure Placement of Circuit Chips

A technique is described whereby an algorithm is used to optimally determine the structural placement of channels for the automation of very large-scale integration (VLSI) circuit chip design. Methodology, based on slicing structures, is emphasized so as to efficiently utilize the empty space for channels and chip placement. The algorithm is used as a first step when determining the slicing structure of the placement, but is also applicable to arbitrary placements that are not slicing structures.

(Image Omitted)

In the physical design of a circuit chip, three elemental structural procedures are generally followed: 1) floorplanning, 2) global wiring, and 3) detailed wiring and layout of the macros. At procedures 1 and 2, the internal details of the macros can be ignored, and the macros can be treated as non-intersecting rectangular objects, as shown in Fig. 1. A placement is a slicing if it contains a single rectangle or if there exists a vertical or a horizontal cut that divides the placement into two parts, each of which is a slicing. A family of physical design algorithms, such as compaction and routing, is based on slicing structures, in that the channels form a hierarchy of "guillotine cuts" separating the macros from each other. Since the dimensions and locations of the macros has previously been determined, it is necessary to determine if the placement is a slicing and if so, the slicing representation is determined. To efficiently determine whether a placement is a slicing, the concept of channels is needed. Given a placement of rectangles, channels are maximal horizontally or vertically extended strips of empty space between the macros. An example of a horizontal channel is shown in Fig. 2. The algorithm for the construction of the horizontal channels of placement consist of three main phases: 1) Initialization: An event queue is formed to contain

the y-coordinates of the bottomside (start event) and

the topside (end event) of each macro, as shown in Fig.

3.

2) Sorting: The queue is sorted by the y-coordinate,

with ties resolved arbitrarily, except that end events

precede start events.

(Image Omitted)

3) Sweeping: The events are processed in the sorted

order, as if sweeping over the macros by a horizontal

"sweep line", and the channels are maintained at each

event. This method relies on two basic structures: a)

the ordered list of macros intersecting the horizontal

sweep line, as shown in Fig. 3, and b) the channel

1

Page 2 of 4

structure, as shown in Fig. 2, which represents the

adjacency relationship between channels and macros.

Each horizontal channel has a bottomside and a topside

which are ordered lists of macros bordering on that

channel. Further, each channel has a start and an end

macro.

(Image Omitted)

At each moment of processing, the channel structure represents the channels of the placement corresponding

to the events met so far. The...