基于多路径路由的片上网络重组缓存的上界优化方法

摘要

本发明公开了基于多路径路由的片上网络重组缓存的上界优化方法，通过以下步骤来实现：首先计算片上网络的路由节点冲突矩阵；计算每条子业务流冲突系数；求目标业务流无交叉路径组的冲突系数表；从冲突系数表得出最大最小预测范围；计算重组缓存值，得出优化结果。本发明的有益效果是提出来一种冲突预测片上网络重组缓存上界的优化方法来预测重组缓存的最大值和最小值，相比于全遍历方法，可以缩短分析时间，简化算法复杂度，提高效率，从而有效减少重组缓存区面积，降低片上网络设计成本。

说明书

技术领域

本发明属于集成电路片上网络设计技术领域，涉及基于多路径路 由的片上网络重组缓存的上界优化方法。

背景技术

《Very Large Scale Integration Design》2007年1-11页中‘Amethod  for routing packets across multiple paths in NoCs with in-order delivery  and fault-tolerance guarantees’一文提出针对无交叉子业务流的多路径 路由方法，以降低网络带宽需求和功耗需求，并针对瞬时和永久错误 提出容错方案；不足之处在于没有讨论如何设置重组缓存的大小，从 而存在丢包或重组缓存面积过大的风险；

《Design,Automation & Test in Europe》2009年1058–1063页中 ‘In-network reorder buffer to improve overall NoC performance while  resolving thein-order requirement problem’一文中介绍了通过将重组缓 存从路由器外边移到路由器里边，通过共享给其他业务流来提高重组 缓存的利用率；不足之处同样没有给出重组缓存的设置方案，存在丢 包或重组缓存面积过大的风险；

《IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF  INTEGRATED CIRCUITS AND SYSTEMS》2010年12期1973-1986 页中‘Buffer Optimization in Network-on-Chip Through Flow  Regulation’一文基于网络演算理论提出了片上路由器输入缓存的分 析模型及其大小的分析方法；不足之处在于没有进一步研究位于业务 流输出端的包重组缓存大小的分析方法。

《IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF  INTEGRATED CIRCUITS AND SYSTEMS》第31卷第一期(2012年 1月)第146-159页文章‘Memory-Efficient On-Chip Network with  Adaptive Interface’提出使用一种流线型的重新排序机制来实现业务 在目的节点的排序，不足之处仍然没有给出重组缓存大小的设置方 案，存在丢包或重组缓存面积过大的风险。

《中国科技论文在线电子杂志》2013年64期中‘多路径路由 NoC重组缓存区的分析及优化’一文基于网络验算提出了计算两条目 标子流的重组缓存区模型，不足之处在于该文章在优化重组缓存上界 中采用传统全遍历法，分析时间长，算法复杂度大。

基于以上背景，本发明提出来一种冲突预测片上网络重组缓存上 界的优化方法，通过冲突矩阵，推导出每条子业务流的冲突系数，进 而从无交叉路径组冲突系数表中选出最大最小范围，来预测重组缓存 的最大值和最小值。

发明内容

本发明的目的在于提供基于多路径路由的片上网络重组缓存的 上界优化方法，解决了现有技术没有给出重组缓存上界的设置方案， 存在重组缓存面积过大、浪费成本的问题。

本发明所采用的技术方案是通过以下步骤来实现：

步骤a：计算片上网络的路由节点冲突矩阵；

步骤b：计算每条目标子业务流冲突系数；

步骤c：求目标业务流无交叉路径组的冲突系数表；

步骤d：从冲突系数表得出最大最小预测范围；

步骤e：根据预测路径计算重组缓存值，得出优化结果。

进一步，所述路由为多路径最短路由，所述片上网络为 N×N(N≥2)的网络结构。

进一步，业务流为分析路径得到的业务流划分为目标业务流和冲 突业务流，目标业务流定义为所需要研究的对象，拆分为两条目标子 业务流；冲突业务流定义为对目标业务流造成冲突的业务流，由于冲 突的存在导致目标流中数据包后发先至形成重组缓存区。

进一步，所述子业务流，为通过全遍历得到全拆分情况下所产生 的所有子流，全拆分指每个路由节点都完全拆分。

进一步，所述目标主流重组缓存值的上界普通计算公式为

$\mathrm{BufferSize}=\max \{\frac{(D_1^{\mathrm{upp}}-D_2^{\mathrm{low}})}{{\mathrm{\Delta t}}_2},\frac{(D_2^{\mathrm{upp}}-D_1^{\mathrm{low}})}{{\mathrm{\Delta t}}_1}\},$

式中Δt₁表示目标子流1上数据包的注入时间间隔，Δt₂表示目标子流2上数据包的注入时间间隔，为目标子流1延迟上界 与目标子流2延迟下界的差值，为目标子流2延迟上界与 目标子流1延迟下界的差值。

进一步，所述冲突矩阵为N²×4矩阵，行代表路由节点，范围为 ∈(1,N²)，列代表东西南北四个方向，由于是最短路由，北和西方向均 为0，每个元素代表路由节点在其方向上的冲突系数，假设网路中共 有M条冲突流，则节点在其方向上的冲突系数定义为 (其中k代表冲突流，i代表路由节点，d代表路由 节点的方向)，即为每条冲突流的参数(εr+ηb)乘以相应冲突流的节点 拆分流量p的总和，r和b分别为表示业务流特性的平均转发速率和 突发度，ε和η分别为平均转发速率和突发度对冲突的贡献指数，p为 冲突流在每个节点的拆分流量，其中ε，η∈(0,1]。

进一步，所述每条目标子业务流冲突系数，为把每条目标子流经 过的节点在其方向上的冲突系数加和C_sub-tag＝ΣC_i,d(其中i代表目标 子流经过的节点，d代表节点的方向)。

