Network on-chip topology generation

1. A computer-based method for synthesizing a Network-on-Chip (NoC), comprising:

determining physical data, device data, bridge data and traffic data based on an input specification for the NoC, the bridge data including a plurality of bridge ports and the traffic data including a plurality of traffic flows;

assigning a virtual channel (VC) to each traffic flow to create a plurality of VC assignments;

constructing a head of line (HoL) conflict graph (HCG) based on the traffic data and the VC assignments, the HCG including a plurality of nodes and a plurality of edges, each node representing a traffic flow and each edge representing an HoL conflict;

assigning a color to each HCG node to minimize HoL conflicts;

constructing a traffic graph (TG) for each color based on the physical data, the bridge data, the traffic data and the HCG;

generating a candidate topology for each color based on the respective TG, the candidate topology including the plurality of bridge ports, a plurality of routers and a plurality of connections;

merging the candidate topology for each color to create a merged candidate topology; and

merging routers within the merged candidate topology to generate a final topology for the NoC.

2. The computer-based method according to claim 1 , where:

the physical data include dimensions for the NoC;

the device data include a plurality of devices, and each device has a location and dimensions;

each bridge port is associated with one of the devices, and has a location and a data width; and

each traffic flow includes a source bridge port, a destination bridge port, a peak traffic rate, an average traffic rate, and a traffic class, the source bridge port and the destination bridge port being included in the bridge data.

3. The computer-based method according to claim 2 , where each traffic class includes a quality of service (QoS) and a latency sensitivity (LS).

4. The computer-based method according to claim 2 , where:

the TG includes a plurality of nodes and a plurality of edges that connect pairs of nodes;

each node is associated with a different bridge port;

each edge is associated with a set of traffic flows between two bridge ports; and

each set of traffic flows includes at least one traffic flow.

5. The computer-based method according to claim 4 , where said generating the candidate topology includes:

generating a grid based on the TG, the grid including a plurality of nodes and a plurality of intersections, where each node is located at a different intersection and is associated with a different bridge port;

adding the plurality of routers to the grid, where each router is located at an intersection not occupied by a node;

connecting adjacent nodes and routers to create an initial mesh having a plurality of connections;

calculating a weight for each connection based on the traffic data to create a weighted mesh;

determining a degree-constrained minimum-cost tree based on the weighted mesh, including removing one or more connections and one or more routers from the weighted mesh; and

generating the candidate topology from the degree-constrained minimum-cost tree.

6. The computer-based method according to claim 5 , further comprising:

generating a plurality of routes based on the final topology and the traffic data, including:

for each traffic flow, generating a route from the source bridge port to the destination bridge port, each route including one or more routers disposed along a connection path between the source bridge port and the destination bridge port.

7. The computer-based method according to claim 6 , further comprising:

generating a configuration/debug network including the bridge ports, the routers, the connections and the routes;

adding a physical clock domain crossing (PCDC) buffer to a connection between a bridge or router in a synchronous clock domain and an adjacent bridge or router in an asynchronous clock domain;

determining a link size for each router in each route;

adding a resizer between a bridge and a router with different link sizes or between adjacent routers with different link sizes;

adding pipeline and retiming components based on timing; and

generating an output specification for the NoC.

8. The computer-based method according to claim 1 , where an HoL conflict is defined as two traffic flows with different traffic classes that are assigned to the same VC.

9. The computer-based method according to claim 1 , where the HCG nodes are assigned a color to minimize the number of colors.

10. A system for synthesizing a Network-on-Chip (NoC), comprising:

a storage element to store an input specification; and

a processor, coupled to the storage element, configured to:

determine physical data, device data, bridge data and traffic data based on an input specification for the NoC, the bridge data including a plurality of bridge ports, and the traffic data including a plurality of traffic flows,

assign a virtual channel (VC) to each traffic flow to create a plurality of VC assignments,

construct a head of line (HoL) conflict graph (HCG) based on the traffic data and the VC assignments, the HCG including a plurality of nodes and a plurality of edges, each node representing a traffic flow and each edge representing an HoL conflict,

assign a color to each HCG node to minimize HoL conflicts,

construct a traffic graph (TG) for each color based on the physical data, the bridge data, the traffic data and the HCG,

generate a candidate topology for each color based on the respective TG, the candidate topology including the plurality of bridge ports, a plurality of routers and a plurality of connections,

