Delay optimization in signal routing

• US 6,886,152 B1
• Filed: 08/09/2002
• Issued: 04/26/2005
• Est. Priority Date: 08/09/2002
• Status: Expired due to Term

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Kong, Raymond
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US10/215,951
• Time in Patent Office: 991 Days
• Field of Search: 716/16, 716/18, 716/6, 716 2- 5, 716/17
• US Class Current: 716/128
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/347 Physical level, e.g. placement or routing
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A delay optimization algorithm has four major steps: (1) selecting signal connections to target for delay improvement; (2) unrouting all signals containing those candidate connections; (3) rerouting those signals, using a “load-balancing”heuristic; and (4) during rip-up and re-try routing, protecting wiring to all signal loads routed by the heuristic, including non-timing critical loads. Load balancing includes (a) applying a branching penalty on logic cell output wire segments, and (b) encouraging all non-route critical loads to route through a single buffered wire segment.

Claims

1. A method for optimizing implementation of a logic design in a programmable logic device comprising:

considering a first routing of the design in the programmable logic device;

determining at least one critical path resulting from the first routing;

selecting candidate connections not on the critical path;

identifying a common buffer through which at least a portion of the candidate connections can be routed; and

re-routing at least one of the candidate connections through the common buffer in order to reduce delay on the critical path.

2. The method of claim 1 wherein the step of considering a first routing comprises routing the design in the programmable logic device and saving routed connections.

3. The method of claim 1 further comprising:

checking whether performance of the design has improved after re-routing the at least one of the candidate connections; and

if the performance has not improved, restoring the at least one of the candidate connections; and

if the performance has improved, protecting the rerouted connection from again being re-routed.

4. The method of claim 1 wherein the candidate connections are selected from a group of connections having positive slack.

5. The method of claim 4 wherein the step of re-routing includes making sure that the at least one of the candidate connections still has positive slack.

6. A method for laying out a logic design of elements, signals, and timing constraints, each signal comprising at least one connection from a source to a load, onto a device having logic blocks, wire segments, and means for connecting the wire segments to form routes, that comprises the steps of:

routing a set of connections;

saving the routed connections;

computing slack at each connection in the design;

identifying a subset of connections that are candidates for improvement;

unrouting all signals containing a connection in the subset; and

applying a load-balancing heuristic to reroute each signal that includes a connection in the subset.

7. The method of claim 6 further comprising:

recomputing the slack at each connection;

checking whether the performance has improved;

if the performance has not improved, restoring the previously saved routing solution and ending the method;

if the performance has improved, continuing with the following substeps;

marking all routed connections in the subset as protected during a rip-up and retry phase;

checking whether predetermined conditions for exit have occurred; and

if the predetermined conditions have occurred, exiting the method, and otherwise looping back to the step of saving the routed connections.

8. The method of claim 7 wherein the predetermined conditions for exit include iterations having reached a preselected maximum.

9. The method of claim 7 wherein the predetermined conditions for exit include performance improvement being less than a preselected threshold.

10. The method of claim 6 wherein the step of applying a load-balancing heuristic comprises identifying at least one balance node downstream from the source that is driven by a buffer and routing a plurality of loads through the buffer.

11. The method of claim 10 wherein plural balance nodes are identified.

12. The method of claim 6 wherein the load-balancing heuristic for a signal includes the following steps:

applying a branching penalty on all logic cell output wire segments of the signal; and

rerouting the signal.

13. The method of claim 6 in which the subset comprises all connections on paths with timing constraints.

14. The method of claim 6 in which the subset comprises only those connections with slack less than a preselected threshold.

15. The method of claim 14 in which the preselected threshold is zero.

16. The method of claim 6 in which at least one iteration combines delay-based routing of connections with resource-based routing of connections.

17. The method of claim 6 in which first delay-based routing is performed, and then unrouted connections are routed.

18. The method of claim 6 in which first resource-based routing is performed, and then delay-based routing is performed.

19. The method of claim 6 in which performance improvement is measured by an increase of a minimum of computed slacks.

20. The method of claim 6 in which performance improvement is measured by an increase of a sum of computed slacks.

21. The method of claim 6 in which performance improvement is measured by an increase of a weighted average of a minimum and a sum of computed slacks.

22. A load-balancing heuristic for routing a signal in a programmable logic device including the following steps:

identifying a balance node;

unrouting all loads of a signal with a slack greater than a prespecified threshold and not routed through the balance node;

applying a branching penalty on all wire segments from a source of the signal to all other loads of the signal; and

rerouting the unrouted loads.

23. The method of claim 22 in which the step of identifying a balance node comprises the following substeps:

examining wire segments along a route from a source of the signal to a load of the signal with largest slack; and

identifying a first buffered wire segment along the route past the source.