基于虫孔直通交换片上网络的共享优先级机制

吴陶迪, 孙自强(华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237 )

基于虫孔直通交换片上网络的共享优先级机制

吴陶迪, 孙自强
(华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237 )

基于传统虫孔直通交换(Conventional Wormhole Cut-Through Switching,Con-WCTS)的片上网络系统(Network-on-Chip,NoC)无法直接实现基于优先级的仲裁逻辑,不适用于对信息传输实时性要求较高的多核片上系统。引入虚拟通道技术,提出了共享优先级虫孔直通交换(Shared Priority Wormhole Cut-Through Switching,SP-WCTS)的网络结构,并给出了该网络信息最坏传输时间的计算方法。通过实验对比了Con-WCT网络、共享优先级虫孔交换(Shared Priority Wormhole Switching,SP-WS)网络、SP-WCTS网络以及轮询虫孔交换 (Round Robin Wormhole Switching,RR-WS)网络的可调度性,并探究了虚拟通道数量和总网络利用率对网络可调度性的影响。实验结果表明:SP-WCTS的可调度性要明显优于另外3种网络;虚拟通道数量和总网络利用率对SP-WS网络可调度性的影响大于共享优先级SP-WCTS网络。

片上网络; 虫孔直通交换; 共享优先级; 可调度性分析

随着多核片上系统(Multiprocessor System-on-Chip,MPSoC)上计算单元(Processing Element,PE)数量的增多,PE之间频繁、大量的数据交换已经成为MPSoC技术发展中需要解决的一个重要问题[1-2]。目前,用于多核间通信的方法主要有基于总线的网络和片上网络(Network-on-Chip,NoC)[3]。其中,NoC克服了总线在大量并行通信环境中存在的长延时、高功耗等问题[4],成为目前MPSoC中主要的通信方式。

交换机制是NoC的关键技术之一,定义了数据从源节点传输到目标节点的方式[4]。目前常用的交换机制有:包交换、虫孔交换、电路交换、虚拟直通交换,其中,虫孔交换机制有着优良的延时性能和较小的缓存要求,已经成为当前片上网络的主流交换机制[5-6]。

在虫孔交换机制中,每个报文被划分成许多固定大小的微片(Flit)。报文的路由信息存储在头微片中,其余微片跟随头微片的路径传输。当头微片被阻塞时,该报文的所有微片就地存储,直至阻塞结束。虫孔交换有着通信延时短、缓存小和易实现等优点,但同时也存在排头阻塞的问题。引入虚拟通道(Virtual Channel,VC)[7]技术可以有效地解决排头阻塞,但也增加了缓存的消耗。目前,已经有很多的NoC设计被提出[8-9]。Schoeberl等[10]改进了时分多路复用NoC,使其适用于通用硬件平台。Lee等[11]设计了一种自适应指令解码NoC结构,允许多报文的融合传输,提高了网络的利用率和吞吐量。文献[12]提出了一种虫孔直通交换机制,在不引入虚拟通道的情况下解决了传统虫孔交换的排头阻塞问题,减少了片上网络所需的缓存。

为了解决来自不同输入口的报文竞争同一个输出端口的问题,NoC路由的每个输出端口都会设有一个仲裁器,实现端口的共享[13]。目前常用的仲裁设计有轮询机制和基于优先级机制。在实时性要求较高的应用中,常采用基于优先级的仲裁机制。然而在虫孔直通交换机制下使用基于优先级的仲裁机制时,可能造成优先级反转,高优先级的信息的阻塞时间变得不可预测。针对这一弊端,本文提出了一种基于虚拟通道技术改进的共享优先级虫孔直通交换(Shared Priority Wormhole Cut-Through Switching,SP-WCTS)机制,消除了共享优先级仲裁机制中存在的优先级反转问题，并给出了信息最坏传输时间(Worst-Case Traversing Time,WCTT)的计算方法。另外,本文对比了不同网络参数对传统虫孔交换网络和SP-WCTS实时性分析的影响,对设计者在不同的应用场景中选择合适的片上网络交换机制有一定的参考意义。

1 基于优先级共享的虫孔直通交换

1.1 虫孔直通交换