进一步，所述无交叉，定义为拆分的两条目标子流不共享除起始 节点和目的节点外的任一相同路由节点，通过设置约束条件 A＝4(N-1),N≥2进行挑选。

进一步，所述无交叉路径组冲突系数表，为挑选出无交叉路径组 中路径冲突系数大的，作为无交叉路径组的冲突系数 C_(m,n)＝max(C_sub-tag-m,C_sub-tag-n)(其中m代表路径组的第一条子流，n代表 路径组的第二条子流)，依据为路径组中重组缓存上界与延迟上界大 的趋势一致，而子流冲突系数与子流延迟的趋势一致，因而可以用路 径组中冲突系数大的来表征重组缓存上界。

进一步，所述从冲突系数表得出最大最小预测范围，为从无交叉 路径组对应的冲突系数表中得到由所有相同最值组成的预测范围对 应的路径组，根据预测路径组计算相应的重组缓存值，从中挑选出重 组缓存最大最小值。

本发明的有益效果是提出来一种冲突预测片上网络重组缓存上 界的优化方法来预测重组缓存的最大值和最小值，可以减少运行时 间，降低运算复杂度。

附图说明

图1是本发明的方法步骤流程图；

图2是本发明实施例的业务流配置图；

图3(a)-(d)是本发明实施例目标业务流f和冲突业务流f₄、f₃f₅、 f₆的全拆分图；

图3(e)是本发明实施例目标子业务流f₁的冲突情况图；

图3(e*)是本发明实施例切割后目标子业务流f₁的冲突情况图；

图3(f)是本发明实施例目标子业务流f₂的冲突情况图；

图4(a)-(d)是本发明实施例冲突流f₃f₄f₅f₆的均匀拆分分布图；

图5是本发明实施例冲突流f₃f₄f₅f₆对应的拆分矩阵图；

图6是本发明实施例20条目标子业务流冲突系数与延迟上界的 对比图；

图7是本发明实施例4条冲突流对应的预测结果图。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细说明。

如图1所示本发明的步骤流程，本发明涉及一种片上网络多路径 最短路由算法，尤其涉及一种片上网络重组缓存上界的优化预测方 法。

本发明克服了现有优化方法中分析时间长，算法复杂度大等不 足，提供了一种以最短多路径路由方式为切入点，以冲突预测为核心， 片上网络(NoC)中重组缓存上界的优化方法。

为了解决上述问题，本发明是通过以下方案实现的：

步骤a：计算片上网络的路由节点冲突矩阵；

步骤b：计算每条目标子业务流冲突系数；

步骤c：求目标业务流无交叉路径组的冲突系数表；

步骤d：从冲突系数表得出最大最小预测范围；

步骤e：根据预测路径计算重组缓存值，得出优化结果。

通过冲突矩阵，推导出每条子业务流的冲突系数，进而从无交叉 路径组冲突系数表中选出最大最小范围，来预测重组缓存的最大值和 最小值，相比于普通遍历方法，可以缩短分析时间，简化算法复杂度， 提高效率，从而有效减少重组缓存区面积，并降低片上网络设计成本。

本发明一种片上网络重组缓存上界的优化方法特点还在于：

优化方法中路由为多路径最短路由，所述片上网络为N×N(N≥2) 的网络结构。

优化方法中业务流，为分析路径得到的业务流划分为目标业务流 和冲突业务流，目标业务流定义为所需要研究的对象，拆分为两条目 标子业务流；冲突业务流定义为对目标业务流造成冲突的业务流，由 于冲突的存在导致目标流中数据包后发先至形成重组缓存区。

优化方法中子业务流，为通过全遍历得到全拆分情况下所产生的 所有子流，全拆分指每个路由节点都完全拆分。

优化方法中目标主流重组缓存上界公式为

$\mathrm{BufferSize}=\max \{\frac{(D_1^{\mathrm{upp}}-D_2^{\mathrm{low}})}{{\mathrm{\Delta t}}_2},\frac{(D_2^{\mathrm{upp}}-D_1^{\mathrm{low}})}{{\mathrm{\Delta t}}_1}\},$

式中Δt₁表示目标子流1上数据包的注入时间间隔，Δt₂表示目标子流 2上数据包的注入时间间隔，为目标子流1延迟上界与目 标子流2延迟下界的差值，为目标子流2延迟上界与目标 子流1延迟下界的差值。

优化方法中冲突矩阵，为N²×4矩阵，行代表路由节点，范围为 ∈(1,N²)，列代表东西南北四个方向，由于是最短路由，北和西方向均 为0，每个元素代表路由节点在其方向上的冲突系数，假设网路中共 有M条冲突流，则节点在其方向上的冲突系数定义为 (其中k代表冲突流，i代表路由节点，d代表路由 节点的方向)，即为每条冲突流的参数(εr+ηb)乘以相应冲突流的节点 拆分流量p的总和，r和b分别为表示业务流特性的平均转发速率和 突发度，ε和η分别为平均转发速率和突发度对冲突的贡献指数，p为 冲突流在每个节点的拆分流量，其中ε，η∈(0,1]。

优化方法中每条子业务流冲突系数，为把每条目标子流经过的节 点在其方向上的冲突系数加和C_sub-tag＝ΣC_i,d(其中i代表目标子流经 过的节点，d代表节点的方向)。

优化方法中无交叉，定义为拆分的两条目标子流不共享除起始节 点和目的节点外的任一相同路由节点，通过设置约束条件 A＝4(N-1),N≥2进行挑选。

