4.3.1.1 Transaction-based bus

Traditionally, shared-bus-based communication architectures are popular choices for on-chip communication. Figure 4.1a shows a bus example architecture which is regarded as a transaction-based communication architecture. The bus is a simple set of wires interconnected to all the master nodes, slave nodes, and an arbiter in a single way. A bus transaction generally consists of first establishing a connection between communicating pairs before sending data (a role endorsed by the bus arbiter). So the bus can be a centric architecture in which all the components are tightly coupled. In one transaction, the master node can reach all the slave nodes directly and immediately. This is very efficient when connecting only a few tens of intellectual property cores. However, these transactions are necessarily serialized, causing heavy contention and poor performance when more cores are integrated. Thus, the bus structure fails to satisfy the requirements of future parallel applications. Furthermore, the global wires introduced by the bus also cause scalability, energy consumption, and performance problems.

4.3.1.2 Packet-based NoC

NoC communication architectures connect the processing and storage resources via a network. Communication among various cores is realized by generating and forwarding packets through the network infrastructure via routers. By eliminating the global wires used in the bus, the NoC approach can provide high bandwidth and scalability. The 2D mesh is by far the most exploited topology since it is particularly easy to implement on current planar CMOS technology. Figure 4.1b shows an example of the mesh network. It consists of 16 tiles arranged in a 4 × 4 grid, where each tile is connected to its four neighbors (with the exception of the edge tiles). Because only neighboring nodes are connected, packets that need to travel long distances suffer from large hop counts. Current packet-based on-chip networks have made each packet need to go through router pipelines, typically four to five stages at each hop [5], and involve multiple hops according to the distance. This widens the gap between the ideal interconnect and the NoC design. A more serious problem may occur when multicast or broadcast communications are activated in that their latency and throughput features usually do not satisfy the demand of applications.

4.3.2.1 Multihop problem

The latency of a unicast message is regarded as the time from the generation of the unicast message at the source node until the time when the last flit of the message is absorbed by the destination node. So the service time of a unicast packet, T_NoC, is given by

$T_{\text{NoC}}=T_{\text{s}}+T_{\text{b}},$

where T_s is the router service time for the header flit and T_b is the number of cycles required by a packet to cross the channel. Since the remaining flits follow the header flit in a pipelined fashion, T_b is simply the quotient of the packet size, S, and the channel width, W:

$T_{\text{b}}=S/W.$

We note that T_s is a function of the router design and its hop number, H, including the time to traverse the router (t_R) and the link (t_L):

$\begin{array}{ll}{T}_{\text{s}}\hfill & ={\displaystyle \sum _1^H{t}_{\text{hop}}}={\displaystyle \sum _1^H\left(t_{\text{R}}+t_{\text{L}}\right)}\hfill \\ \hfill & ={\displaystyle \sum _1^H\left(t_{\text{crossbar}}+t_{\text{BW}}+t_{\text{VA}}+t_{\text{SA}}+t_{\text{contention}}+t_{\text{L}}\right).}\hfill \end{array}$

Here, t_hop is the latency of each router hop, t_BW is the time the flit spends in the buffers, t_VA and t_SA are the times the flit spends in arbitrating the buffer and switching resources, and t_crossbar is the time to actually traverse the router.

In the ideal case, the unicast delay for NoC networks, T_ideal, should be the transmission delay of the physical link. For each hop, the ideal network latency, indicating the intrinsic network delay, can be written as

$t_{\text{ideal}}=t_{\text{L}}+t_{\text{crossbar}}.$

So the total ideal delay, T_ideal, can be written as

$T_{\text{ideal}}={\displaystyle \sum _1^H\left(t_{\text{ideal}}\right)+T_{\text{b}}}={\displaystyle \sum _1^T\left(t_{\text{L}}+t_{\text{crossbar}}\right)+T_{\text{b}}}.$

Compared with the ideal network latency, T_gap, indicating the extra router pipeline and resource contention latency in the NoC network design, can be written as

