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 physical data including dimensions for the NoC, the device data including a plurality of devices, each device having a location and dimensions, the bridge data including a plurality of bridge ports, each bridge port being associated with one of the devices and having a location, the traffic data including a plurality of traffic flows, each traffic flow having a packet rate;

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

generating a baseline topology based on the physical data, the device data, the bridge data, the traffic data and the VC assignments, the baseline topology including the plurality of bridge ports, a plurality of routers and a plurality of connections, each router having one or more input ports and one or more output ports;

identifying each router that has at least one output port that is shared by traffic flows that are received on at least two input ports;

for each identified router:

calculating a minimum frequency for the identified router based on the packet rates of the traffic flows received by the identified router, and

assigning a clock domain to the identified router based on the minimum frequency for the identified router;

balancing the traffic flows received by the identified routers based on the packet rates of the traffic flows; and

generating a final topology based on the baseline topology and the balanced traffic flows for the identified routers.

2. The computer-based method according to claim 1 , where each output port that is shared transmits the traffic flows over a single VC.

3. The computer-based method according to claim 2 , where said calculating a minimum frequency for the identified router includes:

for each output port:

summing the packet rates of the traffic flows received on the input ports that share the output port to generate a total output packet rate, and

calculating a minimum frequency for the output port based on the total output packet rate;

determining a maximum frequency of the minimum frequencies of the output ports; and

setting the minimum frequency for the identified router to the maximum frequency.

4. The computer-based method according to claim 3 , further comprising:

adding a physical clock domain crossing (PCDC) buffer to each link between two routers that are assigned to different clock domains;

determining normalized packet rates for the traffic flows between the bridge ports, routers and PCDC buffers based on the assigned clock domains; and

identifying clock domain violations for the identified routers based on the assigned clock domains and the normalized packet rates.

5. The computer-based method according to claim 4 , where said balancing the traffic flows includes:

identifying packet rate imbalances for the identified routers based on the normalized packet rates;

determining a performance cost based on the assigned clock domains and the normalized packet rates; and

correcting the clock domain violations and the packet rate imbalances based on the performance cost.

6. The computer-based method according to claim 5 , where the performance cost includes a router clock domain violation cost and a packet rate balancing cost.

7. The computer-based method according to claim 6 , where said correcting the clock domain violations and the packet rate imbalances includes at least one of:

assigning a different clock domain to one or more identified routers;

routing one or more traffic flows to a different identified router; and

adding one or more identified routers.

8. The computer-based method according to claim 1 , where said generating a baseline topology includes:

constructing a head of line (HoL) conflict graph (HCG) based on the traffic data and the VC assignments, including:

creating a plurality of nodes, each node representing a traffic flow,

creating a plurality of edges, each edge representing an HoL conflict, and

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

constructing a plurality of traffic graphs (TGs) based on the physical data, the bridge data, the traffic data and the HCG, including constructing a TG for each color of the HCG;

generating a candidate topology for each TG, each candidate topology including at least two bridge ports, at least one router and at least two connections;

merging the candidate topologies to create the baseline topology; and

merging routers within the baseline topology.

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

a memory to store an input specification for a NoC; and

a processor, coupled to the memory, configured to:

determine physical data, device data, bridge data and traffic data based on an input specification for the NoC, the physical data including dimensions for the NoC, the device data including a plurality of devices, each device having a location and dimensions, the bridge data including a plurality of bridge ports, each bridge port being associated with one of the devices and having a location, the traffic data including a plurality of traffic flows, each traffic flow having a packet rate,

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

generate a baseline topology based on the physical data, the device data, the bridge data, the traffic data and the VC assignments, the baseline topology including the plurality of bridge ports, a plurality of routers and a plurality of connections, each router having one or more input ports and one or more output ports,

identify each router that has at least one output port that is shared by traffic flows that are received on at least two input ports,

for each identified router:

calculate a minimum frequency for the identified router based on the packet rates of the traffic flows received by the identified router, and

assign a clock domain to the identified router based on the minimum frequency for the identified router,

balance the traffic flows received by the identified routers based on the packet rates of the traffic flows, and

generate a final topology based on the baseline topology and the balanced traffic flows for the identified routers.

