文献^{[ 7]}提出的IAMCS结构如图1所示。其每个输入端口具有D_n个通道组(CG),每组对应一个独立的输出方向,且组内包含多条通道。以2D Mesh为例,每个输入端口具有5个CG,对应的输出方向分别为东、南、西、北和本地。输入报文根据其流出方向进入合适的通道组,然后路由器以轮询的方式为其分配组内的一条通道。该结构进一步减少了特定输出方向上的HoL阻塞,有效降低了报文平均延时、提高了饱和吞吐率和系统的性能。为了简化IAMCS的分析模型,假定每组具有相同的通道数量 m。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 IAMCS路由器结构Fig.1 Structure of IAMCS router

IAMCS路由器使用四级流水:路由计算(RC)、通道分配(CA)、交换机分配(SA)和交换机通过(ST)^{[ 8]}。IAMCS路由器采用信用流控,当无可用信用时,将出现流控阻塞;在CA流水级,若多个报文争用相同CG的同一通道,将出现通道阻塞;在SA流水级,多个切片争用同一输出链路,将出现交换阻塞。接着,基于文献^{[ 2, 8]}的工作并针对IAMCS路由器结构,对每种阻塞展开分析,构建该路由器的分析模型。

1.1 流控阻塞

考虑到图2中流量 f₁穿越相邻的两个IAMCS路由器的情形。由于切片传递和信用生成之间存在依赖关系,故不能直接使用网络演算的结论。为此,文献^{[ 2]}将流控功能抽象成一个网络元素——流量控制器。然而,文献^{[ 2]}的分析仅针对单通道路由器,每个输入端口仅有一条通道,且每个输出端口来自下游节点的流控反馈也只有一条;而IAMCS路由器为多通道路由器,每个输入端口具有多个CG,每个输出端口来自下游节点的流控反馈亦有多条,每条对应输入端口中的一个CG。因此,文献^{[ 2]}的流控阻塞模型不能直接用于IAMCS路由器。

分析发现,在一条流量通过路由器的过程中,根据其输出方向,进入一个特定CG,切片输出过程受控于该CG对应的流控反馈;因此,针对一条流量路径,可借鉴文献^{[ 2]}的流控阻塞模型,构建其流控反馈模型,如图2(a)所示。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 流控阻塞模型Fig.2 Model for flow control blocking

图2中,B₁为f₁流经路由器R₁中通道的缓冲区大小;σ₁代表R₁的交换机;τ₁代表R₁的流量控制器。当f₁通过R₁和R₂时,由σ₁、τ₁和R₂组成的节点串为其提供服务, 、 和 依次为它们向f₁提供的服务曲线。由文献[2]可知,τ₁和R₁的服务曲线分别为:

(1)

=

(2)

消除流控反馈后,流控阻塞等价服务模型变为开环模型,如图2(b)所示。

1.2 交换阻塞

单通道路由器中,交换阻塞仅在不同输入端口争用同一输出端口时发生,且下游节点的流控反馈仅有一条;而在IAMCS中,某个输入端口的同一CG的多条通道间、不同输入端口的具有相同编号CG的多条通道间,均可能争用同一输出端口而发生交换阻塞,来自下游节点的流控反馈为多条。因此,文献^{[ 8]}的交换阻塞模型同样需要扩展后才能用于IAMCS路由器。

不失一般性,考虑北输入端口的东CG中的两条流量f₁、f₂和西输入端口的东CG中的流量f₃因争用东输出端口而竞争交换机的情况,其中f₁、f₃在下游节点的输出方向相同,进入同一个CG,共用一个流控反馈,而f₂进入另一个CG,使用另外的流控反馈。将路由器抽象成交换机σ和流量控制器τ的组合,可构建交换阻塞分析模型,如图3(a)所示。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 交换阻塞模型Fig.3 Model for switch blocking

在不同输入端口具有相同编号的CGs间,以及同一CG中的不同通道间,交换机均采用加权轮询策略为流量服务。交换机根据为流量f_i配置的权重φ_i为其提供服务。假定权重分配确保在每次轮询中报文可以完全传送,不同报文的切片在传输过程中不会交错。

每次轮询时,若当前CG中轮到的通道缓存非空,交换机将为其服务φ_i个时钟周期后,再服务下一个CG的通道缓存。故一次轮询的最长时间为 个时钟周期。因此,路由器R₁提供给f₁、f₃的等价服务曲线分别为:

=

(3)

=

(4)

