# US 11,310,169 B2 · Network-on-chip topology generation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,310,169 B2
- Document ID: US11310169B2
- Status: Granted
- Kind: B2
- Application number: 17/152,034
- Filed: 2021-01-19
- Published: 2021-05-27
- Granted: 2022-04-19
- Earliest claimed: 2019-07-22
- Assignees: Arm Limited
- Applicants: Arm Limited
- Inventors: Honnahuggi Harinath Venkata Naga Ambica Prasad; Nitin Kumar Agarwal; Anup Gangwar; Narayana Sri Harsha Gade; Ravishankar Sreedharan
- Web page: https://patentgrep.com/patent/US11310169B2

## CPC

- G06F 15/7825: {Globally asynchronous, locally synchronous, e.g. network on chip}
- H04L 41/0806: for initial configuration or provisioning, e.g. plug-and-play
- H04L 41/0873: Checking configuration conflicts between network elements
- H04L 41/0895: Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
- H04L 41/12: Discovery or management of network topologies
- H04L 41/40: using virtualisation of network functions or resources, e.g. SDN or NFV entities
- H04L 41/5022: by giving priorities, e.g. assigning classes of service
- H04L 43/0852: Delays
- H04L 43/0894: Packet rate
- H04L 45/02: Topology update or discovery
- H04L 45/12: Shortest path evaluation
- H04L 45/586: of virtual routers
- H04L 47/24: Traffic characterised by specific attributes, e.g. priority or QoS
- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- H04L 49/109: Integrated on microchip, e.g. switch-on-chip
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The present disclosure provides a computer-based method and system for synthesizing a NoC. Traffic data is determined or received, and a baseline topology is generated or received. For each router in the baseline topology, a number of edge virtual channel (EVC) combinations is determined, the transmittablility of the traffic classes are determined, and, when the traffic classes are not transmittable, the router is identified. A traffic class affinity graph (TCAG) is generated for each identified router. Traffic class combinations are generated for the identified routers based on the TCAGs and EVC combinations. The traffic classes of the identified routers are merged based on the traffic class combinations. A final EVC combination for each identified router is determined based on the merged traffic classes. A final topology is generated based, at least in part, on the merged traffic classes and the final EVC combinations for the identified routers.

## Claims

### Claim 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 including one or more traffic classes;
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 including a number of ports, each router configured to process a plurality of traffic classes and to support a maximum number of VCs;
for each router:
determining a number of edge virtual channel (EVC) combinations, each EVC combination including a number of available edges and a number of available VCs, each available edge corresponding to a different port,
determining whether the traffic classes are transmittable or receivable by at least one EVC combination, and
when the traffic classes are determined not transmittable or receivable, identifying the router;
generating a traffic class affinity graph (TCAG) for each identified router;
generating traffic class combinations for the identified routers based on the TCAGs and the EVC combinations;
merging traffic classes of the identified routers based on the traffic class combinations;
determining a final EVC combination for each identified router based on the merged traffic classes; and
generating a final topology based, at least in part, on the merged traffic classes and the final EVC combinations for the identified routers.

### Claim 2 (depends on 1)

The computer-based method according to claim 1, where, for each router:
the number of available edges is equal to or less than the number of ports; and
the number of available VCs is equal to or less than the maximum number of VCs.

### Claim 3 (depends on 2)

The computer-based method according to claim 2, where the traffic class combinations are generated by k-way minimum cost partitioning for each identified router, where k is the number of EVC combinations for the identified router.

### Claim 4 (depends on 3)

The computer-based method according to claim 3, where said generating traffic class combinations includes:
adding one or more routers to the baseline topology, each added router configured to process one or more traffic classes of the identified routers;
determining a number of EVC combinations for each added router;
generating a TCAG for each added router; and
identifying each added router.

### Claim 5 (depends on 1)

The computer-based method according to claim 1, where the TCAG for each identified router includes:
a plurality of nodes, each node associated with a different traffic class processed by the identified router; and
a plurality of edges, each edge connecting a different pair of nodes, each edge having a weight that indicates a degree to which the traffic classes of the respective nodes are combinable.

### Claim 6 (depends on 5)

The computer-based method according to claim 5, where each edge weight is a traffic-class affinity metric that is determined based on one or more affinity characteristics of the traffic classes of the respective nodes.

### Claim 7 (depends on 6)

The computer-based method according to claim 6, where:
the affinity characteristics include at least one of a latency sensitivity (LS), a watermark, a packet rate and a burst length; and
each traffic class includes at least one of an LS value, a watermark value, a packet rate value, and a burst length value.

### Claim 8 (depends on 7)

The computer-based method according to claim 7, where the traffic-class affinity metric includes at least one of a comparison of the LS values of the respective nodes, a comparison of the watermark values of the respective nodes, an evaluation of the packet rate values of the respective nodes, and an evaluation of the burst length values of the respective nodes.

### Claim 9 (depends on 8)

The computer-based method according to claim 8, where the traffic-class affinity metric is an integer value that includes a plurality of bit fields, each bit field including one or more bits corresponding to a different affinity characteristic.

### Claim 10 (depends on 1)

