algorithm - 通过 bit twiddling 在循环调度中找到下一个

Question

考虑以下问题。您有一个位串，表示单热编码中的当前预定从站。例如，“00000100”(最左边的位是#7，最右边的位是#0)表示从机#2 已被调度。

现在，我想在循环调度方案中选择下一个预定的从站，但要稍作改动。我有一个“请求掩码”，它说明了哪些奴隶实际上想要被安排。下一个奴隶只会从那些想要的人中挑选出来。

一些示例(假设循环调度是通过向左旋转来完成的)。示例 1:

• 当前:“00000100”
• 掩码:“01100000”
• 下一个时间表:“00100000”- 在正常循环中，#3 和#4 应该在#2 之后，但他们没有请求，所以选择了#5。

例子2:

• 当前:“01000000”
• 掩码:“00001010”
• 下一个:“00000010” - 因为调度是通过向左循环完成的，#1 是该顺序中第一个请求的从站。

---

现在，这可以很容易地在循环中编码，我知道。但我实际上想通过一个没有循环的位操作来获得我的结果。动机:我想在 VHDL/Verilog 的硬件中(在 FPGA 中)实现它。

奖励是组成一个算法，该算法对任何数量的奴隶 N 都是通用的。

顺便说一下，这不是一道作业题。每当想要以某种方式调度从站并根据从站的请求来调节调度时，这都是一个重要的问题。我目前的解决方案有点“沉重”，我想知道我是否遗漏了一些明显的东西。

Answer 1

循环不一定是坏的。

我只会做

current[i] = current[i-1] & mask[i] |                         // normal shift logic
                mask[i] & current[i-2] & !mask[i-1] |         // here build logic 
                ...                                          // expression for 
                                                             // remaining 

然后将其放入生成循环(即它将展开到硬件中)，这将为表达式生成并行硬件。

此处提到的其他解决方案使用多个“-”。我只能劝阻他们，因为这会给你带来非常昂贵的操作。特别是一口气你可以轻松获得超过 32 位，这在 HW 中不容易实现，因为借位必须遍历所有位(某些 fpgas 上的死进位逻辑使其可以用于少量位)。