优化方法中无交叉路径组冲突系数表，为挑选出无交叉路径组中 路径冲突系数大的，作为无交叉路径组的冲突系数 C_(m,n)＝max(C_sub-tag-m,C_sub-tag-n)(其中m代表路径组的第一条子流，n代表 路径组的第二条子流)，依据为路径组中重组缓存上界与延迟上界大 的趋势一致，而子流冲突系数与子流延迟的趋势一致，因而可以用路 径组中冲突系数大的来表征重组缓存上界。

优化方法中从冲突系数表得出最大最小预测范围，为从无交叉路 径组对应的冲突系数表中得到由所有相同最值组成的预测范围对应 的路径组。

优化方法中预测重组缓存最大最小值，得出优化结果，为根据预 测路径组计算相应的重组缓存值，从中挑选出重组缓存最大最小值。

本发明通过冲突矩阵，推导出每条子业务流的冲突系数，进而从 无交叉路径组冲突系数表中选出最大最小范围，来预测重组缓存的最 大值和最小值，相比于普通遍历方法，可以缩短分析时间，简化算法 复杂度，提高效率，从而有效减少重组缓存区面积，并降低片上网络 设计成本。

下面列举具体实施例对本发明进行说明：

实施例1：以网络规模为4×4、拓扑结构为二维网格的片上网格 为例，推导优化过程。

推导过程中所需的公式如表1所示。(下面公式中，m代表路由 节点号，n代表流号，N代表N×N的网络结构)：

表1

如图2所示，f_＜1,16＞为目标业务流，f_＜2,12＞f_＜3,8＞f_＜6,11＞和f_＜6,16＞为冲 突业务流(f_＜m,n＞中m代表源节点，n代表目的节点)，为了方便计算， 令f＝f_＜1,16＞、f₃＝f_＜2,12＞、f₄＝f_＜3,8＞、f₅＝f_＜6,11＞和f₆＝f_＜6,16＞。

本实施例中设置目标流f的输入到达曲线(表 示每100个周期发送8个数据包，一次最多发送一个数据包)； 冲突流f₃的输入到达曲线：冲突流f₄的输入 到达曲线：冲突流f₅的输入到达曲线： 冲突流f₆的输入到达曲线： 在本发明中r和b可以取任意值。

所有的路由节点采用FCFS仲裁策略，提供的服务曲线为 β(t)＝R(t-T)⁺，其中，R表示服务速率，T表示处理延迟，且当t＞T时， (t-T)⁺＝t-T；当t≤T时，(t-T)⁺＝0。本实施例中设置β(t)＝0.33(t-3)⁺， 表示每三周期处理一个数据包，处理延迟为三个周期。在本发明中R 和T可以取任意值。

步骤1：计算片上网络的路由节点冲突矩阵：

按照图4a-d的冲突流配置，得到16×4冲突矩阵，行代表16个路 由节点，列代表东西南北四个方向，如图5中a,b,c和d分别为由p 构成的冲突流f₃,f₄,f₅和f₆的拆分矩阵。设定ε＝η＝1(本发明中 ε，η∈(0,1]，为了精确计算结果，实例中设定ε＝η＝1)，把各个冲突流 的r和b，分别带入各自的拆分矩阵，最后将四个修改后的拆分矩阵 相加，表2为路由节点在其方向上的冲突系数：

表2

表2构成目标业务流的冲突矩阵B：

$B=\left(\begin{array}{c}1\\ 2\\ 3\\ 4\\ 5\\ 6\\ 7\\ 8\\ 9\\ 10\\ 11\\ 12\\ 13\\ 14\\ 15\\ 16\end{array}\right)\left(\begin{array}{cccc}E& W& S& N\\ 0& 0& 0& 0\\ 10.04& 0& 10.04& 0\\ 10.06& 0& 10.06& 0\\ 0& 0& 10.06& 0\\ 0& 0& 0& 0\\ 40.1& 0& 40.1& 0\\ 20.08& 0& 30.08& 0\\ 0& 0& 20.06& 0\\ 0& 0& 0& 0\\ 30.08& 0& 10.02& 0\\ 20.06& 0& 10.02& 0\\ 0& 0& 20.04& 0\\ 0& 0& 0& 0\\ 10.02& 0& 0& 0\\ 20.04& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)$

步骤2：计算每条子业务流的冲突系数：

f_＜1,16＞为目标业务流，进行全拆分共有20条目标子流(此处为最 短路由，设置业务流的路径时只有两个方向)，通过分析冲突情况建 立冲突矩阵，计算出20条目标子流中每条子流的冲突系数，即把子 流经过的节点在其对应方向上的冲突系数加和，节点冲突系数为 设定ε＝η＝1，如上表2所示，通过加和得出20 条子流所对应的冲突系数，图6为20条子流对应的冲突系数与延迟 上界的对比图，可以看出结果基本吻合，表明可以用冲突系数来表征 延迟。

例如：

目标子流1经过节点(1 2 3 4 8 12 16)，根据目标业务流的冲突矩 阵B，把1节点向东，2节点向东，3节点向东，4节点向南，8节点 向南，12节点向南的节点冲突系数加和为70.26。

目标子流2经过节点(1 2 3 7 8 12 16)，根据目标业务流的冲突矩 阵B，把1节点向东，2节点向东，3节点向南，7节点向东，8节点 向南，12节点向南的节点冲突系数加和为80.28。

目标子流3经过节点(1 2 3 7 11 12 16)，根据目标业务流的冲突 矩阵B，把1节点向东，2节点向东，3节点向南，7节点向南，11 节点向东，12节点向南的节点冲突系数加和为90.28。

目标子流4经过节点(1 2 3 7 11 15 16)，根据目标业务流的冲突 矩阵B，把1节点向东，2节点向东，3节点向南，7节点向南，11 节点向南，15节点向东的节点冲突系数加和为80.24。

