作者：李虹江
原文：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，并调整相应的算法。
对于每一路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
按照我们上面的仲裁算法，周期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。
推荐阅读
更多数字芯片设计类文章请关注数字芯片实验室。