10. The system according to claim 9 , where each output port that is shared transmits the traffic flows over a single VC.

11. The system according to claim 10 , where said calculate a minimum frequency for the identified router includes:

for each output port:

sum the packet rates of the traffic flows received on the input ports that share the output port to generate a total output packet rate, and

calculate a minimum frequency for the output port based on the total output packet rate;

determine a maximum frequency of the minimum frequencies of the output ports; and

set the minimum frequency for the identified router to the maximum frequency.

12. The system according to claim 11 , where the processor is further configured to:

add a physical clock domain crossing (PCDC) buffer to each link between two routers that are assigned to different clock domains;

determine normalized packet rates for the traffic flows between the bridge ports, routers and PCDC buffers based on the assigned clock domains; and

identify clock domain violations for the identified routers based on the assigned clock domains and the normalized packet rates.

13. The system according to claim 12 , where said balance the traffic flows includes:

identify packet rate imbalances for the identified routers based on the normalized packet rates;

determine a performance cost based on the assigned clock domains and the normalized packet rates; and

correct the clock domain violations and the packet rate imbalances based on the performance cost.

14. The system according to claim 13 , where the performance cost includes a router clock domain violation cost and a packet rate balancing cost.

15. The system according to claim 14 , where said correct the clock domain violations and the packet rate imbalances includes at least one of:

assign a different clock domain to one or more identified routers;

route one or more traffic flows to a different identified router; and

add one or more identified routers.

16. The system according to claim 9 , where said generate a baseline topology includes:

construct a head of line (HoL) conflict graph (HCG) based on the traffic data and the VC assignments, including:

create a plurality of nodes, each node representing a traffic flow,

create a plurality of edges, each edge representing an HoL conflict, and

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

construct a plurality of traffic graphs (TGs) based on the physical data, the bridge data, the traffic data and the HCG, including constructing a TG for each color of the HCG;

generate a candidate topology for each TG, each candidate topology including at least two bridge ports, at least one router and at least two connections;

merge the candidate topologies to create the baseline topology; and

merge routers within the baseline topology.

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

receiving traffic data, virtual channel (VC) assignments and a baseline topology, the traffic data including a plurality of traffic flows, the baseline topology including a plurality of bridge ports, a plurality of routers and a plurality of connections, each router having one or more input ports and one or more output ports, each traffic flow having a packet rate;

identifying each router that has at least one output port that is shared by traffic flows that are received on at least two input ports;

for each identified router:

calculating a minimum frequency for the identified router based on the packet rates of the traffic flows received by the identified router, and

assigning a clock domain to the identified router based on the minimum frequency for the identified router;

balancing the traffic flows received by the identified routers based on the packet rates of the traffic flows; and

generating a final topology based on the baseline topology and the balanced traffic flows for the identified routers.

18. The computer-based method according to claim 17 , where each output port that is shared transmits the traffic flows over a single VC, and said calculating a minimum frequency for the identified router includes:

for each output port:

summing the packet rates of the traffic flows received on the input ports that share the output port to generate a total output packet rate, and

calculating a minimum frequency for the output port based on the total output packet rate;

determining a maximum frequency of the minimum frequencies of the output ports; and

setting the minimum frequency for the identified router to the maximum frequency.

19. The computer-based method according to claim 18 , further comprising:

adding a physical clock domain crossing (PCDC) buffer to each link between two routers that are assigned to different clock domains;

determining normalized packet rates for the traffic flows between the bridge ports, routers and PCDC buffers based on the assigned clock domains; and

identifying clock domain violations for the identified routers based on the assigned clock domains and the normalized packet rates,

where said balancing the traffic flows includes:

identifying packet rate imbalances for the identified routers based on the normalized packet rates,

determining a performance cost based on the assigned clock domains and the normalized packet rates, the performance cost including a router clock domain violation cost and a packet rate balancing cost, and

correcting the clock domain violations and the packet rate imbalances based on the performance cost.

20. The computer-based method according to claim 19 , where said correcting the clock domain violations and the packet rate imbalances includes at least one of:

assigning a different clock domain to one or more identified routers;

routing one or more traffic flows to a different identified router; and

adding one or more identified routers.