9

考虑以下问题。您有一个位串，它表示单热编码中的当前计划从站。例如，“00000100”（最左边的位为#7，最右边的位为#0）表示从#2 被调度。

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

一些示例（假设循环调度是通过向左旋转完成的）。示例 1：

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

示例 2：

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

现在，我知道，这可以很容易地在一个循环中编码。但我实际上想通过一个不循环的操作来得到我的结果。动机：我想在 VHDL/Verilog 中的硬件（在 FPGA 中）实现这一点。

一个额外的好处是组成一个对任意数量的奴隶 N 通用的算法。

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

4

9 回答 9

6

循环不一定是坏的。

我会简单地做

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 位，这在硬件中不容易实现，因为借用必须通过所有位（某些 fpgas 上的死去进位逻辑使其对于少量位来说是可接近的）。

于 2009-01-26T17:11:07.793 回答
4

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

于 2009-01-29T19:08:27.130 回答
3

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

电流和掩码之间的逻辑门链本质上创建了一个优先系统，该系统有利于链中“较低”的位。该链在末端是循环的，但当前位用于断开该链。

为了可视化操作，假设在当前字段中设置了第3位，并在图中向下跟随信号。第3位的逻辑 1 在第一个与门的输入处放置一个逻辑零，这保证了与门的输出也将为零（这是或门链中断的地方）。第一个与门输出处的零在第二个与门的输入处放置一个。这使得next的第 2位直接依赖于mask的第 2位。

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

如果设置了掩码的第2位，则直接位于其左侧的 OR 门的逻辑输出也将为 1，这将在电流的第2位下方的 AND 门的输入处放置逻辑 1 （将为零，因为一次只能设置一位电流）。顶部与门输出的逻辑 1 将逻辑零置于底部与门的输入端，因此将next的第1位设置为零。

如果未设置掩码的第 2位，则或门的两个输入都为零，因此电流第2位下方的与门的输出将为零，在底部与门的输入端放置一个 1，因此使next的第1位依赖于mask 的第1位。

这个逻辑遵循“向上”位的或门链，从左侧循环到右侧，确保下一个中只有一位可以设置为一位。由于该位被设置，循环一旦返回到current的第 3位，就会停止。这可以防止电路停留在永久循环中。

我没有使用 Verilog 或 VHDL 的经验，所以我将把实际代码留给你和 stackoverflow 的其余部分。

替代文字 http://img145.imageshack.us/img145/5125/bitshifterlogicdiagramkn7.jpg

笔记：

  1. 这个解决方案只是部分的。它仍然需要某种锁存机制来保存位字段。
  2. 请记住，随着位数的增加，栅极电压稳定所需的时间也会增加。
  3. 必须有一些逻辑来处理当前字段等于零的情况。请参阅此 stackoverflow 问题。
于 2009-01-28T04:26:54.043 回答
2

假设二进制补码表示，在 C 中调用你的两个单词maskand current：

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
于 2009-01-26T16:48:02.007 回答
2

减法 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

这将在内部使用一个循环......

于 2009-01-26T16:57:51.253 回答
2

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

鉴于您了解 VHDL，我不会详细介绍，但我的建议如下：

使用 3 位编码器将当前计划的任务变成一个数字：

01000000 --> 6

然后使用桶形移位器将遮罩旋转该数字 + 1（以跳过当前任务）：

00001010 --> 00010100

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

00010100 --> 00000100 --> 2

然后通过加法反转桶形移位：

(2+7) % 8 = 1

重新编码时将给出下一个计划任务：

00000010

应该非常快速和直接，尽管桶式移位器在房地产方面“昂贵”，但我目前看不到一个简单的方法来解决这个问题。

编辑：Doug 的解决方案要优雅得多……

-亚当

于 2009-01-26T16:59:01.203 回答
1

这应该做你想要的：

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

于 2009-01-28T21:39:58.107 回答
1

未经测试，但在我的脑海中，如果这没有产生合理的综合，我会感到惊讶......与典型的比特旋转黑客相比，它具有相对可读的优势（无论如何对我来说）。

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;
于 2013-09-27T18:42:47.740 回答
0

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

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

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

于 2015-11-24T00:49:56.070 回答