Supporting multicast in NoC interconnect

Patent metadata

Field	Value
Publication number	US-9590813-B1
Application number	US-201615265590-A
Country	US
Kind code	B1
Filing date	Sep 14, 2016
Priority date	Aug 7, 2013
Publication date	Mar 7, 2017
Grant date	Mar 7, 2017

Abstract

Example implementations are directed to more efficiently delivering a multicast message to multiple destination components from a source component. Multicast environment is achieved with transmission of a single message from a source component, which gets replicated in the NoC during routing towards the destination components indicated in the message. Example implementations further relate to an efficient way of implementing multicast in any given NoC topology, wherein one or more multicast trees in the given NoC topology are formed and one of these trees are used for routing a multicast message to its intended destination components mentioned therein.

First claim

What is claimed is:

1. A method, comprising:
configuring each port of each of a plurality of nodes of a Network on Chip (NoC) with a filter in a form of a filter bit vector representing a multicast tree from one or more multicast trees of the NoC, wherein each bit of the filter bit-vector is indicative of whether a corresponding destination bit from a destination bit-vector of a multicast message is to be filtered, and
configuring each of the plurality of nodes of the NoC to execute a process for receipt of the multicast message, the process comprising:
selecting a port configured with a filter representing the multicast tree from the one or more multicast trees directed to the received multicast message, the selecting conducted based on an application of logic between a destination bit-vector of the multicast message and the filter bit-vector; and
transmitting the multicast message through the selected port.

2. The method of claim 1 , wherein the selecting based on an application of logic between the destination bit-vector of the multicast message and the filter bit-vector comprises comparing each bit of the destination bit-vector to each bit of the filter bit-vector, and selecting the port having at least one matching bit.

3. The method of claim 1 , wherein the configuring each port of the each of the plurality of nodes of a NoC with the filter comprises implementing the filter for each pair of input ports and output ports.

4. The method of claim 1 , further comprising selecting the multicast tree from the one or more multicast trees for the each port based on at least one of a distance of a destination node, a bandwidth attribute and a latency attribute.

5. The method of claim 1 , further comprising configuring an aggregation node from the plurality of nodes, to aggregate a plurality of messages from the plurality of nodes to form the multicast message.

6. The method of claim 1 , wherein the one or more multicast trees are generated by:
generating a minimum spanning tree for each of the plurality of nodes;
generating subsets from the generated minimum spanning trees; and
combining edges of the minimum spanning trees for each subset to form one of the one or more multicast trees.

7. A non-transitory computer readable medium storing instructions for executing a process, the instructions comprising:
configuring each port of each of a plurality of nodes of a Network on Chip (NoC) with a filter in a form of a filter bit vector representing a multicast tree from one or more multicast trees of the NoC, wherein each bit of the filter bit-vector is indicative of whether a corresponding destination bit from a destination bit-vector of a multicast message is to be filtered, and
configuring each of the plurality of nodes of the NoC to execute a process for receipt of the multicast message, the process comprising:
selecting a port configured with a filter representing the multicast tree from the one or more multicast trees directed to the received multicast message, the selecting conducted based on an application of logic between a destination bit-vector of the multicast message and the filter bit-vector; and
transmitting the multicast message through the selected port.

8. The non-transitory computer readable medium of claim 7 , wherein the selecting based on an application of logic between the destination bit-vector of the multicast message and the filter bit-vector comprises comparing each bit of the destination bit-vector to each bit of the filter bit-vector, and selecting the port having at least one matching bit.

9. The non-transitory computer readable medium of claim 7 , wherein the configuring each port of the each of the plurality of nodes of a NoC with the filter comprises implementing the filter for each pair of input ports and output ports.

10. The non-transitory computer readable medium of claim 7 , the instructions further comprising selecting the multicast tree from the one or more multicast trees for the each port based on at least one of a distance of a destination node, a bandwidth attribute and a latency attribute.

11. The non-transitory computer readable medium of claim 7 , the instructions further comprising configuring an aggregation node from the plurality of nodes, to aggregate a plurality of messages from the plurality of nodes to form the multicast message.

12. The non-transitory computer readable medium of claim 7 wherein the one or more multicast trees are generated by:
generating a minimum spanning tree for each of the plurality of nodes;
generating subsets from the generated minimum spanning trees; and
combining edges of the minimum spanning trees for each subset to form one of the one or more multicast trees.

13. A Network on Chip (NoC), comprising:
a plurality of nodes, each port of the plurality of nodes configured with a filter in a form of a filter bit vector representing a multicast tree from one or more multicast trees of the NoC, wherein each bit of the filter bit-vector is indicative of whether a corresponding destination bit from a destination bit-vector of a multicast message is to be filtered, and each of the plurality of nodes of the NoC are configured to:
select a port configured with a filter representing the multicast tree from the one or more multicast trees directed to the received multicast message, the selecting conducted based on an application of logic between a destination bit-vector of the multicast message and the filter bit-vector; and
transmit the multicast message through the selected port.

14. The NoC of claim 13 , wherein the plurality of nodes are configured to select based on the application of logic between the destination bit-vector of the multicast message and the filter bit-vector by comparing each bit of the destination bit-vector to each bit of the filter bit-vector, and selecting the port having at least one matching bit.

15. The NoC of claim 13 , wherein the filter is implemented for each pair of input ports and output ports.

16. The NoC of claim 13 , wherein the multicast tree from the one or more multicast trees is configured for the each port based on at least one of a distance of a destination node, a bandwidth attribute and a latency attribute.

17. The NoC of claim 13 , wherein the plurality of nodes further comprises an aggregation node configured to aggregate a plurality of messages from the plurality of nodes to form the multicast message.

18. The NoC of claim 13 , wherein the one or more multicast trees are generated by a process comprising:
generating a minimum spanning tree for each of the plurality of nodes;
generating subsets from the generated minimum spanning trees; and
combining edges of the minimum spanning trees for each subset to form one of the one or more multicast trees.

Assignees

• Netspeed Systems

Inventors

• Kumar Sailesh
• Norige Eric
• Rowlands Joe
• Philip Joji

Classifications

• H04L12/1886 Primary

  with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains · CPC title

• H04L12/185

  with management of multicast group membership · CPC title

• H04L41/0823

  characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability (for optimising operational conditions of wireless networks H04W24/02) · CPC title

• H04L47/31

  by tagging of packets, e.g. using discard eligibility [DE] bits · CPC title

• H04L49/109

  Integrated on microchip, e.g. switch-on-chip · CPC title