通过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 

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

此处提到的其他解决方案使用多个" - ".我只能劝阻他们,因为这会给你带来非常昂贵的操作.ESP.在一个热点中你可以很容易地获得超过32位,这在HW中是不容易实现的,因为借用必须通过所有位(某些fpgas上的死区进位逻辑使得它可以接近少量位).

Answer 2

我在 Altera 高级综合手册中找到了以下用于实现该任务的 Verilog 代码。

// 'base' is a one hot signal indicating the first request
// that should be considered for a grant.  Followed by higher
// indexed requests, then wrapping around.
//

module arbiter (
    req, grant, base
);

parameter WIDTH = 16;

input [WIDTH-1:0] req;
output [WIDTH-1:0] grant;
input [WIDTH-1:0] base;

wire [2*WIDTH-1:0] double_req = {req,req};
wire [2*WIDTH-1:0] double_grant = double_req & ~(double_req-base);
assign grant = double_grant[WIDTH-1:0] | double_grant[2*WIDTH-1:WIDTH];

endmodule

它使用减法（尽管只使用一次），因此从概念上讲，它与 Doug 的解决方案非常相似。