虫孔直通交换融合了虫孔交换和直通交换技术。如图1所示,路由为各微片设置一个本地ID,来自同一个报文的微片,其本地ID相同。传输过程中,各输出端口对发出传输请求的输入端口轮流接通,从而使得来自不同输入端口的微片交错地从同一个输出端口输出。为保证来自不同报文的微片正确地选择其路径,虫孔直通交换路由设置有一个路径保留表,存储了每个本地ID及其对应的输出端口。每个报文的本地ID在头微片传入路由时分配,尾微片传出时回收。

图1 虫孔直通交换

传统虫孔直通交换中,来自不同输入端口的报文在同一输出端口公平地输出,不适用于实时性要求较高的场合。为了保证实时报文在截止期限之前到达目的节点,需要采用基于优先级的仲裁机制,而在虫孔直通交换机制下直接使用优先级仲裁可能会导致优先级反转。假设图1中的业务优先级顺序为A>C>B,若A恰好在B的某个微片后传入,则C会抢占B,从而阻塞A,造成优先级反转,高优先级业务A被阻塞的时间难以预测。

1.2 共享优先级虫孔直通交换

为了解决优先级反转问题,本文引入虚拟通道技术,提出了一种共享优先级虫孔直通交换(Shared Priority Wormhole Cut-Through Switching,SP-WCTS)网络。虚拟通道技术是将每个网络通道的缓存划分为若干独立的小片,从而将网络中单个的物理连接划分成若干个逻辑上独立的虚拟通道,每个虚拟通道拥有独立的缓存队列。虚拟通道技术主要用来避免死锁(Deadlock),提高带宽使用率[4]。

SP-WCTS网络的传输机制如图2所示。每个输入端口的缓存被划分为几个独立的小片,每一个小片都可以作为一个虚拟通道。SP-WCTS网络为每一个优先级分配一个虚拟通道,各虚拟通道有独立的先进先出队列,优先级为i的业务只能使用优先级为i的虚拟通道。不同优先级业务间的抢占发生在微片级,即高优先级业务可以在低优先级业务传输完一个微片后抢占输出端口。当一个网络连接上的高优先级业务被阻塞时,低优先级的业务可以使用该连接进行传输。

图2 共享优先级虫孔直通交换网络仲裁机制

虚拟通道的引入会增加路由缓存的消耗,为了兼顾实时性能和资源消耗,SP-WCTS允许多个传输任务共享同一个优先级,以减少虚拟通道的数目。同优先级的报文在微片级相互交错传输,避免了同优先级传输任务之间的长时间阻塞。网络中,优先级标号越大表示优先级别越低,优先级1为最高优先级。τ1与τ2共享优先级1,该输入端缓存中微片被读取的顺序如图2中Output所示。每个输出端在发出请求的输入端选择最高优先级的虚拟通道进行传输。

2 网络最坏延时分析

2.1 实时通信模型

设一个虫孔直通交换网络Γ中存在n个业务:

(1)

其中τi代表业务i,并假设所有的业务都是周期性地发送报文。每个业务可以用如下5个属性来表示:

(2)

2.2 业务之间关系分析

图3 片上网络业务示例

当不同的业务共享同一个物理连接时,信息传输的过程中可能发生资源竞争的现象。在SP-WCTS网络的同一连接上,来自同优先级业务的报文在微片级别相互交错传输,共享带宽;来自高优先级业务的报文可以在微片级别抢占低优先级的业务进行传输,在当前报文传输结束时,低优先级的业务继续传输。高优先级业务抢占低优先级进行传输的现象称为干扰(Interference)。

(3)

若高优先级业务j不与业务i共享物理连接,但存在一个中介业务k,分别与业务j和业务i共享物理连接,且k的优先级满足Pj≥Pk>Pi,则业务j可能通过业务k依然对业务i造成间接干扰。业务i的间接干扰集合为

(4)

(5)

2.3 信息最坏传输时间计算

实时性能分析在片上网络系统的设计中有着至关重要的作用[16],WCTT是衡量系统实时性能的一个重要参数。在实时系统中,各实时业务的报文必须在其截止期限前完整传输至目的节点。当某一报文不能满足实时性要求时,可能会造成系统的降级运行,甚至灾难性后果。