The computer-based method according to claim 1, where said generating the 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.

### Claim 11

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 the input specification, 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 including one or more traffic classes,
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 including a number of ports, each router configured to process a plurality of traffic classes and to support a maximum number of VCs,
for each router:
determine a number of edge virtual channel (EVC) combinations, each EVC combination including a number of available edges and a number of available VCs, each available edge corresponding to a different port,
determine whether the traffic classes are transmittable or receivable by at least one EVC combination, and
when the traffic classes are determined not transmittable or receivable, identify the router,
generate a traffic class affinity graph (TCAG) for each identified router,
generate traffic class combinations for the identified routers based on the TCAGs and the EVC combinations,
merge traffic classes of the identified routers based on the traffic class combinations,
determine a final EVC combination for each identified router based on the merged traffic classes, and
generate a final topology based, at least in part, on the merged traffic classes and the final EVC combinations for the identified routers.

### Claim 12 (depends on 11)

The system according to claim 11, where:
for each router, the number of available edges is equal to or less than the number of ports, and the number of available VCs is equal to or less than the maximum number of VCs; and
the traffic class combinations are generated by k-way minimum cost partitioning for each identified router, where k is the number of EVC combinations for the identified router.

### Claim 13 (depends on 12)

The system according to claim 12, where said generate traffic class combinations includes:
add one or more routers to the baseline topology, each added router configured to process one or more traffic classes of the identified routers;
determine a number of EVC combinations for each added router;
generate a TCAG for each added router; and
identify each added router.

### Claim 14 (depends on 11)

The system according to claim 11, where the TCAG for each identified router includes:
a plurality of nodes, each node associated with a different traffic class processed by the identified router; and
a plurality of edges, each edge connecting a different pair of nodes, each edge having a weight that indicates a degree to which the traffic classes of the respective nodes are combinable,
where each edge weight is a traffic-class affinity metric that is determined based on one or more affinity characteristics of the traffic classes of the respective nodes.

### Claim 15 (depends on 14)

The system according to claim 14, where:
the affinity characteristics include at least one of a latency sensitivity (LS), a watermark, a packet rate and a burst length;
each traffic class includes at least one of an LS value, a watermark value, a packet rate value, and a burst length value; and
the traffic-class affinity metric includes at least one of a comparison of the LS values of the respective nodes, a comparison of the watermark values of the respective nodes, an evaluation of the packet rate values of the respective nodes, and an evaluation of the burst length values of the respective nodes.

### Claim 16

A computer-based method for synthesizing a Network-on-Chip (NoC), comprising:
receiving traffic data and a baseline topology, the traffic data including a plurality of traffic flows, each traffic flow including one or more traffic classes, the baseline topology including a plurality of bridge ports, a plurality of routers and a plurality of connections, each router including a number of ports, each router configured to process a plurality of traffic classes and to support a maximum number of virtual channels (VCs);
for each router:
determining a number of edge virtual channel (EVC) combinations, each EVC combination including a number of available edges and a number of available VCs, each available edge corresponding to a different port,
determining whether the traffic classes are transmittable or receivable by at least one EVC combination, and
when the traffic classes are determined not transmittable or receivable, identifying the router;
generating a traffic class affinity graph (TCAG) for each identified router;
generating traffic class combinations for the identified routers based on the TCAGs and the EVC combinations;
merging traffic classes of the identified routers based on the traffic class combinations;
determining a final EVC combination for each identified router based on the merged traffic classes; and
generating a final topology based, at least in part, on the merged traffic classes and the final EVC combinations for the identified routers.

### Claim 17 (depends on 16)

The computer-based method according to claim 16, where:
for each router, the number of available edges is equal to or less than the number of ports, and the number of available VCs is equal to or less than the maximum number of VCs; and
the traffic class combinations are generated by k-way minimum cost partitioning for each identified router, where k is the number of EVC combinations for the identified router.

### Claim 18 (depends on 17)

The computer-based method according to claim 17, where said generating traffic class combinations includes:
adding one or more routers to the baseline topology, each added router configured to process one or more traffic classes of the identified routers;
determining a number of EVC combinations for each added router;
generating a TCAG for each added router; and
identifying each added router.

### Claim 19 (depends on 16)

The computer-based method according to claim 16, where the TCAG for each identified router includes:
a plurality of nodes, each node associated with a different traffic class processed by the identified router; and
a plurality of edges, each edge connecting a different pair of nodes, each edge having a weight that indicates a degree to which the traffic classes of the respective nodes are combinable,
where each edge weight is a traffic-class affinity metric that is determined based on one or more affinity characteristics of the traffic classes of the respective nodes.

### Claim 20 (depends on 19)

The computer-based method according to claim 19, where:
the affinity characteristics include at least one of a latency sensitivity (LS), a watermark, a packet rate and a burst length;
each traffic class includes at least one of an LS value, a watermark value, a packet rate value, and a burst length value; and
the traffic-class affinity metric includes at least one of a comparison of the LS values of the respective nodes, a comparison of the watermark values of the respective nodes, an evaluation of the packet rate values of the respective nodes, and an evaluation of the burst length values of the respective nodes.