CN110601996B - 一种采用令牌保底分布式贪心算法的环网防饥饿流控方法 - Google Patents

Abstract

一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，属于分布控制环网流控技术领域。方法包括步骤S01,当监测到环网的网上状态为空闲时，本地节点发送报文上网；步骤S02,本地节点在一定时间后仍未能传送报文时，请求网上正在传送报文的微片携带对应令牌；步骤S03,环网上传送报文的微片依次传送，微片传送至目标节点后下网，令牌绕环网传送回到本地节点并失效；其中，在微片自本地节点传送至目标节点的路径中的其他节点不能上网。本发明在不增加额外缓冲资源的前提下，避免饥饿问题、平衡各节点负载，优化环网的性能和可实现性。

Description

一种采用令牌保底分布式贪心算法的环网防饥饿流控方法

技术领域

本发明属于分布控制环网流控技术领域，具体涉及一种采用令牌保底分布式贪心算法的环网防饥饿流控方法。

背景技术

作为高性能计算机的重要组成部分，微处理器对于全系统性能指标、集成规模与稳定运行都有着决定性的影响。现阶段，片上网络技术NoC(Networks on Chip)在微处理器中广泛应用。相比总线和交叉开关，片上网络的带宽大幅提升，可实现性大幅增强。环网是一种常见的片上网络拓扑结构，适合于20个节点以内的高效互连，在高性能微处理器中得到广泛使用。从流控方式上看，环网可以分为集中控制和分布控制两类。集中控制环网需要一个中心控制逻辑，对各个节点的请求状况进行全局判断，可扩展性较差；分布控制环网的每个节点独立控制报文发送，可扩展性较强。

分布控制环网在使用中也存在着一些问题。由于每个节点难以确知全局信息，分布控制环网的负载均衡问题就较难处理。例如，一个节点本地有报文需要上网，而环网上前一个节点也有已经上网的报文到达，此时如果阻塞前一个节点的报文，则将导致整个环网上所有已经上网的报文阻塞。一种可能的解决方法是已经上网的报文允许被阻塞，额外增加缓冲资源存储上一个节点发来的报文，但是这会导致环网的资源开销增加、运行时功耗增大，而且缓冲需求和网络的注入率关系很大，当注入率很大时，缓冲需求将急剧增加。

另一种可能的解决方法是已经上网的报文不允许被阻塞，但是这可能导致严重的饥饿问题。例如，前一个节点持续不断地发送报文，则本地节点的报文始终无法上网，导致环网上的负载严重不均衡。当饥饿现象出现时，还可能造成一个报文的多个微片被拉得很开，信息传输的连续性严重下降。

综上所述，常规方法难以有效地在不增加额外缓冲资源的情况下处理分布控制环网负载均衡、饥饿避免等问题。

发明专利CN200810116021.4公开了一种多业务调度方法，并具体公开了方法包括A、计算当前调度时隙之前一定时间段的业务传输速率，统计业务的L2分组丢包率以及头分组等待时长，之后，计算业务间的调度优先级；B、从调度队列中获取优先级最高的业务，确定该业务为GBR业务时，通过GBR令牌桶为该业务分配资源；C、更新可用资源，并确定可用资源不为空时，通过MBR令牌桶继续为GBR业务分配资源，并合并通过GBR令牌桶和MBR令牌桶为该业务分配的资源。该发明考虑业务的QoS属性，在避免“饥饿”状况发生的同时，满足业务的GBR要求，但该发明仅解决优先级最高业务的饥饿问题。

发明内容

本发明针对现有技术存在的问题，提出了一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，在不增加额外缓冲资源的前提下，避免饥饿问题、平衡各节点负载，优化环网的性能和可实现性。

本发明是通过以下技术方案得以实现的：

本发明提供一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，包括：

步骤S01,当监测到环网的网上状态为空闲时，本地节点发送报文上网；

步骤S02,本地节点在一定时间后仍未能传送报文时，请求网上正在传送报文的微片携带对应令牌；

步骤S03,环网上传送报文的微片依次传送，微片传送至目标节点后下网，令牌绕环网传送回到申请节点并失效；其中，在微片自本地节点传送至目标节点的路径中的其他节点不能上网。

该发明利用贪心算法保证了环网上数据传送的效率，而令牌方法则保证了环网数据通路使用的公平性。

