Exploring partitioning methods for multicast in 3D bufferless Network on Chip

In this paper, we first propose two multicast partitioning methods named TBP (two block partitioning) and LBP (layer block partitioning), each of which has a different level of efficiency in 3D bufferless network on chip. In addition, we present a Recursive Partitioning (RP) method in which the network is recursively partitioned until all partitions contain comparable number of multicast destination nodes. By this method, the multicast destination nodes are distributed evenly and the network latency is significantly decreased. Simulation results illustrate that the RP scheme achieves 39%, 45% and 41% less latency on average than that of the TBP scheme and 8%, 17% and 12% less latency on average than that of the LBP scheme under three synthetic traffic patterns respectively.


Introduction
As technology scaling with Moore's law, a single die can integrate several hundreds of cores. When the number of cores increases, interconnect becomes more and more complicated in System-on-Chip design. Networks on chip (NoC) were shown to be feasible and easy to scale for supporting a large number of cores and memory [1]. NoC can provide high throughput and low latency for one-to-one (unicast) traffic at present. In order to run many kinds of parallel applications on Multi-Processors System-on-Chip (MPSoC), collective communications must be supported. In an MPSoC system, the cache-coherent shared memory protocols (such as directory-based or token-based) require one-to-many or broadcast communications to obtain shared data or invalidate shared data on different cache blocks [2]. It has been proved that only 2-5% multicast traffic in the total network traffic will have a serious impact on system performance [3]. As a result, supporting efficient multicast in NoC can make the performance of the MPSoC system better.
Furthermore, with the increasing number of cores, the 2D plane is not an efficient way due to its long wire interconnections [4]. The emerging of the 3D integrated circuit stacks several dies to reduce the long wire delay, which results in lower power consumption and higher performance [5,6]. The 3D integrated circuit is also an attractive way for Network on chip. The 3D NoC architecture is widely studied in the network topology [7], router architecture [8], and routing algorithms [9].
Previous researches on NoC focus on the wormhole/virtual-channel router which contains buffers in each input port to buffer the packets. Though buffers can improve the bandwidth efficiency of the network, they also consume much energy and chip area [10]. Bufferless NoC has become a potential alternative to the traditional wormhole based NoC lately [10,11,12]. The bufferless router makes use of deflection routing to eliminate the buffers, which has two benefits: simplicity in design and reduce hardware cost. However, in bufferless NoC, packets cannot wait in a router and deflection routing makes the routing path unpredictable. Therefore it is impossible to employ existing multicast algorithms used in networks with buffers.
A method related to our work is discussed in [13] and [14] which propose partitioning methods for the 3D mesh network with buffers. However, it is not suitable for 3D bufferless network due to the fact that unpredictable routing path exists in bufferless network. To the best of our knowledge, there is no work addressing multicasting in 3D bufferless NoC systems. In this paper, we first propose two multicast partitioning methods named TBP (two block partitioning) and LBP (layer block partitioning), each of which has a different level of efficiency in 3D bufferless network on chip. In addition, we present a Recursive Partitioning (RP) method in which the network is recursively partitioned until all partitions contain comparable number of multicast destination nodes. By this method, the multicast destination nodes are distributed evenly and the network latency is significantly decreased. Simulation results illustrate that the RP scheme achieves 39%, 45% and 41% less latency on average than that of the TBP scheme and 8%, 17% and 12% less latency on average than that of the LBP scheme under three synthetic traffic patterns respectively.

3D bufferless router architecture
The baseline 3D bufferless router is a 1-cycle router with a 3-stage permutation network [8]. The structure of the baseline 3D bufferless router is show in Fig. 1. There are 7 input/output ports in each router. Each input port has only one input register, therefore the packet is not buffered in the router. It utilizes deflection routing to route packets. In the case of two or more flits contending for the same output of the permutation cell, the permutation cell selects the flit with the higher priority to the shortest output port and misroutes the other flit to the other output. The priority is decided according to the number of hops the packet has been routed in the network which can limit the number of misroutings to avoid livelock. The router can handle at most six packets at the same cycle and make output port allocation for each packet from high priority to low.

Partitioning methods for 3D bufferless mesh architecture
In this section, we propose three different partitioning methods for 3D bufferless mesh architecture.

Two-block partitioning (TBP) method
As the number of multicast destination increases, the long path of baseline 3D bufferless deflection routing without packets replication will lead to large multicast latency. To solve this problem, we propose TBP scheme with adaptive packets replication at the source node. Fig. 2 shows an example of this partitioning policy and the portions of each partition depending on the source node position. It is assumed that the source node is node 25 while the destination node set is D ¼ f9; 16; 17; 24; 39; 44g. The multicast based on TBP method is shown in Fig. 2

