Placement, routing, and deadlock removal for network-on-chip using integer linear programming

• US 10,565,346 B1
• Filed: 06/30/2017
• Issued: 02/18/2020
• Est. Priority Date: 06/30/2017
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Suthar, Vishal, Gaitonde, Dinesh D., Gupta, Amit, Singh, Jinny
• Primary Examiner(s): Memula, Suresh
• Application Number:
  US15/640,009
• Time in Patent Office: 963 Days
• Field of Search: 716104
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 2115/02 System on chip [SoC] design
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Implementing a circuit design can include generating an integer linear programming (ILP) formulation for a routing problem by determining constraints for implementing nets of a circuit design within a programmable network-on-chip (NOC) of an integrated circuit, wherein the constraints include placement constraints and routability constraints for the nets. The nets can be simultaneously placed and routed by executing an ILP solver using a processor to minimize an objective function of the ILP formulation while observing the constraints. The ILP solver maps logical units of the nets to interface circuits of the programmable NOC concurrently with mapping the nets to channels of the programmable NOC.

Claims

1. A method of implementing a circuit design, comprising:

generating, using a processor, an integer linear programming formulation for a routing problem by determining constraints for implementing nets of a circuit design within a programmable network-on-chip of an integrated circuit, wherein the constraints include placement constraints and routability constraints for the nets; and

simultaneously placing and routing the nets by executing, using the processor, an integer linear programming solver using a processor to minimize an objective function of the integer linear programming formulation while observing the constraints, wherein the integer linear programming solver maps logical units of the nets to interface circuits of the programmable network-on-chip concurrently with mapping the nets to channels of the programmable network-on-chip.

2. The method of claim 1, wherein the placement constraints specify that:

each logical unit that is a logical master unit must be mapped to exactly one master circuit;

each logical unit that is a logical slave unit must be mapped to exactly one slave circuit;

each master circuit is mapped to a maximum of one logical master unit; and

each slave circuit is mapped to a maximum of one logical slave unit.

3. The method of claim 1, wherein the routability constraints specify that for each channel of the programmable network-on-chip, if a net is mapped to the channel, the net is mapped to one switch driven by the channel and one switch driving the channel.

4. The method of claim 1, wherein the objective function depends upon latency of all nets through the programmable network-on-chip.

5. The method of claim 1, wherein determining constraints further comprises:

determining a latency constraint for each net specifying that a sum of latencies of the switches used by the net does not exceed a required latency of the net.

6. The method of claim 1, wherein determining constraints further comprises:

determining a bandwidth constraint for each channel specifying that a sum of required bandwidths of all nets mapped to the channel does not exceed a maximum bandwidth of the channel.

7. The method of claim 1, further comprising:

resolving deadlocks by determining a cycle within the programmable network-on-chip, determining which of the nets are included in the cycle, and assigning a plurality of nets included in the cycle to virtual channels, where at least two of the plurality of nets included in the cycle are assigned to different virtual channels.

8. The method of claim 7, wherein resolving deadlocks further comprises:

in response to determining that the cycle is not broken, assigning a channel restriction to a low priority net of the plurality of nets included in the cycle.

9. A system, comprising:

a memory configured to store program code; and

a processor coupled to the memory, wherein the processor, in response to executing the program code, is configured to initiate operations for implementing a circuit design including;

generating an integer linear programming formulation for a routing problem by determining constraints for implementing nets of a circuit design within a programmable network-on-chip of an integrated circuit, wherein the constraints include placement constraints and routability constraints for the nets; and

simultaneously placing and routing the nets by executing an integer linear programming solver to minimize an objective function of the integer linear programming formulation while observing the constraints, wherein the integer linear programming solver maps logical units of the nets to interface circuits of the programmable network-on-chip concurrently with mapping the nets to channels of the programmable network-on-chip.

10. The system of claim 9, wherein the placement constraints specify that:

each logical unit that is a logical master unit must be mapped to exactly one master circuit;

each logical unit that is a logical slave unit must be mapped to exactly one slave circuit;

each master circuit is mapped to a maximum of one logical master unit; and

each slave circuit is mapped to a maximum of one logical slave unit.

11. The system of claim 9, wherein the routability constraints specify that for each channel of the programmable network-on-chip, if a net is mapped to the channel, the net is mapped to one switch driven by the channel and one switch driving the channel.

12. The system of claim 9, wherein the objective function determines structural latency of all nets through the programmable network-on-chip.

13. The system of claim 9, wherein determining constraints further comprises:

determining a latency constraint for each net specifying that a sum of latencies of the switches used by the net does not exceed a required latency of the net.

14. The system of claim 9, wherein determining constraints further comprises:

determining a bandwidth constraint for each channel specifying that a sum of required bandwidths of all nets mapped to the channel does not exceed a maximum bandwidth of the channel.

15. The system of claim 9, wherein the processor is configured to initiate operations further including:

resolving deadlocks by determining a cycle within the programmable network-on-chip, determining which of the nets are included in the cycle, and assigning a plurality of nets included in the cycle to virtual channels, where at least two of the plurality of nets included in the cycle are assigned to different virtual channels.

16. The system of claim 15, wherein resolving deadlocks further comprises:

in response to determining that the cycle is not broken, assigning a channel restriction to a low priority net of the plurality of nets included in the cycle.

17. A computer program product comprising a computer readable storage medium having program code stored thereon, the program code executable by a processor to perform operations for implementing a circuit design, comprising:

generating an integer linear programming formulation for a routing problem by determining constraints for implementing nets of a circuit design within a programmable network-on-chip of an integrated circuit, wherein the constraints include placement constraints and routability constraints for the nets; and

simultaneously placing and routing the nets by executing an integer linear programming solver to minimize an objective function of the integer linear programming formulation while observing the constraints, wherein the integer linear programming solver maps logical units of the nets to interface circuits of the programmable network-on-chip concurrently with mapping the nets to channels of the programmable network-on-chip.

18. The computer program product of claim 17, wherein determining constraints further comprises:

determining a latency constraint for each net specifying that a sum of latencies of the switches used by the net does not exceed a required latency of the net.

19. The computer program product of claim 17, wherein determining constraints further comprises:

determining a bandwidth constraint for each channel specifying that a sum of required bandwidths of all nets mapped to the channel does not exceed a maximum bandwidth of the channel.

20. The computer program product of claim 17, wherein the program code is executable by the processor to perform operations further comprising:

resolving deadlocks by determining a cycle within the programmable network-on-chip, determining which of the nets are included in the cycle, and assigning a plurality of nets included in the cycle to virtual channels, where at least two of the plurality of nets included in the cycle are assigned to different virtual channels.