✎ 编 者 按
该小系列就SpinalHDL中关于StreamArbiter部分从基础原理到最终的实现细节进行总结。本篇先从roundRobin讲起。
》最低优先级调度
SpinalHDL中关于roundRobin的实现背后原理其实一开始困惑挺久，后来方慢慢理解。在讲解roundRobin之前，先来看看lowerFirst讲起。
假定N个端口，编号为0～N-1。在采用最低优先级调度时，当有任务到来时，优先取最低端口的任务调度。
如果将每个端口是否有任务用一个bit表示，那么最低优先级调度其实也就是寻求这个N bit数据的为1的最低bit位。而在之前的文章里，如何寻找一个二进制数据中为1的最低bit位的方式已经说明，这里不再阐述：
oneHotCode=symbol& ~(symbol-1)
》roundRobin
在对最低优先级调度有了一定的了解后，再来考虑roundRobin。对于roundRobin调度的目的。其无非是每个端口均能够“雨露均沾”的获取端口访问。在SpinalHDL中，该部分的核心代码为：
老实讲，这段代码的实现机制当初让我费解了很久。理解起来或许没有那么直接。那我们不妨换种思路～
相较于最低优先级调度，而roundRobin则是一个最低优先级处于变化的一个调度。以N=4为例:
在初始状态时，bit0位置优先级最低。我们假定四个req均有任务，那么所谓的roundRobin调度算法可以采用最低优先级调度，只不过最低优先级所对应的bit是不断变化的，而非一直固定在bit0处。
这里所采用的规则为：
- 从右向左优先级降低(环回)
- 每当一个任务所处的req被消耗，那么其优先级则将为最低。其左侧第一个位置的优先级变为最高(若已达到最左侧，则环回)
- 而每次优先级最高的位置我们可以用一个oneHot来进行表示，那么其在上面的表格中分别为:
在基于此的基础上，我们再来理解上面代码中的运算方法。以N=8为例:
我们假定ohPority此时在bit3处为高电平:
这里的处理思路和前面的寻找最低bit为1的思路很相像，只不过,这里的最低bit变成了bit3。我们先来考虑假定在bit3～bit7处存在任务，假定在bit5处有任务:
那么此时减去ohPority所得到的结果为:
取反后再与原数据相“与”所得到的结果则为:
前后两部分相或即可得到对应下一次任务的位置信息。其实像上面的这种情况完全不需要进行拼接扩展位宽至16bit，而之所以进行位宽扩展拼接(环回)，则是为了应对ohPority中bit3～bti7均为0，而任务在bit0～bit2间。考虑当bit3～7均没有任务，此时仅有bit1～2有任务，即：
前后两半部分相或即为本次任务仲裁的位置。而当当前仲裁到的任务被消耗后，那么当前ret值循环右移1位即位新的ohPority。
roundRobin的设计理念其实基于最低优先级策略，只不过最低优先级不再是普通的一只bit0位置处为最高优先级，而是最高优先级bit位置变化的一种特殊“最低优先级”策略。
》weightRoundRobin
在RoundRobin的基础上，可以进一步改造设计成带权重的RoundRobin。
在RoundRobin里，每当一个通道的任务被调用后，其权重就会变为最低。而在weightRoundRobin里，我们需要为每个通道维护一个计数器，每当调度到该通道时减一。当调度到某个通道后，当计数器变为0时，那么其优先级才会降为最低。
而另外一个需要解决的问题是，何时将每个通道计数器的值降至最低。对于一个通道来讲，当仲裁通道由该通道切换到其他通道时，那么其优先级就会降至最低，以上面的RoundRobin为例，当ohPority由00000100变换为00001000时，那么req3下次只有在req0～req2及req4～req7上的任务均处理完成后才会再度仲裁到req3上。那么也就意味着当某个通道没有被仲裁时，其计数器便可以清零。
给出一个四通道的example：
而这种算法也存在一点缺陷，就是当每个通道都有任务时，其任务通道时间片较粗。以上面的四通道例子为例，任务调度顺序就是{1,2,2,3,3,3,4,4,4,4}。在负载均衡算法里的带权重调度有另外一种形式，这里给出参考链接：
https://blog.csdn.net/qq_32069155/article/details/96469907
☆ END ☆
作者：玉骐
原文链接：Spinal FPGA
微信公众号：
推荐阅读
更多SpinalHDL技术干货请关注[Spinal FPGA]欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。