信息的WCTT是指在最坏情况下,该业务的报文从释放到完整地被目的节点接收所需要的传输时间。根据2.2节的分析可知,在共享优先级虫孔直通交换网络中,业务会受到来自高优先级业务的干扰,同时与同优先级的业务共享带宽。所以,对任意一个业务i的报文,其传输的最坏情况是:所有高优先级数据流与之同时竞争共享资源,并且所有同优先级的业务在其完成传输任务前不间断地进行数据传输,占用带宽。

(6)

来自业务i的报文在传输过程中会受到来自高优先级报文的干扰,由2.2节可知,在最坏情况下,高优先级报文的干扰如图4所示,业务τi受到来自高优先级业务τj的直接干扰。当业务τi的同优先级业务被其他高优先级业务的传输任务抢占时,业务τi同时会被该同优先级业务阻塞。这一阻塞现象可近似看成业务τi受到来自该高优先级数据流的直接干扰。

图4 高优先级业务的干扰

由上述分析可得出业务τi的最坏传输时间为

(7)

(8)

(9)

3 仿真实验与分析

3.1 实验设计

针对共享优先级虫孔交换 (Shared Priority Wormhole Switching,SP-WS) 网络[15]、轮询虫孔交换 (Round Robin Wormhole Switching,RR-WS)网络[19]、传统虫孔直通交换 (Conventional Wormhole Cut-Through Switching,Con-WCTS) 网络[12]以及本文SP-WCTS网络设计了仿真实验,比较了业务数目、虚拟通道个数以及总网络利用率对片上网络可调度性的影响。当系统中存在业务不能满足其截止期限时,该系统不可调度。可调度性采用每组实验中可调度的系统数占总系统数的比例表示:

(10)

其中:Ras为可调度性;Ns为可调度系统数目;Nt为实验中总的系统数目。

实验中采用的片上网络结构为常用的4×4 的2D mesh 结构。为了不失一般性,实验中业务的各参数均随机生成,具体生成方法如下:

(1) 报文长度。实验前给定报文长度的范围,各数据流的数据长度在该范围内,采用均匀分布的方式随机生成。本文实验使用的报文长度范围为[5,100],网络中微片的长度为1。

(2) 网络利用率。设置网络利用率的范围,各业务在该范围内采用均匀分布的方式随机生成网络利用率,业务的网络利用率计算公式为Ui=Ci/Ti。

(3) 路径。随机生成各业务的源节点和目的节点,并采用XY路由算法生成路径,XY路由算法是目前常用的路由算法之一,可避免死锁和活锁问题[4]。

各业务发送单个报文所需要的基本传输时间可根据式(7)计算,需要注意的是,基本传输时间是在不考虑网络中其他业务的干扰,该业务享有全部带宽的情况下,单个报文从源节点传输至目的节点所需要的时间。实验中,各业务的截止期限等于其周期,即Di=Ti。

3.2 业务数量的影响

将网络中业务数量从10增加到50,各业务网络利用率的范围设为[0.001,0.01],图5展示了不同数量业务对网络可调度性的影响。实验比较了RR-WS、Con-WCTS、SP-WS以及SP-WCTS 4种网络,其中SP-WS和SP-WCTS同时考虑了在3VC和6VC下的可调度性。由图5可知:

(1) 随着业务数量的增加,各网络的可调度性下降。其原因是随着业务数量的增加,网络的负载增大,导致网络延时增加,可调度性下降。

(2) 在相同的业务数量下,不同网络的可调度性存在差异。 其中,6VC的SP-WCTS网络可调度性最优,RR-WS最差。这是由于在RR-WS网络中存在严重的排头阻塞,当某个报文在一个连接上被阻塞,则其上游的所有与之相关的报文都会被相应阻塞,从而导致了严重的网络延时。

(3) 在相同数目的VC下,SP-WCTS的可调度性明显优于SP-WS。其原因是,在SP-WCTS网络中,同优先级业务之间交错传输,其阻塞时间要远远小于SP-WS网络。此外,Con-WCTS网络的可调度性介于6VC和3VC的SP-WCTS之间,其主要原因是当虚拟通道较少时,同优先级业务之间的阻塞比较大,而在Con-WCTS网络中所有业务共享带宽,没有排头阻塞,从而导致了VC数目较少时,SP-WCTS网络的可调度性劣于Con-WCTS网络。但是,由于SP-WCTS 采用了基于优先级的仲裁逻辑,可以更好地满足高优先级业务的实时性要求,比Con-WCTS网络更加适用于实时性应用。