$T_{\text{gap}}=T_{\text{NoC}}-T_{\text{ideal}}={\displaystyle \sum _1^H\left(t_{\text{BW}}+t_{\text{VA}}+t_{\text{SA}}+t_{\text{contention}}\right)}.$

From Equation (4.6), it can be seen that if we want to reduce the unicast latency of the NoC, we should reduce the number of transmission hops, the processing time of router pipelines, and the contention time caused by multiple packets waiting for transmission.

4.3.2.2 Multicast problem

The multicast latency can be defined as the time from the generation of the message at the source node until the time when the last flit of the multicast message is absorbed by the last destination of the multicast message among messages leaving injection ports. We use unicast-based message passing mechanisms to provide multicast communication. These multicast packets are broken down into multiple unicasts by the network interface controllers as the packet-switched routers are not designed to handle multiple destinations for one packet. Then the service time of a multicast packet, T_{NoC_mc}, is given by

$\begin{array}{ll}{T}_{\text{NoC\_mc}}\hfill & =\text{max}\left\{t_{\text{inject}}+t_{\text{NoC\_mc}}\right\}\hfill \\ \hfill & =\text{max}\left\{t_{\text{inject}}+\left(S/W\right)+{\displaystyle \sum _1^H\left(t_{\text{crossbar}}+t_{\text{BW}}+t_{\text{VA}}+t_{\text{SA}}+t_{\text{contention}}+t_{\text{L}}\right)}\right\},\hfill \end{array}$

where t_inject is the injection time of the multicast flit. Since a multicast packet has multiple destinations, this causes competition at the network interface for injection into the network. This adds significant delays to the packet communications. From Equation (4.7), it can be seen that we can reduce the multicast delay in two ways. One is to reduce the unicast traffic caused by multicast packets so that the competition for network resources can be reduced. The other is to choose a good routing algorithm so that the communication path to each destination is the shortest.

4.4.1.1 Wire delay consideration

Technology scaling has resulted in a steady increase in transistor speed. However, unlike transistors, global wires that span the chip show a reverse trend of getting slower with the shrinkage process. Modern processors are severely constrained by the wire delay. However, wire delays are somewhat tolerable when repeaters are judiciously employed [2]. Figure 4.3 shows the interconnect delay scaling from the prediction of the International Technology Roadmap for Semiconductors 2008 report [27]. This wire delay prediction can help us to decide the optimal length of VBs in many-core processor chips. The table in Figure 4.3 shows the wire transmission length per nanosecond under different technology nodes. We can see that with repeaters, the delay of transmitting signals on global wire can be reduced from 2000 to 120ps/mm with 22 nm technology, i.e., the wire data can be transmitted at a rate of 8 mm/ns.

If we assume the chip die area is 10 × 10 mm² and the frequency is 1 GHz, the data can be transmitted in a relatively long range across the chip in one cycle. Therefore, in this chapter, we consider only the case that a VB can transmit in one cycle. If a higher frequency is required, the maximal length of the VB may be decreased or one VB segment can be transmitted in multiple cycles.

Figure 4.4 illustrates the mechanism for constructing the VB. It is established by bypassing the existing datapaths of the conventional router. Though only the concept structure of the row/column VB implementation is presented, this bypassing method can be used in any other type of VB. Each node is simply composed of some switches that can establish internal connections among its ports. In addition, each node has some simple controller logic. The controller can read control signals from bus arbiters and configure the internal switches. Four possible node configurations for the internal switches are displayed in Figure 4.4a, i.e., (N → S), (S → N), (W → E), and (E → W). The connections among the controller and the ports are not shown in Figure 4.4 for simplicity.

Figure 4.4b gives two examples for how to construct the row/column VB. There are bypassing nodes for transmission in each row or column VB, and bridge nodes for transmission between the row and column VBs. So the real transmission in the VB link can be completed by bypassing existing router pipelines. This is different from the multihop transmission in the conventional NoC design. Through a little logic overhead in the basic router and dynamic link sharing between NoCs and buses, the VBON improves the conventional NoC while preserving all its essential features, including high efficiency, high throughput, and high bandwidth for unicast traffic, as well as scalability and low power consumption.