(a).
First the multicast packet in Node 25 is copied into two and sent to the two different partitions separately, if the source router has more than two empty ports. Node 24 and 39 are chosen as the first best candidate since they have the minimum Manhattan distance to the source node 25. After the packet is sent to node 24 and 39, node 16 and 9 are chosen as the second best candidate. Without contention, the minimum multicast latency is equal to 9 hops. The path shown in Fig. 2(a) is not the only one path since the packet may be deflected due to contention. As illustrated in Fig. 2(a), the source node is located at the middle layer, two partitions cover comparable number of nodes. However in Fig. 2(b), the source is located at the first layer, one partition contains much more nodes than the other. Now suppose that the multicast message m ¼ ð6; f1; 16; 17; 24; 39; 44gÞ is generated by the source node 6. The destination nodes are split into two groups according to the labels: G H ¼ f16; 17; 24; 39; 44g and G L ¼ f1g. The packet created for G H uses the manhattan path as follows: f6; 25; 24; 39; 40; 47; 16; 17; 46; 45; 44g where 10 hops are needed to reach the last destination. The packet path for the G L is: f6; 1g only one hop is required for delivering the packet to the destination. This is the drawback of TBP method.

Layer block partitioning (LBP) method
In this method, the network is partitioned into layer 0; 1; . . . ; n subnetworks. Destination are sorted based on each layer. The nodes with the same z value will be put into the same group. The scheme has several advantages over the TBP scheme as it achieves a high degree of parallelism and avoids the creation of long multicast paths. For the LBP scheme, when a multicast packet is being injected into the network from the local port, if free output ports are plane ports, the packet will not be replicated and routed the same way as the path-based 3D bufferless multicast scheme. If the number of free output ports is more than one and is the up or down port and destinations fall into different layer corresponding to the free output ports, the destinations will be grouped according to the layer partition and the multicast packet will be replicated and routed through different output ports. The pseudo code of LBP scheme is shown in Table I.
Free_port is a 6-bit vector, each bit of which indicates the corresponding output port is free or not. Output_prio sorts the priority of the output port from the highest priority to the lowest. The router always chooses a free output port with the highest priority to replicate and delivery a copy of the multicast packet. The function replicate_addr_gen acquires the address of the replicated packet. After replication, the original destination address will be updated and the number of packet copies will increase by 1. Fig. 3 shows an example of the multicast routing algorithm based on the LBP method. For the multicast message m ¼ ð25; f9; 16; 17; 18; 24; 39; 46gÞ, three groups are formed: layer0 ¼ f9g, layer1 ¼ f16; 17; 18; 24g, layer2 ¼ f39; 46g. Without contention, the multicast packet requires 5 link traversals in total. The path shown in Fig. 3(a) is not the only one path since the packet may be deflected due to contention. The unbalanced partitions are shown in Fig. 3(b). The multicast message m ¼ ð6; f1; 9; 16; 17; 18; 24; 39; 46gÞ requires 6 hops in total to reach the final destination without contention.

Recursive partitioning (RP) method
The objective of the recursive partitioning method is to optimize the number of destination nodes that can be included in a partition. In this method, the network is recursively partitioned until each partition includes less than n destination nodes. In the worst case, the network is partitioned into c layer partitions like the LBP method in an a Â b Â c network. So, we have considered the value n as the maximum number of destination nodes in a partition of the LBP method. The pseudo code of RP scheme is shown in Table II. Num_dst indicates whether a partition of the LBP method includes more than n destination nodes. The number of n will change if the number of destinations of the multicast packets is changed or the size of the network is changed. When free_port and num_dst are equal to 1, the router will choose a free output port to replicate destination address and delivery a copy of the multicast packet. The function replicate_addr_gen_1 acquires the address of the replicated packet in a partition of the LBP method. After replication, the original destinaiton address will be updated and the number of packet copies will increase by 1.
An example of the multicast routing algorithm based on the RP method is illustrated in Fig. 4, where a multicast message is generated at the source node 25. The steps of the RP algorithm can be expressed as follow: 1. The value n is set to 4 in a 4 Â 4 Â 3 network; 2. The network is divided into three partitions using LBP method. The Fig. 4(a) shows the partitions when the source node is 25; 3. If the number of nodes in a partition exceeds the predefined value n, the function replicate_addr_gen_1 acquires the address of the replicated packet in a partition of the LBP method. the partition is divided into new partitions according to the location of the destination nodes. A region partition policy is proposed to divide the layer into at most 4 regions (P1,P2,P3,P4) according to the position of the source node, as shown in Fig. 4(a) layer1. If there is only one free output port, the packet will not be replicated and will be routed the same way as the LBP scheme. If the number of free output ports is more than one and destinations fall into different regions corresponding to the free output ports, the RP scheme will work. Fig. 4(a) shows the example of recursive partitioning. There are 5 destination nodes in layer1 which is greater than n = 4. So, the multicast packet will be replicated according to the region partition in layer1. Without contention, the multicast path requires 5 hops. However, the multicast path will require 12 hops when it using the LBP method.
The same partitioning technique is applied to the low layer subnetwork. Fig. 4(b) shows another example of the RP method where the source node is 6. In this example, the multicast path requires 6 hops as the maximum latency.