目标子流5经过节点(1 2 6 7 8 12 16)，根据目标业务流的冲突矩 阵B，把1节点向东，2节点向南，6节点向东，7节点向东，8节点 向南，12节点向南的节点冲突系数加和为110.32。

目标子流6经过节点(1 2 6 7 11 12 16)，根据目标业务流的冲突 矩阵B，把1节点向东，2节点向南，6节点向东，7节点向南，11 节点向东，12节点向南的节点冲突系数加和为120.32。

目标子流7经过节点(1 2 6 7 11 15 16)，根据目标业务流的冲突 矩阵B，把1节点向东，2节点向南，6节点向东，7节点向南，11 节点向南，15节点向东的节点冲突系数加和为110.28。

目标子流8经过节点(1 2 6 10 11 12 16)，根据目标业务流的冲突 矩阵B，把1节点向东，2节点向南，6节点向南，10节点向东，11 节点向东，12节点向南的节点冲突系数加和为120.32。

目标子流9经过节点(1 2 6 10 11 15 16)，根据目标业务流的冲突 矩阵B，把1节点向东，2节点向南，6节点向南，10节点向东，11 节点向南，15节点向东的节点冲突系数加和为110.28。

目标子流10经过节点(1 2 6 10 14 15 16)，根据目标业务流的冲 突矩阵B，把1节点向东，2节点向南，6节点向南，10节点向南， 14节点向东，15节点向东的节点冲突系数加和为90.22。

目标子流11经过节点(1 5 6 7 8 12 16)，根据目标业务流的冲突 矩阵B，把1节点向南，5节点向东，6节点向东，7节点向东，8节 点向南，12节点向南的节点冲突系数加和为100.28。

目标子流12经过节点(1 5 6 7 11 12 16)，根据目标业务流的冲突 矩阵B，把1节点向南，5节点向东，6节点向东，7节点向南，11 节点向东，12节点向南的节点冲突系数加和为110.28。

目标子流13经过节点(1 5 6 7 11 15 16)，根据目标业务流的冲突 矩阵B，把1节点向南，5节点向东，6节点向东，7节点向南，11 节点向南，15节点向东的节点冲突系数加和为100.24。

目标子流14经过节点(1 5 6 10 11 12 16)，根据目标业务流的冲 突矩阵B，把1节点向南，5节点向东，6节点向南，10节点向东，11 节点向东，12节点向南的节点冲突系数加和为110.28。

目标子流15经过节点(1 5 6 10 11 15 16)，根据目标业务流的冲 突矩阵B，把1节点向南，5节点向东，6节点向南，10节点向东， 11节点向南，15节点向东的节点冲突系数加和为100.24。

目标子流16经过节点(1 5 6 10 14 15 16)，根据目标业务流的冲 突矩阵B，把1节点向南，5节点向东，6节点向南，10节点向南， 14节点向东，15节点向东的节点冲突系数加和为80.18。

目标子流17经过节点(1 5 9 10 11 12 16)，根据目标业务流的冲 突矩阵B，把1节点向南，5节点向南，9节点向东，10节点向东， 11节点向东，12节点向南的节点冲突系数加和为70.18。

目标子流18经过节点(1 5 9 10 11 15 16)，根据目标业务流的冲 突矩阵B，把1节点向南，5节点向南，9节点向东，10节点向东， 11节点向南，15节点向东的节点冲突系数加和为60.14。

目标子流19经过节点(1 5 9 10 14 15 16)，根据目标业务流的冲 突矩阵B，把1节点向南，5节点向南，9节点向东，10节点向南， 14节点向东，15节点向东的节点冲突系数加和为40.08。

目标子流20经过节点(1 5 9 13 14 15 16)，根据目标业务流的冲 突矩阵B，把1节点向南，5节点向南，9节点向南，13节点向东， 14节点向东，15节点向东的节点冲突系数加和为30.06。

步骤3：求目标业务流无交叉路径组的冲突系数表：

目标业务流f<1,16>通过流量分割共有20条目标子流(与步骤 2中的20条求出冲突系数的子流相同)，这20条目标子流为全遍历 所得到的从源节点1到目的节点16的所有可能的目标子流，此处我 们讨论的是多路径路由(即目标业务流拆分为多条目标子流的情况)， 本发明设定目标流拆分为两条目标子流，因此对20条所有可能的目 标子流进行两两组合，共有190对。无交叉为拆分的两条目标子流不 共享除起始节点和目的节点外的任一相同路由节点，通过设置约束条 件A＝4(N-1),N≥2,进行挑选。本实施例中对于4×4网格，通过设置约 束条件为A＝4(4-1)＝12，从190对路径组中挑选得到40对无交叉的路 径组，每一对路径组即为一对目标流，此处目标流和冲突流均匀拆分， 拆分比为0.5，与图4中冲突流均匀全拆分相统一，而本发明中目标 流和冲突流拆分比取值范围为(0.1-0.9)，求解40对无交叉路径组对 应的冲突系数表。取路径组中子流冲突系数大的为该路径组的冲突系 数。

1.目标子流1的冲突系数为70.26，目标子流13的冲突系数为 100.24，路径组(113)的冲突系数为目标子流13的冲突系数100.24。

2.目标子流1的冲突系数为70.26，目标子流15的冲突系数为 100.24，路径组(115)的冲突系数为目标子流15的冲突系数100.24。

3.目标子流1的冲突系数为70.26，目标子流16的冲突系数为 80.18，路径组(116)的冲突系数为目标子流16的冲突系数80.18。

4.目标子流1的冲突系数为70.26，目标子流18的冲突系数为 60.14，路径组(118)的冲突系数为目标子流1的冲突系数70.26。

5.目标子流1的冲突系数为70.26，目标子流19的冲突系数为 40.08，路径组(119)的冲突系数为目标子流1的冲突系数70.26。

