Browse Prior Art Database

Optimal Algorithm for Determining Slicing Structure Placement of Circuit Chips

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

Publishing Venue

IBM

Related People

Luk, WK: AUTHOR [+5]

Abstract

A technique is described whereby an algorithm is used to determine the maximal slicing structure of macro placements as used in the automation of very large-scale integration (VLSI) circuit chip design. The algorithm is designed to be computationally efficient, in that in any given placement defined only as a set of non-intersecting rectangular macros, the slicing structure can be determined and later applied to other physical design algorithms developed for 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 48% of the total text.

Page 1 of 4

Optimal Algorithm for Determining Slicing Structure Placement of Circuit Chips

A technique is described whereby an algorithm is used to determine the maximal slicing structure of macro placements as used in the automation of very large-scale integration (VLSI) circuit chip design. The algorithm is designed to be computationally efficient, in that in any given placement defined only as a set of non-intersecting rectangular macros, the slicing structure can be determined and later applied to other physical design algorithms developed for 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. 1A. The algorithm described herein concerns a particular family of placements if it contains a single rectangle or if there exists a vertical or a horizontal (guillotine) cut that divides the placement into two parts, each of which is a slicing. Since the dimensions and locations of the macros have previously been determined, it is necessary to determine if the placement is a slicing, and if so, the corresponding slicing structure is to be determined. This problem generally occurs at the end of the initial floorplanning stage when the placement is modified interactively based on human evaluation of its quality, such as wiring congestion and overall shape of the chip. The design of the chip may change the location and shape of the macros many times as the optimal orientations of macros and global wiring are repeated.

As a result, the algorithm described herein provides an efficient mechanism of optimizing the slicing structure of a placement. To be able to efficiently construct the slicing structure of a placement, 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, as shown in Fig. 2. Cuts of a sub-placement are channels whose two ends are both outside of that sub-placement. Given a placement that is a slicing, the slicing structure is defined as hierarchy of sub-placements separated from each other by horizontal and vertical cuts, so that each bottom level sub- placement consists of a single macro. To obtain a unique slicing representation for a placement, the concept of a maximal slicing structure is considered, as shown in Fig. 1B. The maximal slicing structure of a placement is a hierarchy of sub-placements separated from each other by cuts such that each level of the hierarchy is split alternately by all possible vertical or horizontal cuts. The hierarchy ends when a sub-placement consists of a single macro. The slicing construction method relies on a global channel structure of the placement, construc...