提供给f₂的等价服务曲线为:

=

(5)

式中: 为交换机σ₁的服务曲线; 为流量控制器τ₁为f₁、f₃提供的服务曲线; 为流量控制器τ₁为f₂提供的服务曲线,可由1.1节的流控阻塞服务模型推导得到。

图3(b)给出了路由器R₁提供给f_i(i=1,2,3)的等价服务模型。

1.3 通道阻塞

考虑图4(a)给出的情形:在路由器R₁及R₂中具有相同的输出方向的流量f₁和f₂,在R₁的RC流水级被路由到相同的输出端口,进入CA流水级,f₁和f₂又因在R₂中具有相同输出方向被分配到同一CG,并竞争该CG中的同一通道。通道分配竞争失败的流量将被阻塞,即通道阻塞。接着在SA流水级,通道分配成功的流量将独占输出链路,分配失败的流量将发生交换阻塞。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 通道阻塞模型Fig.4 Model for ohannel blocking

由于通道分配以报文为单位进行,且不同报文的切片在穿过路由器的过程中不能交错^{[ 8]},路由器按照分配给流量f_i的权重(ρ_i个报文)提供服务。使用1.2节交换阻塞的分析方法,可得R₁提供给f₁的等价服务曲线为:

=

(6)

式中:λ_i为流量f_i的报文长度,单位为切片; 、 分别为R₁中交换机σ₁和流量控制器τ₁的服务曲线;C₁为R₁的端口服务速率,单位为切片/周期。

类似地,可得到R₁提供给f₂的等价服务曲线 ,这里不再给出。

如图4(a)所示,f₁和f₂的报文A和B在R₂中占用同一通道,共享其缓存B₃,且因争用同一输出端口而会再次出现交换阻塞,这与文献[8]通道阻塞的情形是不同的。然而,可将f₁、f₂放在一起看成一条聚集流,其切片缓存在B₃中,该聚集流经交换机σ₂后流向输出端口,其切片传输受下游节点流控反馈控制,其服务曲线记为 。由串联系统服务定理可得路由器R₂提供给聚集流的服务曲线为:

=

(7)

R₂提供给f_i的等价服务曲线依赖于它的冲突流在缓冲区入口处的到达曲线。路由器R₂为流量f₁提供的等价服务曲线为^{[ 2]}:

=∈( , ) (8)

式中: 为f₂在路由器R₂的到达曲线;∈(·,·)为等价服务曲线计算函数。

类似地,可得到为f₂提供的等价服务曲线 ,这里不再给出。流量在某个节点的到达曲线可参考文献^{[ 2]}。

图5所示的NoC平台中同时存在f₁、f₂和f₃三条流量,每条流量的路径也在图中标出。令f₁为目标流,f₂和f₃为冲突流。假设到达服从仿射曲线,服务服从延迟-速率服务曲线和确定性路由算法,基于文献^{[ 2, 8]}的方法推导目标流f₁的切片延迟上界。

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 4*4网格结构的NoCFig.5 4*4 mesh NoC

步骤1 构建等价服务分析网络。在路由器R₅中,流量f₁和f₂发生交换阻塞;在路由器R₁₀中,流量f₁和f₃发生交换阻塞;在路由器R₁₁中,流量f₁和f₃发生通道阻塞。利用网络元素构建闭环分析网络,并将其简化成前向等价服务分析网络,如图6所示。图6中所有网络元素的服务曲线公式为:

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 等价服务分析网络Fig.6 Analysis network for equivalent service

步骤2 构建冲突树。图6描绘了流量如何穿越串联的路由器,竞争共享缓冲区资源。对于这样的冲突关系,构建目标流量f₁的冲突树,如图7所示。

图7

Fig.7

	Figure Option ViewDownloadNew Window
	图7 目标流量 f1的冲突树Fig.7 Contention tree of target flow f1

步骤3 计算冲突树中流的输出曲线。采用深度优先策略遍历图7中的冲突树。首先计算流量f₂流经树枝{R₉}后,对于{R₁→R₁₆}的输出到达曲线为:

=α2Ø

(9)

流量f₂流经树枝{R₉}后,对于{R₁→R₆}的输出到达曲线与式(9)相同。然后,使用文献[2]中的嵌套冲突模型,可得f₁流经{R₁→R₆}后的输出曲线(也即对于分支{R₁₄→R₁₀}的到达曲线)为:

=α₁Ø( ∈( , ) ) (10)