Experimental evaluation
In this section, we evaluate the performance of the three proposed multicasting partitioning mechanism for the 3D mesh interconnection network with a cycleaccurate NoC simulator which is developed in VHDL.

Methodology
The experiments are performed on a 4 Â 4 Â 4 3D mesh network. The routing process is partitioned into two steps. First of all, the routing computation in company with the input and output priority sorting are executed in parallel. Then the output port allocator allocates each packet based on the results of the first step. For the LBP and RP routers with adaptive packets replication, multicast packets are replicated at the moment of output allocation when at least one free output port left for replication. The three multicast routers are more complicated than the regular unicast bufferless router as a result of increasing route computation for multicast packets and packets replication. For the purpose of simplify the design, we use a 1cycle router [8] for three kinds of multicast routers (TBP, LBP, RP routers) which is shown in Fig. 1. To perform the simulations, a combination of unicast and multicast traffic is used. For unicast traffic, we use three synthetic traffic patterns: uniform random, bit complement, transpose. For multicast packet, the destination positions are uniformly distributed.
We measure the average packet latency T which is calculated by the equation and measured in cycle, where T src is the time that a packet startup latency and T net is the network delivery time. We also evaluate the link utilization, which is the average percentage of used links in total links. Link utilization can reflect the power consumption. The more used links, the higher power consumption is consumed.

Latency analysis
We measure the performance of the three multicast schemes in this subsection. Fig. 5(a)-(c) illustrate the average packet latency of the three multicast schemes. The multicast traffic is 10% of the total traffic and the number of destinations is 8. It can be observed that the RP scheme achieves the smaller average latency than the other two multicast schemes. However, the network with the RP scheme reaches saturation earlier than the other two schemes. As the network is not saturated, the average latency of the LBP scheme is 32%, 40% and 35% less than that of TBP scheme under three synthetic traffic patterns respectively. The RP scheme achieves 39%, 45% and 41% less latency on average than that of the TBP scheme and 8%, 17% and 12% less latency on average than that of the LBP scheme under three synthetic traffic patterns respectively. The results are consistent with our expectations. The RP scheme outperforms the LBP scheme and TBP scheme at low or medium traffic loads. The RP scheme performs similar as the LBP scheme when the network reaches saturation point. The fact is that they can replicate multicast packets at both source and intermediate nodes which increases the network loads, so the throughput of the network is a little bit lower than TBP scheme. However, under real application workloads the network is never fully loaded, so the RP scheme is a better alternative for bufferless NOC than the other two schemes. We synthesize three routers using Synopsys Design Compiler with 65 nm technology at the typical condition (25°C and 1.0 v). The critical path delay of the TBP multicast routers is 2 ns while the LBP and RP methods are at most 8% higher than this value, thus all the above conclusions still hold. Fig. 6 shows the link utilization with the number of multicast destinations increasing from 4 to 16 under random traffic with 10% multicast traffic. In the case of the network not saturated, compared with TBP scheme, the RP scheme can save 12%, 16% and 23% of link utilization on average for different number of multicast destinations respectively. Compared with LBP scheme, the RP scheme can save 3%, 5% and 10% of link utilization. It can also be concluded that as the number of destinations increases, the RP scheme can save more power consumption than that of the other two multicast schemes.

Scalability
We also evaluate the performance of the three multicast schemes with different portion of multicast traffic and different number of multicast destinations. Fig. 7(a) shows the performance variation of the three multicast schemes with different  portion of multicast traffic from 10% to 40%. The number of multicast destinations is 8. It can be seen from the figure, the RP scheme achieves much less average latency than the TBP and LBP schemes with the increasing portion of multicast traffic. Fig. 7(b) reveals the average latency of the three multicast schemes with the increasing number of multicast destinations. The portion of multicast destinations is 10%. As the number of multicast destinations increases from 4 to 32, the average latency of the RP scheme does not vary so much, while the average latency of the LBP scheme increases by up to 1 times and the average latency of the TBP scheme increases by up to 3 times.

Conclusion
This paper proposes a novel idea of balanced partitioning which leads the 3D mesh architecture to be partitioned effectively. We first presented TBP and LBP partitioning methods for 3D bufferless mesh architecture, each of which has a different level of efficiency. In order to achieve higher performance, the recursive partitioning (RP) method was introduced. This method partitions the network recursively until all partitions contain considerable number of nodes. Our simulations with different traffic profiles showed that the RP method reduces the average packet latency and provides higher degree of parallelism compared with the other two methods.