通过一点一点的玩弄来寻找循环调度中的下一个

循环不一定是坏的。

我就这么做

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

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

这里提到的其他解决方案使用多个“-”。我只能劝阻他们,因为这会给你带来非常昂贵的手术。尤其是在一个热门话题中,你可以轻松获得超过>32位,这在硬件中不容易实现,因为借用必须遍历所有位(某些FPGA上的空进位逻辑使其适用于少量位)。

我在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的解决方案非常相似。

以下解决方案适用于任意数量的从属设备(K),在FPGA中为O(n)。对于字段中的每个位,您将需要三个逻辑门和两个反相器。我用一个基本的逻辑模拟器测试了这个概念,它奏效了。

逻辑门之间的链条 当前的 和 面具 本质上创建了一个优先级系统,该系统有利于链中“较低”的位。这条链子的末端是环状的,但 当前的 钻头被用来打破链条。

要可视化操作,请想象一下 3. 设置在 当前的 字段,并在图中向下跟随信号。位上的逻辑 3. 在第一个AND门的输入端放置一个逻辑零,这保证了该AND门的输出也将为零(这是OR门链断裂的地方)。第一AND门输出端的零将第二AND门的输入端置为一。这使得bit 2. 属于的 下一个 直接依赖于bit 2. 属于的 面具 .

现在,OR门链开始发挥作用。

如果bit 2. 属于的 面具 如果已设置,则直接位于其左侧的OR门的逻辑输出也将是1,这将在位以下的AND门输入处放置一个逻辑1 2. 属于的 当前的 (这将是零,因为只有一个比特 当前的 可以一次设置)。顶部AND门输出端的逻辑1在底部AND门输入端放置逻辑0,从而设置位 1. 属于的 下一个 等于零。

如果bit 2. 属于的 面具 如果未设置,OR门的两个输入都将为零,因此AND门的输出低于位 2. 属于的 当前的 将为零,在底部AND门的输入端放置一个1,从而使位 1. 属于的 下一个 取决于bit 1. 属于的 面具 .

该逻辑遵循OR门链“向上”比特,从左侧循环到右侧,确保只有一个比特 下一个 可以设置为1。循环一旦回到位就停止了 3. 属于的 当前的 ,作为设置该位的结果。这可以防止电路处于永久循环中。

我没有Verilog或VHDL的经验,所以我会把实际的代码留给你 and the rest of stackoverflow .

alt text http://img145.imageshack.us/img145/5125/bitshifterlogicdiagramkn7.jpg

笔记:

1. 这个解决方案只是部分的。它仍然需要某种锁存机制来保存位字段。
2. 请记住,随着比特数的增加,栅极电压稳定所需的时间也会增加。
3. 必须有一些逻辑来处理这种情况 当前的 字段等于零。看见 this stackoverflow question .

有趣的问题!我不禁想知道,你是否不能简化你的调度程序操作,所以这种操作是必要的。

鉴于你知道VHDL,我不会详细介绍,但我的建议如下:

使用3位编码器将当前计划的任务转换为数字:

01000000-->6.

然后使用桶形移位器将掩码旋转该数字+1(跳过当前任务):

00001010-->00010100

然后使用优先级编码器找到第一个可用的“下一个”任务:

00010100-->;00000100->2.

然后通过添加来反转枪管移位:

(2+7) % 8 = 1

重新编码后,将给出下一个计划任务:

00000010

应该非常快速和简单,尽管就房地产而言,桶转换器是“昂贵的”,但我目前看不到一个简单的方法来解决这个问题。

编辑:Doug的解决方案要优雅得多。..

-亚当

第1小节是这里的基本思想。它用于级联借用比特以找到下一个任务。

bits_before_current = ~(current-1) & ~current
bits_after_current = current-1
todo = (mask & bits_before_current) 
if todo==0: todo = (mask & bits_after_current) // second part is if we have to wrap around
next = last_bit_of_todo = todo & -todo

不过,这将在内部使用循环。..

假设two是补码表示法,称你的两个单词为 mask 和 current ,在C中:

mask_lo = (current << 1) - 1; // the bits to the right and including current
mask_hi = ~mask_lo;           // the bits to the left of current
                              // the left bits, otherwise right:
next = (mask & mask_hi) ? (mask & mask_hi) : (mask & mask_lo);
return (next & -next);        // the least significant bit set

这应该符合您的要求:

number_of_tasks= <number of tasks, in the example this is 8>
next_mask= current | (current - 1);
next_barrel= next | (next << number_of_tasks);
next_barrel&= ~number_of_tasks;
next_barrel&= -next_barrel;
next_barrel|= next_barrel >> number_of_tasks;
next_task_mask= next_barrel & -next_barrel;

基本上,复制下一个任务掩码的比特,屏蔽掉我们不想考虑的比特,找到最低的集合比特,将高位折叠回去,然后取最低的比特集。这是在恒定时间内运行的。

编辑:更新以考虑当前==00010000和next_mask==00111000

未经测试,但在我脑海中,如果这没有产生合理的合成,我会感到惊讶。..它的优点是相对可读(无论如何对我来说),不像典型的比特游戏。

for i in current'range loop
  current := rotate_left(current, 1);
  if or_reduce(mask and current) = '1' then
     current:= mask and current;
  end if;
end loop;

完整的可参数化仲裁器实现,可以配置为循环或优先级仲裁:

https://github.com/alexforencich/verilog-axis/blob/master/rtl/arbiter.v

该设计使用一对优先级编码器来选择序列中的下一个输出。所使用的优先级编码器被有效地实现为树。