6.目标子流1的冲突系数为70.26，目标子流20的冲突系数为 30.06，路径组(120)的冲突系数为目标子流1的冲突系数70.26。

7.目标子流2的冲突系数为80.28，目标子流13的冲突系数为 100.24，路径组(213)的冲突系数为目标子流13的冲突系数100.24。

8.目标子流2的冲突系数为80.28，目标子流15的冲突系数为 100.24，路径组(215)的冲突系数为目标子流15的冲突系数100.24。

9.目标子流2的冲突系数为80.28，目标子流16的冲突系数为 80.18，路径组(216)的冲突系数为目标子流2的冲突系数80.28。

10.目标子流2的冲突系数为80.28，目标子流18的冲突系数为 60.14，路径组(218)的冲突系数为目标子流2的冲突系数80.28。

11.目标子流2的冲突系数为80.28，目标子流19的冲突系数为 40.08，路径组(219)的冲突系数为目标子流2的冲突系数80.28。

12.目标子流2的冲突系数为80.28，目标子流20的冲突系数为 30.06，路径组(220)的冲突系数为目标子流2的冲突系数80.28。

13.目标子流3的冲突系数为90.28，目标子流15的冲突系数为 100.24，路径组(315)的冲突系数为目标子流15的冲突系数100.24。

14.目标子流3的冲突系数为90.28，目标子流16的冲突系数为 80.18，路径组(316)的冲突系数为目标子流3的冲突系数90.28。

15.目标子流3的冲突系数为90.28，目标子流18的冲突系数为 60.14，路径组(318)的冲突系数为目标子流3的冲突系数90.28。

16.目标子流3的冲突系数为90.28，目标子流19的冲突系数为 40.08，路径组(319)的冲突系数为目标子流3的冲突系数90.28。

17.目标子流3的冲突系数为90.28，目标子流20的冲突系数为 30.06，路径组(320)的冲突系数为目标子流3的冲突系数90.28。

18.目标子流4的冲突系数为80.24，目标子流11的冲突系数为 100.28，路径组(411)的冲突系数为目标子流11的冲突系数100.28。

19.目标子流4的冲突系数为80.24，目标子流14的冲突系数为 110.28，路径组(414)的冲突系数为目标子流14的冲突系数110.28。

20.目标子流4的冲突系数为80.24，目标子流17的冲突系数为 70.18，路径组(417)的冲突系数为目标子流4的冲突系数80.24。

21.目标子流5的冲突系数为110.32，目标子流15的冲突系数 为100.24，路径组(515)的冲突系数为目标子流5的冲突系数110.32。

22.目标子流5的冲突系数为110.32，目标子流16的冲突系数 为80.18，路径组(516)的冲突系数为目标子流5的冲突系数110.32。

23.目标子流5的冲突系数为110.32，目标子流18的冲突系数 为60.14，路径组(518)的冲突系数为目标子流5的冲突系数110.32。

24.目标子流5的冲突系数为110.32，目标子流19的冲突系数 为40.08，路径组(519)的冲突系数为目标子流5的冲突系数110.32。

25.目标子流5的冲突系数为110.32，目标子流20的冲突系数 为30.06，路径组(520)的冲突系数为目标子流5的冲突系数110.32。

26.目标子流6的冲突系数为120.32，目标子流15的冲突系数 为100.24，路径组(615)的冲突系数为目标子流6的冲突系数120.32。

27.目标子流6的冲突系数为120.32，目标子流16的冲突系数 为80.18，路径组(616)的冲突系数为目标子流6的冲突系数120.32。

28.目标子流6的冲突系数为120.32，目标子流18的冲突系数 为60.14，路径组(618)的冲突系数为目标子流6的冲突系数120.32。

29.目标子流6的冲突系数为120.32，目标子流19的冲突系数 为40.08，路径组(619)的冲突系数为目标子流6的冲突系数120.32。

30.目标子流6的冲突系数为120.32，目标子流20的冲突系数 为30.06，路径组(620)的冲突系数为目标子流6的冲突系数120.32。

31.目标子流7的冲突系数为110.28，目标子流14的冲突系数 为110.28，路径组(714)的冲突系数为目标子流7或14的冲突系数 110.28。

32.目标子流7的冲突系数为110.28，目标子流17的冲突系数 为70.18，路径组(717)的冲突系数为目标子流7的冲突系数110.28。

33.目标子流8的冲突系数为120.32，目标子流13的冲突系数 为100.24，路径组(813)的冲突系数为目标子流8的冲突系数120.32。

34.目标子流8的冲突系数为120.32，目标子流19的冲突系数 为40.08，路径组(819)的冲突系数为目标子流8的冲突系数120.32。

35.目标子流8的冲突系数为120.32，目标子流20的冲突系数 为30.06，路径组(820)的冲突系数为目标子流8的冲突系数120.32。

36.目标子流9的冲突系数为110.28，目标子流11的冲突系数 为100.28，路径组(911)的冲突系数为目标子流9的冲突系数110.28。

37.目标子流9的冲突系数为110.28，目标子流12的冲突系数 为110.28，路径组(912)的冲突系数为目标子流9或12的冲突系数 110.28。

38.目标子流10的冲突系数为90.22，目标子流11的冲突系数 为100.28，路径组(1011)的冲突系数为目标子流11的冲突系数 100.28。

39.目标子流10的冲突系数为90.22，目标子流12的冲突系数 为110.28，路径组(1012)的冲突系数为目标子流12的冲突系数 110.28。

40.目标子流10的冲突系数为90.22，目标子流17的冲突系数 为70.18，路径组(1017)的冲突系数为目标子流10的冲突系数90.22。

如表3所示为无交叉路径组冲突系数表与全遍历所得重组缓存 表。