图5 不同业务数量下的可调度性

3.3 虚拟通道数目的影响

本实验研究了VC数目对SP-WCTS网络和SP-WS网络可调度性的影响。实验网络的业务数量为30,各业务的参数设置同3.2节,VC数目从2增加到8,对不同虚拟通道数目下的网络各进行200组实验。

图6示出了两种网络在不同数目VC下的可调度性。可以看出,随着VC数目的增加,SP-WS网络中的可调度性增强,SP-WCTS网络的可调度性先降低后增强,并在3VC时最低。造成这一现象的原因是,在SP-WCTS网络中,随着VC数目的增加,同优先级业务之间的阻塞减少,而来自高优先级业务的干扰增多。然而SP-WCTS网络中的阻塞本质来源于高优先级业务的干扰,阻塞和干扰相互影响,导致了SP-WCTS网络的可调度性随着VC数目的增加,先降低后增加。

3.4 平均网络利用率的影响

为了研究SP-WCTS网络和SP-WS网络的负载能力,本文在不同网络利用率下对两种网络进行了可调度性实验。各组实验的业务的网路利用率范围分别为[0.001 0,0.009 0],[0.001 4,0.012 6],[0.001 8,0.016 2],[0.002 2,0.019 8],[0.002 6,0.023 4],[0.003,0.027]。业务集合中的业务数量为30,其余参数设置同3.2节,实验结果如图7所示。图中横坐标为总网络利用率,为所有业务的网络利用率之和,采用如下计算公式:

(11)

其中:Umax和Umin分别为业务网络利用率的上下限;Nflow为网络中业务的数目。

图6 不同虚拟通道数下的可调度性

图7 不同总网络利用率下的可调度性

由图7可知,随着总网络利用率的增加,各网络的可调度性降低,且SP-WS网络的下降速度明显快于SP-WCTS网络,表明SP-WCTS网络相对于SP-WS网络可承受更大的业务负载。在相同的网络利用率下,SP-WCTS网络的可调度性基本上优于SP-WS网络。在网络利用率为0.4时,6VC的SP-WS网络的可调度性高于3VC 的SP-WCTS网络,但随着网路利用率的增加,前者的可调度性下降剧烈,在网络利用率为0.5时,其可调度性已经低于3VC的SP-WCTS网路。

4 结论与展望

虫孔直通交换网络实现了业务之间的交错传递,解决了传统虫孔交换网络的排头阻塞问题,但其无法满足较高的实时性要求。本文引入了虚拟通道技术,在虫孔直通交换网络中使用了基于优先级的仲裁机制,提出了共享优先级虫孔直通交换网络结构,并给出了信息最坏网络延时的计算方法,方便设计人员对网络的实时性能进行分析。

为了研究共享优先级虫孔直通交换网络的实时性能,通过一系列实验对比了Con-WCTS网络、RR-WS网络以及SP-WS网络。由实验结果可知,共享优先级虫孔直通网络交换网络有着良好的实时性能,可以承担更大的网络负载。在未来工作中,还可以对SP-WCTS网络的资源和能源消耗进行更加深入的研究。

[1]周君,王天成,李华伟,等.多核处理器片上网络的验证技术综述[J].计算机科学,2013,40(专刊):33-39.

[2]黄国睿,张平,魏广博,等.多核处理器的关键技术及其发展趋势[J].计算机工程与设计,2009,30(10) :2414-2418.

[3]李丽,许居衍.片上网络技术发展现状及趋势浅析[J].电子产品世界,2009,16(1):32-37.

[4]COTA É,DE MORAIS AMORY A,LUBASZEWSKI M S.Reliability,Availability and Serviceability of Networks-on-Chip[M].USA: Springer Science & Business Media,2011.

[5]王峥,顾华玺,杨烨,等.片上网络交换机制的研究[J].中国集成电路,2007,16(12):22-27.

[6]NI L M,MCKINLEY P K.A survey of wormhole routing techniques in direct networks[J].Computer,1993,26(2):62-76.

[7]KAVALDJIEV N,SMIT G J M,JANSEN P G,etal. A virtual channel network-on-chip for GT and BE traffic[C]//IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures (ISVLSI′06).USA:IEEE,2006:211-217.

