Das Finden der nächsten in Round Robin von Bit twiddling

Question

Sie sich das folgende Problem. Sie haben eine Bit-Kette, die den aktuellen geplanten Slave-in One-Hot-Codierung darstellt. Zum Beispiel: "00000100" (mit dem am weitesten links stehende Bit # 7 und # rechtesten ist 0) bedeutet, dass Slave # 2 geplant ist.

Nun, ich mag den nächsten geplanten Slave in einem Round-Robin-Scheduling-Schema holen, mit einem Twist. Ich habe eine „Anforderungsmaske“, die sagt, welche Slaves tatsächlich geplant werden soll. Der nächste Slave nur von denen, werden bei Ihnen abgeholt, die wollen.

Einige Beispiele (unter der Annahme Round Robin wird durch Drehen links durchgeführt). Beispiel 1:

• Aktuell: "00000100"
• Maske: "01100000"
• Nächster Zeitplan:. "00100000" - in normal Round-Robin, # 3 und dann 4 # nach # 2 kommen sollte, aber sie nicht verlangen, so # 5 gerichtet

Beispiel 2:

• Aktuell: "01000000"
• Maske: "00001010"
• Next:. "00000010" - denn Terminierung durch zyklische links durchgeführt wird, und # 1 ist der erste anfordernden Slave in dieser Reihenfolge

---

Nun, kann dies leicht in einer Schleife codiert werden, ich weiß. Aber ich will eigentlich mein Ergebnis durch einen Bit-twiddling Betrieb bekommen, ohne Schleifen. Die Motivation. Ich möchte dies in Hardware implementieren (in einem FPGA) in VHDL / Verilog

Ein Bonus ist, um einen Algorithmus zu bilden, die für jede Menge Sklaven N generic ist.

By the way, ist dies keine Hausaufgaben Frage. Es ist ein wichtiges Problem, wenn man will Sklaven in irgendeiner Art und Weise planen, und von den Slaves Anfragen der Terminierung konditioniert. Meine aktuelle Lösung ist etwas „schwer“ und ich wollte wissen, ob ich etwas offensichtlich fehlt bin.

Answer 1

Ich habe den folgenden Verilog-Code für die Implementierung der Aufgabe in der Altera erweiterte Synthese Kochbuch gefunden.

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

Es verwendet Subtraktion (nur einmal, obwohl), so ist es vom Konzept her sehr ähnlich Dougs Lösung.

Answer 2

Eine Schleife muss nicht schlecht sein.

Ich würde einfach tun

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

Und dann legt sie in eine Schleife erzeugen (dh es wird in der Hardware ausgerollt werden), die parallel Hardware für die Ausdrücke erzeugen wird.

Andere hier genannte Lösungen verwenden, um mehr „-“. Ich kann sie nur entmutigen, da dies wird Ihnen eine wirklich teure Operation erhalten. Esp. in einer heißen können Sie leicht mehr als> 32 Bit erhalten, die in HW nicht leicht implementierbar sein wird, da die borrow durch alle Bits (die deadicated Tragslogik auf bestimmten FPGAs es für kleine Anzahl von Bits zugänglich machen) zu gehen.

Answer 3

Die folgende Lösung funktioniert für eine beliebige Anzahl von Slaves (K) und O (n) in Ihrem FPGA. Für jedes Bit in dem Gebiet, werden Sie drei Logikgatter und zwei Wechselrichter benötigen. Ich testete das Konzept mit einem grundlegenden Logik-Simulator, und es funktioniert.

Die Kette von logischen Gattern zwischen Strom und Maske schafft im wesentlichen ein Prioritätssystem, das Bits „unten“ in der Kette begünstigt. Diese Kette wird an den Enden geschlungen, aber die Strom Bits werden verwendet, um die Kette zu brechen.

Um den Betrieb zu visualisieren vorstellen, dass Bit 3 in dem Strom Feld folgen und dem Signal nach unten in dem Diagramm eingestellt. Die logische Eins bei Bit 3 legt eine logische Null am Eingang des ersten UND-Gatter, das gewährleistet, dass der Ausgang dieser UND-Gatter wird auch Null sein (dies ist in dem die ODER-Gatter-Kette unterbrochen ist ). Die Null am Ausgang des ersten UND-Gatters legt eine am Eingang mit dem zweiten UND-Gatter. Dies macht Bit 2 von neben direkt abhängig von Bit 2 von Maske .

Jetzt kommt die Kette des ODER-Gatters ins Spiel.

Wenn das Bit 2 von Maske gesetzt wurde, wird der logische Ausgang des ODER-Gatters direkt links von ihm wird auch eine sein, die eine logische Eins setzen werden an dem Eingang zu dem UND-Gatter unterhalb Bit 2 der Strom (die nur ein Bit wird in Null, da Strom bei einem eingestellt werden Zeit). Die logische Eins am Ausgang des oberen UND-Gatters legt eine logische Null am Eingang des unteren UND-Gatters, wodurch Bit Einstellung 1 der Weiter gleich Null ist.

Wenn das Bit 2 von Maske wurde nicht gesetzt ist, beide Eingänge zu dem ODER-Gatter würde Null sein, so wird der Ausgang des UND-Gatters unter Bit 2 die Strom wäre eine Null sein, eine eins an dem Eingang zu dem Boden und Gate platzieren und daher macht Bit 1 die weiter abhängig von Bit 1 von Maske .

Diese Logik folgt der Kette von ODER-Gattern „oben“ die Bits, Umschlingung von der linken Seite zurück zu der rechten Seite, um sicherzustellen, dass nur ein Bit in Weiter kann auf eins gesetzt werden. Die Schleife stoppt, sobald er seinen Weg macht zu wenig zurück 3 von Strom , als Folge dieses Bit gesetzt wird. Dies verhindert, dass die Schaltung von einem ewigen Schleife zu bleiben.

Ich habe keine Erfahrung mit Verilog oder VHDL, also werde ich den eigentlichen Code up verlassen Sie a href <= "https://stackoverflow.com/questions/486471/how-would-you-implement-this- Digital-Logik-in-Verilog-oder-vhdl "> und der Rest von Stackoverflow .

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

Hinweise:

1. Diese Lösung ist nur teilweise. Es wird noch eine Art erfordern Verriegelungsmechanismus der Bitfelder zu halten.
2. Denken Sie daran, dass, wie Sie die Anzahl der Bits zu erhöhen, die Zeit für die Gate-Spannungen erforderlich wird auch absetzen erhöhen.
3. Es muss eine gewisse Logik vorhanden sein, um den Fall zu behandeln, in denen die Strom Feld gleich Null ist. Siehe diese Frage Stackoverflow .

Answer 4

Interessantes Problem! Ich kann mir nicht helfen, aber frage mich, wenn Sie nicht Ihre Scheduler Betrieb vereinfachen können so diese Art der Operation erforderlich wäre.

Da Sie VHDL wissen, werde ich nicht ins Detail gehen, aber mein Vorschlag wäre, die folgende:

Verwenden Sie ein 3-Bit-Encoder die aktuell geplante Aufgabe in eine Reihe zu machen:

01000000 -> 6

Dann einen Barrel-Shifter verwenden, um die Maske durch die Zahl + 1 (überspringt die aktuelle Aufgabe) zu drehen:

00001010 -> 00010100

Dann einen Prioritätscodierer verwenden, um die erste verfügbare „next“ Aufgabe zu finden:

00010100 -> 00000100 -> 2

Dann kehren die Barrel-Shift durch Zusatz:

(2 + 7)% 8 = 1

Welche wenn umcodiert wird die nächste geplante Aufgabe geben:

00000010

Wenn sehr schnell und unkompliziert sein, obwohl der Barrel-Shifter ‚teuer‘ in Bezug auf Realestate ist, aber ich weiß nicht eine einfache Möglichkeit sieht um, dass im Moment zu bekommen.

Edit: Doug Lösung ist wesentlich elegantere ...

-Adam

Answer 5

Subracting 1 ist die wesentliche Idee hier. Es wird verwendet, um Kaskade leiht sich durch die Bits die nächste Aufgabe zu finden.

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

Dies wird intern eine Schleife verwenden, obwohl ...

Answer 6

Unter der Annahme, Zweier-Komplement-Darstellung, rufen Sie Ihre zwei Worte mask und current, in 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

Answer 7

Dies sollte das tun, was Sie wollen:

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;

Grundsätzlich duplizieren die Bits der nächsten Task-Maske, die Bits maskieren wir den niedrigsten Satz Bit nicht berücksichtigen wollen, finden, die hohen Bits zurück in falten, dann nehmen Sie die niedrigsten Bit gesetzt. Diese läuft in konstanter Zeit.

Edit: Aktualisierung zu berücksichtigen aktuelle == 00010000 und next_mask == 00111000

Answer 8

Nicht getestet, aber aus der Spitze von meinem Kopf, würde ich überrascht, wenn dies nicht ma vernünftige Synthese produziert ... hat den Vorteil, relativ lesbar ist (für mich jedenfalls) im Gegensatz zu typischem Bit-twiddling Hacks.

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;

Answer 9

Komplette parametrisierbare Schiedsrichter-Implementierung, die für Round-Robin oder Prioritätsarbitrierungsschema konfiguriert werden kann:

https://github.com/alexforencich/verilog- Achse / Blob / Master / rtl / arbiter.v

Dieser Entwurf benutzt ein Paar Prioritätscodierer die nächste Ausgabe in der Reihenfolge zu wählen. Die Prioritätscodierer verwendet werden effizient wie Bäume umgesetzt.