Supporting multicast in NOC interconnect
View Patent ↗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.
1. A method, comprising:
generating one or more multicast trees for a provided Network on Chip (NoC) interconnect comprising a plurality of nodes;
configuring a source node from the plurality of nodes to receive a multicast message, the configuring the source node comprising storing the generated one or more multicast trees at the source node;
before receipt of the multicast message at the source node, configuring each port of each of the plurality of nodes with a filter based on the generated one or more multicast trees, the filter configured with a set of destination nodes representing a multicast tree from the generated one or more multicast trees in a form of a filter bit-vector, the filter configured as one of a logic or a circuit, wherein each bit of the filter bit-vector indicative of whether a corresponding destination bit from a destination bit-vector of the multicast message is to be filtered, and
for receipt of the multicast message at the source node, 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 by the source node based on an application of logic between the destination bit-vector of the multicast message and the filter bit-vector; and
transmitting the multicast message from the source node through the selected port.
2. The method of claim 1 , wherein the selecting the multicast tree from the one or more multicast trees is based on at least one of a distance of a destination node, a bandwidth attribute and a latency attribute.
3. 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.
4. The method of claim 1 , wherein the generating one or more multicast trees comprises:
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.
5. The method of claim 1 , wherein the selecting conducted by the source node 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.
6. A non-transitory computer readable storage medium storing instructions for executing a process, the instructions comprising:
generating one or more multicast trees for a provided Network on Chip (NoC) interconnect comprising a plurality of nodes;
configuring a source node from the plurality of nodes to receive a multicast message, the configuring the source node comprising storing the generated one or more multicast trees at the source node;
before receipt of the multicast message at the source node, configuring each port of each of the plurality of nodes with a filter based on the generated one or more multicast trees, the filter configured with a set of destination nodes representing a multicast tree from the generated one or more multicast trees in a form of a filter bit-vector, the filter configured as one of a logic or a circuit, wherein each bit of the filter bit-vector indicative of whether a corresponding destination bit from a destination bit-vector of the multicast message is to be filtered, and
for receipt of the multicast message at the source node, 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 by the source node based on an application of logic between the destination bit-vector of the multicast message and the filter bit-vector; and
transmitting the multicast message from the source node through the selected port.
7. The non-transitory computer readable storage medium of claim 6 , wherein the selecting the multicast tree from the one or more multicast trees is based on at least one of a distance of a destination node, a bandwidth attribute and a latency attribute.
8. The non-transitory computer readable storage medium of claim 6 , wherein the instructions further comprise configuring an aggregation node from the plurality of nodes to aggregate a plurality of messages from a the plurality of nodes to form the multicast message.
9. The non-transitory computer readable storage medium of claim 6 , wherein the generating one or more multicast trees comprises:
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.
10. A system, comprising:
a processor coupled to a memory, configured to:
generate one or more multicast trees for a provided Network on Chip (NoC) interconnect comprising a plurality of nodes;
configure a source node from the plurality of notes nodes to receive a multicast message, wherein the configuration of the source node comprises storing the generated one or more multicast trees at the source node;
before receipt of the multicast message at the source node, configuring each port of each of the plurality of nodes with a filter based on the generated one or more multicast trees, the filter configured with a set of destination nodes representing a multicast tree from the generated one or more multicast trees in a form of a filter bit-vector, the filter configured as one of a logic or a circuit, wherein each bit of the filter bit-vector indicative of whether a corresponding destination bit from a destination bit-vector of the multicast message is to be filtered, and
for receipt of the multicast message at the source node, 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 by the source node based on an application of logic between the destination bit-vector of the multicast message and the filter bit-vector; and
transmit the multicast message from a transmitter of the source node through the selected port.
11. The system of claim 10 , wherein the processor is configured to select the multicast tree from the one or more multicast trees based on at least one of a distance of a destination node, a bandwidth attribute and a latency attribute.
12. The system of claim 10 , wherein the processor is configured to configure an aggregation node from the plurality of nodes to aggregate a plurality of messages from a the plurality of nodes to form the multicast message.
13. The system of claim 10 , wherein the processor is configured to generate one or more multicast trees from a plurality of nodes of a Network on Chip (NoC) 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.