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. 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:
From Eq. 1 we can know:
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:
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:
From Eq. 4, we can know that:
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:
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:
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:
The study Dong et al. (1997) gives the equation
to calculate the average distance of 2-D mesh:
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:
The normalized average distance of a level k THIN, denoted by μTHIN,
can be obtained by Eq. 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:
|
| 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:
The zero-load latency of a 2-D mesh is given by:
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:
where, Davg represents the average distance of a interconnection
network. In order to simplify the calculations, we define:
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:
The average power dissipated for a packet transfer in 2-D mesh is given by:
|
| 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:
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
).
Subscribe Today