merge the candidate topology for each color to create a merged candidate topology, and

merge routers within the merged candidate topology to generate a final topology for the NoC.

11. The system according to claim 10 , where:

the physical data include dimensions for the NoC;

the device data include a plurality of devices, and each device has a location and dimensions;

each bridge port is associated with one of the devices, and has a location and a data width; and

each traffic flow includes a source bridge port, a destination bridge port, a peak traffic rate, an average traffic rate, and a traffic class, the source bridge port and the destination bridge port being included in the bridge data.

12. The system according to claim 11 , where each traffic class includes a quality of service (QoS) and a latency sensitivity (LS).

13. The system according to claim 11 , where:

the TG includes a plurality of nodes and a plurality of edges that connect pairs of nodes;

each node is associated with a different bridge port;

each edge is associated with a set of traffic flows between two bridge ports; and

each set of traffic flows includes at least one traffic flow.

14. The system according to claim 13 , where said generate the candidate topology includes:

generate a grid based on the TG, the grid including a plurality of nodes and a plurality of intersections, where each node is located at a different intersection and is associated with a different bridge port;

add the plurality of routers to the grid, where each router is located at an intersection not occupied by a node;

connect adjacent nodes and routers to create an initial mesh having a plurality of connections;

calculate a weight for each connection based on the traffic data to create a weighted mesh;

determine a degree-constrained minimum-cost tree based on the weighted mesh, including removing one or more connections and one or more routers from the weighted mesh; and

generate the candidate topology from the degree-constrained minimum-cost tree.

15. The system according to claim 14 , where the processor is further configured to:

generate a plurality of routes based on the final topology and the traffic data, including:

for each traffic flow, generating a route from the source bridge port to the destination bridge port, each route including one or more routers disposed along a connection path between the source bridge port and the destination bridge port.

16. The system according to claim 15 , where the processor is further configured to:

generate a configuration/debug network including the bridge ports, the routers, the connections and the routes;

add a physical clock domain crossing (PCDC) buffer to a connection between a bridge or router in a synchronous clock domain and an adjacent bridge or router in an asynchronous clock domain;

determine a link size for each router in each route;

add a resizer between a bridge and a router with different link sizes or between adjacent routers with different link sizes;

add pipeline and retiming components based on timing; and

generate an output specification for the NoC.

17. The system according to claim 10 , where an HoL conflict is defined as two traffic flows with different traffic classes that are assigned to the same VC.

18. The system according to claim 10 , where the HCG nodes are assigned a color to minimize the number of colors.

19. A non-transitory computer-readable medium storing instructions that, when executed by a processor, cause the processor to synthesize a Network-on-Chip (NoC), the instructions comprising:

determining physical data, device data, bridge data and traffic data based on an input specification for the NoC, the bridge data including a plurality of bridge ports, and the traffic data including a plurality of traffic flows;

assigning a virtual channel (VC) to each traffic flow to create a plurality of VC assignments;

constructing a head of line (HoL) conflict graph (HCG) based on the traffic data and the VC assignments, the HCG including a plurality of nodes and a plurality of edges, each node representing a traffic flow and each edge representing an HoL conflict;

assigning a color to each HCG node to minimize HoL conflicts;

constructing a traffic graph (TG) for each color based on the physical data, the bridge data, the traffic data and the HCG;

generating a candidate topology for each color based on the respective TG, the candidate topology including the plurality of bridge ports, a plurality of routers and a plurality of connections;

merging the candidate topology for each color to create a merged candidate topology; and

merging routers within the merged candidate topology to generate a final topology for the NoC.

20. The non-transitory computer-readable medium according to claim 19 , where said generating the candidate topology includes:

generating a grid based on the TG, the grid including a plurality of nodes and a plurality of intersections, where each node is located at a different intersection and is associated with a different bridge port;

adding the plurality of routers to the grid, where each router is located at an intersection not occupied by a node;

connecting adjacent nodes and routers to create an initial mesh having a plurality of connections;

calculating a weight for each connection based on the traffic data to create a weighted mesh;

determining a degree-constrained minimum-cost tree based on the weighted mesh, including removing one or more connections and one or more routers from the weighted mesh; and

generating the candidate topology from the degree-constrained minimum-cost tree.