Method and apparatus for parallel simultaneous global and detail routing

A apparatus for routing nets in an integrated circuit design, said apparatus comprising:

• a. means for dividing the integrated circuit design with lines in a first direction and lines in a second direction;
• b. means for forming a routing graph having vertices and edges, wherein vertices correspond to locations where lines in the first direction cross lines in the second direction;
• c. means for routing nets as a function of said routing graph with parallel processors operating substantially simultaneously;
• d. means for determining the relative wire congestion among different areas in the integrated circuit design;
• e. means for rerouting nets passing though areas with a relatively high wire congestion.

A computer encoded storage medium with instructions thereon for routing nets in an integrated circuit design, said storage medium comprising:

• a. a computer encoded instruction for dividing the integrated circuit design with lines in a first direction and lines in a second direction;
• b. a computer encoded instruction for forming a routing graph having vertices and edges, wherein vertices correspond to locations where lines in the first direction cross lines in the second direction;
• c. a computer encoded instruction for routing nets as a function of said routing graph with parallel processors operating substantially simultaneously;
• d. a computer encoded instruction for determining the relative wire congestion among different areas in the integrated circuit design;
• e. a computer encoded instruction for rerouting nets passing though areas with a relatively high wire congestion.