Method and apparatus for generating steiner trees using simultaneous blockage avoidance, delay optimization and design density management

A computer program product in a computer readable medium for optimizing routing and buffer insertion in an integrated circuit design, comprising:

• first instructions for generating an initial timing-driven Steiner tree connecting a source node to at least one sink node in an integrated circuit design, wherein the initial timing-driven Steiner tree is generated without accounting for densities of regions in the integrated circuit design;
• second instructions for dividing the initial timing-driven Steiner tree into a plurality of tiles;
• third instructions for associating a cost with each tile of the plurality of tiles, wherein the cost includes a timing component and an environmental component;
• and
• fourth instructions for adjusting a portion of the topology of the initial timing-driven Steiner tree based on the cost associated with each tile in the plurality of tiles, thereby generating an adjusted Steiner tree topology.

An apparatus for optimizing routing and buffer insertion in an integrated circuit design, comprising:

• means for generating an initial timing-driven Steiner tree connecting a source node to at least one sink node in an integrated circuit design, wherein the initial timing-driven Steiner tree is generated without accounting for densities of regions in the integrated circuit design;
• means for dividing the initial timing-driven Steiner tree into a plurality of tiles;
• means for associating a cost with each tile of the plurality of tiles, wherein the cost includes a timing component and an environmental component;
• and
• means for adjusting a portion of the topology of the initial timing-driven Steiner tree based on the cost associated with each tile in the plurality of tiles, thereby generating an adjusted Steiner tree topology.