The transmission to multiple destinations on a single row or a single column is enough with only one VB. However, in several cases, the destinations are scattered so as to be distributed on multiple rows or columns. For multiple destinations on different rows or different columns, a single-row VB and multiple-column VBs have to be established. Their arbitrations and data transmissions are done in a dimensional order fashion.

4.4.2.3 Packet format

In order to support multicasting, we expand the packet format into that shown in Figure 4.7. We explain the packet fields as follows. The 38-bit packet format for unicast is shown in Figure 4.7a. The packet consists of the header flit followed by payload flits. Three additional 3-bit heads are the Type, ID (identity), and Mode bits. The Type can be header, data body, and the end of data body (last flit). The Mode can be the unicast, multicast, and broadcast communication pattern for different packet formats. The source and target addresses of the packet are asserted in the header flit. Passing a communication segment of the NoC, each packet has the same local identity number (ID tag) to differentiate it from another packet. The local ID tag of the data flits of one packet will vary over different communication segments in order to provide a scalable concept. Figure 4.7b shows the packet format for multicast services. The target addresses are specified in the bitstring field. Each bit in the bitstring represents a node, the hop distance of which from the source node corresponds to the position of the bit in the bitstring. The status of each bit indicates whether the visited node is a target of the multicast or not. For broadcast communication as shown in Figure 4.7c, all nodes in the NoC are receiver nodes, so they can be specified implicitly.

4.4.2.4 VB operation

We apply the procedure used in the connection-oriented multicasting NoC [19] in the VB operation. The VBs can be dynamically established, and all conflicting ongoing messages can be paused during the VB transmission. This consists of three phases, VB setup, communication, and VB release:

(1) VB setup. First the source node sends a request to the arbiter to access the VB. In order to resolve VB requests from many sources, the row ID of a node stands for its priority. The row ID of highest priority is able to continue its VB transaction. As a result, others withdraw their VB requests, which will be retried afterwards. When the bypassing circuits for the VB are established, the existing routing data are frozen intact in the flit buffers.

(2) Communication. The VB data is being transmitted to the destination nodes. Except for the broadcast packet, the destination information is needed in multicast or urgent unicast packets. At the beginning of data transmission, the source transfers encoded destination vectors through point-to-point links, and then transfers the following raw data. Once the vectors have been received, the nodes can determine which nodes are destinations or bridges connected to the destinations in the other dimension.

(3) VB release. After the VB transmission, the datapath seized by the VB is released. The paused routing data can continue to proceed to its destination.

The transition state of VB operation is illustrated in Figure 4.8. If the source and destination nodes belong to the same bus segment (the same row or column), the packet can be transferred by using one VB operation (IDLE → SETUP → BUSY → IDLE). If they are in different bus segments (different rows or columns), multiple VB operations are used.

The bridge node is responsible for transition from one row VB to one column VB. When this happens, the flits from the row VB can be stored in the bridge node and then they request another VB operation. Since a row VB has only one packet at a time, there is no contention for the buffer in the same bridge node.

A simple and illustrative timing diagram of one VB operation is shown in Figure 4.9. The VB transmits four flits in the burst mode, where three different roles of nodes are involved: the source node Src, the intermediate node Inter, and the destination node Dst. The signal names begin with the type of node that connects to the signal. When the Src node requests the VB transmission by asserting the Request signal, it also asserts the Burst signal. Then the VB arbiter grants the VB access according to the Ready signals from other nodes and the priority information. At the same time, it generates the Pause and Dir signals for bypassing Inter nodes. Then the flit data can be sent to the Dst node. After the VB transmission, the Src node withdraws the Request signal, and the arbiter will release the VB in the next cycle.

4.4.2.5 A simple example for VB communication

