Active region management techniques and associated methods...

Details Active region management techniques and associated methods... Active region management techniques and associated methods...

2002-03-28

2004-11-02

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

06813755

ABSTRACT:

BACKGROUND
1. Technical Field
This relates to the design and manufacture of very large scale integrated (“VLSI”) circuits and, more particularly, to an active region management technique suitable for use in conjunction with the design and manufacture of VLSI circuits.
2. Description of the Relevant Art
A VLSI circuit is typically composed of a plurality of layers, each having a plurality of generally rectangular shaped components positioned thereon, oriented in either the horizontal or vertical axis. VLSI circuit designers commonly refer to these generally rectangular shaped components as “component tiles” and to the generally rectangular shaped open spaces that surround the component tiles as “space tiles.” Component tiles that are to be connected on a VLSI circuit are said to form a “net”, while any component tile not connected to a particular net is considered to be an obstruction to that net. Two tiles are said to be “adjacent” if they touch along their edges and “overlapping” if there is even a single point located within the interior of both tiles. A set of tiles positioned within a routing area is said to be “maximal” if no two tiles are either overlapping or adjacent on their left or right edges.
One step in the design of a VLSI circuit is to select the wire paths that extend through the space tiles to connect the electrically equivalent component tiles that form nets. A current technique used to determine these paths utilizes a tile expansion algorithm. More specifically, clear space around the component tiles forming a net is fractured into maximal space tiles. Adjoining ones of these maximal space tiles are used to define the most efficient tile path between two components. The path of the actual connection between the components, known as the wire path, is then defined as the route through the space tile path from the component source tile to the component destination tile.
The aforementioned technique for selecting the wire paths for a VLSI circuit design suffers from two drawbacks, both of which may add to the cost of VLSI circuits manufactured in accordance with the design. First, if defined in accordance with the above-described manner, a tile path is not necessarily the optimal tile path through the clear space. Second, since the width of a tile path is typically much larger than the width of a wire path, multiple wire paths may exist through a given tile path. If the wire path located within the tile path is arbitrarily selected, the selected wire path is not necessarily the most efficient wire path potentially located within the tile path.
SUMMARY
Disclosed herein is a method and associated apparatus for determining an active region for a routing area having a plurality of components, each having a lower edge, an upper edge and a horizontal span, positioned thereon. A set of sweep lines, each extending along an upper or lower edge of at least one of the plurality of components, are determined for the routing area. A component tile density is determined along each one of the set of sweep lines. An active region for the routing area may then be generated from the component tile density along each one of the set of sweep lines. In determine component tile density along a sweep line, the component tile density is incremented by a pre-selected value for the horizontal span of a component tile upon encountering a lower edge thereof and decremented by the pre-selected value for the horizontal span of a component tile upon encountering an upper edge thereof.
The set of sweep lines may be arranged in an ascending order relative to an axis of the routing area and the component tile density determined, for the set of sweep lines, in the ascending order thereof. The first sweep line of the set of sweep lines is aligned with a lower edge of the routing area. For the first sweep line, the component tile density is set to zero at a first side edge of the routing area. A sweep is performed across the routing area and, for each lower edge or interior of a component tile encountered, the component tile density is incremented by the pre-selected value. For the next sweep line in the ascending order, the component tile density is initially set to that determined for the prior sweep line and subsequently adjusted for each lower or upper edge of a component tile encountered. Finally, for the uppermost sweep line in the ascending order, the component tile density is initially set to that determined for the prior sweep line and subsequently adjusted for each lower edge, interior or upper edge of a component tile encountered.


REFERENCES:
patent: 5748197 (1998-05-01), Guibas et al.
patent: 6071315 (2000-06-01), Ramamurthi et al.
patent: 6324673 (2001-11-01), Luo et al.
patent: 2003/0145301 (2003-07-01), Xing et al.
Lee et al., “A Gridless Area Router For Multichip Module Design,” IEEE, Aug. 8, 1999, pp. 206-209.
Cha et al., “Segra: A Very Fast General Area Router For Multichip Modules,” IEEE, May 1999, pp. 659-665.
Markl et al., “Processing Operations With Restrictions in Rdrams Without External Sorting: The Tetris Algorithm,” IEEE, Jul. 1998, pp. 1-10.
Wang et al., “Two Algorithams For a Reachability Problem in One-Dimensional Space,” IEEE, Jul. 1998, pp. 478-486.
Xing et al.; U.S. patent Ser. No. 10/109,125; Filed Mar. 28, 2002.
Xing et al.; U.S. patent Ser. No. 10/119,173; Filed Apr. 8, 2002.

Affiliated with

Also associated with

Rating

Active region management techniques and associated methods... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Active region management techniques and associated methods..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Active region management techniques and associated methods... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3343226