表3

步骤4：从冲突系数表得出最大最小预测范围：

从无交叉冲突系数表中挑选出突系数最大值对应的路径组为(6 15)、(616)、(618)、(619)、(620)、(813)、(819)、(820)， 根据网络演算，计算出路径组(615)、(616)、(618)、(619)、(620)、 (813)、(819)、(820)对应的重组缓存依次为35.4869、34.4503、 34.6949、29.8786、29.8891、32.5543、26.4018、26.4122。因此，重 组缓存最大值为35.4869。

从无交叉冲突系数表中挑选出突系数最小值对应的路径组为(1 18)、(119)、(120)，根据网络演算，计算出路径组(118)、(119)、 (120)对应的重组缓存依次为25.809、21.0235、21.0339。因此，重组 缓存最小值为35.4869。

步骤5：计算40对无交叉路径组对应的重组缓存值：

全遍历得到40对无交叉路径组对应的重组缓存值，得到重组缓 存最大值为35.4869，相应路径组为(615)；最小值为21.0235，相应 路径组为(119)与冲突预测所得结果吻合(步骤4)，验证了冲突预测优 化方法的准确性。

以40对无交叉路径组中的任一路径组为例(此处为方便计算，选 取(119)路径组，即目标流拆分为路径f₁(1 2 3 4 8 12 16)和路径f₂(1  5 9 10 14 15 16))，分析重组缓存的推导过程，步骤如下：

(1)比例计算：

对于目标流(119)路径组的情况，如图3.(a)(b)(c)(d)所示通过流 量拆分，目标流f_＜1,16＞拆分成两条子流，分别为标号为1的f₁和标 号为19的f₂；冲突流分别为f₃、f₄、f₅和f₆。均匀全拆分情况下， f₃拆分为f₃₁、f₃₂，f₄拆分成f₄₁、f₄₂、f₄₃、f₄₄、f₄₅、f₄₆，f₅拆分为f₅₁、f₅₂， f₆拆分为f₆₁、f₆₂、f₆₃、f₆₄、f₆₅、f₆₆。

由图3和图4可知，所有流的拆分比例分别为：$P_{\left(f_{31}\right)}=P_{\left(f_{32}\right)}=0.5,P_{\left(f_{41}\right)}=P_{\left(f_{46}\right)}=0.25,P_{\left(f_{42}\right)}=P_{\left(f_{43}\right)}=P_{\left(f_{44}\right)}=P_{\left(f_{45}\right)}=0.125,$$P_{\left(f_{51}\right)}=P_{\left(f_{52}\right)}=0.5,P_{\left(f_{61}\right)}=P_{\left(f_{66}\right)}=0.25,P_{\left(f_{62}\right)}=P_{\left(f_{63}\right)}=P_{\left(f_{64}\right)}=P_{\left(f_{65}\right)}=0.125.$

(2)所有流的输入到达曲线：

目标流f的输入到达曲线

目标子流f₁的输入到达曲线

目标子流f₂的输入到达曲线

冲突流f₃的输入到达曲线：

冲突子流f₃₁的输入到达曲线${\alpha }_3^{f_{31}}=r_{31}t+b_{31}=P_{\left(f_{31}\right)}(0.08t+10);$

冲突子流f₃₂的输入到达曲线${\alpha }_3^{f_{32}}=r_{32}t+b_{32}=P_{\left(f_{32}\right)}(0.08t+10);$

冲突流f₄的输入到达曲线：

冲突子流f₄₁的输入到达曲线${\alpha }_2^{f_{41}}=r_{41}t+b_{41}=P_{\left(f_{41}\right)}(0.08t+20);$

冲突子流f₄₂的输入到达曲线${\alpha }_2^{f_{42}}=r_{42}t+b_{42}=P_{\left(f_{42}\right)}(0.08t+20);$

冲突子流f₄₃的输入到达曲线${\alpha }_2^{f_{43}}=r_{43}t+b_{43}=P_{\left(f_{43}\right)}(0.08t+20);$

冲突子流f₄₄的输入到达曲线${\alpha }_2^{f_{44}}=r_{44}t+b_{44}=P_{\left(f_{44}\right)}(0.08t+20);$

冲突子流f₄₅的输入到达曲线${\alpha }_2^{f_{45}}=r_{45}t+b_{45}=P_{\left(f_{45}\right)}(0.08t+20);$

冲突子流f₄₆的输入到达曲线${\alpha }_2^{f_{46}}=r_{46}t+b_{46}=P_{\left(f_{46}\right)}(0.08t+20);$

冲突流f₅的输入到达曲线：

冲突子流f₅₁的输入到达曲线${\alpha }_6^{f_{51}}=r_{51}t+b_{51}=P_{\left(f_{51}\right)}(0.08t+30);$

冲突子流f₅₂的输入到达曲线${\alpha }_6^{f_{52}}=r_{52}t+b_{52}=P_{\left(f_{52}\right)}(0.08t+30);$

冲突流f₆的输入到达曲线：

冲突子流f₆₁的输入到达曲线${\alpha }_6^{f_{61}}=r_{61}t+b_{61}=P_{\left(f_{61}\right)}(0.08t+40);$

冲突子流f₆₂的输入到达曲线${\alpha }_6^{f_{62}}=r_{62}t+b_{62}=P_{\left(f_{62}\right)}(0.08t+40);$

冲突子流f₆₃的输入到达曲线${\alpha }_6^{f_{63}}=r_{63}t+b_{63}=P_{\left(f_{63}\right)}(0.08t+40);$

冲突子流f₆₄的输入到达曲线${\alpha }_6^{f_{64}}=r_{64}t+b_{64}=P_{\left(f_{64}\right)}(0.08t+40);$

