Betrachten Sie das folgende Problem. Sie haben eine Bit-Zeichenfolge, die den aktuellen geplanten Slave in One-Hot-Codierung darstellt. Zum Beispiel bedeutet "00000100" (wobei das am weitesten links liegende Bit # 7 und ganz rechts # 0 ist), dass der Slave # 2 geplant ist.
Nun möchte ich den nächsten geplanten Slave in einem Round-Robin-Scheduling-Schema auswählen, mit einer Wendung. Ich habe eine "Anfrage-Maske", die besagt, welche Slaves tatsächlich geplant werden sollen. Der nächste Slave wird nur von denen ausgewählt, die wollen.
Einige Beispiele (angenommen, die Round-Robin-Planung erfolgt durch Drehen nach links). Beispiel1:
Beispiel2:
Nun, das kann leicht in einer Schleife codiert werden, ich weiß. Aber ich möchte mein Ergebnis tatsächlich durch eine Bit-Twiddling-Operation ohne Schleifen erreichen. Die Motivation: Ich möchte dies in Hardware (in einem FPGA) in VHDL / Verilog implementieren.
Ein Bonus besteht darin, einen Algorithmus zu erstellen, der für eine beliebige Anzahl von Slaves N generisch ist.
Übrigens, das ist keine Hausaufgabenfrage. Es ist ein wichtiges Problem, wenn man Slaves in irgendeiner Weise planen und die Planung durch die Anforderungen der Slaves konditionieren will. Meine aktuelle Lösung ist etwas "schwer" und ich wollte wissen, ob mir etwas offensichtlich fehlt.
Ich habe den folgenden Verilog-Code zur Implementierung der Aufgabe im Altera-Synthesekochbuch gefunden.
%Vor%Es verwendet Subtraktion (nur einmal), so konzeptionell ist es Dougs Lösung ziemlich ähnlich.
Eine Schleife muss nicht schlecht sein.
Ich würde es einfach tun
%Vor%Und dann lege es in eine generierte Schleife (dh es wird in Hardware gerollt), was parallele Hardware für die Ausdrücke erzeugt.
Andere hier erwähnte Lösungen verwenden mehrere "-". Ich kann sie nur entmutigen, weil Sie dadurch eine wirklich teure Operation bekommen. Esp. in einem heißen können Sie leicht mehr als & gt; 32 Bits, die in HW nicht einfach implementierbar sind, da der Kredit alle Bits durchlaufen muss (die festgelegte Übertragslogik bei bestimmten fpgas macht sie für eine kleine Anzahl von Bits zugänglich).
Die folgende Lösung funktioniert für eine beliebige Anzahl von Slaves (K) und ist O (n) in Ihrem FPGA. Für jedes Bit im Feld benötigen Sie drei Logikgatter und zwei Inverter. Ich habe das Konzept mit einem einfachen Logiksimulator getestet und es funktioniert.
Die Kette von Logikgattern zwischen Strom und Maske erzeugt im Wesentlichen ein Prioritätssystem, das Bits "weiter unten" in der Kette bevorzugt. Diese Kette ist an den Enden geschleift, aber die Strom Bits werden verwendet, um die Kette zu unterbrechen.
Um die Operation zu visualisieren, stellen Sie sich vor, dass das Bit 3 im Feld current gesetzt ist und folgen Sie dem Signal im Diagramm nach unten. Die logische Eins bei Bit 3 platziert eine logische Null am Eingang des ersten UND-Gatters, was garantiert, dass der Ausgang dieses UND-Gatters ebenfalls Null ist (hier wird die ODER-Gatter-Kette unterbrochen) ). Die Nullstelle am Ausgang des ersten UND-Gatters platziert eine Eins am Eingang des zweiten UND-Gatters. Dies macht das Bit <2> von nächst direkt abhängig von dem Bit <2> der Maske . . .
Jetzt kommt die Kette von ODER-Gattern ins Spiel.
Wenn Bit 2 von mask gesetzt wurde, ist die logische Ausgabe des OR-Gatters direkt links davon ebenfalls eine Eins, die eine logische Eins plaziert an dem Eingang des UND-Gatters unterhalb von Bit <2> von Strom <(was Null ist, da nur ein Bit in Strom gesetzt werden kann bei a Zeit). Die logische Eins am Ausgang des oberen UND-Gatters platziert eine logische Null am Eingang des unteren UND-Gatters, wodurch das Bit 1
Wenn Bit 2 von Maske nicht gesetzt war, wären beide Eingänge des ODER-Gatters Null, also der Ausgang des UND-Gatters unter Bit 2 von current wäre eine Null, wobei eine Eins an den Eingang des unteren UND-Gatters gelegt wird und daher das Bit 1
Diese Logik folgt der Kette von OR-Gattern die Bits nach oben, wobei sie von der linken Seite zurück nach rechts umlaufen, um sicherzustellen, dass nur ein Bit in nächsten auf eine Eins gesetzt werden kann. Die Schleife stoppt, sobald sie zu Bit 3 von current zurückkehrt, da dieses Bit gesetzt ist. Dies verhindert, dass die Schaltung in einer Dauerschleife bleibt.
Ich habe keine Erfahrung mit Verilog oder VHDL, also überlasse ich Ihnen den eigentlichen Code und der Rest von stackoverflow .
Alternativtext http://img145.imageshack.us/img145/5125/bitshifterlogicdiagramkn7.jpg
Notizen:
Interessantes Problem! Ich kann nicht helfen, aber frage mich, ob Sie Ihre Scheduler-Operation nicht vereinfachen können, so dass diese Art von Operation notwendig wäre.
Da Sie VHDL kennen, werde ich nicht ins Detail gehen, aber mein Vorschlag wäre folgender:
Verwenden Sie einen 3-Bit-Encoder, um die aktuell geplante Aufgabe in eine Zahl umzuwandeln:
01000000 - & gt; 6
Verwenden Sie dann einen Barrel Shifter, um die Maske um diese Zahl + 1 zu drehen (um die aktuelle Aufgabe zu überspringen):
00001010 - & gt; 00010100
Verwenden Sie dann einen Prioritätscodierer, um die erste verfügbare "nächste" Aufgabe zu finden:
00010100 - & gt; 00000100 - & gt; 2
Dann kehren Sie den Barrel Shift um:
(2 + 7)% 8 = 1
Was beim erneuten Codieren die nächste geplante Aufgabe ergibt:
00000010
Sollte sehr schnell und geradlinig sein, obwohl der Barrel Shifter im Hinblick auf den Realzustand "teuer" ist, aber ich sehe im Moment keinen einfachen Weg, das zu umgehen.
Edit: Dougs Lösung ist deutlich eleganter ...
-Adam
Wenn Sie zwei Komplement-Repräsentationen annehmen, rufen Sie Ihre beiden Wörter mask und current in C:
Dies sollte tun, was Sie wollen:
%Vor%Im Grunde genommen duplizieren Sie die Bits der nächsten Task-Maske, maskieren Sie die Bits, die wir nicht betrachten wollen, finden Sie das niedrigste gesetzte Bit, falten Sie die hohen Bits zurück und nehmen Sie dann das niedrigste Bit-Set. Dies läuft in konstanter Zeit.
Bearbeiten: Aktualisierung zur Berücksichtigung von current == 00010000 und next_mask == 00111000
Ungetestet, aber von der Spitze meines Kopfes würde ich überrascht sein, wenn dies keine vernünftige Synthese hervorbringen würde ... Hat den Vorteil, dass es (im Gegensatz zu typischen Bit-Twiddling-Hacks) für mich relativ gut lesbar ist / p> %Vor%
Komplette parametrisierbare Arbiter-Implementierung, die für Round-Robin oder Priority Arbitration konfiguriert werden kann:
Dieser Entwurf verwendet ein Paar von Prioritätscodierern, um den nächsten Ausgang in der Sequenz auszuwählen. Die verwendeten Prioritätscodierer sind effizient als Bäume implementiert.
Tags und Links algorithm bit-manipulation verilog vhdl
