- 1 -
基于自相似性的片上网络业务量模型设计#
陈亦欧，胡剑浩*
（电子科技大学通信抗干扰技术国家级重点实验室，成都，611731）
5 摘要：本文在分形理论的基础上，一方面验证了承载经典 DSP 系统：MIMO-OFDM 发端系统的
片上网络链路业务量的自相似性；另一方面根据大量实验数据拟合通信系统的 MPSoC 数据关
联模型参数与 Hurst 参数的函数关系，提出预测和估计片上网络业务量 Hurst 参数的方法。
实验表明，采用本文提的业务量模型估计的 Hurst 参数与其真实值误差较小，能较准确的描
述业务量的自相似性。 10
关键词：集成电路；片上网络；业务量模型；自相似性
中图分类号：TN4
Self-Similar Traffic Modeling of On-chip Interconnection
Networks 15
CHEN Yiou, HU Jianhao
(National Key Lab of Science and Technology on Communications, University of Electronic
Science and Technology of China,Chengdu,611731)
Abstract: This paper proposes a self-similar NoC traffic model based on multiple parameters to
provide accurate benchmarks for Network on Chip (NoC) designs and verifications. It verifies the 20
self-similarity of MIMO-OFDM based NoC traffic. Using theoretical derivation and experimental
method, this paper establishes an MPSoC information relevence model, and provides an empirical
fitting function between the parameters of the relevence model and Hurst parameter, and
establishs the method to estimate Hurst parameter of NoC traffic. The case studies prove that this
traffic model can achieve an approximate and effective Hurst parameter. 25
Key words: integrated circuit; Network on Chip; traffic model; self-similarity
0 引言
在 NoC 研究中，仿真与性能评估时为了模拟真实的 NoC 系统，需要加入业务量信息，
包括数据的注入方式、数据在链路传递的分布模型等。以映射算法为例，如果要将
解码器映射在 NoC 平台上，需要知道准确的网络业务量信息，才能建立正确的目标函数与
约束条件的模型。
NoC 研究初期，业务量模型的研究发展非常缓慢。当需要应用业务量模型进行仿真和
验证的时候，通常采用基于马尔科夫模型和自回归模型的短程相关模型[1]。后来，Varatkar
等人经过研究发现，和宏观网络类似，NoC 的业务量也具有突发性。这种突发性可以用自35
相似性以及分形理论进行描述[2][3][4]。由于自相似随机过程与基于马尔科夫模型的泊松过
程在时域序列和统计值上有很大差异[2]，基于泊松过程的业务量模型不能准确的描述业务
量特性，利用其进行仿真与性能评估获得的结论也是不可靠的。当前虽然已有一些对分形特
性的业务量建模与应用的研究，但主要集中在对特定系统的自相似性的证明、基于经验的参
数统计和利用已知的自相似程度对延时建模这几个方面，缺乏一个完整的，根据实际应用的40
参数估计自相似程度的通用方法。
- 2 -
为了解决上述问题，本文从分形理论出发，分析 NoC 业务量自相似特性的形成原因，
利用 MIMO-OFDM 实例检验承载了 DSP 系统的 NoC 业务量的自相似性；根据通信系统的
信号处理特点建立 MPSoC 数据关联模型，利用典型 DSP 系统进行建模实验，用实测的业务
量 Hurst 参数拟合数据关联模型参数与 Hurst 参数的函数关系，并利用上述拟合函数对 NoC45
业务量的 Hurst 参数进行预测和估计。实验表明，采用本文提出的业务量模型估计的 Hurst
参数与其真实值误差较小，能较准确的描述业务量的自相似性。
1 自相似理论与 R/S 分析法
自相似性表现为当时间或空间进行缩放时，业务量的时空特性不会随之变化。随机自相
似过程的数学定义如下： 50
如果随机过程{ ( ), }X t t R 满足：
( ) ( ), 0
d
HX t X t
（1）
则称{ ( )}X t 是自相似（self-similar）的，表示为 H-ss。其中
d
表示有限维上的分布相等，H
为 Hurst 参数或自相似参数。Hurst 参数是描述业务量自相似程度的参数，其取值范围为
(,1) 。Hurst 参数的值越大，业务量的自相似特性越明显，突发性越强。通过数学方法估55
算 Hurst 参数可以帮助判断业务量是否具有自相似性，并分析其突发性的强度。目前，国内
外学者已经提出多种 Hurst 参数估计法，大致可分为时域估计和频域估计两类，包括方差时
间法、R/S 分析法、绝对值法、留数法、周期图法、Whittle 估计法和小波分析法等。本文将
采用经典的 R/S 分析法[5]对采集的业务量数据进行分析。
R/S 分析法的具体步骤如下： 60
1) 将长度为 N的序列 { , 1,2,..., }iX X i N 分成 K个子序列，每个子序列长度为 /n N K ，
用 ( ) , 1,2,...,kinX X i K 表示，其中： ( ) ( 1) 1,...,ink i n inX X X ；
2) 计算各个子序列（聚集序列）的数学期望与方差：
( ) ( 1) 1[ ] ... /i
n
k i n inE X X X n
（2）
2
2 ( )
( 1)
1
1
( , ) [ ]
i
n
n
i i n l k
l
S k n X E X
n
（3） 65
3) 计算各子序列的 R/S 统计量：
2
( )
( 1)
1
max 0, (1),..., ( ) min 0, (1),..., ( )
( , ) / ( , )
1
[ ]
i i i i
i
k k k k
i i
n
n
i n l k
l
W W n W W n
R k n S k n
X E X
n
（4）
其中， ( )( 1) 1 ( 1)( ) ... [ ]i i
n
k i n i n l kW l X X l E X 。
4) 计算各子序列的 R/S 统计量的均值：
1
1
( ) / ( ) ( , ) / ( , )
K
i i
i
E R n S n R k n S k n
K
（5） 70
5) 取其他的 n值，重复步骤 1）-4），得到不同 n值对应的 ( ) / ( )E R n S n
6) 作 ln ( ) / ( ) ~ lnE R n S n n曲线，根据最小均方根准则拟合该曲线得到斜率为 H参数的直
线。
- 3 -
2 片上网络的业务量建模
典型 DSP 系统结构 75
经典的 DSP 系统一般为流水结构，如图 1 所示。其中，节点按功能类型分为两类：控
制节点（图中灰色节点）和处理节点（图中白色节点）。处理节点以流水节拍的方式实现特
定功能，而控制节点对各处理节点的任务进行配置与调度。在图 1 所示的系统中，控制节点
（节点 1）依次向各处理节点发送配置信息；各处理节点在收到配置信息与前一级节点送来
的数据后开始工作，工作完毕后，将结果数据输出到下一级节点。 80
1
2 3 4 5
7
8
9
111213
15
16
6
1014
图 1 典型 DSP 系统的结构图
为了建立简单、通用的业务量模型，本文进行如下两点假设：
1) 应用的数据源是非自相似的。如果采用带自相似性的应用数据源，网络业务量的
自相似性既包含数据源的自相似性，也包括网络传输带来的自相似性，分析过程85
复杂。本文旨在研究网络传输带来的自相似性，因此假设源节点的数据注入满足
马尔科夫模型。
2) 应用基于流水结构。流水结构能够提高数据处理的效率，降低功耗，因此复杂的
通信信号处理系统通常设计为流水结构，本文旨在分析复杂系统的业务量，故采
用基于流水结构的应用。 90
NoC 业务量模型
定义：MPSoC 数据关联模型是描述 NoC 应用特征的有向图，表示为 ( , )G G V U 。其
中节点数为 | |V ，边数为 | |U 。每个节点 ( , 1,2,...,| |)i iv v V i V 表示 NoC 上承载应用
子任务的处理核，每条有向边 , ( , 1, 2,...,| |)k i j ku u u U k U 表示从节点 i到节点 j的链
路。已知网络拓扑、应用的任务流图和映射方案后，将其信息抽象为数据关联模型的参数：95
关联系数（ ir ）和数据注入率（ ,i jf ）。 ir 描述节点 i和应用源节点之间的相关性，取值由
节点间距离和处理级数决定； ,i jf 描述单位时间内节点 i到节点 j的链路上的业务量负载强
度。图 1 所示系统的数据关联模型如图 2 所示。
2 3 4 5 6 7 8 9 10 11 12 131 14 15 16
1r 2r 3r 4r 5r 6r 7r 8r 9r 10r 11r 12r 13r 14r 15r 16r
2,3f1,2f 4,5f3,4f 6,7f5,6f 8,9f7,8f 10,11f9,10f 12,13f11,12f 14,15f13,14f 15,16f
图 2 图 1 中系统的数据关联模型 100
在 NoC 仿真平台 MSNS[6]上进行 NoC 业务量序列的采集，仿真过程中源节点注入 10
万个数据包，NoC 各节点用 ON/OFF 模型进行抽象。节点的 ON 和 OFF 状态分别对应忙闲
- 4 -
中国科技论文在线
状态。实验过程中，数据注入率的变化范围为 10Mbps 到 100Mbps，变化步长为 10Mbps。
由于应用层采用的数据包大小会影响数据传输和业务量特征，因此本文选用四种不同的数据
包长度，分别为 300，500，700 和 900 微片。用 R/S 分析法估计链路的 Hurst 参数。图 3 至105
图 6 给出了不同数据包长度下，Hurst 参数与数据关联模型参数的关系曲线。
0 5 10 15
关联系数
H
u
rs
t参
数
0 5 10 15
关联系数
H
u
rs
t参
数
注入率为10Mbps
注入率为20Mbps
注入率为40Mbps
注入率为60Mbps
注入率为60Mbps
注入率为80Mbps
注入率为100Mbps
图 3 包长为 300 时 Hurst 参数与数据关联模型参数的关系曲线
0 5 10 15
关联系数
H
u
rs
t参
数
5 10 15
关联系数
H
u
rs
t参
数
0
注入率为10Mbps
注入率为20Mbps
注入率为40Mbps
注入率为60Mbps
注入率为60Mbps
注入率为80Mbps
注入率为100Mbps
图 4 包长为 500 时 Hurst 参数与数据关联模型参数的关系曲线 110
0 5 10 15
关联系数
H
u
rs
t参
数
5 10 150
关联系数
H
u
rs
t参
数
注入率为10Mbps
注入率为20Mbps
注入率为40Mbps
注入率为60Mbps
注入率为60Mbps
注入率为80Mbps
注入率为100Mbps
图 5 包长为 700 时 Hurst 参数与数据关联模型参数的关系曲线
- 5 -
中国科技论文在线
0 5 10 15
关联系数
H
u
rs
t参
数
5 10 150
关联系数
H
u
rs
t参
数
注入率为10Mbps
注入率为20Mbps
注入率为40Mbps
注入率为60Mbps
注入率为60Mbps
注入率为80Mbps
注入率为100Mbps
图 6 包长为 900 时 Hurst 参数与数据关联模型参数的关系曲线
从图 3 至图 6 可以看出，Hurst 参数的取值与数据关联模型参数有很强的关联性。例如，115
当关联系数低于 3 时，多数情况下 Hurst 参数值小于 ，表明不具有自相似性。随着关联
系数的增大，业务量受处理核之间相关性的影响与对应的 Hurst 参数随之增大。因此，分析
链路延时时，对这两种情况要区别对待。对前者而言，由于其业务量的自相似性很弱，故采
用马尔科夫模型对其链路延时进行建模；对后者而言，利用基于 Hurst 参数的 MMPP 模型
分析其链路延时。 120
当数据注入率从 10Mbps 变化到 100Mbps 时，大部分的曲线都很接近，且具有相近的最
大值和最小值。然而在数据包长度为 300 微片的情况下，当注入率范围在 10Mbps~60Mbps
时，曲线斜率明显比其他注入率和数据包长度下的曲线斜率小。造成这个现象的原因是，虫
洞路由中，当某条虫占据一条路由路径后，整个数据包的数据将连续地从该路径上传过。如
果数据包长度较短，则数据包能快速传完，并释放占用的路由资源；如果此时数据注入率也125
较低，则网络拥塞程度较轻，业务量的突发性较小，相应的 Hurst 参数的值也较小。
综上所述，由数据包长度和数据注入率的联合取值将业务量 Hurst 参数的估计分为两种
类型，如图 7 所示。
100
10
60
300 500 700 900
注
入
率
/M
b
p
s
数据包长/flits
类型1
类型2
图 7 两种业务量类型的分布空间 130
由于同一类型中各条 Hurst 参数曲线非常接近，因此采用最小均方估计法将同一类型中
所有曲线用同一个二次函数进行拟合，其函数式为：
2
1 2 3i iH p r p r p （6）
其中， , 1,2,3ip i 是二次函数的系数。两种业务量类型的经验拟合函数分别为：
类型 1： iH r r （7） 135
类型 2： iH r r （8）
为了比较拟合函数的性能，另外用线性函数对图 3 至图 6 中的关系曲线进行拟合。图 8
- 6 -
中国科技论文在线
给出了用线性函数和二次函数拟合关系曲线的均方误差（Mean Square Errors, MSEs）。其中，
线性函数和二次函数分别用实线和虚线表示。
10 20 40 60 80 100
M
S
E
Injection rate/Mbps
M
S
E
Injection rate/Mbps
10 20 40 60 80 100
包长700、二次函数
包长300、二次函数
包长700、线性函数
包长300、线性函数
包长900、二次函数
包长500、二次函数
包长900、线性函数
包长500、线性函数
140
图 8 线性函数和二次函数的 MSE
从0可以看出，二次函数拟合曲线在各种数据包长度与数据注入率条件下获得的误差都
较小，性能较优。
业务量模型的验证与评估
本节用实例评估上节提出的 NoC 业务量模型的性能。将图 1 所示的 DSP 系统映射到145
4 4 Mesh 拓扑上，得到的数据关联模型如图 9 所示。设计两个业务量类型不同的评估实例，
参数如表 1 所示。
2 3 4
5 6 7 8
9 10 11 12
1
13 14 15 16
1r 2r 3r 4r
5r 6r 7r 8r
9r 10r 11r 12r
13r 14r 15r 16r
2,3f1,2f 3,4f
6,7f5,6f 7,8f
10,11f9,10f 11,12f
14,15f13,14f 15,16f
5,9f
1,5f
9,13f
图 9 4 4 Mesh NoC 的数据关联模型
表 1 评估实例的参数设置 150
数据包长度/flits 数据注入率/Mbps
评估实例 1 (分布类型 1) 300 40
评估实例 2 (分布类型 2) 700 80
分别采用式（7）和式（8）预测实例 1 和实例 2 的 Hurst 参数。同时，在 MSNS 仿真平
台上对该应用进行建模仿真，采集真实的链路业务量序列，用 R/S 分析法估计其 Hurst 参数。
采用业务量模型预测的 Hurst 参数和仿真实测的结果如 10 所示。
- 7 -
中国科技论文在线
0 5 10 15
1
仿真结果
模型预测
关联系数
H
u
rs
t参
数
0 5 10 15
1
关联系数
H
u
rs
t参
数
仿真结果
模型预测
155
(a) 实例 1 (b) 实例 2
图 10 评估实例的预测和实测结果比较
从图 10 可以看出，尽管通过 MSNS 仿真平台实测的 Hurst 参数曲线有一定的波动，但
采用业务量模型预测的 Hurst 参数曲线仍能较好的跟踪实测曲线包络。因此，本文提出的业
务量模型能较好的捕捉 NoC 链路的突发特性。 160
3 结论
本文在分形理论的基础上，一方面验证了承载经典 DSP 系统：MIMO-OFDM 发端系统
的 NoC 链路业务量的自相似性；另一方面根据大量实验数据拟合通信系统的 MPSoC 数据关
联模型参数与 Hurst 参数的函数关系，提出预测和估计 NoC 业务量 Hurst 参数的方法。实验
表明，采用本文提出的业务量模型估计的 Hurst 参数与其真实值误差较小，能较准确的描述165
业务量的自相似性。
[参考文献]
[1] M. Moadeli, A. Shahrabi, W. Vanderbauwhede, et al. An Analytical Performance Model for the Spidergon
NoC. In Proc. 21st International Conf. on Advanced Information Networking and Applications, Niagara Falls, ON,
Canada, 2007, 1014-1021. 170
[2] G. Varatkar, R. Marculescu. On-chip traffic modeling and synthesis for MPEG-2 video applications. IEEE
Trans Very Large Scale Integration (VLSI) Systems, 2004, 12(1):108-119.
[3] Chen Y O, Hu J H, Chen G S, et al. Energy and Delay-Aware V. Ngo, J. Chang, Y. Bae, H. Cho, H. Choi.
Latency Optimization for NoC Design of Decoder Based on Self-similar Traffic Modeling. In Proc.
International Symposium on Parallel and Distributed Processing and Applications, Ontario, Canada, 2007, 289-302. 175
[4] V. Soteriou, . Wang, and L. Peh. A statistical traffic model for onchip interconnection networks. In Proc.
International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication System,
Monterey, USA, 2006, 104-116.
[5] . Taqqu, V. Teverovsky, W. Willinger. Estimators for long-range dependence: An empirical study. Fractals.
1995, 785-798. 180
[6] Z. Li, X. Ling, J. Hu. MSNS: a Top-Down MPI-Style Hierar-chical Simulation Framework for
Network-on-Chip. In Proc. International Conference on Communications and Mobile Computing, Kunming, China,
2009, 609-614.