再次使用嵌套冲突模型,可得对于分支{ R₁→ R₁₆}, f₃流经{ R₁₄→ R₁₀}后的输出到达曲线为:

=α₃ Ø( ∈( , )) (11)

得到所有树枝流注入树干的到达曲线后,流量 f₁的树干服务曲线可表示为:

= ∈( , ) ∈( , )

(12)

步骤4 计算延迟上界。目标流量 f₁的延迟上界可由式(13)计算得到:

=H(α₁, ) (13)

式中:H(·,·)为到达曲线与服务曲线最大水平距离的计算函数^{[ 2]}。

使用SoCLib^{[ 9]}构建基于IAMCS路由器见图5的NoC平台。为该平台分配以下嵌入式应用:在MIPS1上分配一个MP3音频解码器,处理5 kB/s的音频流;在MIPS2上分配一个JPEG解码器,处理250×160的图像;在MIPS3上分配一个MPEG2视频解码器,处理176×144的视频帧。上述应用共生成三条多媒体流量(f₁、f₂和f₃)。并在平台上设置三对测量点用于测量流量f₁、f₂和f₃的通信延迟。同时运行这3个应用,采集各测量点的踪迹文件,得到它们的端到端最大延迟;分析3个多媒体流量的踪迹文件,推导它们的仿射到达曲线,并使用前面的分析模型对端到端延迟上界进行分析。

假定一个CG的所有通道的Buffer总数为60切片,在实验平台上对不同的配置进行了多次仿真;并分别设定f₁、f₂和f₃为目标流,由分析模型推导它们的延迟上界,针对不同配置进行计算。

表1和表2列出了当报文长度分别为15和20切片,各目标流在CG所含通道数目m不同时,切片延迟的模拟和分析结果。仿真所得的最大延迟记为D _max,分析得到的延迟上界记为 。延迟结果的单位为时钟周期。从表1和表2知:

(1)IAMCS网络中,报文长度及缓存大小固定时,为通道组选择合适的通道数目可降低端到端延迟。这是因为:当通道组CG的缓存总量不变,CG中的通道数量m适当增加时,会降低HoL阻塞,而m超过合适的值后,造成通道中的缓存过小,流控反馈增加。本实验平台中,每CG中通道数目 m=2时延迟最小,与最大的通道需求为2相吻合。

表1

Table 1

表1(Table 1)

表1 报文长度为15切片时延迟的模拟和分析结果 Table 1 Simulation and analysis results when the packet is 15 flits 通道数 m MP3 JPEG MPEG2 2 49 56.08 46 53.12 47 55.09 3 55 63.36 53 59.90 55 62.09 4 89 102.31 65 74.23 80 92.79 5 185 201.04 92 99.85 151 172.61

表1 报文长度为15切片时延迟的模拟和分析结果 Table 1 Simulation and analysis results when the packet is 15 flits

表2

Table 2

表2(Table 2)

表2 报文长度为20切片时延迟的模拟和分析结果 Table 2 Simulation and analysis results when the packet is 20 flits 通道数 m MP3 JPEG MPEG2 2 53 60.93 49 57.89 51 59.58 3 60 69.85 58 65.41 59 67.77 4 103 117.88 72 82.92 90 105.73 5 211 229.78 102 111.30 170 195.79

表2 报文长度为20切片时延迟的模拟和分析结果 Table 2 Simulation and analysis results when the packet is 20 flits

(2)对所有设置均有D _max< ,说明可以使用分析的延迟上界限定仿真的最大延迟。表3给出的实验延迟上界紧致度η(延迟上界紧致度定义为η=D _max/ )表明,IAMCS分析模型得到的延迟上界是紧致的。

表3

Table 3

表3(Table 3)

表3 延迟上界紧致度 Table 3 Tightness of delay bound 报文长度 η min/% η max/% η avg/% 15 85.5 92.1 87.9 20 85.2 91.8 87.4

表3 延迟上界紧致度 Table 3 Tightness of delay bound

通过对IAMCS路由器信用阻塞、交换阻塞和通道阻塞进行详细分析,推导了其提供给流量的等价服务曲线,分别建立了对应的分析模型,进而得出一种使用IAMCS路由器NoC的端到端延迟上界分析模型。实验结果表明:该延迟上界模型可以界定仿真的最大延迟,且上界是紧致的。对采用IAMCS或非对称多通道路由器的NoC,该模型可有效地计算每条流量的最坏延迟上界,对设计进行指导和优化。