Browse Prior Art Database

Optimal Algorithm for Finding Minimal Height Binary Slicing Tree for VLSI Chip Design

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

Publishing Venue

IBM

Related People

Luk, WK: AUTHOR [+3]

Abstract

A technique is described whereby an algorithm is used to optimize the computational requirements for deriving the maximum height of equivalent binary slicing tree representations, as related to the physical design of VLSI semiconductor chips. The concept is defined for general ordered trees, not only slicing trees, enabling the concept to be utilized in other applications. Physical design of a VLSI chip typically requires slicings be represented as binary trees, whereby the computational aspects of the algorithms involved depend upon the height of the binary slicing tree. Distinct steps are followed, so as to provide requirements of floorplanning, global wiring, detailed wiring and layout of 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 44% of the total text.

Page 1 of 4

Optimal Algorithm for Finding Minimal Height Binary Slicing Tree for VLSI Chip Design

A technique is described whereby an algorithm is used to optimize the computational requirements for deriving the maximum height of equivalent binary slicing tree representations, as related to the physical design of VLSI semiconductor chips. The concept is defined for general ordered trees, not only slicing trees, enabling the concept to be utilized in other applications. Physical design of a VLSI chip typically requires slicings be represented as binary trees, whereby the computational aspects of the algorithms involved depend upon the height of the binary slicing tree. Distinct steps are followed, so as to provide requirements of floorplanning, global wiring, detailed wiring and layout of macros. At the floorplanning and global wiring stages, the internal details of the macros may be ignored, and both the chip and the macros may be treated as rectangular objects. A floorplan is a partition, or rectangular dissection, of the entire chip region into rectangular regions.

(Image Omitted)

The concept described herein refers to the tree representation of a particular kind of floorplan, whereby the floorplan is a slicing, if it contains a single rectangle or if there exists a vertical or horizontal line that divides the slicing into two parts, each of which is a slicing, as shown in Fig. 1a. The binary slicing tree, as shown in Fig. 1b, depicts internal nodes V and H as the vertical and horizontal cut lines. The endings, or leaves, A to G correspond to the macros. A maximal slicing tree is represented as a slicing structure with maximal branching and is obtained recursively by partitioning a slicing into sub-slicings by the maximal possible number of vertical or horizontal cut lines at each level, up to the basic rectangles. There are at most two maximal slicing trees for a given floorplan: One with root V, which corresponds to the top-level cuts being vertical; and the other with root H, which corresponds to the top-level cuts being all horizontal.

It should be noted that a maximal slicing tree can be represented by many different binary slicing trees. In order to construct a minimal height binary representation of a maximal slicing tree, a conflict between the floorplanning and the global wiring phases in VLSI custom chip designs is defined as: Given a tree T of unbounded degree (referred to as K-ary) having N leaves, construct a binary tree T' such that each subtree of T corresponds to a subtree of T' with the same leaves and the height of T' is minimal. Figs. 2a and 2b represent the maximal slicing trees of types H and V for the floorplan of Fig. 1a. Note that the required correspondence between subtrees of T, the maximal slicing tree, and T', its binary representation, comes from the nodes each having a specific type V or
H. The concept, therefore provides a method that, given a K-ary tree with N leaves, obtain its binary representation in time...