寻找下一个轮询调度按位操作 [英] Finding the next in round-robin scheduling by bit twiddling

问题描述

考虑以下问题。你有一个位字符串，再presents在一个热编码当前安排的奴隶。例如，00000100（与最左边的位是第7和最右边的＃0）表示从站2＃定。

Consider the following problem. You have a bit-string that represents the current scheduled slave in one-hot encoding. For example, "00000100" (with the leftmost bit being #7 and rightmost #0) means that slave #2 is scheduled.

现在，我要挑下一个计划从在循环调度方案，与一捻。我有一个请求屏蔽，这表示它的奴隶其实是想安排。接下来从机将只能从那些想挑。

Now, I want to pick the next scheduled slave in a round-robin scheduling scheme, with a twist. I have a "request mask" which says which slaves actually want to be scheduled. The next slave will be picked only from those that want to.

一些例子（假设轮转调度是通过旋转左边完成）。 例1：

Some examples (assume round-robin scheduling is done by rotating left). Example1:

• 在当前是00000100
• 面膜：01100000
• 下一步计划：00100000 - 在正常循环，＃3，然后＃4应该＃2后，但他们没有要求，所以＃5拾取

例2：

• 在当前是01000000
• 面膜：00001010
• 下一页：00000010 - 因为调度是通过骑自行车离开做的，和＃1的顺序的第一个请求的从属

---

现在，这可以很容易美元的循环C $ CD，我知道了。但其实我是想通过一个位变换操作让我的成绩，离不开循环。动机：我想在硬件中实现这个（在FPGA）的VHDL / Verilog的

Now, this can be easily coded in a loop, I know. But I actually want to get my result by a bit-twiddling operation, without loops. The motivation: I want to implement this in hardware (in an FPGA) in VHDL/Verilog.

一个好处是弥补了一个算法，它是通用的，只要金额奴隶N个。

A bonus is to make up an algorithm that's generic for any amount of slaves N.

顺便说一句，这不是一个家庭作业的问题。这是每当一个人想安排以某种方式从站，以及由所述从站的要求调节所述调度的一个重要问题。我目前的解决方案是有点重，我想知道如果我失去了一些东西明显。

By the way, this is not a homework question. It's an important problem whenever one wants to schedule slaves in some manner, and condition the scheduling by the slaves' requests. My current solution is somewhat "heavy" and I wanted to know if I'm missing something obvious.

推荐答案

我发现下面的Verilog code实现在Altera的高级合成菜谱任务。

I've found the following Verilog code for implementing the task in the Altera advanced synthesis cookbook.

// '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

它采用减法（只有一次，虽然），所以在概念上是非常相似道格的解决方案。

It uses subtraction (only once, though), so conceptually it's quite similar to Doug's solution.

这篇关于寻找下一个轮询调度按位操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！