论文部分内容阅读
摘 要：随着研究的深入和片上网络业务的发展，片上通信变得日益复杂，传统的服务方式已经不能够满足数据传输的需求，为片上网络通信提供有保障的服务质量成为一个关键的问题。本文在系统分析相关研究文献的基础上，对目前片上网络服务质量的关键问题和典型研究成果进行综述，并分析比较了目前提高片上网络的服务质量的不同方法。
关键词：片上网络；三维片上网络；服务质量；路由算法
Network-on-chip quality of service research overview
TANG Huai-yin
（1.School of computer science and software， Tianjin Polytechnic University， Tianjin 300387；）
Abstract： With in-depth research and development of NoC（network-on-chip），communication on chip became more and more complex ， traditional services have not been able to guarantee requirements of data transmission， As a result， network data transmission can not be guaranteed，providing a guaranteed quality of service has become a key problem for network on chip communication.Based on the systemic analysis of relevant research studies，this article reviewed the key problem of NoC service and classic research result ，at the same time ，analyzed the different ways of improving NoC quality of service.
Key words： Network-on-chip（NoC）；3D-NoC；Quality of Service（QoS）；routing algorithm
0引言
20世纪90年代出现了片上网絡（Network-on-chip，NoC）的概念，即将宏观网络技术引入到片上系统，以解决芯片中的通信问题[1]。Dally在2001年首次将采用分组路由模式的片内通信称为NoC[2]。 随着市场需求和芯片集成工艺地不断提高，三维片上网络（3D-NoC）应运而生。2005 年，Liu C. C.， Jeng-Huei Chen， Manohar R.等首次提出了3D-NoC的概念[3]。
工艺的进步使片上网络突破了总线结构的各种瓶颈，也导致片上网络系统全局通信需求日益复杂和不可预测，服务质量是保障片上网络通信的关键技术。因此，引起了学术界的广泛关注。
1片上网络服务质量
1.1 服务质量
片上网络服务质量概念最初源于宏观计算机网络上的QoS，为片上系统中通信网络提供各种灵活、准确的服务质量保障。好的服务质量是指NoC具有低时延、高吞吐量、低功耗等特性。服务质量的关键指标主要包括可用性、吞吐量、时延、时延变化和丢包等。 同一业务流中分组的时延往往会出现不同，这种现象被称为抖动和漂移现象。抖动是高频率的时延变化，而漂移是低频率的时延变化。利用缓存可以克服过量的抖动，但这将增加时延，造成其他问题。
随着片上网络中各种通信服务需求日益复杂，QoS已经没有了统一的规范，QoS的指标被更广泛的概括为性能约束、资源约束和优先级约束[4]。性能约束是对通信网络中数据包传输质量进行度量的一些性能限制，例如时延、吞吐量、准确率等。资源约束是根据一系列独特的特征对特定类型的网络资源的使用进行限制，例如编码等。优先级约束是影响网络资源分配的限制条件，以便于从当前通信节点中将数据包传输到下一个通信节点。
1.2 QoS服务模型
服务模型是指一组端到端的QoS功能，目前NOC中主要的QoS服务模型有：保障服务、尽力服务、综合服务、区分服务和多协议标记交换。保障服务模型[5]（Guaranteed Through put service，GT）是一种基于面向连接的服务。会带来额外的时延，但是在很大程度上提高数据的吞吐率。
尽力服务模型[6]（Best Effert service，BE）是一种单一也是最简单的服务模型。BE服务对于较短的消息可以提高传输效率、降低时延。
综合服务[7]可以满足多种QoS需求，它主要的协议是资源预留协议（RSVP），它负责在报文发送前向网络申请特定的服务。综合服务可以提供保证服务和负载控制两种服务。综合服务中这种基于流的算法容易受到“路由器崩溃”的攻击。
区分服务[8]通过将不同数据流划分为不同服务类型来获得QoS，而不需要维护每一个数据流，它不需要使用RSVP，基于虫孔交换机制的区分服务模型目前比较广泛。
区分服务有两种服务类别：快速型转发和确保型转发。快速型转发：是一种最简单的服务类型，服务类别包括常规类型和快速类型。大多数通信流量应该属于常规流量，有一小部分分组属于快速类别。快速类别的分组应该可以直接通过网络。符号化表示如图1所示：
确保型转发：它是一种更加精细的管理服务类别的方案，其规定了4种优先级别，每种级别都有它自己的资源。并且对于正在经历拥塞条件的分组，定义了三种丢弃概率：低、中、高。 多协议标记交换[9]是一种基于数据包标记的交换技术，其工作思想是，在每个分组前端加上一个标签，然后根据这个标签而不是目的地址进行路由。将标签做成内部表中的一个索引 ，这样就可以把寻找路径变成非常简单的表格查询，很快的完成路由过程。
1.3 片上网络路由算法
片上网络路由算法研究主要是通过评估优化、裁减用于并行计算机集群的路由算法。在考虑路由算法的自适应性、连通性、容错能力、死锁发生率等基本性能的同时，更加关注路由算法在、时间开销以及硬件实现复杂度方面的情况。根据不同的标准可将路由算法分为如下几类[10]，如图2所示。
1.4设计路由算法时要满足的要求
面积和功耗限制着芯片上复杂的片上网络系统，设计NoC路由算法时要注意以下几点要求：
（1）更简单化的路由信息计算，这样才能避免的硬件设施的体积过大、速度无法满足需要；
（2）路由算法能避免饥饿，对NoC中的所有节点一视同仁；
（3）考虑到网络资源有限，倾向于选择最短路径，或者绕道次数低的路由算法；
（4）路由算法确保分组能够准确地到达目的地，即算法活锁和无死锁。
1.5 常见路由算法
路由算法是常见的片上网络中提供服务质量的重要手段，好的路由算法可以极大地改善片上网络的性能，并提供较好的服务质量。因此对常见的路由算法做一个简要的介绍。目前常见的适用于NoC的路由算法有自适应路由、无关路由、无关路由和自适应路由相结合的路由算法。
1.5.1无关路由算法
无关路由决策与网络状态无关，但它的选择却未必是最佳的。常见的无关路由算法有：确定性路由、维序路由、随机路由算法等。
（1）维序路由算法
维序路由包括超立方体中的E-cube路由和2D Mesh中的XY路由。该类算法路由逻辑简单，在维序间没有死锁，容易实现，但网络中心节点的业务流量最大，整个网络的业务流量不均衡，容易造成网络的拥塞。
（2）确定性路由算法
确定性路由算法的高可靠性和低延迟表现在网络没有拥塞时。包按正确顺序到达目的节点，因此实时系统一般采用确定性路由。一般情况下，每个路由器都有一个包括所有路由消息的全局路由表，网络改变时，路由表随之更新路由消息。确定性路由算法硬件设计和实现简单，具有较小的时延，是无活锁和无死锁路由。
（3）随机路由算法
随机路由算法算法简单，且能容错，假定每个分组迟早都能到达其目的节点，基于概率将分组按不同的路径发送到目的节点，但其速度慢，并且占用大量的网络资源。常见的随机路由算法有洪泛路由算法、IVAL随机路由算法和IVAL随机路由算法。洪泛路由算法包括概率洪泛路由算法[11]和直接洪泛算法。该算法的缺点是占用大量的网络资源。相比概率洪泛算法，直接洪泛算法有了改进。直接洪泛算法比概率洪泛算法有更高的容错能力和更少的网络资源占有率。Valiant算法分组分两步路由：将原始的一个路由问题转换成两个路由问题，较好的平衡了网络负载，降低了拥塞概率。IVAL随机路由算法是对Valiant随机路由算法的改进。IVAL算法两步路由都采用维序XY路由算法，只是两次维序顺序相反。
1.5.2自适应路由算法
常见的自适应路由算法包括伪自适应XY路由、转弯模型（Turn Model）、奇偶转弯模型、XY-YX路由、基于Torus网络的负向优先路由（NF-T）、跳步容错路由、DyXY路由、NoC-LS路由、SRN路由算法等。
（1）伪自适应XY路由算法
该算法根据网络状态在确定性路由和自適应路由之间转换，是对确定性XY路由的一种改进[12]。当网络没有或拥塞很小时，用确定性路由算法；当网络拥塞状况比较严重时，数据选择拥塞程度较小的链路进行数据传输。伪自适应XY路由在一定程度上能减少热点的产生，对网络流量的分布也相对合理。
（2）转弯模型路由算法
转弯模型[13]是Mesh网络中一种经典的无死锁路由算法。其基本思想是分析信息分组在网络中可能的转向（Turn）以及这些转向可能形成的环，通过禁止一定数量的转向来破坏信道的环形依赖关系，从而破坏死锁的形成条件。根据禁止转向的不同，形成了3种基本的算法，即西向优先WF（West First）、北向最后NL（North Last）和负向优先NF（Negative First）算法。
（3）奇偶转弯模型算法
奇偶转弯模型[14]主要适用于Mesh结构的NoC，它不需要使用虚通道便能避免死锁。不像转弯模型那样通过限制某些方向的转弯来防止死锁的产生，而是对发生转弯的位置进行了约束。
（4）XY-YX路由算法
XY-YX路由算法[15]是对XY路由算法的改进，基本思想是数据并不总是先X方向，后Y方向，而是根据目的节点和当前节点的位置来选择。当目的节点Y方向的值小于当前节点Y方向的值时，即目的节点在当前节点的北边，选择先Y后X；当目的节点Y方向的值大于当前节点对应的值时，即目的节点在当前节点的南边，选择先X后Y，从而减轻XY路由算法在X方向产生的阻塞。本算法路由过程只允许NE，ES，WS，NW 4个转向。
（5）基于Torus网络的负向优先路由算法
基于Torus网络的负向优先路由算法[16]是在转弯路由算法的基础上，引入虚信道（Virtual channel），将物理网络划分成2个虚拟网络，每条物理链路（Physical link）使用3条虚信道，文[17]中证明这是2D Torus网络实现无死锁自适应路由算法所需虚信道数目的最小值。通过相应的路由规则，破坏2D-Torus网络中信道之间的环形依赖关系，从而实现了无死锁无活锁的自适应路由算法。该算法基于引入虚信道完成了自适应路由，但大部分的流量集中在0号虚信道上，2号虚信道则相对较少使用，使得0号虚信道成为整个网络通信的瓶颈，而2号虚信道负载不足，3条虚信道的使用存在着严重的负载不均衡，浪费严重。新的虚信道使用策略的核心思想是达到各个虚信道的负载均衡。减少1号虚拟网络中0号虚信道中的部分流量，将部分流量尽早地分配到2号虚拟网络中，增加2号虚信道的使用几率。 （6）跳步容错路由算法
跳步容错路由算法[18]是对转弯模型的改进，适用于Mesh网络结构中，具有实现简单、能兼顾网络吞吐和时延的特点。路由函数因为限制了转弯的方向并且在限制转弯的方向上设置了逃离虚通道，不会形成死锁环路，从而避免了死锁。
（7）DyXY路由算法
DyXY路由算法[19]中，节点通过监视其相邻节点的拥塞状况来选择分组路由的下一跳。该算法在获得端口分组的目的节点地址后，如果当前节点与目的节点地址具有相同的X维（或Y维）坐标，则将分组沿Y维（或X维）路由至目的节点；如果当前节点就是目的节点，分组会发送给本地节点端口，否则，本地节点检测其相邻节点到目的节点的拥塞状况，选择拥塞最小的路径将分组发送出去。这样能避免死锁和活锁的发生，限制了分组通过最短路径传输。
（8）NoC-LS路由算法
在NoC-LS路由算法[20]中节点将路由消息发送给网络中每一个节点，网络中的每个节点都有一张整个网络的状态图，根据网络状态进行路由计算。该算法非常复杂，路由表会随着网络中节点数的增大而增大，但能够将分组高效地发送到任一目的节点。
（9）SRN路由算法
SRN路由算法[21]不需要产生大量的冗余分组，它允许网络可以自行组织，自行配置，并且能够容错，而不需要周期性的路由管理，并且仿真结果表明，该算法具有比洪泛算法更好的容错性能。
（10）蚁群动态路由算法ANDR
蚁群动态路由算法能够使流量均衡，减少网络中热点的产生，它使用路由表，路由表中记录每个节点到网络中其它节点时，选择东、西、南、北方向4条链路的概率，因此分組路由能选择具有最小流量的最短路径，适用于Mesh结构。
1.5.3无关路由和自适应路由相结合的路由算法
无关路由算法和自适应路由算法优点相结合的算法有DyAD路由算法和SD路由算法。
（1）DyAD路由算法
DyAD路由算法[22]是一种将维序路由与奇偶转向路由相结合的路由算法。在网络处于低负载情况下采用维序路由，而当网络处于高负载情况下采用奇偶转向的适应性路由。
（2）SD路由算法
SD路由算法[23]是确定性路由算法和适应性路由算法相结合的产物，由于中心区域的节点采用的是适应性路由算法，所以可以很好的解决Mesh，Torus网络中中心节点易出现热点和网络拥塞的情况。该路由算法实现简单，可以大幅度降低路由器实现的复杂度，节约了网络实现的硬件资源。
2通过路由算法来解决服务质量问题
2.1国际研究
国外对确定性路由算法、自适应路由算法、容错路由算法和适用于不规则拓扑结构的路由算法研究比较多。文献[24]介绍的XY维序路由算法简单易实现，适用于二维网格拓扑结构、二维折叠环拓扑结构等规则的拓扑结构，在无拥塞和故障的网络环境下能获得较低的延时，是研究中常用的确定性路由算法。在自适应路由算法方面的研究成果比较多。Glass C.J.等人提出的转弯模型[25]是一种自适应路由算法，适用于规则拓扑结构。该模型限制数据传输在一些节点的转弯方向形成死锁。因为没有采用虚拟通道，减少了面积开销。Ge Ming Chiu在转弯模型的基础上提出了奇偶转弯模型[26]。Ming Li等人提出了自适应路由算法[27]DyXY（Dynamic XY routing）。该算法根据相邻通信节点的拥塞状况分配路径，确保了最短路径。在路由器结构中设计了检测相邻通信节点的拥塞状况的功能以支持该算法。Hu J 等人提出了能够预测竞争的自适应路由算法 DyAD[28]（Dynamic Adaptive Deterministic switching），通过监控相邻通信节点间的通信事务，为当前通信节点的路由做出选择。Pejman Lotfi-Kamran等人提出了路由算法 BARP[29]，该算法充分利用源节点和目的节点之间具有多条最短路径的特点，将通信任务均匀分布在所有的最短路径中以平衡网络负载。Daneshtalab M.等人将蚁群算法用于解决片上网络的路径分配问题[30]。Dehyadgari M.等人提出了将 XY 维序路由算法和自适应路由算法相结合的路由算法PAXY[31]（Pseudo Adaptive XY Routing），通过监测相邻节点的状态选择合适的路由算法进行路由。Mohamed M. Sabry等人提出了一种动态自适应路由算法[32]，在路由过程中可以避免死锁和活锁。为了满足算法的需求，研究者在C语言环境设计实现了路由器和路由算法，重新定义了数据包格式和路由器结构，并将其应用到二维折叠换拓扑结构和二维网格拓扑结构的片上网络系统中。 Duato 提出了在虫孔流控机制中设计自适应无死锁路由算法的理论[33]。有一些论文研究适用于不规则拓扑结构的路由算法[34]。不规则拓扑结构的片上网络系统中一些大于tile面积的特殊区域，通常用于共享存储。由于特殊区域的存在占据了一些路由器的位置，使得某些位置没有路由器。由于这些路由器的缺失，增加了路由路径的长度，用于规则拓扑结构的死锁避免规则不再适用。容错路由算法的情况与这种情况类似。这两种情况的路由算法考虑的因素相似，基本可以相互通用。在容错路由算法方面，Mediratta S.D.等人提出了一种容错路由算法[35]，在网络中传输路径探测数据包收集链路的状态信息，根据状态信息进行路径分配避免经过发生故障的链路。文献[36， 37， 38]均是在转弯模型的基础上提出了可容错的确定性路由算法，文献[36]介绍了XY维序路由算法与奇偶转弯模型相结合的E-XY容错路由算法，文献[37]和文献[38]介绍的容错路由算法在奇偶转弯模型的基础上增加一些限制条件以实现容错功能。
2.2国内研究
在确定性路由算法方面，黎黎提出了适用于二维折叠环拓扑结构的确定性路由算法[39]，对通信节点采用特定的方式编码，根据编码分配路径。朱小虎等人提出了具有多级拥塞控制功能的路由算法，将网络的拥塞状态分为三种：未拥塞、轻度拥塞、重度拥塞。在网络未发生拥塞时选择固定的传输路径，使用XY维序路由算法；当网络发生轻度拥塞时，对数据进行分流，采用自适应的XY路由算法；当片上网络处于中度和重度拥塞时，根据等待时间权衡分流数据包与不分流数据包对整个网络造成的影响，选择等待时间较短的传输路径[40]。容错路由算法方面，文献[41，42]中带有端到端反馈的随机路由算法，有效地处理传输过程中的随机错误，具有较高的转发速度，保证了传输的可靠性。在自适应路由算法方面，岳培培等人提出了列举路径分配算法[43]，在算法中设置最大带宽作为限制条件，寻找符合带宽约束的路径组合，符合带宽限制条件的通信路径为合法的通信路径，然后根据合法路径的数目将通信流进行分类，根据各种分类的优先级进行路径分配。吕勇等人参照蚁群算法中收集信息和更新信息素表的方法，设计了一个能够收集和更新网络链路信息的路由算法[44]。 蜂群算法是近几年提出的一种模拟蜜蜂“舞蹈”的优化算法，在求解NP完全问题方面有很大的优势。刘宝起采用最短路由，提出一种基于蜂群算法的QoS路由算法，使路由的自由度得到了最大程度开放，用基于软件的死锁恢复机制来检测和恢复死锁；采用了综合考虑历史信息和当前网络状态的路由策略，使用代理来更新路由信息，仿真结果显示，蜂群算法能够提高吞吐，降低时延和抖动，有效地保障了NoC 中的服务质量。 南京航空航天大学的王婷基于网络延时、带宽、吞吐量等QoS的性能指标，提出了一种动态路径算法，设计了一组面向特定应用的性能约束条件。在C语言环境下对算法进行功能验证和仿真，在不同通信任务模型下，分析网络负载的分布情况，对算法的性能进行评估。然后，在RTL级采用Verilog语言设计实现了路径分配算法，使功能得到验证，在此基础上，对算法在不同网络状态和不同网络负载下的网络延时、带宽、吞吐量等指标进行仿真，将结果与XY维序路由和DyXY路由算法进行对比分析。最后在Synopsys的EDA平台上分析对算法面积和功耗开销。 分析RTL级仿真之后获得的平均传输延时、网络吞吐量、链路利用率等QoS性能指标，结果表明动态路径分配算法能有效地平衡了网络负载，降低了数据包阻塞率，在不同的网络状态下能普遍改善了网络中有链路拥塞，提高故障状态下的性能。
西安电子科大的宁欢提出了一种改进型路由算法，该算法有效的克服了DyAD方法在网络负载较高时所采用的奇偶转向策略的缺点---可能会使得传输跳数增加，从而导致数据传输时延加大、服务性能下降。在数据包受到阻塞时，改进型的路由算法每个包的尾部的等待数据域会进行阻塞计时。该算法在网络负载较低时采取XY维序路由算法，但是当传输遇到阻塞时，尝试在Y维方向探测，这种策略减少了不必要的传输过程，仍然会保证数据包以最短路徑进行传输，以降低延迟。如果Y维方向的链路传输失败，则路由器会初始化包的等待数据域，并给该数据域赋一个定好的容忍极值，这个数据包将会因为暂停发送而在该路由节点进入等待期，到该路由节点的下一个判断周期时，先进行X维路由判断；如果该方向不存在阻塞，发送数据包并将数据包的等待数据域清0；如果X维方向仍然存在阻塞状态，则判断Y维路由是否阻塞，若Y维方向不存在阻塞，则并发送数据包并将该数据包的等待数据域清0。当X维和Y维方向的路由均阻塞时，则判断等待数据域中的容忍值。如果该值为0，则路由器设置flag域并转为奇偶路由模式；否则将该数据包中等待数据域中的容忍值递减1个单位，重新进入等待期。仿真结果显示该算法在网络负载较高时能够有效减小时延、使得网络的性能网络的吞吐量得到很大提升。
根据生物智能路由算法以及Qos路由模型，宁欢利用遗传算法来使片上网络中Qos路由问题得到了很好的解决。选择一条最优或是次优路径，通过对所需要的时延、吞吐、抖动等参数进行考量，为各种所需的QoS参数提供一种综合保证。对SWD算法和遗传算法进行的路径分配方法的时延、吞吐、抖动性能等进行的仿真结果表明SWD算法和遗传算法能够使传输的时延、吞吐和抖动性能得到显著改善。然而该方案并未探索遗传算法与其它生物算法（如蚁群算法）的融合，仅仅通过遗传算法遗传算法本身来保障NoC中的服务质量，并未多方面尝试提高算法的收敛性和局部最优解等。文献结合唯序路由和奇偶转向路由提出了一种新的保证QoS路由算法———区域路由算法。该算法既能克服QoS的抖动，又能提高吞吐并降低时延性能。该算法按照当前节点的位置将网络划分为两个区域，左区域为西优先路由，右边域为东最后路由，算法将确定性路由和适应性路由的优点结合起来形成一种新的路由.通过仿真结果表明，区域路由算法时延、吞吐以及抖动情况都得到了很大的改善，从而有效地保障了片上网络的QoS。
3通过一种新架构来保障片上网络服务质量 堆叠片上网络（图3）在垂直方向上的大吞吐量但是使系统有更大的面积成本，更高的复杂度，纤毛片上网络（图4）可以减少面积和功耗，但是对于繁忙的业务量，垂直方向上会有瓶颈，针对这两种特点，巴西圣保罗大学Johanna Sepúlveda， Guy Gogniat， Ricardo Pires等人结合堆叠和纤毛两种片上网络的优点，形成一种新的混合的片上网络结构[51]（图5），既减少了面积和功耗，又能使垂直方向上通信有更大吞吐量。
4通过一种新机制来保障片上网络解决服务质量
片上网络是将不同的IP核集成在单个芯片上，芯片资源十分有限，在保证服务质量的同时提高资源的利用率便成为设计片上网络服务质量保证机制时必须考虑的一个问题。
电子科技大学的汪凡设计了3D-TTL-QoS保证机制的模型[52]，该模型通过对数据包的性能进行约束，引进宏观网络生存时间（time to live，TTL）概念，用数据包的跳数代表TTL，通过限制数据包的最大跳数来区别网络中的各种不同级别的数据包。他提出的TTL-QoS能够极大地保证高优先级的保证性能。同时当网络中业务的等级较少时，基于虚通道预留的QoS机制会造成大量缓存资源的浪费，但TTL-QoS却能够充分地利用缓存资源。主要思路是在源节点发送具有最大跳数限制的数据包，数据包中的TTL信息每经过一个路由节点或在路由节点竞争失败一次都将减一，当数据包中的TTL减为零时还没到目节点，则该数据包自动变为最低优先级的BE数据包，说明该TTL数据包没有实现服务质量保证；相反，当该数据包到达目的节点时TTL还没有等于零，则说明该数据包得到的服务质量保证。其不足之处在于 TTL-QoS 保证理论下，若 TTL-GT 数据包的 TTL 值小于网络中的平均跳数，源节点将修改 TTL 值直到满足要求为止，这样将使一些急需要服务质量保证的数据包得不到响应。所以在未来的研究中可以将硬GT服务和软GT服务结合起来。为低于网络TTL平均值的TTL-GT数据包提供虚电路连接，保证其服务质量，其他高于TTL均值的TTL-GT数据包仍将按照软GT服务机制传输。结合 GT服务和软GT服务的混合型 TTL-QoS 保证机制将进一步提高网络各种TTL-GT业务的保证率。
5总结
本文总结了片上网络服务质量研究的关键问题和典型的研究成果，限于篇幅，主要综述了从QoS路由算法、架构和新机制来解决片上网络服务质量，除此之外，其他方式如：拓扑结构、路由器结构、映射方法等，也可以为片上网络的服务质量保证提供新的方法。 参考文献：
[1] Baidu encyclopedia. SoC [EB/OL]. [2014-10-07]. http：//baike.baidu.com/view/58056.htm.
[2]W. J. Dally， B. Towles. Route ackets， not wires： on-chip interconnection networks[C]//Proceedings of the 38th Design automation conference （DAC‘01）. New York， NY， USA： ACM， 2001： 684-689.
[3]Liu C. C.， Jeng-Huei Chen， Manohar R， et al. Mapping system-on-chip designs from 2-D to 3-D Cs[C]//Proceedings of the 2005 IEEE International Symposium on Circuits and Systems （ISCAS‘05）. Piscataway， NJ， USA： IEEE， 2005： 2939- 2942.
[4] A Parasuraman， VA Zeithaml， LL Berry. A Conceptual Model of Service Quality and Its Implications for Future Research. Journal of Marketing， 1985.
[5]M.D.Harmanei，et_al.Quantitative Modelling and Comparison of Communieation Schemes to Guarantee Quality-of-Service in Networks-on-ChiP.IEEE Intemational Symposium on Circuits and Systems.Vol.2，PP.1782-1785，2005.
[6]E.Rijpkema，et_al.Trade Offs in the Design of a Router with Both Guaranteed and Best Effert Services for Networks-on-Chip.DATE 03，pp.1530-1591，2003.
[7]R.Chakravorty，S.Kar and P.Fami.End-to-end intenet quality of service（QoS）：An overview of issues， architectues and frameworks. India：Bhuwaneshwar.2000.
[8]Ankur Agarwal，Mehmet Mustafa， A.S， Pandya. Study of Network on ChiP resoures alloeation for QoS.Canadian Conference on Eletrical and Computer Engineering.pp.1291-1295，May2006.
[9]M.Kim，D.Kim，G.E.Sobelman.Network on ChiP Quality of Service through MultiProtocol Label Switching.IEEE Intemational Symposium on Circuits and Systems.2006.
[10]周干民. NoC 基礎研究，[博士学位论文].合肥：合肥工业大学，2005.
[11]陆俊林，王宏伟.支持服务质的片上网络路由器设计[J].计算机辅助设计与图形学学报，2008，20（11）：1403-1410.
[12]M.Dehyadgari，M.Nickray，A.Afzali-kusha，Z.Navabi：Evaluation of Pseudo Adaptive XY Routing Using an Object Oriented Model for NOC[C].The 17th International Conference on Microelectronics，Decem-ber 2005：13-15.
[13]Glass C J，Ni L M.The turn model for adaptive routing[J].Journal of the ACM（JACM）.1994，41（5）：874-902.
[14]J.Hu，R.Marculescu.DyAD–Smart Routing for Networks-on-Chip Proceedings[C]，41st Design Automation Conference， 2004：260-263.
[15]欧阳一鸣，董少周，梁华国.基于2D Mesh的NoC路由算法设计与仿真[J].工程应用技术与实现2009，35（22）：228-229.
[16]顾华玺，刘增基，王琨，等.Torus网络中分布式自适应路由算法[J].西安电子科技大学学报，2006，33（3）：352-358.
[17]Cypher R，Gravano L.Requirement s for Dead-lock2Free，Adaptive Packet Routing[J] . SIAMJon Computing， 1994，23（6）： 1262-1274.
[18]李旺远，王长山.Mesh跳步容错路由算法[J].计算机与现代化，2010，26（3）：40-41. [19]Li M，Zeng Q A，Jone W B.DyXY：a proximity congestion-aware deadlock-free dynamic routing method for network-on chip[C].43rd ACM/IEEE Design Automation Conference.San Francisco，CA，USA：ACMPress，2006：849-852.
[20]M.Ali，M.Welzl，S.Hellebrand.A Dynamic Routing Mechanism for Network on Chip[C].23rd NORCHIPConference，21-22 November 2005：70-73.
[21]Kim Y B.Fault tolerant source routing for network-on-chip[C].22nd IEEE International Symposium onDefect and Fault-Tolerance in VLSI Systems，2007：12-20.
[22]Hu Jingcao，Ma rculescu Radu.DyAD：Smart routing for networks-on-chip[C]//Proceedings of the 41st Annual Design Automation Conference.2004：260-263.
[23]朱小兵，顧华玺，王长山.SD：一种适用于基于mesh拓扑的片上网络路由算法[J].微计算机信息，2009，25（8-2）：63，93-94.
[24]William J. Dally， Brian Towles. Route Packets， not Wires： on-Chip Interconnection Networks.Proceedings of Design Automation Conference，2001：684～689.
[25]Ge Ming Chiu. The odd-even turn model for adapyive routing. IEEE Transactions on Parallel and Distributed Systems，2000： 729～738.
[26]Ming Li， Qing-An Zeng， Wen-Ben Jone. DyXY-A proximity congestion aware deadlock free dynamic routing method for network on chip. Proceedings of Design Automation Conference，2006：849～852.
[27]Glass C.J.， Ni L.M.. The turn model for adaptive routing. Proceedings of the 19th Annual International Symposium on Computer Architecture，1992：278～287.
[28] Hu J， Marculescu R. DyAD-smart routing for networks-on-chip. Proceedings of Design Automation Conference ， 2004： 260～263.
[29] Pejman Lotfi-Kamran， Masoud Daneshtalab， Caro Lucas， et al. BARP-A Dynamic Routing Protocol for Balanced Distribution of Traffic in NOCs. Design， Proceedings of Automation and Test in Europe，2008，3：10～14.
[30] Daneshtalab M.， Sobhani A， Afzali-Kusha A.， et al.NoC Hot Spot minimization Using AntNet Dynamic Routing Algorithm. Proceedings of International Conference on Application-specific Systems， Architectures and Processors，2006，9：33～38.
[31] Dehyadgari M.， Nickray M.， Afzali-kusha A.， et al. Elevation of Pseudo Adaptive XY Routing Using an Objected Model for NOC. Proceedings of the 17th International Conference on Microelectronics，2005：5～12.
[32] Dauto J.A. New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks. IEEE Transactions on Parallel and Distributed Systems，1993，12：1320～1331.
[33] Mohamed M. Sabry， M. Watheq El-Kharashi， Hassan Shehata Bedor.A New Dynamic Routing Algorithm for Networks-on-Chips. IEEE Pacific Rim Conference on Computers and Signal Processing，2007：346～349. [34]朱晓静.片上网络的结构设计与性能分析，[博士学位论文].合肥：中国科学技术大学，2008.
[35] Mediratta S.D.， Draper J.. Characterization of a Fault-tolerant NoC Router. Proceedings of IEEE International Symposium on Circuits and Systems，2007：381～384.
[36] Jie Wu. A Fault-Tolerant and Deadlock_Free Routing Protocol in 2D Meshes Based on Odd_Even Turn Model. IEEE Computer Society，2003.
[37]Chen Kuo-hsuan， Chiu Ge-ming. Fault-tolerant Routing Algorithm for Meshes without Using Virtual Channels.Journal of information science and engineer，1998：765～783.
[38]Jie Wu. A Deterministic Fault-Tolerant and Deadlock free Routing Protocol in 2-D Meshed Based on Odd-Even Turn Model. Proceedings of the 16th international conference on Supercomputing，2002：67～76.
[39] 黎黎.片上網络路由算法研究及路由节点的 FPGA 设计，[硕士学位论文].成都：电子科技大学，2007.
[40]朱小虎，曹阳，王力纬.多级拥塞控制的 NoC 路由算法.北京邮电大学学报，2007，10（5）：91～94.
[41]张磊，李华伟，李晓维.用于片上网络的容错通信算法.计算机辅助设计与图形学学报，2007，4（4）：904～912.
[42]张磊，李华伟，李晓维.一种用于片上容错通信的随机路由算法.第四届中国测试学术会议论文集，2006.
[43]岳培培，刘建，Sheikh Anjum， et al.NoC 映射问题中的列举路径分配算法.电子科技大学学报，2008，1（1）：54～57.
[44]吕勇，赵光宙，苏凡军.基于蚁群算法的自适应动态路径算法.浙江大学学报，2005， 10（10）：8350～8353.
关键词：片上网络；三维片上网络；服务质量；路由算法
Network-on-chip quality of service research overview
TANG Huai-yin
（1.School of computer science and software， Tianjin Polytechnic University， Tianjin 300387；）
Abstract： With in-depth research and development of NoC（network-on-chip），communication on chip became more and more complex ， traditional services have not been able to guarantee requirements of data transmission， As a result， network data transmission can not be guaranteed，providing a guaranteed quality of service has become a key problem for network on chip communication.Based on the systemic analysis of relevant research studies，this article reviewed the key problem of NoC service and classic research result ，at the same time ，analyzed the different ways of improving NoC quality of service.
Key words： Network-on-chip（NoC）；3D-NoC；Quality of Service（QoS）；routing algorithm
0引言
20世纪90年代出现了片上网絡（Network-on-chip，NoC）的概念，即将宏观网络技术引入到片上系统，以解决芯片中的通信问题[1]。Dally在2001年首次将采用分组路由模式的片内通信称为NoC[2]。 随着市场需求和芯片集成工艺地不断提高，三维片上网络（3D-NoC）应运而生。2005 年，Liu C. C.， Jeng-Huei Chen， Manohar R.等首次提出了3D-NoC的概念[3]。
工艺的进步使片上网络突破了总线结构的各种瓶颈，也导致片上网络系统全局通信需求日益复杂和不可预测，服务质量是保障片上网络通信的关键技术。因此，引起了学术界的广泛关注。
1片上网络服务质量
1.1 服务质量
片上网络服务质量概念最初源于宏观计算机网络上的QoS，为片上系统中通信网络提供各种灵活、准确的服务质量保障。好的服务质量是指NoC具有低时延、高吞吐量、低功耗等特性。服务质量的关键指标主要包括可用性、吞吐量、时延、时延变化和丢包等。 同一业务流中分组的时延往往会出现不同，这种现象被称为抖动和漂移现象。抖动是高频率的时延变化，而漂移是低频率的时延变化。利用缓存可以克服过量的抖动，但这将增加时延，造成其他问题。
随着片上网络中各种通信服务需求日益复杂，QoS已经没有了统一的规范，QoS的指标被更广泛的概括为性能约束、资源约束和优先级约束[4]。性能约束是对通信网络中数据包传输质量进行度量的一些性能限制，例如时延、吞吐量、准确率等。资源约束是根据一系列独特的特征对特定类型的网络资源的使用进行限制，例如编码等。优先级约束是影响网络资源分配的限制条件，以便于从当前通信节点中将数据包传输到下一个通信节点。
1.2 QoS服务模型
服务模型是指一组端到端的QoS功能，目前NOC中主要的QoS服务模型有：保障服务、尽力服务、综合服务、区分服务和多协议标记交换。保障服务模型[5]（Guaranteed Through put service，GT）是一种基于面向连接的服务。会带来额外的时延，但是在很大程度上提高数据的吞吐率。
尽力服务模型[6]（Best Effert service，BE）是一种单一也是最简单的服务模型。BE服务对于较短的消息可以提高传输效率、降低时延。
综合服务[7]可以满足多种QoS需求，它主要的协议是资源预留协议（RSVP），它负责在报文发送前向网络申请特定的服务。综合服务可以提供保证服务和负载控制两种服务。综合服务中这种基于流的算法容易受到“路由器崩溃”的攻击。
区分服务[8]通过将不同数据流划分为不同服务类型来获得QoS，而不需要维护每一个数据流，它不需要使用RSVP，基于虫孔交换机制的区分服务模型目前比较广泛。
区分服务有两种服务类别：快速型转发和确保型转发。快速型转发：是一种最简单的服务类型，服务类别包括常规类型和快速类型。大多数通信流量应该属于常规流量，有一小部分分组属于快速类别。快速类别的分组应该可以直接通过网络。符号化表示如图1所示：
确保型转发：它是一种更加精细的管理服务类别的方案，其规定了4种优先级别，每种级别都有它自己的资源。并且对于正在经历拥塞条件的分组，定义了三种丢弃概率：低、中、高。 多协议标记交换[9]是一种基于数据包标记的交换技术，其工作思想是，在每个分组前端加上一个标签，然后根据这个标签而不是目的地址进行路由。将标签做成内部表中的一个索引 ，这样就可以把寻找路径变成非常简单的表格查询，很快的完成路由过程。
1.3 片上网络路由算法
片上网络路由算法研究主要是通过评估优化、裁减用于并行计算机集群的路由算法。在考虑路由算法的自适应性、连通性、容错能力、死锁发生率等基本性能的同时，更加关注路由算法在、时间开销以及硬件实现复杂度方面的情况。根据不同的标准可将路由算法分为如下几类[10]，如图2所示。
1.4设计路由算法时要满足的要求
面积和功耗限制着芯片上复杂的片上网络系统，设计NoC路由算法时要注意以下几点要求：
（1）更简单化的路由信息计算，这样才能避免的硬件设施的体积过大、速度无法满足需要；
（2）路由算法能避免饥饿，对NoC中的所有节点一视同仁；
（3）考虑到网络资源有限，倾向于选择最短路径，或者绕道次数低的路由算法；
（4）路由算法确保分组能够准确地到达目的地，即算法活锁和无死锁。
1.5 常见路由算法
路由算法是常见的片上网络中提供服务质量的重要手段，好的路由算法可以极大地改善片上网络的性能，并提供较好的服务质量。因此对常见的路由算法做一个简要的介绍。目前常见的适用于NoC的路由算法有自适应路由、无关路由、无关路由和自适应路由相结合的路由算法。
1.5.1无关路由算法
无关路由决策与网络状态无关，但它的选择却未必是最佳的。常见的无关路由算法有：确定性路由、维序路由、随机路由算法等。
（1）维序路由算法
维序路由包括超立方体中的E-cube路由和2D Mesh中的XY路由。该类算法路由逻辑简单，在维序间没有死锁，容易实现，但网络中心节点的业务流量最大，整个网络的业务流量不均衡，容易造成网络的拥塞。
（2）确定性路由算法
确定性路由算法的高可靠性和低延迟表现在网络没有拥塞时。包按正确顺序到达目的节点，因此实时系统一般采用确定性路由。一般情况下，每个路由器都有一个包括所有路由消息的全局路由表，网络改变时，路由表随之更新路由消息。确定性路由算法硬件设计和实现简单，具有较小的时延，是无活锁和无死锁路由。
（3）随机路由算法
随机路由算法算法简单，且能容错，假定每个分组迟早都能到达其目的节点，基于概率将分组按不同的路径发送到目的节点，但其速度慢，并且占用大量的网络资源。常见的随机路由算法有洪泛路由算法、IVAL随机路由算法和IVAL随机路由算法。洪泛路由算法包括概率洪泛路由算法[11]和直接洪泛算法。该算法的缺点是占用大量的网络资源。相比概率洪泛算法，直接洪泛算法有了改进。直接洪泛算法比概率洪泛算法有更高的容错能力和更少的网络资源占有率。Valiant算法分组分两步路由：将原始的一个路由问题转换成两个路由问题，较好的平衡了网络负载，降低了拥塞概率。IVAL随机路由算法是对Valiant随机路由算法的改进。IVAL算法两步路由都采用维序XY路由算法，只是两次维序顺序相反。
1.5.2自适应路由算法
常见的自适应路由算法包括伪自适应XY路由、转弯模型（Turn Model）、奇偶转弯模型、XY-YX路由、基于Torus网络的负向优先路由（NF-T）、跳步容错路由、DyXY路由、NoC-LS路由、SRN路由算法等。
（1）伪自适应XY路由算法
该算法根据网络状态在确定性路由和自適应路由之间转换，是对确定性XY路由的一种改进[12]。当网络没有或拥塞很小时，用确定性路由算法；当网络拥塞状况比较严重时，数据选择拥塞程度较小的链路进行数据传输。伪自适应XY路由在一定程度上能减少热点的产生，对网络流量的分布也相对合理。
（2）转弯模型路由算法
转弯模型[13]是Mesh网络中一种经典的无死锁路由算法。其基本思想是分析信息分组在网络中可能的转向（Turn）以及这些转向可能形成的环，通过禁止一定数量的转向来破坏信道的环形依赖关系，从而破坏死锁的形成条件。根据禁止转向的不同，形成了3种基本的算法，即西向优先WF（West First）、北向最后NL（North Last）和负向优先NF（Negative First）算法。
（3）奇偶转弯模型算法
奇偶转弯模型[14]主要适用于Mesh结构的NoC，它不需要使用虚通道便能避免死锁。不像转弯模型那样通过限制某些方向的转弯来防止死锁的产生，而是对发生转弯的位置进行了约束。
（4）XY-YX路由算法
XY-YX路由算法[15]是对XY路由算法的改进，基本思想是数据并不总是先X方向，后Y方向，而是根据目的节点和当前节点的位置来选择。当目的节点Y方向的值小于当前节点Y方向的值时，即目的节点在当前节点的北边，选择先Y后X；当目的节点Y方向的值大于当前节点对应的值时，即目的节点在当前节点的南边，选择先X后Y，从而减轻XY路由算法在X方向产生的阻塞。本算法路由过程只允许NE，ES，WS，NW 4个转向。
（5）基于Torus网络的负向优先路由算法
基于Torus网络的负向优先路由算法[16]是在转弯路由算法的基础上，引入虚信道（Virtual channel），将物理网络划分成2个虚拟网络，每条物理链路（Physical link）使用3条虚信道，文[17]中证明这是2D Torus网络实现无死锁自适应路由算法所需虚信道数目的最小值。通过相应的路由规则，破坏2D-Torus网络中信道之间的环形依赖关系，从而实现了无死锁无活锁的自适应路由算法。该算法基于引入虚信道完成了自适应路由，但大部分的流量集中在0号虚信道上，2号虚信道则相对较少使用，使得0号虚信道成为整个网络通信的瓶颈，而2号虚信道负载不足，3条虚信道的使用存在着严重的负载不均衡，浪费严重。新的虚信道使用策略的核心思想是达到各个虚信道的负载均衡。减少1号虚拟网络中0号虚信道中的部分流量，将部分流量尽早地分配到2号虚拟网络中，增加2号虚信道的使用几率。 （6）跳步容错路由算法
跳步容错路由算法[18]是对转弯模型的改进，适用于Mesh网络结构中，具有实现简单、能兼顾网络吞吐和时延的特点。路由函数因为限制了转弯的方向并且在限制转弯的方向上设置了逃离虚通道，不会形成死锁环路，从而避免了死锁。
（7）DyXY路由算法
DyXY路由算法[19]中，节点通过监视其相邻节点的拥塞状况来选择分组路由的下一跳。该算法在获得端口分组的目的节点地址后，如果当前节点与目的节点地址具有相同的X维（或Y维）坐标，则将分组沿Y维（或X维）路由至目的节点；如果当前节点就是目的节点，分组会发送给本地节点端口，否则，本地节点检测其相邻节点到目的节点的拥塞状况，选择拥塞最小的路径将分组发送出去。这样能避免死锁和活锁的发生，限制了分组通过最短路径传输。
（8）NoC-LS路由算法
在NoC-LS路由算法[20]中节点将路由消息发送给网络中每一个节点，网络中的每个节点都有一张整个网络的状态图，根据网络状态进行路由计算。该算法非常复杂，路由表会随着网络中节点数的增大而增大，但能够将分组高效地发送到任一目的节点。
（9）SRN路由算法
SRN路由算法[21]不需要产生大量的冗余分组，它允许网络可以自行组织，自行配置，并且能够容错，而不需要周期性的路由管理，并且仿真结果表明，该算法具有比洪泛算法更好的容错性能。
（10）蚁群动态路由算法ANDR
蚁群动态路由算法能够使流量均衡，减少网络中热点的产生，它使用路由表，路由表中记录每个节点到网络中其它节点时，选择东、西、南、北方向4条链路的概率，因此分組路由能选择具有最小流量的最短路径，适用于Mesh结构。
1.5.3无关路由和自适应路由相结合的路由算法
无关路由算法和自适应路由算法优点相结合的算法有DyAD路由算法和SD路由算法。
（1）DyAD路由算法
DyAD路由算法[22]是一种将维序路由与奇偶转向路由相结合的路由算法。在网络处于低负载情况下采用维序路由，而当网络处于高负载情况下采用奇偶转向的适应性路由。
（2）SD路由算法
SD路由算法[23]是确定性路由算法和适应性路由算法相结合的产物，由于中心区域的节点采用的是适应性路由算法，所以可以很好的解决Mesh，Torus网络中中心节点易出现热点和网络拥塞的情况。该路由算法实现简单，可以大幅度降低路由器实现的复杂度，节约了网络实现的硬件资源。
2通过路由算法来解决服务质量问题
2.1国际研究
国外对确定性路由算法、自适应路由算法、容错路由算法和适用于不规则拓扑结构的路由算法研究比较多。文献[24]介绍的XY维序路由算法简单易实现，适用于二维网格拓扑结构、二维折叠环拓扑结构等规则的拓扑结构，在无拥塞和故障的网络环境下能获得较低的延时，是研究中常用的确定性路由算法。在自适应路由算法方面的研究成果比较多。Glass C.J.等人提出的转弯模型[25]是一种自适应路由算法，适用于规则拓扑结构。该模型限制数据传输在一些节点的转弯方向形成死锁。因为没有采用虚拟通道，减少了面积开销。Ge Ming Chiu在转弯模型的基础上提出了奇偶转弯模型[26]。Ming Li等人提出了自适应路由算法[27]DyXY（Dynamic XY routing）。该算法根据相邻通信节点的拥塞状况分配路径，确保了最短路径。在路由器结构中设计了检测相邻通信节点的拥塞状况的功能以支持该算法。Hu J 等人提出了能够预测竞争的自适应路由算法 DyAD[28]（Dynamic Adaptive Deterministic switching），通过监控相邻通信节点间的通信事务，为当前通信节点的路由做出选择。Pejman Lotfi-Kamran等人提出了路由算法 BARP[29]，该算法充分利用源节点和目的节点之间具有多条最短路径的特点，将通信任务均匀分布在所有的最短路径中以平衡网络负载。Daneshtalab M.等人将蚁群算法用于解决片上网络的路径分配问题[30]。Dehyadgari M.等人提出了将 XY 维序路由算法和自适应路由算法相结合的路由算法PAXY[31]（Pseudo Adaptive XY Routing），通过监测相邻节点的状态选择合适的路由算法进行路由。Mohamed M. Sabry等人提出了一种动态自适应路由算法[32]，在路由过程中可以避免死锁和活锁。为了满足算法的需求，研究者在C语言环境设计实现了路由器和路由算法，重新定义了数据包格式和路由器结构，并将其应用到二维折叠换拓扑结构和二维网格拓扑结构的片上网络系统中。 Duato 提出了在虫孔流控机制中设计自适应无死锁路由算法的理论[33]。有一些论文研究适用于不规则拓扑结构的路由算法[34]。不规则拓扑结构的片上网络系统中一些大于tile面积的特殊区域，通常用于共享存储。由于特殊区域的存在占据了一些路由器的位置，使得某些位置没有路由器。由于这些路由器的缺失，增加了路由路径的长度，用于规则拓扑结构的死锁避免规则不再适用。容错路由算法的情况与这种情况类似。这两种情况的路由算法考虑的因素相似，基本可以相互通用。在容错路由算法方面，Mediratta S.D.等人提出了一种容错路由算法[35]，在网络中传输路径探测数据包收集链路的状态信息，根据状态信息进行路径分配避免经过发生故障的链路。文献[36， 37， 38]均是在转弯模型的基础上提出了可容错的确定性路由算法，文献[36]介绍了XY维序路由算法与奇偶转弯模型相结合的E-XY容错路由算法，文献[37]和文献[38]介绍的容错路由算法在奇偶转弯模型的基础上增加一些限制条件以实现容错功能。
2.2国内研究
在确定性路由算法方面，黎黎提出了适用于二维折叠环拓扑结构的确定性路由算法[39]，对通信节点采用特定的方式编码，根据编码分配路径。朱小虎等人提出了具有多级拥塞控制功能的路由算法，将网络的拥塞状态分为三种：未拥塞、轻度拥塞、重度拥塞。在网络未发生拥塞时选择固定的传输路径，使用XY维序路由算法；当网络发生轻度拥塞时，对数据进行分流，采用自适应的XY路由算法；当片上网络处于中度和重度拥塞时，根据等待时间权衡分流数据包与不分流数据包对整个网络造成的影响，选择等待时间较短的传输路径[40]。容错路由算法方面，文献[41，42]中带有端到端反馈的随机路由算法，有效地处理传输过程中的随机错误，具有较高的转发速度，保证了传输的可靠性。在自适应路由算法方面，岳培培等人提出了列举路径分配算法[43]，在算法中设置最大带宽作为限制条件，寻找符合带宽约束的路径组合，符合带宽限制条件的通信路径为合法的通信路径，然后根据合法路径的数目将通信流进行分类，根据各种分类的优先级进行路径分配。吕勇等人参照蚁群算法中收集信息和更新信息素表的方法，设计了一个能够收集和更新网络链路信息的路由算法[44]。 蜂群算法是近几年提出的一种模拟蜜蜂“舞蹈”的优化算法，在求解NP完全问题方面有很大的优势。刘宝起采用最短路由，提出一种基于蜂群算法的QoS路由算法，使路由的自由度得到了最大程度开放，用基于软件的死锁恢复机制来检测和恢复死锁；采用了综合考虑历史信息和当前网络状态的路由策略，使用代理来更新路由信息，仿真结果显示，蜂群算法能够提高吞吐，降低时延和抖动，有效地保障了NoC 中的服务质量。 南京航空航天大学的王婷基于网络延时、带宽、吞吐量等QoS的性能指标，提出了一种动态路径算法，设计了一组面向特定应用的性能约束条件。在C语言环境下对算法进行功能验证和仿真，在不同通信任务模型下，分析网络负载的分布情况，对算法的性能进行评估。然后，在RTL级采用Verilog语言设计实现了路径分配算法，使功能得到验证，在此基础上，对算法在不同网络状态和不同网络负载下的网络延时、带宽、吞吐量等指标进行仿真，将结果与XY维序路由和DyXY路由算法进行对比分析。最后在Synopsys的EDA平台上分析对算法面积和功耗开销。 分析RTL级仿真之后获得的平均传输延时、网络吞吐量、链路利用率等QoS性能指标，结果表明动态路径分配算法能有效地平衡了网络负载，降低了数据包阻塞率，在不同的网络状态下能普遍改善了网络中有链路拥塞，提高故障状态下的性能。
西安电子科大的宁欢提出了一种改进型路由算法，该算法有效的克服了DyAD方法在网络负载较高时所采用的奇偶转向策略的缺点---可能会使得传输跳数增加，从而导致数据传输时延加大、服务性能下降。在数据包受到阻塞时，改进型的路由算法每个包的尾部的等待数据域会进行阻塞计时。该算法在网络负载较低时采取XY维序路由算法，但是当传输遇到阻塞时，尝试在Y维方向探测，这种策略减少了不必要的传输过程，仍然会保证数据包以最短路徑进行传输，以降低延迟。如果Y维方向的链路传输失败，则路由器会初始化包的等待数据域，并给该数据域赋一个定好的容忍极值，这个数据包将会因为暂停发送而在该路由节点进入等待期，到该路由节点的下一个判断周期时，先进行X维路由判断；如果该方向不存在阻塞，发送数据包并将数据包的等待数据域清0；如果X维方向仍然存在阻塞状态，则判断Y维路由是否阻塞，若Y维方向不存在阻塞，则并发送数据包并将该数据包的等待数据域清0。当X维和Y维方向的路由均阻塞时，则判断等待数据域中的容忍值。如果该值为0，则路由器设置flag域并转为奇偶路由模式；否则将该数据包中等待数据域中的容忍值递减1个单位，重新进入等待期。仿真结果显示该算法在网络负载较高时能够有效减小时延、使得网络的性能网络的吞吐量得到很大提升。
根据生物智能路由算法以及Qos路由模型，宁欢利用遗传算法来使片上网络中Qos路由问题得到了很好的解决。选择一条最优或是次优路径，通过对所需要的时延、吞吐、抖动等参数进行考量，为各种所需的QoS参数提供一种综合保证。对SWD算法和遗传算法进行的路径分配方法的时延、吞吐、抖动性能等进行的仿真结果表明SWD算法和遗传算法能够使传输的时延、吞吐和抖动性能得到显著改善。然而该方案并未探索遗传算法与其它生物算法（如蚁群算法）的融合，仅仅通过遗传算法遗传算法本身来保障NoC中的服务质量，并未多方面尝试提高算法的收敛性和局部最优解等。文献结合唯序路由和奇偶转向路由提出了一种新的保证QoS路由算法———区域路由算法。该算法既能克服QoS的抖动，又能提高吞吐并降低时延性能。该算法按照当前节点的位置将网络划分为两个区域，左区域为西优先路由，右边域为东最后路由，算法将确定性路由和适应性路由的优点结合起来形成一种新的路由.通过仿真结果表明，区域路由算法时延、吞吐以及抖动情况都得到了很大的改善，从而有效地保障了片上网络的QoS。
3通过一种新架构来保障片上网络服务质量 堆叠片上网络（图3）在垂直方向上的大吞吐量但是使系统有更大的面积成本，更高的复杂度，纤毛片上网络（图4）可以减少面积和功耗，但是对于繁忙的业务量，垂直方向上会有瓶颈，针对这两种特点，巴西圣保罗大学Johanna Sepúlveda， Guy Gogniat， Ricardo Pires等人结合堆叠和纤毛两种片上网络的优点，形成一种新的混合的片上网络结构[51]（图5），既减少了面积和功耗，又能使垂直方向上通信有更大吞吐量。
4通过一种新机制来保障片上网络解决服务质量
片上网络是将不同的IP核集成在单个芯片上，芯片资源十分有限，在保证服务质量的同时提高资源的利用率便成为设计片上网络服务质量保证机制时必须考虑的一个问题。
电子科技大学的汪凡设计了3D-TTL-QoS保证机制的模型[52]，该模型通过对数据包的性能进行约束，引进宏观网络生存时间（time to live，TTL）概念，用数据包的跳数代表TTL，通过限制数据包的最大跳数来区别网络中的各种不同级别的数据包。他提出的TTL-QoS能够极大地保证高优先级的保证性能。同时当网络中业务的等级较少时，基于虚通道预留的QoS机制会造成大量缓存资源的浪费，但TTL-QoS却能够充分地利用缓存资源。主要思路是在源节点发送具有最大跳数限制的数据包，数据包中的TTL信息每经过一个路由节点或在路由节点竞争失败一次都将减一，当数据包中的TTL减为零时还没到目节点，则该数据包自动变为最低优先级的BE数据包，说明该TTL数据包没有实现服务质量保证；相反，当该数据包到达目的节点时TTL还没有等于零，则说明该数据包得到的服务质量保证。其不足之处在于 TTL-QoS 保证理论下，若 TTL-GT 数据包的 TTL 值小于网络中的平均跳数，源节点将修改 TTL 值直到满足要求为止，这样将使一些急需要服务质量保证的数据包得不到响应。所以在未来的研究中可以将硬GT服务和软GT服务结合起来。为低于网络TTL平均值的TTL-GT数据包提供虚电路连接，保证其服务质量，其他高于TTL均值的TTL-GT数据包仍将按照软GT服务机制传输。结合 GT服务和软GT服务的混合型 TTL-QoS 保证机制将进一步提高网络各种TTL-GT业务的保证率。
5总结
本文总结了片上网络服务质量研究的关键问题和典型的研究成果，限于篇幅，主要综述了从QoS路由算法、架构和新机制来解决片上网络服务质量，除此之外，其他方式如：拓扑结构、路由器结构、映射方法等，也可以为片上网络的服务质量保证提供新的方法。 参考文献：
[1] Baidu encyclopedia. SoC [EB/OL]. [2014-10-07]. http：//baike.baidu.com/view/58056.htm.
[2]W. J. Dally， B. Towles. Route ackets， not wires： on-chip interconnection networks[C]//Proceedings of the 38th Design automation conference （DAC‘01）. New York， NY， USA： ACM， 2001： 684-689.
[3]Liu C. C.， Jeng-Huei Chen， Manohar R， et al. Mapping system-on-chip designs from 2-D to 3-D Cs[C]//Proceedings of the 2005 IEEE International Symposium on Circuits and Systems （ISCAS‘05）. Piscataway， NJ， USA： IEEE， 2005： 2939- 2942.
[4] A Parasuraman， VA Zeithaml， LL Berry. A Conceptual Model of Service Quality and Its Implications for Future Research. Journal of Marketing， 1985.
[5]M.D.Harmanei，et_al.Quantitative Modelling and Comparison of Communieation Schemes to Guarantee Quality-of-Service in Networks-on-ChiP.IEEE Intemational Symposium on Circuits and Systems.Vol.2，PP.1782-1785，2005.
[6]E.Rijpkema，et_al.Trade Offs in the Design of a Router with Both Guaranteed and Best Effert Services for Networks-on-Chip.DATE 03，pp.1530-1591，2003.
[7]R.Chakravorty，S.Kar and P.Fami.End-to-end intenet quality of service（QoS）：An overview of issues， architectues and frameworks. India：Bhuwaneshwar.2000.
[8]Ankur Agarwal，Mehmet Mustafa， A.S， Pandya. Study of Network on ChiP resoures alloeation for QoS.Canadian Conference on Eletrical and Computer Engineering.pp.1291-1295，May2006.
[9]M.Kim，D.Kim，G.E.Sobelman.Network on ChiP Quality of Service through MultiProtocol Label Switching.IEEE Intemational Symposium on Circuits and Systems.2006.
[10]周干民. NoC 基礎研究，[博士学位论文].合肥：合肥工业大学，2005.
[11]陆俊林，王宏伟.支持服务质的片上网络路由器设计[J].计算机辅助设计与图形学学报，2008，20（11）：1403-1410.
[12]M.Dehyadgari，M.Nickray，A.Afzali-kusha，Z.Navabi：Evaluation of Pseudo Adaptive XY Routing Using an Object Oriented Model for NOC[C].The 17th International Conference on Microelectronics，Decem-ber 2005：13-15.
[13]Glass C J，Ni L M.The turn model for adaptive routing[J].Journal of the ACM（JACM）.1994，41（5）：874-902.
[14]J.Hu，R.Marculescu.DyAD–Smart Routing for Networks-on-Chip Proceedings[C]，41st Design Automation Conference， 2004：260-263.
[15]欧阳一鸣，董少周，梁华国.基于2D Mesh的NoC路由算法设计与仿真[J].工程应用技术与实现2009，35（22）：228-229.
[16]顾华玺，刘增基，王琨，等.Torus网络中分布式自适应路由算法[J].西安电子科技大学学报，2006，33（3）：352-358.
[17]Cypher R，Gravano L.Requirement s for Dead-lock2Free，Adaptive Packet Routing[J] . SIAMJon Computing， 1994，23（6）： 1262-1274.
[18]李旺远，王长山.Mesh跳步容错路由算法[J].计算机与现代化，2010，26（3）：40-41. [19]Li M，Zeng Q A，Jone W B.DyXY：a proximity congestion-aware deadlock-free dynamic routing method for network-on chip[C].43rd ACM/IEEE Design Automation Conference.San Francisco，CA，USA：ACMPress，2006：849-852.
[20]M.Ali，M.Welzl，S.Hellebrand.A Dynamic Routing Mechanism for Network on Chip[C].23rd NORCHIPConference，21-22 November 2005：70-73.
[21]Kim Y B.Fault tolerant source routing for network-on-chip[C].22nd IEEE International Symposium onDefect and Fault-Tolerance in VLSI Systems，2007：12-20.
[22]Hu Jingcao，Ma rculescu Radu.DyAD：Smart routing for networks-on-chip[C]//Proceedings of the 41st Annual Design Automation Conference.2004：260-263.
[23]朱小兵，顧华玺，王长山.SD：一种适用于基于mesh拓扑的片上网络路由算法[J].微计算机信息，2009，25（8-2）：63，93-94.
[24]William J. Dally， Brian Towles. Route Packets， not Wires： on-Chip Interconnection Networks.Proceedings of Design Automation Conference，2001：684～689.
[25]Ge Ming Chiu. The odd-even turn model for adapyive routing. IEEE Transactions on Parallel and Distributed Systems，2000： 729～738.
[26]Ming Li， Qing-An Zeng， Wen-Ben Jone. DyXY-A proximity congestion aware deadlock free dynamic routing method for network on chip. Proceedings of Design Automation Conference，2006：849～852.
[27]Glass C.J.， Ni L.M.. The turn model for adaptive routing. Proceedings of the 19th Annual International Symposium on Computer Architecture，1992：278～287.
[28] Hu J， Marculescu R. DyAD-smart routing for networks-on-chip. Proceedings of Design Automation Conference ， 2004： 260～263.
[29] Pejman Lotfi-Kamran， Masoud Daneshtalab， Caro Lucas， et al. BARP-A Dynamic Routing Protocol for Balanced Distribution of Traffic in NOCs. Design， Proceedings of Automation and Test in Europe，2008，3：10～14.
[30] Daneshtalab M.， Sobhani A， Afzali-Kusha A.， et al.NoC Hot Spot minimization Using AntNet Dynamic Routing Algorithm. Proceedings of International Conference on Application-specific Systems， Architectures and Processors，2006，9：33～38.
[31] Dehyadgari M.， Nickray M.， Afzali-kusha A.， et al. Elevation of Pseudo Adaptive XY Routing Using an Objected Model for NOC. Proceedings of the 17th International Conference on Microelectronics，2005：5～12.
[32] Dauto J.A. New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks. IEEE Transactions on Parallel and Distributed Systems，1993，12：1320～1331.
[33] Mohamed M. Sabry， M. Watheq El-Kharashi， Hassan Shehata Bedor.A New Dynamic Routing Algorithm for Networks-on-Chips. IEEE Pacific Rim Conference on Computers and Signal Processing，2007：346～349. [34]朱晓静.片上网络的结构设计与性能分析，[博士学位论文].合肥：中国科学技术大学，2008.
[35] Mediratta S.D.， Draper J.. Characterization of a Fault-tolerant NoC Router. Proceedings of IEEE International Symposium on Circuits and Systems，2007：381～384.
[36] Jie Wu. A Fault-Tolerant and Deadlock_Free Routing Protocol in 2D Meshes Based on Odd_Even Turn Model. IEEE Computer Society，2003.
[37]Chen Kuo-hsuan， Chiu Ge-ming. Fault-tolerant Routing Algorithm for Meshes without Using Virtual Channels.Journal of information science and engineer，1998：765～783.
[38]Jie Wu. A Deterministic Fault-Tolerant and Deadlock free Routing Protocol in 2-D Meshed Based on Odd-Even Turn Model. Proceedings of the 16th international conference on Supercomputing，2002：67～76.
[39] 黎黎.片上網络路由算法研究及路由节点的 FPGA 设计，[硕士学位论文].成都：电子科技大学，2007.
[40]朱小虎，曹阳，王力纬.多级拥塞控制的 NoC 路由算法.北京邮电大学学报，2007，10（5）：91～94.
[41]张磊，李华伟，李晓维.用于片上网络的容错通信算法.计算机辅助设计与图形学学报，2007，4（4）：904～912.
[42]张磊，李华伟，李晓维.一种用于片上容错通信的随机路由算法.第四届中国测试学术会议论文集，2006.
[43]岳培培，刘建，Sheikh Anjum， et al.NoC 映射问题中的列举路径分配算法.电子科技大学学报，2008，1（1）：54～57.
[44]吕勇，赵光宙，苏凡军.基于蚁群算法的自适应动态路径算法.浙江大学学报，2005， 10（10）：8350～8353.