作为优选，步骤S01包括：

步骤S11,于每一个时钟周期，监测环网的网上状态；

步骤S12，若前一个节点没有报文经过，则本地节点发送报文上网。

作为优选，步骤S02包括：

步骤S21,本地节点处的超时计数器计数达到超时阈值时，本地节点的饥饿避免状态机由初始空闲状态S0进入令牌请求状态S1,本地节点的令牌计数器记录超时报文的剩余报文长度；

步骤S22，网上传送报文中的每个微片携带一个令牌，所述令牌包括令牌有效位和跳数域；所述跳数域的令牌跳数初始值设置为环网节点数。

作为优选，步骤S21中本地节点处的超时计数器计数达到超时阈值时的判断过程包括：

本地节点处的超时计数器初始值为0，当本地报文被阻塞一个时钟周期，则超时计数器计数加1；

当本地节点处的超时计数器计数等于超时阈值时，则认为本地节点处的超时计数器计数达到超时阈值。

作为优选，所述超时阈值为可配置寄存器值。

作为优选，步骤S03包括：

步骤S31,本地节点向环网上请求一个令牌,令牌计数器计数减1；

步骤S32，微片传送至目标节点后下网，令牌绕环网传送回到本地节点；所述令牌跳数随令牌在环网上每向前走一跳而减1，当回到本地节点时，令牌跳数为0，令牌失效；

步骤S33，当令牌计数器计数大于0时，返回步骤S31，本地节点向环网上请求下一个令牌，直至令牌计数器计数为0时结束；其中，当令牌计数器计数为0时，本地节点的饥饿避免状态机由令牌请求状态S1转为初始空闲状态S0。

作为优选，步骤S31还包括：当微片携带的令牌为无效时，将令牌设置为有效。

作为优选，步骤S03还包括：在上述本地节点至目标节点传送路径外的环网其他节点之间也存在报文传送路径。

作为优选，在上述本地节点至目标节点传送路径外的环网其他节点之间的报文传送过程包括：

在上述本地节点至目标节点传送路径外的环网其他节点中的两个分别作为本地节点和目标节点，所述本地节点执行步骤S01-S03。

作为优选，在上述本地节点至目标节点传送路径外的环网其他节点之间存在报文传送路径不止一条。

本发明具有以下有益效果：

本发明一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，优化环网的可扩展性，最小化环网的资源开销，最小化环网运行时功耗，避免环网中出现饥饿现象，保证环网上信息传输的连续性，优化环网负载均衡状况，保证环网有效带宽利用率。

附图说明

图1为本发明一种采用令牌保底分布式贪心算法的环网防饥饿流控方法的总流程图；

图2为饥饿避免状态机的管理结构示意图；

图3a为采用本发明一种采用令牌保底分布式贪心算法的环网防饥饿流控方法的具体示例的流程（1）示意图；

图3b为采用本发明一种采用令牌保底分布式贪心算法的环网防饥饿流控方法的具体示例的流程（2）示意图；

图3c为采用本发明一种采用令牌保底分布式贪心算法的环网防饥饿流控方法的具体示例的流程（3）示意图；

图3d为采用本发明一种采用令牌保底分布式贪心算法的环网防饥饿流控方法的具体示例的流程（4）示意图；

图3e为采用本发明一种采用令牌保底分布式贪心算法的环网防饥饿流控方法的具体示例的流程（5）示意图。

具体实施方式

以下是本发明的具体实施例并结合附图，对本发明的技术方案作进一步的描述，但本发明并不限于这些实施例。

如图1，本发明一种采用令牌保底分布式贪心算法的环网防饥饿流控方法包括：

步骤S01,当监测到环网的网上状态为空闲时，本地节点发送报文上网；

步骤S02,本地节点在一定时间后仍未能传送报文时，请求网上正在传送报文的微片携带对应令牌；

步骤S03,环网上传送报文的微片依次传送，微片传送至目标节点后下网，令牌绕环网传送回到申请节点并失效；其中，在微片自本地节点传送至目标节点的路径中的其他节点不能上网。

在采用本发明方法对环网结构进行流控前，需在环网结构的各个节点处设置超时控制模块。所述超时控制模块包括一个饥饿避免状态机、一个令牌计数器、一个超时计数器。