冲突子流f₆₅的输入到达曲线${\alpha }_6^{f_{65}}=r_{65}t+b_{65}=P_{\left(f_{65}\right)}(0.08t+40);$

冲突子流f₆₆的输入到达曲线${\alpha }_6^{f_{66}}=r_{66}t+b_{66}=P_{\left(f_{66}\right)}(0.08t+40).$

(3)目标子流等价服务曲线计算：

a.计算目标子流f₁的等价服务曲线：

如图3.(e)所示，有13条流与f₁形成冲突，f₄₁和f₆₁之间为交 叉冲突，对f₄₁在路由节点4和路由节点8之间进行切割，切割后 的流记为f₄₁'，如图3.(e*)。

f₁的等价服务曲线推导如下：

从节点3、4中去除f₃₁的服务，得到节点3、4提供给f₁和f₄₁的 等价服务曲线为：${\beta }_{\left(\mathrm{3,4}\right)}^{\{f_1,f_{41}\}}=\in ({\beta }_3\otimes {\beta }_4,{\alpha }_3^{f_{31}})$

从节点2中去除f₄₂、f₄₄的服务，得到节点2、3、4提供给f₁和f₄₁的等价服务曲线为：${\beta }_{\left(\mathrm{2,3,4}\right)}^{\{f_1,f_{41}\}}=\in ({\beta }_2,{\alpha }_2^{f_{42}+f_{44}})\otimes \in ({\beta }_3\otimes {\beta }_4,{\alpha }_3^{f_{31}})$

从节点2、3、4中去除f₄₁的服务，得到节点2、3、4提供给f₁的 等价服务曲线为：${\beta }_{\left(\mathrm{2,3,4}\right)}^{\left\{f_1\right\}}=\in (\in ({\beta }_2,{\alpha }_2^{f_{42}+f_{44}})\otimes \in ({\beta }_3\otimes {\beta }_4,{\alpha }_3^{f_{31}}),{\alpha }_2^{f_{41}})$

从节点8中移除f′₄₁、f₄₂、f₄₃的服务，得到节点8提供给f₁和f₆₁的 等价服务曲线为：${\beta }_{\left(8\right)}^{\{f_1,f_{61}\}}=\in \left({{\beta }_8,\alpha }_8^{{f_{41}^{\prime }+f}_{42}+f_{43}}\right)$

从节点16中去除f₂、f₆₄、f₆₅、f₆₆的服务，得到节点16提供给f₁、 f₆₁、f₆₂、f₆₃的等价服务曲线：${\beta }_{\left(16\right)}^{\{f_1,f_{61},f_{62},f_{63}\}}=\in ({\beta }_{16},{\alpha }_{16}^{f_2+f_{64}+f_{65}+f_{66}})$

从节点12、16中移除f₆₂、f₆₃的服务，得到节点12、16提供给f₁和f₆₁的等价服务曲线为：${\beta }_{\left(\mathrm{12,16}\right)}^{\{f_1,f_{61}\}}=\in ({\beta }_{12}\otimes \in ({\beta }_{16},{\alpha }_{16}^{f_2+f_{64}+f_{65}+f_{66}}),{\alpha }_{12}^{f_{62}+f_{63}})$

因此节点8、12、16提供给f₁和f₆₁的等价服务曲线为：

${\beta }_{\left(\mathrm{8,12,16}\right)}^{\{f_1,f_{61}\}}=\in ({\beta }_8,{\alpha }_8^{f_{41}^{\prime }+f_{42}+f_{43}})\otimes \in ({\beta }_{12}\otimes \in ({\beta }_{16},{\alpha }_{16}^{f_2+f_{64}+f_{65}+f_{66}}),{\alpha }_{12}^{f_{62}+f_{63}})$

从节点8、12、16中移除f₆₁的服务，得到节点8、12、16提供 给f₁的等价服务曲线为：

${\beta }_{\left(\mathrm{8,12,16}\right)}^{\left\{f_1\right\}}=\in (\in ({\beta }_8,{\alpha }_8^{f_{41}^{\prime }+f_{42}+f_{43}})\otimes \in ({\beta }_{12}\otimes \in ({\beta }_{16},{\alpha }_{16}^{f_2+f_{64}+f_{65}+f_{66}}),{\alpha }_{12}^{f_{62}+f_{63}}),{\alpha }_8^{f_{61}})$

最后，根据串联定理，求出节点1、2、3、4、8、12、16提供给 f₁的等价服务曲线为：

$\left(\begin{array}{c}{\beta }_{\mathrm{eq}}^{\left\{f_1\right\}}={\beta }_1\otimes {\beta }_{\left(\mathrm{2,3,4}\right)}^{\left\{f_1\right\}}\otimes {\beta }_{\left(\mathrm{8,12,16}\right)}^{\left\{f_1\right\}}\\ ={\beta }_1\otimes \in (\in ({\beta }_2,{\alpha }_2^{f_{42}+f_{44}})\otimes \in ({\beta }_3\otimes {\beta }_4,{\alpha }_3^{f_{31}}),{\alpha }_2^{f_{41}})\\ \otimes \in (\in ({\beta }_8,{\alpha }_8^{f_{41}^{\prime }+f_{42}+f_{43}})\otimes \in ({\beta }_{12}\otimes \in ({\beta }_{16},{\alpha }_{16}^{f_2+f_{64}+f_{65}+f_{66}}),{\alpha }_{12}^{f_{62}+f_{63}}),{\alpha }_8^{f_{61}})\\ =R_{\left(\mathrm{1,16}\right)}^{f_{1,\mathrm{eq}}}{(t-T_{\left(\mathrm{1,16}\right)}^{f_{1,\mathrm{eq}}})}^{+}\end{array}\right)$

