Method and apparatus for routing an integrated circuit

1. A method of routing a circuit having a set of nets and a set of circuit elements, the circuit specified with a slicing tree and a set of linear constraints, the method comprising:

finding paths for the set of nets using a minimum-spanning-tree algorithm applied to a floorplan for each net of the set of nets, the floorplan derived from the slicing tree;

routing the nets as conductors within channels of the floorplan,

linear programming being used to ensure that the conductors have locations that satisfy the constraints of the set of linear constraints, the paths being used to influence the nets' routes and,

using linear programming to re-route the conductors along a second coordinate axis, the linear programming used to re-route the conductors along a second coordinate axis having constraints that regard the conductors as being frozen at their coordinates along a first coordinate axis.

2. The method of claim 1 further comprising:

using linear programming to re-route the conductors along the first coordinate axis, the linear programming used to re-route the conductors along the first coordinate axis having constraints that regard the conductors as being frozen at their coordinates for the second coordinate axis.

3. The method of claim 2 further comprising:

re-routing the conductors using linear programming with a modified set of constraints, the modified set of constraints relating to DRC violations resulting from the routing of the conductors, the modified set of constraints derived from the set of linear constraints.

4. The method of claim 3 further comprising:

altering coordinates of the conductors to satisfy parasitic matching requirements of the nets.

5. A machine-readable medium embodying instructions which, when executed by a processor, cause the processor to perform a method of routing a circuit having a set of nets and a set of circuit elements, the circuit specified with a slicing tree and a set of linear constraints, the method comprising:

finding paths for the set of nets using a minimum-spanning-tree algorithm applied to a floorplan for each net of the set of nets, the floorplan derived from the slicing tree;

routing the nets as conductors within channels of the floorplan, linear programming being used to ensure that the conductors have locations that satisfy the constraints of the set of linear constraints, the paths being used to influence the nets' routes; and,

using linear programming to re-route the conductors along a second coordinate axis, the linear programming used to re-route the conductors along a second coordinate axis having constraints that regard the conductors as being frozen at their coordinates along a first coordinate axis.

6. The machine-readable medium of claim 5 wherein the method further comprises:

using linear programming to re-route the conductors along the first coordinate axis, the linear programming used to re-route the conductors along the first coordinate axis having constraints that regard the conductors as being frozen at their coordinates for the second coordinate axis.

7. The machine-readable medium of claim 6 wherein the method further comprises:

re-routing the conductors using linear programming with a modified set of constraints, the modified set of constraints relating to DRC violations resulting from the routing of the conductors, the modified set of constraints derived from the set of linear constraints.

8. The machine-readable medium of claim 7 wherein the method further comprises:

altering coordinates of the conductors to satisfy parasitic matching requirements of the nets.

9. A system comprising:

a processor;

a control hub coupled to the processor;

an i/o hub coupled to the control hub;

computer readable media at least including memory coupled to the control hub;

a medium interface coupled to the i/o hub;

wherein the processor is to execute instructions retrieved from the machine readable medium to determine a circuit's routing, the circuit having a set of nets and a set of circuit elements, the circuit specified with a slicing tree and a set of linear constraints, the processor to execute the instructions:

to find paths for the set of nets on using a minimum-spanning-tree solution algorithm applied to a floorplan for each net of the set of nets, the floorplan derived from the slicing tree,

to route the nets as conductors within channels of the floorplan, linear programming being used to ensure that the conductors have locations that satisfy the constraints of the set of linear constraints, the paths being used to influence the nets' routes, and,

to use linear programming to re-route the conductors along a second coordinate axis, the linear programming used to re-route the conductors along a second coordinate axis having constraints that regard the conductors as being frozen at their coordinates along a first coordinate axis.

10. The system of claim 9 wherein the processor is further to use linear programming to re-route the conductors along the first coordinate axis, the linear programming used to re-route the conductors along the first coordinate axis having constraints that regard the conductors as being frozen at their coordinates for the second coordinate axis.

11. The system of claim 10 wherein the processor is further to re-route the conductors using linear programming with a modified set of constraints, the modified set of constraints relating to DRC violations resulting from the routing of the conductors, the modified set of constraints derived from the set of linear constraints.

12. The system of claim 11 wherein the processor is further to alter coordinates of the conductors to satisfy parasitic matching requirements of the nets.