当环网结构中的某个节点（下文称“本地节点”）发现前一个节点没有报文经过时，则认为环网的网上状态为空闲状态，则本地节点发送报文上网，执行后续报文传送。在此过程中需要用到超时控制模块。

具体地，步骤S01包括：

步骤S11,于每一个时钟周期，监测环网的网上状态；

步骤S12，若前一个节点没有报文经过，则本地节点发送报文上网。

以一个时钟周期为监测期，确定环网的网上状态。若前一个节点有报文经过，则本地节点不能发送报文上网；反之，则可以发送报文上网。其中，报文中含有多个微片，主要是发送报文的微片上网。例如，当检测到微片有效位为0时，则认为前一个节点没有报文经过，可将此微片发送上网。

具体地，步骤S02包括：

步骤S21,本地节点处的超时计数器计数达到超时阈值时，本地节点的饥饿避免状态机由初始空闲状态S0进入令牌请求状态S1（参照图2）,本地节点的令牌计数器记录超时报文的剩余报文长度；

步骤S22，网上传送报文中的每个微片携带一个令牌，所述令牌包括令牌有效位和跳数域；所述跳数域的令牌跳数设置为环网节点数。

其中，步骤S21中本地节点处的超时计数器计数达到超时阈值时的判断过程包括：本地节点处的超时计数器初始值为0，当本地报文被阻塞一个时钟周期，则超时计数器计数加1；当本地节点处的超时计数器计数等于超时阈值M时，则认为本地节点处的超时计数器计数达到超时阈值。所述超时阈值M为可配置寄存器值。

本地节点的令牌计数器记录超时报文的剩余报文长度指的是：设置令牌计数器的初始值为超时报文的剩余报文长度。其中，报文的剩余报文长度根据超时报文微片有几个，则需要多少个令牌（每个微片携带一个令牌）的方式确定。

具体地，步骤S03包括：

步骤S31,本地节点于环网上请求一个令牌,令牌计数器计数减1；

步骤S32，微片传送至目标节点后下网，令牌绕环网传送回到本地节点；所述令牌跳数随令牌在环网上每向前走一跳而减1，当回到本地节点时，令牌跳数为0，令牌失效；

步骤S33，当令牌计数器计数大于0时，返回步骤S31，本地节点向环网上请求下一个令牌，直至令牌计数器计数为0时结束；其中，当令牌计数器计数为0时，本地节点的饥饿避免状态机由令牌请求状态S1转为初始空闲状态S0（参照图2）。

步骤S31还包括：当微片携带的令牌为无效时，将令牌设置为有效。对于每个节点，饥饿避免状态机由S0状态转换为S1状态时，或处于S1状态且令牌计数器大于0时，如果经过本地节点的微片所携带的令牌无效，则将该令牌置为有效。例如，令牌有效位为0，认为无效，将令牌有效位置1，认为有效。令牌计数器的作用在于持续请求令牌，让剩余报文能够连续上网。

令牌在环网上每向前走一跳，则令牌跳数减1，当令牌跳数变为0时（令牌在环网上转了一圈，回到原始请求节点）该令牌失效。对于每个节点而言，如果经过该节点的微片携带的令牌有效，无论该微片本身是否有效，都不能发送目标超过令牌请求节点的报文上网。这样可以保证携带令牌的微片回到请求节点时，一定是一个空闲微片，从而让超时报文上网。

为了充分利用环网资源，步骤S03还包括：在上述本地节点至目标节点传送路径外的环网其他节点之间也存在报文传送路径。在一实施方式下，上述报文传送过程包括：在上述本地节点至目标节点传送路径外的环网其他节点中的两个分别作为本地节点和目标节点，所述本地节点执行步骤S01-S03:步骤S01,当监测到环网的网上状态为空闲时，本地节点发送报文上网；步骤S02,本地节点在一定时间后仍未能传送报文时，请求网上正在传送报文的微片携带对应令牌；步骤S03,环网上传送报文的微片（无论是否携带令牌），依次传送，微片传送至目标节点后下网，令牌绕环网传送回到请求节点并失效；其中，在微片自本地节点传送至目标节点的路径中的其他节点不能上网。在另一实施方式下，上述报文传送过程包括：当监测到环网的网上状态为空闲时，本地节点发送报文上网。

只要不干扰其他报文传送，在上述本地节点至目标节点传送路径外的环网其他节点之间可存在不止一条报文传送路径。

