仲裁器设计(三)-- Weighted Round Robin 权重轮询调度

作者:李虹江
原文:https://mp.weixin.qq.com/s/GY05HFLTYcjLQIly-y4gxg
本文授权转自IC加油站微信号,未经作者授权,严禁二次转载。
这一篇继续仲裁器的话题,来讲一个更加复杂的仲裁算法,并且给出设计的思路。

我们前面一篇仲裁器设计(二)-- Round Robin Arbiter里的Round Robin仲裁算法是一种公平的仲裁算法,每个requestor在得到许可之后优先级自动掉到最后,每个requestor之间都是平等的,大家都request的时候被grant的几率是相等的。公平固然好,**但是有的时候我们并不希望绝对的公平,反而希望有侧重。**咱们还是以老师点名回答问题为例讲一讲今天的主题:weighted round robin, 即加权轮询。

老师在问出一个问题之后,看到下面同学举手。老师可能心里想的并不是让大家有同样的几率回答到问题。假设有两个同学小A和小B,小A的学习成绩很好,小B的成绩要差一点。从老师的角度,如果小A和小B都举手回答同一个问题,那么老师可能更希望给小B以更多鼓励,所以叫他的可能性就高。在老师心里,这点“偏心”就是老师给小B同学加的权重,即weight。“偏心”越多,即权重越大。 当然,老师也不能一直都叫小B同学而完全不叫小A同学回答问题,这样小A同学的积极性也会受到打击。所以我们假设,老师决定按照下面的规则:

小A和小B同学的偏心值为1:2。也就是说,如果对连续3个问题小A和小B都举手,那么先让小B回答两次,第三个问题轮给小A回答。接下来开始新的一轮,即连续3个问题都举手,小B回答两次,小A回答一次。这个很好理解,只要小A和小B都举手,那么他们被叫到的几率就正比于他们的权重,即1:2。

我们可以这样理解,在老师的心目中对小A和小B都有一个计数器,计数器初始值就是老师心中的“偏心值”,每叫谁回答一次问题,那么就要给他的计数器减个1,对于偏心的同学,就可以连续叫他回答,直到计数器减到0,才换下一个同学。

注意,换下一个同学不是说换下一个偏心值最大的同学,而是按照之前约定好的顺序来换人,比如按照学号从大到小。这里要把偏心值和叫谁先回答区分开。偏心值大的意思是被叫到的次数多。上面的例子里,老师也可以这样叫,让小A回答第1个问题,然后让小B回答第2,3个问题。这样依然保持了回答几率是1:2。

我们对比一下Round Robin,如果小A和小B连续都举手,那么Round Robin仲裁会小A小B轮流来叫,而weighted round robin则是要把weight计数器消耗光之后才轮换。这也就是weighted round robin的设计思路,基于round robin,但是要设计一个weight counter,并调整相应的算法。
仲裁器设计(三)-- Weighted Round Robin 权重轮询调度
对于每一路requestor, 都有一个counter来记录这个requestor被grant的次数。counter的初始值就是他们的weight值,这个值可以是固定的,也可以是来自寄存器的配置。

和Round robin不同的是对于mask的调整。回想一下,round robin里的mask是,只要第i路被许可,那么从0到第i路的req都会被mask掉,只允许更高位的request 通过,去往上面的那个Masked Priority Arbiter。但是对于Weighted Round Robin,一次grant不足以立刻让这一路request被mask掉,而是要看这一路的counter值,如果counter值还没有减为0,那么就认为这一路依然有credit,mask值就和之前保持不变,下次仲裁的时候依然可以选择这一路grant。

那么什么时候调整mask值呢?就是当这一路被grant完之后,它的counter减到了0,所有的credit用完了,那么mask再调整,调整的做法和Round Robin一样,把第0路和第i路的req都mask掉,其余没有被mask掉的再继续这个过程。

那么你肯定会问,什么时候再重新把counter值load回初始weight值呢?在下面两种情况的时候:

所有的路都被mask掉了,即所有路都被依次轮过一遍了,这个时候我们需要再来一轮公平的仲裁,大家都各自载入自己的权重,再来一轮。
没有active req了,也就是所有的request都被许可了。
其实上面两种情况合并起来就是一种情况,即上面图中Masked ==0 (req全为0也对应Masked ==0)。

老李这里就不放代码了,相信大家有了Round Robin的设计和上面的算法,稍加改动就可以得到。

注意weighted round robin里面虽然有weight,但本质还是round robin,即轮询,要一个一个轮着来。有weight,但是并不代表weight高的这一路一定被许可的次数多,这是怎么回事呢?我们看下面这个例子:

有三个request[2:0],它们的weight 分别为1:1:2, req[0]在1和3周期有request
仲裁器设计(三)-- Weighted Round Robin 权重轮询调度
按照我们上面的仲裁算法,周期1, req[0]有request,grant给req[0],req[0]的weight counter从2减到1。当周期2的时候,req[0]因为没有request,而req[1]有request,那么grant给req[1],而且,注意这个周期req[1]的weight counter减为0,那么mask就要调整,会把req[0]和req[1]都给mask掉,即使req[0]的weight counter还没有减到0!这一点就是大家要注意的,weight round robin保证的是你有连续的request的时候,grant可以持续给你,但是一旦你有一个周期没有request,那么你就被跳过了,得再等一圈。

本篇图片来自rtlery.com。

上一篇:boost::maximum_weighted_matching用法的测试程序


下一篇:初试React脚手架