Patent ID: 7065730

Claim:
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.