Abstract: A new chip design paradigm called Network-on-Chip (NoC) offers a promising architectural choice for future System-on-Chip (SoC). Communication latency and power efficiency are the most important concerns in NoC architecture design. Triple-based Hierarchical Interconnection Network (THIN) was proposed that aims to decrease the node degree, reduce the links and shorten the diameter. In this study, the zero-load latency and energy consumption are thoroughly studied and compared with 2-D mesh. The compare results show that THIN is a better candidate for constructing the NoC than 2-D mesh, when there are not too many nodes.
INTRODUCTION
With the advance of the VLSI technology, future System-on-Chip (SoC) will integrate from several dozens to hundreds of cores in a single billion-transistor chip and the on-chip communication is soon becoming the bottleneck. Bus-based architecture suffers from the clear bottleneck of the share media used for the transmission. The bus allows only one communication at a time, all the cores in the system share its bandwidth and its operating frequency decreases with the system growth.
Network on Chip (NoC), a new chip design paradigm concurrently proposed by many research groups (Benini and De Micheli, 2002; Kumar et al., 2002), is expected to be an important architectural choice for future SoCs. Using a network to replace global wiring has advantages of structure, performance and modularity. Performance and power efficiency are the important concerns in NoC architecture design. Consider a 10x10 tile-based NoC, assuming a regular mesh topology and 32 bit link width in 0.18 um technology and minimal spacing, under 100 Mbit sec-1 pair-wise communication demands, interconnects will dissipate 290W of power (Hu et al., 2005). Thus, reducing the power consumption on global interconnects is a key factor to the success of NoC designs.
A new interconnection architecture named THIN (Triple-based Hierarchical Interconnection Network) was proposed by Qiao et al. (2007) and Shi et al. (2006). THIN is a particular case of WK-recursive topology whose basic modules are 3-node complete graph. THIN offers a high degree of regularity, scalability and symmetry which very well conform to a modular design and implementation of NoC. In this study, we thoroughly studied the network properties and power consumption of THIN and compared them with 2-D mesh from a theoretical perspective.
NETWORK TOPOLOGY PROPERTIES OF THIN
THIN is a hierarchical and scalable interconnection network and it emphasizes particularly on decreasing the node degree, reducing the links and shortening the diameter. Figure 1 shows the topology of THIN. As shown in Fig. 1a, we define a single node as a level 0 THIN. A level 1 THIN can be constructed by connecting three nodes with three communication channels and then forming a triangle, as shown in Fig. 1b. The level 1 THIN is the base component to form any level THIN.
THIN is easily scalable and the constructing process is: replacing the node of level 1 THIN with lower level THIN to structure a higher one, reiterating this process, we can get any level THIN, as illustrated in Fig. 2.
The topology of THIN is very simple and the node degree is very low. THIN has obviously hierarchical, symmetric and scalable characteristic. The nodes in the lowest hierarchy of THIN are fully connected, whilst other hierarchies have relatively less number of links and thus the complexity of network is reduced and the silicon costs is decreased.
As interconnection network can be mainly characterized by two factors: Number of links and diameter.
| Fig. 1: | Topology of THIN |
| Fig. 2: | Constructing process of level k THIN |
This section addresses these principle properties of THIN and compares it with 2-D mesh. In the following, we first introduce the definitions and notations of these properties.
Definition 1: We use Lk to denote the number of links in a level k THIN.
According to the constructing process of THIN, the number of links in a level k THIN can be represented by Eq. 1:
| (1) |
From Eq. 1 we can know:
| (2) |
where, N = 3k, represents the number of nodes in level k THIN.
Definition 2: Pi,j is used to represent the path from vertices i and j of a graph G, we call the distance between i and j the length of the shortest Pi,j and denote it by Di,j.
Definition 3: The diameter of a graph G, denoted by DG, is the maximum of the distance Di,j over all pairs of vertices of G. By the definition:
DG = max(Di,j) |
(3) |
Let DTHIN(k) denotes the diameter of a level k THIN. Following the constructing process of THIN, DTHIN(k) can be represented as Eq. 4:
| (4) |
From Eq. 4, we can know that:
| (5) |
Table 1 compares the network properties of THIN with 2-D mesh, where N denotes the number of nodes in network.
The number of links is used to represent the cost and complexity of a network. When the nodes of a network increase, the links should increase in the linear model in order to minimize the connect cost.
| Table 1: | Comparison of topoloty properties of THIN and 2-D mesh |
The links of THIN are the fewest when they have the same network size. This is very important for constructing NOC, because the fewer the number of links is, the less the chip resource will be cost.
The diameter is one of important parameters for interconnection network and it impacts the communication delay between nodes. In a packet switching network, the diameter is always required to be as short as possible. The diameter of THIN is shorter than 2-D mesh when the network size is not very large. The comparison results show that when there are not too many cores, THIN is a better candidate for constructing NOC, taking into account the number of links and diameter.
LATENCY OF THIN
To evaluate an interconnection network, the network latency must be taken into account. In this section, we mainly research the zero-load latency of THIN and compare it and 2-D mesh.
In the study, Duato et al. (1997), a zero-load latency model is presented for wormhole switching networks. Suppose the message contains L-bit data. The phit size and flit size are assumed to be equivalent and equal to the physical data channel width of W bits. The routing header is assumed to be 1 flit; thus the message size is L+W bits. The latency to transfer the message in the network is:
| (6) |
where, tr is the time spent by the router to make a routing decision; ts is the intra-router or switching delay and tw is the inter-router delay (the propagation delay across the wires of an external channel). L/W is the packet payload and when addresses and data must be transmitted.
The first expression in Eq. 6 computes the latency to transfer the packet header, while the second one determines the time spent by the packet payload to reach the destination node following the header in a pipelined fashion. In this study, Davg is taken as the average distance of the interconnection network.
Definition 4: The average distance of a interconnection network is the result of the sum of all the minimal path length between any two nodes in the network dividing by the total number of paths (Dong et al., 1997) and we denote it by Davg. Davg can be calculated as the following equation:
| (7) |
where, DG represents the diameter and ρ(i) denotes the probability of the message which transmission distance is i over all the messages in the network.
The average distance of a level k THIN, denoted by Davg_THIN, is given in:
| (8) |
The study Dong et al. (1997) gives the equation to calculate the average distance of 2-D mesh:
| (9) |
Increasing network degree can reduce the average distance of an interconnection network. So, it is very difficult to accurately evaluate the latency of interconnection networks with different degree, if only using the average distance without taking into account the network degree. In this study, we use the normalized average distance (Peng, 2004) when analyzing the latency.
Definition 5: The normalized average distance of an interconnection network, denoted by μ, is the result of the average distance Davg multiplied by the degree d:
μ = d.Davg |
(10) |
The normalized average distance of a level k THIN, denoted by μTHIN, can be obtained by Eq. 11:
| (11) |
where, N represents the number of nodes in the THIN.
We use μ2-D Mesh to denote the normalized average distance of a 2-D mesh and it can be given by:
| (12) |
| Fig. 3: | Comparison of zero-load latency between THIN and 2-D mesh |
In this study, when comparing the zero-load latency of different interconnection networks, we use the normalized average distance μ to take place the average distance Davg. Based on Eq. 6 and 11, the zero-load latency of level k THIN, denoted by TTHIN, is given by:
| (13) |
The zero-load latency of a 2-D mesh is given by:
| (14) |
Figure 3 compares the zero-load latency generated by THIN and 2-D mesh, respectively. The same routing decision, network switching and communication bandwidth are used by both interconnection networks. Suppose the routing decision time (tr), switching delay (ts) and channel delay (tw) all are fixed constant and we use the normalized average distance to measure the zero-load latency. Figure 3 indicates that the zero-load latency of THIN is lower than 2-D mesh when the scale of network is not very large.
THIN AND 2-D MESH POWER MODEL AND COMPARISON
The power consumption of SoC especially from the interconnection network becomes more and more important for the whole power optimization. With the high speed and great amount of data exchange among the chip components, power problem must be solved, because consumers demand longer battery life in addition to lower cost in computers, battery-operated systems and many consumer products. In this section, we analyze and model the power consumption of THIN and compare it with 2-D mesh. The model computes power dissipation for a packet crossing the interconnect network in low traffic mode that there is no packet contention.
As defined in the study Ye et al. (2002), the average energy consumed for transferring a packet is dissipated on three components: (1) The internal node switches, located on the intermediate nodes between ingress and egress ports, (2) The internal buffers, used to temporarily store the packers and (3) The interconnect wires for packet transfer. Es is defined as the average switching energy dissipated in a node for packet transfer, Eb is the buffering energy and the average wiring energy dissipated between two nodes is defined as Ew. We use a single parameter Esb to denote both the buffering and switching energy dissipated in a node. We call Esb router energy. Defining Epacket as the average power dissipated for packet transfer, we can have:
| (15) |
where, Davg represents the average distance of a interconnection network. In order to simplify the calculations, we define:
β = Ew/Esb |
(16) |
The parameter β shows the relation of wiring and router energy dissipation for a packet transfer.
Taking into account the network degree, we use the normalized average distance described in section 3 when model the power consumption of interconnection network. Based on Eq. 11 and 15, the average energy dissipated for a packet transfer in THIN, denoted by ETHIN, is given by:
| (17) |
The average power dissipated for a packet transfer in 2-D mesh is given by:
| (18) |
| Fig. 4: | Ratio of packet transfer power dissipation for a level 2 THIN and mesh (3x3) |
| Fig. 5: | Ratio of packet transfer power dissipation in THIN and 2-D mesh for different values of β and N |
In this study, we use the method mentioned by Rahmati et al. (2006) to compare the energy consumption of THIN and 2-D mesh. Therefore, we define K as follows:
| (19) |
where, K shows the ration of the energy dissipated for 2-D mesh and THIN for a packer transfer. Figure 4 shows the ratio of packet transfer power dissipation for a level 2 THIN and 2-D mesh (3x3) as function of β. Depending on all values of β, the power consumption ratio may vary from 0.75-0.78. This means that the THIN consumes lower amount of power than its mesh counterpart.
Figure 5 shows the K as a function of β and N (number of nodes). As can be seen in the figure, with the network scale enlarged, THIN will consumes more power than 2-D mesh. Because with the number of nodes increasing, the normalized average distance of THIN will be longer than 2-D mesh.
CONCLUSION
In this study, we study the communication latency and power consumption of THIN and compare them with 2-D mesh. THIN is preferable to construct interconnection network for system-on-chip when the network size is not very large. Our future research should be on modeling the energy consumption for high traffic loads in THIN.
ACKNOWLEDGMENTS
The authors wish to acknowledge the support of the National Natural Science
Foundation of China (No. 61100173, 51305021, U1334211, No. 11226173 and 61102163)
and fund of ShaanXi Province Education Department (No. 2013JK1139) and Fundamental
Research Funds for the Central Universities (2012JBZ014). This project is also
supported by China Postdoctoral Science Foundation (No. 2013M542370) and supported
by the Specialized Research Fund for the Doctoral Program of Higher Education
of China (Grant No. 20136118120010). This work is also supported by Scientific
Research Program Funded by Xi'an University of Science and Technology (Program
No. 201139). This job is also supported by Science and Technology Project of
Xi'an (CXY1139 (7) and CX1262