Figure 4.10 shows a simple example for VB communication, which includes three packets. We assume that the transmission times of three packets overlap and the packet ID indicates the message generation order. Packet1 and Packet2 are unicast messages, and these two packets can be transferred concurrently since their required channels are disjoint. In this time, node N₁₃ generates a multicast packet Packet3 which goes to destination nodes: N₀₁, N₁₀, N₁₂, and N₃₁. Two VBs are involved in the communication process for Packet3. The row VB (VB_R1, from node N₁₀ to node N₁₃) is first established after the arbitration. Then the column VB (VB_C1, from node N₀₁ to node N₃₁) is established. Node N₁₁ is the bridge between two VBs. When the flits of Packet3 are sent to node N₁₁, they are stored in VB buffers and node N₁₁ requests the column VB transmission. The ongoing flits of P-U1 and P-U2, which share the same datapath with the two VBs, are just frozen, because VBs have the highest priority to transmit.

4.5.1.1 Router choices for comparison

We compare various characteristics of the proposed VBON schemes against two existing baseline packet-switched networks: the basic router [9] and the NOCHI EVC router [15].

The basic router is representative of conventional NoC designs. It originally had a four-stage router pipeline. The first stage is the buffer write; the routing computation (RC) occurs in the second stage. In the third stage, VC allocation (VA) and switch allocation (SA) are performed. In the fourth stage, the flit traverses the switch. Each pipeline stage takes one cycle, followed by one cycle to do the link traversal to the next router. To shorten the pipeline, the basic router uses lookahead routing [7] and the speculative method [24]. Lookahead routing determines the output port of a packet one hop in advance. That is to say while the flit is traversing the switch, a lookahead signal is traveling to the next router to perform the RC. In the next cycle, when the flit arrives, it will proceed directly to SA. The speculative method can eliminate the VA and SA stage by causing flits to directly enter the switch traversal pipeline.

The NOCHI EVC router was chosen because its concept is similar to our work. It is an optimized design based on the EVC router design [17]. A conventional EVC router sets up virtual express paths in the network that let packets bypass intermediate routers, thus improving the energy-delay throughput of NoC interconnects. We can regard this virtual express path as a multiple-stage VB. Though it uses the low-latency benefit of the bus mechanism for unicast communication, it does not use the broadcast feature of the bus, leading to some limitations. First, buffers at an EVC's end point must be managed conservatively to ensure that the destination router (the EVC end point) can accept the traffic. This leads to buffer overprovision and underutilization. The second deficiency is that VCs must be partitioned between different express paths statically, and the control latency limits the number. To overcome these limitations, the NOCHI EVC router is proposed to enable single-cycle control communication across all nodes in a row or column of a mesh network through G-line. Using timely information reduces the demand on router buffers as well as the number of buffers needed to sustain a specific bandwidth. In a sentence, the NOCHI EVC approach is a very effective method for unicast communication, but it does not support multicast communication.

Table 4.1 lists the comparison results for the three different NoC designs. The comparison parameters are

(1) the hardware overhead of the basic router,

(2) the setup mechanism of the bus link,

(3) the number of hops for each unicast packet,

(4) the number of pipeline stages for each router,

(5) the RC method,

(6) the communication mechanism for the unicast traffic, and

(7) the communication mechanism for multicast traffic.

We extended the network model to capture these aspects of the VB protocol and G-line EVC protocol.

4.5.1.2 Network configuration

Table 4.2 lists the network configurations across all the studies. The mesh network is simulated with two configurations: one is that only cluster 1 with a 4 × 4 mesh is enabled and the other is that all 8 × 8 hierarchical clusters are enabled. It should be noted that this is a fair comparison between the proposed VBON architecture and other architectures since these different network configurations are just caused by their different architectures.

Each simulation experiment is run until the network reaches its steady state. The destinations of unicast messages at each node are selected randomly. For unicast-only scenarios, once the number of hops of the unicast message is not less than three (the threshold in a 4 × 4 mesh) or five (the threshold in an 8 × 8 mesh), then the messages are transmitted by VBs. For multicast scenarios, all the multicast messages are transmitted through VBs. To decrease the contention caused by the VB transmission, the threshold for VB transmission is decreased to four (4 × 4 mesh) or eight (8 × 8 mesh). The multicast destinations and their numbers are generated randomly at the beginning of the simulation.

