GROUP BASED ROUTING IN PROGRAMMABLE LOGIC DEVICE

• US 20150178437A1
• Filed: 12/20/2013
• Published: 06/25/2015
• Est. Priority Date: 12/20/2013
• Status: Active Grant

• Current Assignee: Lattice Semiconductor Corporation
• Original Assignee: Lattice Semiconductor Corporation
• Inventors: Zhang, Qinhai
• Granted Patent: US 9,152,756 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2119/12 Timing analysis or timing optimisation
• CPC Class Codes: G06F 30/3312 Timing analysis
• 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
• CPC Class Codes: G06F 30/398 Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] optical proximity correction [OPC] design processes G03F1/36

Abstract

Various techniques are provided to route connections within a programmable logic device (PLD). In one example, a method includes determining timing slacks for connections described in a netlist for a programmable logic device (PLD). The method also includes determining a plurality of priority groups. The connections are associated with one or more of the priority groups based on the timing slacks. The method also includes routing the connections associated with each priority group, from a highest priority group to a lowest priority group. Each priority group is iteratively routed to remove routing conflicts before lower priority groups are routed. Additional methods, systems, machine-readable mediums, and other techniques are also provided.

Claims

1. A computer-implemented method comprising:

determining timing slacks for connections described in a netlist for a programmable logic device (PLD);

determining a plurality of priority groups, wherein the connections are associated with one or more of the priority groups based on the timing slacks; and

routing the connections associated with each priority group, from a highest priority group to a lowest priority group, wherein each priority group is iteratively routed to remove routing conflicts before lower priority groups are routed.

2. The computer-implemented method of claim 1, wherein the iterative routing for each priority group comprises:

updating the timing slacks corresponding to routed connections; and

adjusting at least one of the plurality of priority groups based on the updated timing slacks.

3. The computer-implemented method of claim 1, wherein the iterative routing for at least one of the plurality of priority groups comprises signal-based routing negotiation.

4. The computer-implemented method of claim 3, wherein the signal-based routing negotiation comprises reusing a portion of a maze expansion wave for the connections that are associated with the at least one priority group and that are associated with a single signal.

5. The computer-implemented method of claim 1, wherein the iterative routing for at least one of the plurality of priority groups comprises connection-based routing negotiation.

6. The computer-implemented method of claim 1, wherein the plurality of priority groups are determined by percentages applied to a range of the timing slacks.

7. The computer-implemented method of claim 1, wherein the plurality of priority groups are determined by percentages applied to a total number of the connections.

8. The computer-implemented method of claim 1, wherein the lowest priority group includes all the connections.

9. The computer-implemented method of claim 1, wherein the determining timing slacks comprises determining positions of source and load nodes for the connections.

10. The computer-implemented method of claim 1, wherein the determining timing slacks comprises estimating signal propagation times between source and load nodes for the connections.

11. A system comprising:

a processor; and

a memory adapted to store a plurality of computer readable instructions which when executed by the processor are adapted to cause the system to perform a computer-implemented method comprising;

determining timing slacks for connections described in a netlist for a programmable logic device (PLD),

determining a plurality of priority groups, wherein the connections are associated with one or more of the priority groups based on the timing slacks, and

routing the connections associated with each priority group, from a highest priority group to a lowest priority group, wherein each priority group is iteratively routed to remove routing conflicts before lower priority groups are routed.

12. The system of claim 11, wherein the iterative routing for each priority group comprises:

updating the timing slacks corresponding to routed connections; and

adjusting at least one of the plurality of priority groups based on the updated timing slacks.

13. The system of claim 11, wherein the iterative routing for at least one of the plurality of priority groups comprises signal-based routing negotiation.

14. The system of claim 13, wherein the signal-based routing negotiation comprises reusing a portion of a maze expansion wave for the connections that are associated with the at least one priority group and that are associated with a single signal.

15. The system of claim 11, wherein the iterative routing for at least one of the plurality of priority groups comprises connection-based routing negotiation.

16. The system of claim 11, wherein the plurality of priority groups are determined by percentages applied to a range of the timing slacks.

17. The system of claim 11, wherein the plurality of priority groups are determined by percentages applied to a total number of the connections.

18. The system of claim 11, wherein the lowest priority group includes all the connections.

19. The system of claim 11, wherein the determining timing slacks comprises determining positions of source and load nodes for the connections and/or estimating signal propagation times between source and load nodes for the connections.

20. A non-transitory machine-readable medium storing a plurality of machine-readable instructions which when executed by one or more processors of a computer system are adapted to cause the computer system to perform a computer-implemented method comprising:

determining timing slacks for connections described in a netlist for a programmable logic device (PLD);

determining a plurality of priority groups, wherein the connections are associated with one or more of the priority groups based on the timing slacks; and

routing the connections associated with each priority group, from a highest priority group to a lowest priority group, wherein each priority group is iteratively routed to remove routing conflicts before lower priority groups are routed.