Method for reducing wiring congestion in a VLSI chip design

A method of reducing wiring congestion in a placed and globally routed integrated circuit design comprising the steps of

• a) subdividing said integrated circuit design into a plurality of wiring tiles, each wiring tile separated from another by a wiring edge;
• b) identifying all of said wiring tiles to determine congested areas across the wiring edges of each of said wiring tiles;
• c) iteratively determining a congestion across each of said wiring edges of said integrated circuit design;
• d) successively performing a local transformation on at least one of said wiring edges to reduce said estimated congestion across said wiring edge;
• e) incrementally rerouting portions of said design wherein said local transformation was applied;
• f) determining that the incremental reroute has caused no new congestion problems and whether the congestion across said wiring edge has improved;
• g) determining whether any design constraint is violated by said local transformation;
• and
• h) accepting said local transformation only if no design constraint is determined to have been violated.

A method of reducing wiring congestion in a placed netlist of an integrated circuit chip comprising the steps of:

• a) executing a global routing of said placed netlist, said global routing including the step of subdividing said netlist into a plurality of wiring tiles, each wiring tile separated from another by a wiring edge;
• b) during the execution of step a), simultaneously determining congestion across each of said wiring edges of said integrated circuit design;
• c) performing a local transformation on at least one of said wiring edges to reduce said estimated congestion across said wiring edge;
• d) determining whether said congestion across said wiring edge has improved and whether said local transportation has caused new congestion problems or violations of design constraints;
• and
• e) accepting said local transformation only if no new congestion problems have been caused and no design constraint is determined to have been violated.

A method of reducing wiring congestion in a placed netlist of an integrated circuit chip comprising the steps of:

• a) executing a partial global routing of said placed netlist, said global routing including the step of subdividing said netlist into a plurality of wiring tiles, each wiring tile separated from another by a wiring edge;
• b) after the execution of step a), determining of congestion across each of said wiring edges of said integrated circuit design;
• c) performing a local transformation on at least one of said wiring edges to reduce said estimated congestion across said wiring edge;
• d) incrementally rerouting portions of said design wherein said local transformation was performed;
• e) determining whether said congestion across said wiring edge has improved and whether the incremental reroute has caused no new congestion problems;
• f) accepting said local transformation only if no new congestion problems have been caused and no design constraint is determined to have been violated;
• and
• g) repeating steps a) through f) until all the nets have been routed.

A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for of reducing wiring congestion in a placed and globally routed integrated circuit design, said method steps comprising:

• a) subdividing said integrated circuit design into a plurality of wiring tiles, each wiring tile separated from another by a wiring edge;
• b) determining a congestion across each of said wiring edges of said integrated circuit design;
• c) performing a local transformation on at least one of said wiring edges to reduce said congestion across said wiring edge;
• d) determining whether said congestion across said wiring edge has improved and whether the local transformation has caused new congestion problems or violations of design constraints;
• and
• e) accepting said local transformation only if no new congestion problems have been caused and no design constraint is determined to have been violated.