b.计算目标子流f₂的等价服务曲线：

如图3.(f)所示，有7条流与f₂形成冲突,分别为 f₁、f₆₁、f₆₂、f₆₃、f₆₄、f₆₅、f₆₆。

从节点16中去除f₁、f₆₁、f₆₂、f₆₃的服务，得到节点16提供给f₂、 f₆₄、f₆₅、f₆₆的等价服务曲线为：${\beta }_{\left(16\right)}^{\{f_2,f_{64},f_{65},f_{66}\}}=\in ({\beta }_{16},{\alpha }_{16}^{f_1+f_{61}+f_{62}+f_{63}})$

从节点15、16中移除f₆₄、f₆₅的服务，得到节点15、16提供给f₂和f₆₆的等价服务曲线为：${\beta }_{\left(\mathrm{15,16}\right)}^{\{f_2,f_{66}\}}=\in ({\beta }_{15}\otimes \in ({\beta }_{16},{\alpha }_{16}^{f_1+f_{61}+f_{62}+f_{63}}),{\alpha }_{15}^{f_{64}+f_{65}})$

从节点10、14、15、16中移除f₆₆的服务，得到节点10、14、15、 16提供给f₂的等价服务曲线为：

${\beta }_{\left(\mathrm{10,14,15,16}\right)}^{\left\{f_2\right\}}=\in ({\beta }_{10}\otimes {\beta }_{14}\otimes \in ({\beta }_{15}\otimes \in ({\beta }_{16},{\alpha }_{16}^{f_1+f_{61}+f_{62}+f_{63}}),{\alpha }_{15}^{f_{64}+f_{65}}),{\alpha }_{10}^{f_{66}})$

最后，根据串联定理，求出节点1、5、9、10、14、15、16提供 给f₂的等价服务曲线为：

$\left(\begin{array}{c}{\beta }_{\mathrm{eq}}^{\left\{f_1\right\}}={\beta }_1\otimes {\beta }_5\otimes {\beta }_9\otimes {\beta }_{\left(\mathrm{10,14,15,16}\right)}^{\left\{f_2\right\}}\\ ={\beta }_1\otimes {\beta }_5\otimes {\beta }_9\otimes \in ({\beta }_{10}\otimes {\beta }_{14}\otimes \in ({\beta }_{15}\otimes \in ({\beta }_{16},{\alpha }_{16}^{f_1+f_{61}+f_{62}+f_{63}}),{\alpha }_{15}^{f_{64}+f_{65}}),{\alpha }_{10}^{f_{66}})\\ =R_{\left(\mathrm{1,16}\right)}^{f_{2,\mathrm{eq}}}{(t-T_{\left(\mathrm{1,16}\right)}^{f_{2,\mathrm{eq}}})}^{+}\end{array}\right)$

(4)目标流重组缓存上界计算：

计算重组缓存区的公式如下：

$\mathrm{BufferSize}=\max \{r_1(T_2+b_2/R_2-T_1^{\mathrm{low}})+b_1+r_1{T}_1,r_2(T_1+b_1/R_1-T_2^{\mathrm{low}})+b_2+r_2{T}_2\}$

${\mathrm{RB}}_1=r_1(T_2+b_2/R_2-T_1^{\mathrm{low}})+b_1+r_1{T}_1=r_1(T_{\left(\mathrm{1,16}\right)}^{f_{2,\mathrm{eq}}}+b_2/R_{\left(\mathrm{1,16}\right)}^{f_{2,\mathrm{eq}}}-T_1^{\mathrm{low}})+b_1+r_1{T}_1$

${\mathrm{RB}}_2=r_2(T_1+b_1/R_1-T_2^{\mathrm{low}})+b_2+r_2{T}_2=r_2(T_{\left(\mathrm{1,16}\right)}^{f_{1,\mathrm{eq}}}+b_1/R_{\left(\mathrm{1,16}\right)}^{f_{1,\mathrm{eq}}}-T_2^{\mathrm{low}})+b_2+r_2{T}_2$

BufferSize＝max{RB₁，RB₂}

对于4×4的网络，$T_1^{\mathrm{low}}=3\times (2\times 4-1)=21,T_2^{\mathrm{low}}=3\times (2\times 4-1)=21.$把计 算出的等参数带入到重组缓存区的计算公式 中，得到路径组(119)的重组缓存上界为21.0235。

验证结果的正确性：

对比步骤4和5，说明本发明可以很好的预测重组缓存的最大最 小值。在实际计算中，我们只需要计算预测的路径组对应的重组缓存 大小，相比全遍历，可以节省遍历时间和算法复杂度。

如图7所示，横坐标表示4×4网络中40对无交叉路径组；纵坐 标表示两组曲线的取值；正方形曲线代表40对无交叉路径组对应的 冲突系数表(步骤4所得结果)，圆形曲线代表全遍历得到的40对无交 叉路径组对应的重组缓存大小(步骤5所得结果)。步骤4从3个冲突 系数值来预测一个重组缓存最小值，步骤5从40个冲突系数值来预 测一个重组缓存最小值，计算效率提高了13.3倍，准确率达到33.3％； 步骤4从8个冲突系数值来预测一个重组缓存最小值，步骤5从40 个冲突系数值来预测一个重组缓存最小值，计算效率提高了5倍，准 确率达到12.5％。

本发明为了更清楚地描述预测过程，仅以4×4的片上网络实例， 对于更大规模的网络，预测结果会更明显。另外，上例只列举了两条 子业务流，不代表本发明只能处理目标业务流拆分为两条子流的网 络，可以拓展到拆分为任意数量的子流的处理；示例中虽然仅以二维 网格结构的NoC为例说明，不代表本发明只适用于该拓扑结构，可 以适用于任意结构的片上网络。