[8]DINECHIN B D,DURAND Y,VAN AMSTEL D,etal.Guaranteed services of the NoC of a manycore processor[C]//Proceedings of the 2014 International Workshop on Network on Chip Architectures.USA: ACM,2014:11-16.

[9]POLURI P,LOURI A.Shield:A reliable network-on-chip router architecture for chip multiprocessors[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(10):3058-3070.

[10]SCHOEBERL M,BRANDNER F,SPARSØ J,etal.A statically scheduled time-division-multiplexed network-on-chip for real-time systems[C]//2012 Sixth IEEE/ACM International Symposium on Networks on Chip (NoCS).USA:IEEE,2012:152-160.

[11]LEE T Y,HUANG C H,LIU M J,etal.Adaptive instruction codec architecture design for network-on-chip[J].Computers & Electrical Engineering,2016,51(4):207-224.

[12]SAMMAN F A,HOLLSTEIN T,GLESNER M.Wormhole cut-through switching:Flit-level messages interleaving for virtual-channelless network-on-chip[J].Microprocessors and Microsystems,2011,35(3):343-358.

[13]官铮,钱文华,杜长青,等.具有服务质量保障的片上网络路由仲裁控制[J].计算机科学,2015,42(2):55-59.

[14]LU Z,JANTSCH A,SANDER I.Feasibility analysis of messages for on-chip networks using wormhole routing [C]//Proceedings of the ASP-DAC 2005,Asia and South Pacific Design Automation Conference.USA:IEEE,2005:960-964.

[15]SHI Z,BURNS A,INDRUSIAK L S.Schedulability analysis for real time on-chip communication with wormhole switching[J].International Journal of Embedded and Real-Time Communication Systems,2010,1(2):1-22.

[16]ABDALLAH L,JAN M,ERMONT J,etal.Wormhole networks properties and their use for optimizing worst case delay analysis of many-cores[C]//10th IEEE International Symposium on Industrial Embedded Systems (SIES).USA:IEEE,2015:1-10.

[17]SHI Z,BURNS A.Real-time communication analysis for on-chip networks with wormhole switching [C]//Proceedings of the Second ACM/IEEE International Symposium on Networks-on-Chip.USA: IEEE Computer Society,2008:161-170.

[18]AUDSLEY N,BURNS A,RICHARDSON M,etal.Applying new scheduling theory to static priority pre-emptive scheduling[J].Software Engineering Journal,1993,8(5):284-292.

[19]LIU M,BECKER M,BEHNAM M,etal.Using segmentation to improve schedulability of real-time packets on NoCs with mixed traffic[R].Sweden:Mälardalen University,2016.

A Shared Priority Policy in Wormhole Cut-Through Switching Based Network-on-Chip

WU Tao-di, SUN Zi-qiang

(Key Laboratory of Advanced Control and Optimization for Chemical Process,Ministry of Education, East China University of Science and Technology,Shanghai 200237,China)

Network-on-Chip (NoC) based conventional wormhole cut-through switching (Con-WCTS) cannot employ the priority based arbitration logic directly,so it is not suitable for the multiprocessor system-on-chip with high real-time requirements.By utilizing the virtual channel technique,this paper constructs a shared priority wormhole cut-through switching (SP-WCTS) network and proposes a method to calculate the worst-case traversing time for the traffic-flow of the SP-WCTS NoC.Furthermore,some experiments are made for comparing the schedulability of Con-WCT,shared priority wormhole switching (SP-WS),SP-WCTS and round robin wormhole switching (RR-WS) NoCs and analyzing the effect of the number of VCs and the total network utilization on the schedulability of these different NoCs.It is shown that the SP-WCTS NoCs can achieves the best schedulability and the number of VCs has a greater effect on the schedulability of the SP-WS than SP-WCTS NoCs.

network-on-chip; wormhole cut-through switching; shared priority; schedulability analysis

1006-3080(2017)02-0254-06

10.14135/j.cnki.1006-3080.2017.02.016

2016-09-06

上海市重点学科建设基金(B504)

吴陶迪(1992-),男,硕士生,研究方向为实时嵌入式系统。E-mail:taodi_wu@foxmail.com

孙自强,E-mail:sunziqiang@ecust.edu.cn

TP302

A