4.5.1.3 Traffic generation

For the sake of comprehensive study, numerous validation experiments have been performed for several combinations of workload types and network sizes. In what follows, the capability of the VBON will be assessed for both synthetic and realistic traffic. The synthetic traffic patterns used in this research are the uniform random, transpose, complement, and Cauchy patterns to have a more specific evaluation for different traffic patterns [5]. Each simulation runs for 1 × 10⁶ cycles. To obtain stable performance results, the initial 1 × 10⁵ cycles are used for simulation warm-up and the following 9 × 10⁵ cycles are used for analysis. When destinations are chosen randomly, we repeat the simulation run five times and get the average of the values obtained in each run. We also studied the VBON architecture using real application network traffic. We ran Splash-2 benchmarks [32] on a chip multiprocessor simulator, M5[1], with shared second-level caches distributed in a tiled manner. Each core consists of a two-issue in-order SPARC processor with two-way 16 kB first-level ICache and two-way 32 kB DCache. Each tile also includes a 1 MB second-level cache. We used the MESI-based directory protocol for cache coherence.

We first evaluate the performance of a VBON compared with other NoC designs in the environment of a single-level 4 × 4 mesh. Figure 4.12 shows the average latencies of the networks when all the packets are unicast ones. It can be seen that the conventional NoC routers perform very well when the traffic load is low. The latencies of the VBON, NOCHI EVC, and NoC designs are almost the same. But as the traffic load increases, the NOCHI EVC and VBON designs gradually reduce the latency of unicast communications. This is because unicast communication with long latency can be performed by global channels in the NOCHI EVC design or by VBs (when the number of hops exceeds two). This feature is very useful when some urgent messages need to be transmitted. The VBON design also outperforms the NOCHI EVC design when the traffic load is heavy. This is because the real VB transmission can be fulfilled by one cycle, while the EVC transmission is completed in a pipelined fashion, which takes several cycles.

Figure 4.13 shows the performance results when 10% of packets are multicast ones. In conventional NoCs, the multicast transmission path is defined by the source node. The performance significantly degrades and it saturates at a rate less than 0.3 flits per node per cycle. This is because a few multicast packets can cause a lot of the NoC workload, leading to significant throughput degradation. It can be seen that although the optimized NoC design, NOCHI EVC, alleviates this situation by decreasing the pipelining cycles of the routing path, it does not solve the multicast problem. The VBON design can greatly outperform the NOCHI EVC design for multicast transmission. The support for multicast in the VBON design leads to only a small increase in the average latency. This is because the VB can transmit the message to multiple nodes in a broadcast way. And for each multicast transmission, only a few VB transactions are involved.

4.5.2.2 Hierarchical 8 × 8 VBON

For an 8 × 8 mesh structure, the comparison results for average latencies for unicast communication are shown in Figure 4.14. These results are given with different traffic patterns: uniform random, transpose, complement, and Cauchy patterns. The packet communication in this hierarchical VBON may involve four VB clusters. Compared with a 4 × 4 mesh, the average latency of unicast communications in an 8 × 8 conventional NoC design increases significantly owing to the increased number of transmission hops. In this case, the performance improvement caused by the NOCHI EVC and VBON designs is more obvious. For all traffic patterns, the VBON design also performs better than the NOCHI EVC design, ranging from 8% for uniform random traffic to 19% for complement traffic at a rate of 0.3 flits per node per cycle. This is because the communication of multiple-segment VBs can take less time than that of pipelined EVCs.

Figure 4.15 shows the comparison results for average latencies for multicast communication. To get an accurate understanding of the performance impact for multicast communications, we provide three different multicast percentages in the whole communication: 5%, 10%, and 20%. Compared with the NOCHI EVC design, the proposed VBON design shows better throughput for all three cases. Furthermore, as the percentage of multicast communication increases, this improvement is more obvious. This demonstrates that the VBON design can scale well for large multicast communication in a hierarchical way.