图3a-3e示出了采用本发明一种采用令牌保底分布式贪心算法的环网防饥饿流控方法的示例。图3为11节点的环网。在图3a中，RIU6为第一本地节点，RIU6待上网报文超时，饥饿避免状态机进入S1状态，请求令牌6，令牌跳数为11。在图3b中，微片在RIU3下网,在RIU6至RI3沿箭头方向的路径上有RIU7的微片要上网，由于网上微片已被预约，故不能上网。在图3c中，在RIU4至RIU6沿箭头方向的路径并未与在RIU6至RI3沿箭头方向的路有干扰，则在RIU4至RIU6沿箭头方向的路径中的第二本地节点RIU4微片要上网，则可以上网；并在RIU5处微片下网（如图3d），微片变为无效。在图3e中，令牌6回到原点，令牌跳数为0，如果3a中待上网报文仍没有上网，则此时可以上网，并将令牌置无效；如果在此前已有机会上网，则仅将令牌置无效。

本领域的技术人员应理解，上述描述及附图中所示的本发明的实施例只作为举例而并不限制本发明。本发明的目的已经完整有效地实现。本发明的功能及结构原理已在实施例中展示和说明，在没有背离所述原理下，本发明的实施方式可以有任何变形或修改。

Claims (8)

1.一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，其特征在于，包括：

步骤S01，当监测到环网的网上状态为空闲时，本地节点发送报文上网；

步骤S02，本地节点在一定时间后仍未能传送报文时，请求网上正在传送报文的微片携带对应令牌；步骤S02包括：

步骤S21，本地节点处的超时计数器计数达到超时阈值时，本地节点的饥饿避免状态机由初始空闲状态S0进入令牌请求状态S1,本地节点的令牌计数器记录超时报文的剩余报文长度；

步骤S22，网上传送报文中的每个微片携带一个令牌，所述令牌包括令牌有效位和跳数域；所述跳数域的令牌跳数初始值设置为环网节点数；

步骤S03，环网上传送报文的微片依次传送，微片传送至目标节点后下网，令牌绕环网传送回到本地节点并失效；其中，在微片自本地节点传送至目标节点的路径中的其他节点不能上网；步骤S03包括：

步骤S31，本地节点向环网上请求一个令牌,令牌计数器计数减1；

步骤S32，微片传送至目标节点后下网，令牌绕环网传送回到本地节点；所述令牌跳数随令牌在环网上每向前走一跳而减1，当回到本地节点时，令牌跳数为0，令牌失效；

步骤S33，当令牌计数器计数大于0时，返回步骤S31，本地节点向环网上请求下一个令牌，直至令牌计数器计数为0时结束；其中，当令牌计数器计数为0时，本地节点的饥饿避免状态机由令牌请求状态S1转为初始空闲状态S0。

2.根据权利要求1所述的一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，其特征在于，步骤S01包括：

步骤S11，于每一个时钟周期，监测环网的网上状态；

步骤S12，若前一个节点没有报文经过，则本地节点发送报文上网。

3.根据权利要求1所述的一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，其特征在于，步骤S21中本地节点处的超时计数器计数达到超时阈值时的判断过程包括：

本地节点处的超时计数器初始值为0，当本地报文被阻塞一个时钟周期，则超时计数器计数加1；

当本地节点处的超时计数器计数等于超时阈值时，则认为本地节点处的超时计数器计数达到超时阈值。

4.根据权利要求1所述的一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，其特征在于，所述超时阈值为可配置寄存器值。

5.根据权利要求1所述的一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，其特征在于，步骤S31还包括：当微片携带的令牌为无效时，将令牌设置为有效。

6.根据权利要求1所述的一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，其特征在于，步骤S03还包括：在上述本地节点至目标节点传送路径外的环网其他节点之间也存在报文传送路径。

7.根据权利要求6所述的一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，其特征在于，在上述本地节点至目标节点传送路径外的环网其他节点之间的报文传送过程包括：

在上述本地节点至目标节点传送路径外的环网其他节点中的两个分别作为本地节点和目标节点，所述本地节点执行步骤S01-S03。

8.根据权利要求6所述的一种采用令牌保底分布式贪心算法的环网防饥饿流控方法，其特征在于，在上述本地节点至目标节点传送路径外的环网其他节点之间存在报文传送路径不止一条。

Images