A Buffer Allocation Algorithm for Network-on-Chip
with Self-similar Traffic *
*
This work was supported by the National Natural Science Foundation of China under Contracts 61204024 and 61179036, as well as the Natural Science Founda-
tion of Jiangsu Province under Contract BK2011185.
Wei Ni, Yanzhu Liu
†
, Su Zhang
Institute of VLSI Design
Hefei University of Technology
Hefei, Anhui Province, China
{ni.wei, zhangsu}@hfut.edu.cn
†
alishapi1111@126.com
Yanhui Yang, Jichun Bu
LZeal Information Technology Co., Ltd
Wuxi, Jiangsu Province, China
{yangyh, bujch}@lzeal.com
Abstract – A buffer allocation algorithm based on self-similar
queuing model is proposed, with the consideration of self-similar
communication characteristics of Networks-on-Chip and virtual-
channels. It calculates the overflow probability of each virtual-
channel according the Discrete Poisson Pareto Burst Process
(DPPBP) model, which is the basis of distributing buffer re-
sources. And the experimental results indicate that the average
packet latency is lower than that of existing algorithm in the con-
dition of the same buffer resources.
Index Terms - network-on-chip, self-similar, buffer allocation
algorithm, DPPBP, virtual-channel.
I. INTRODUCTION
Wormhole routing and virtual-channel flow control are
widely used in Networks-on-Chip (NoC). Buffers are valuable
resources for NoC and the amount of used buffer resources
has an impact on the performance of the overall system. Uni-
form buffer allocation is the most universal and simple method
to improve performance. The traffic load of each port on
different nodes is different, however, since researchers recent-
ly found that the traffic of some specific applications in NoC
exhibited self-similar characteristics [1][2]. It’s necessary to
get an appropriate allocation of buffer resources to match the
self-similar communication patterns.
A dynamic virtual-channel allocation algorithm featuring
the Service-Level (SL) priority tag is proposed in [3][4] to
support traffic communication requirements. In [5], the busy
input ports in routers can temporarily share the free and empty
buffers of other inputs, so that dynamically to adjust the depth
of the buffers. Hu first proposed an algorithm under commu-
nication patterns, e.g. exponential distribution, which is based
on the queuing model and store-and-forward or virtual cut-
through routing [6]. According to the conclusion in [6],
DPPBP is used to predict the optimal buffer size based on
wormhole flow control [7]. However, the NoC in [7] does not
have virtual-channels, the similar algorithm based on virtual-
channels is studied further in this paper.
II.
SELF -SIMILAR QUEUING MODEL
For a time series, self-similarity would imply that the spa-
tio-temporal properties of the object remain preserved with
respect to scaling in time. It has long range dependence (LRD)
and burstiness characteristics in time scale. The self-similar
degree of a stationary stochastic process with self-similarity is
represented by Hurst parameter
H
.
Each node of NoC will generates a traffic stream in accor-
dance with certain rules to match self-similar characteristics.
Assuming the coordinate
()
,xy of one node is
,
x
y
I
P , and thus
,
x
y
Y is the volume of the generated traffic, which is an aggre-
gation of several flows
s
. The moment each flow starts to
generate traffic is denoted by
x,
s
y
w
, and the generation rate of
the flow
s
at each time
{
}
,,
1, 1, ,
ss
x
yxy
ii
ωτ
+− ∈ …
is
,
x
y
R
.
These times
,,,
,..., 1
sss
xy xy xy
ωτω
+−
are called the active time,
such that
,
s
x
y
τ
is called active period of flow
s
. That is, traffic
is not generated before
,
s
x
y
and after
,,
1
ss
xy xy
τ
−+
. At time
t
,
the total number of flow arrivals is
,
t
x
y
ε
, and the whole traffic
generated is given as
()
()
,,,
1,
ss
xy xy xy
sZ
Yt t tZ
θω
+
+
∈
=−+∈
¦
,
where
()
{
}
,,
,
, 1, 2,...,
0,
s
x
yxy
s
xy
Ri
i
others
τ
θ
∈
°
=
®
°
¯
.
With the assumption that all of the nodes generate traffic in-
dependently, and the flow generate rate
,
x
y
R
is equal to each
other, therefore
,
x
y
R
is also denoted by
R
. It will be a DPPBP
process when the length of active time period
is distributed
as a Pareto process with the location parameter
0
c
and the
shape parameter
, and when the number of flows
,
t
x
y
ε
is dis-
tributed as a Poisson process with parameter
,
x
y
. It has been
proved that DPPBP is a progressive self-similarity process
with the Hurst parameter
(3 ) / 2H
α
=−
in [8].
If each virtual-channel of a node is modeled as a queuing
____________________________________
978-1-4799-4808-6 /14/$31.00 ©2014 IEEE
资源评论
