Back to results
US 7,065,730 B2Granted
Porosity aware buffered steiner tree construction
AssigneeInternational Business Machines Corporation
InventorsCharles Jay Alpert, Rama Gopal Gandham, Jiang Hu, Stephen Thomas Quay
Life of this patent
Estimating the term…
Abstract
A method, computer program product, and data processing system for porosity-aware buffered Steiner tree construction are disclosed. A preferred embodiment begins with a timing-driven Steiner tree generated without regard for porosity, then applies a plate-based adjustment guided by length-based buffer insertion. After performing localized blockage avoidance, the resulting tree is then passed to a buffer placement algorithm, such as van Ginneken's algorithm, to obtain a porosity-aware buffered Steiner tree.
Claims8
A method comprising:
- generating an initial Steiner tree connecting a source node to at least one sink node in an integrated circuit layout, wherein the initial Steiner tree is generated according to heuristics that do not take into account density of regions in the integrated circuit layout;
- adjusting a topology of the initial Steiner tree so as to avoid dense regions in the integrated circuit layout, thus obtaining a porosity-aware Steiner tree;
- and
- inserting buffers into the porosity-aware Steiner tree;
- wherein adjusting the initial Steiner tree includes:
- determining a first plate, wherein the first plate includes a plurality of tiles in a neighborhood of a first node in the initial Steiner tree;
- determining a second plate, wherein the second plate includes a plurality of tiles in a neighborhood of a second node in the initial Steiner tree, wherein the second node is connected to the first node via a wiring path in the initial Steiner tree;
- generating node candidate solutions for adjustment of the first node by enumerating locations within the first plate;
- generating wiring path candidate solutions for adjustment of the wiring path by forming alternative paths from the candidate solutions for adjustment of the first node;
- calculating a cost function associated with each of the wiring path candidate solutions;
- and
- choosing a new location for to first node and a new wiring path by choosing a minimum-cost candidate solution from the wiring path candidate solutions.
9 more elements
A computer program product in at least one computer-readable medium, comprising functional descriptive material that, when executed by a computer, enables the computer to perform acts including:
- generating an initial Steiner tree connecting a source node to at least one sink node in an integrated circuit layout, wherein the initial Steiner tree is generated according to heuristics that do not take into account density of regions in the integrated circuit layout;
- adjusting a topology of the initial Steiner tree so as to avoid dense regions in the integrated circuit layout, thus obtaining a porosity-aware Steiner tree;
- and
- inserting buffers into the porosity-aware Steiner tree;
- wherein adjusting the initial Steiner tree includes:
- determining a first plate, wherein the first plate includes a plurality of tiles in a neighborhood of a first node in the initial Steiner tree;
- determining a second plate, wherein the second plate includes a plurality of tiles in a neighborhood of a second node in the initial Steiner tree, wherein the second node is connected to the first node via a wiring path in the initial Steiner tree;
- generating node candidate solutions for adjustment of the first node by enumerating locations within the first plate;
- generating wiring path candidate solutions for adjustment of the wiring path by forming alternative paths from the candidate solutions for adjustment of the first node;
- calculating a cost function associated with each of the wiring path candidate solutions;
- and
- choosing a new location for the first node and a new wiring path by choosing a minimum-cost candidate solution from the wiring path candidate solutions.
9 more elements
A data processing system comprising:
- means for generating an initial Steiner tree connecting a source node to at least one sink node in an integrated circuit layout, wherein the initial Steiner tree is generated according to heuristics that do not take into account density of regions in the integrated circuit layout;
- means for adjusting a topology of the initial Steiner tree so as to avoid dense regions in the integrated circuit layout, thus obtaining a porosity-aware Steiner tree;
- and
- means for inserting buffers into the porosity-aware Steiner tree;
- wherein adjusting the initial Steiner tree includes:
- means for determining a first plate, wherein the first plate includes a plurality of tiles in a neighborhood of a first node in the initial Steiner tree;
- means for determining a second plate, wherein the second plate includes a plurality of tiles in a neighborhood of a second node in the initial Steiner tree, wherein the second node is connected to the first node via a wiring path in the initial Steiner tree;
- means for generating node candidate solutions for adjustment of the first node by enumerating locations within the first plate;
- means for generating wiring path candidate solutions for adjustment of the wiring path by forming alternative paths from the candidate solutions for adjustment of the first node;
- means for calculating a cost function associated with each of the wiring path candidate solutions;
- and
- means for choosing a new location for the first node and a new wiring path by choosing a minimum-cost candidate solution from the wiring path candidate solution.
9 more elements
Dependencies are inferred from the claim text.