Der Suche nach dem nächsten im round-robin-scheduling von bit twiddling

Betrachten Sie das folgende problem. Haben Sie ein bit-string für den aktuellen geplanten slave in-one-hot-Codierung. Zum Beispiel, "00000100" (mit die am weitesten Links stehende bit #7 und am weitesten rechts liegenden #0) bedeutet, dass der slave #2 ist geplant.

Nun, ich möchte, um die nächste geplante slave in einem round-robin-scheduling-Schema, mit einem twist. Ich habe eine "Anfrage-Maske", die sagt, die Sklaven eigentlich wollen geplant werden. Der nächste slave wird wieder nur von denen, die wollen.

Einige Beispiele (angenommen, round-robin-scheduling erfolgt durch drehen nach Links).
Beispiel1:

  • Aktuell: "00000100"
  • Maske: "01100000"
  • Nächsten Termine: "00100000" - in der normalen round-robin -, #3 und #4 kommen sollte, nach #2, aber Sie nicht verlangen, also #5 ist ausgewählt.

Beispiel2:

  • Aktuell: "01000000"
  • Maske: "00001010"
  • Weiter: "00000010" - weil Planung ist mit dem Rad Links, und #1 ist die erste anfordernde slave-in dieser Reihenfolge.

Nun, dies kann leicht codiert in einer Schleife, die ich kenne. Aber eigentlich möchte ich, um mein Ergebnis mit einer bit-twiddling-Betrieb, ohne Schleifen. Die motivation: ich möchte, um dies zu implementieren in hardware (FPGA) in VHDL/Verilog.

Einen bonus ist ein Algorithmus, der den generische für jede Menge Sklaven N.

Übrigens, dies ist keine Hausaufgaben Frage. Es ist ein wichtiges problem ist, Wann immer man will, zu planen Sklaven in irgendeiner Art und Zustand der Planung von den Sklaven fordert. Meine aktuelle Lösung ist etwas "schwer" und ich wollte wissen, ob ich etwas fehlt offensichtlich.

InformationsquelleAutor Eli Bendersky | 2009-01-26
  1. 6

    Einer Schleife muss nicht schlecht sein.

    Ich würde einfach das 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 legen Sie Sie in einer Schleife generieren (dh es wird aufgerollt in hardware), die produzieren parallel-hardware für die Ausdrücke.

    Anderen hier erwähnten Lösungen verwenden mehrere "-". Ich kann nur raten Sie Ihnen, wie diese erhalten Sie eine wirklich teure operation. Esp. in einem heißen, Sie kann leicht mehr als > 32 bits, die nicht so leicht umsetzbar sind, in HW, wie das ausleihen über alle bits (die deadicated carry-Logik auf bestimmte fpgas machen es zugänglich für die kleine Anzahl von bits).

    • Vereinbart, mein bit-twiddling-Lösung ist weniger effizient in der hardware.
    • können Sie etwas näher über den Algorithmus, es ist nicht offensichtlich! was ist "ich"? generieren Schleife durch das, was durch "ich", d.h. pro bit von den "aktuellen" ?
    InformationsquelleAutor flolo
  2. 4

    Habe ich Folgendes gefunden Verilog-code für die Umsetzung der Aufgabe in die Altera erweiterte Synthese Kochbuch. 

    // '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 nutzt die Subtraktion (nur einmal, obwohl), so konzeptionell ist es ganz ähnlich wie Doug die Lösung.

    InformationsquelleAutor Eli Bendersky
  3. 3

    Folgende Lösung funktioniert für eine beliebige Anzahl von slaves (K), und ist O(n), die in Ihrem FPGA. Für jedes bit in dem Feld, Sie benötigen drei Logik-Gatter und zwei invertern. Getestet habe ich das Konzept mit einem Logik-simulator, und es funktioniert.

    Die Kette von Logik-Gattern, die zwischen aktuell und die Maske im wesentlichen erstellt eine Priorität system, das begünstigt bits "unten" in der Kette. Diese Kette geschlungen ist, an den enden, aber der aktuell bits verwendet werden, die Kette zu durchbrechen.

    Visualisierung der Bedienung, stellen Sie sich vor, dass etwas 3 liegt in der aktuell - Feld, und Folgen Sie den signal nach unten im Diagramm. Die logische eins an der bit - 3 Orte einer logischen null am Eingang des ersten UND-Gatter, das garantiert, dass der Ausgang dieses UND-Gatter wird auch null sein (dies ist, wo der ODER-gate-Kette ist gebrochen). Die null am Ausgang des ersten UND-Gatter stellen Sie ein ein an den Eingang der zweiten UND-Gatter. Das macht bit - 2 von weiter direkt abhängig von bit 2 von die Maske.

    Nun, die Kette der ODER-Gatter ins Spiel kommt.

    Wenn bit 2 von die Maske gesetzt wurde, wird der logische Ausgang von dem ODER-Tor direkt auf der linken Seite ist es auch eine, die eine logische eins am Eingang zu dem UND-Gatter unten etwas 2 von aktuell (der gleich null sein wird, da nur ein bit in aktuell können gleichzeitig eingestellt werden). Die logische eins am Ausgang des top-gate UND stellen eine logische null am Eingang des unteren UND-Gatter, damit Sie bit 1 von weiter gleich null.

    Wenn bit 2 von die Maske wurde nicht gesetzt ist, sind beide Eingänge zu dem ODER-Tor auf null, so dass der Ausgang der UND-Gatter unten etwas 2 von aktuell wäre eine null, wodurch man am Eingang zum unteren AND-Gatter, und so etwas 1 von weiter, abhängig von bit 1 von die Maske.

    Dieser Logik folgt die Kette der ODER-Gatter "bis" die bits, die Umschlingung von der linken Seite wieder zur rechten Seite, zu gewährleisten, dass nur ein bit in weiter kann man. Die Schleife wird beendet, sobald es seinen Weg zurück zu bit - 3 von aktuell, als Ergebnis, dass das bit gesetzt. Dies verhindert, dass die Schaltung von einem Aufenthalt in einer ewigen Schleife.

    Habe ich keine Erfahrung mit Verilog oder VHDL, also lasse ich den eigentlichen code, bis Sie und der rest von stackoverflow.

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

    Hinweise:

    1. Diese Lösung ist nur teilweise. Es werden immer noch erfordern eine Art von Verriegelungsmechanismus zum halten der bit-Felder.
    2. Beachten Sie, dass so erhöhen Sie die Anzahl der bits, die erforderliche Zeit für die gate-Spannung zu Regeln, wird ebenfalls zunehmen.
    3. Gibt es auch einige Logik für den Umgang mit dem Fall, wo die aktuell - Feld ist gleich null. Sehen diese stackoverflow-Frage.
    • große Lösung. aber ich sehe immer noch eine kombinatorische Schleife hier
    • obwohl es geschieht nur, wenn Strom alle 0s (sonst ist es blockiert, indem Sie einige UND), ich bin nicht sicher, wie der synthesizer wird es dauern.
    • Ja, da muss noch ein check für Strom == 0. Pax schlägt eine gute Lösung in der stackoverflow.com/questions/486473/...
    • In falls Sie es verpasst, Marty gepostet verilog-code für diese Logik in stackoverflow.com/questions/486471/...
    InformationsquelleAutor e.James
  4. 2

    Interessantes problem! Ich kann mir nicht helfen, aber Frage mich, wenn Sie können nicht vereinfachen Sie Ihre scheduler-Betrieb, so dass diese Art der operation notwendig wäre.

    Gegeben, dass Sie wissen, VHDL, ich werde nicht ins detail gehen, aber mein Vorschlag wäre der folgende:

    Verwenden Sie ein 3-bit-encoder drehen Sie den derzeit geplanten task in eine Reihe:

    01000000 --> 6

    Dann mit einem barrel-shifter zum drehen der Maske durch die Anzahl + 1 (zum überspringen der aktuellen Aufgabe):

    00001010 --> 00010100

    Dann verwenden Sie einen priority-encoder zu finden, der erste verfügbare "weiter" Aufgabe:

    00010100 --> 00000100 --> 2

    Dann rückwärts den Lauf-Verschiebung durch den Zusatz:

    (2+7) % 8 = 1

    Welche, wenn Sie re-codiert werden, geben die nächsten geplanten Aufgabe:

    00000010

    Sollte sehr schnell und einfach, obwohl der barrel-shifter ist "teuer" in Bezug auf realestate, aber ich sehe nicht einen einfachen Weg, das zu umgehen, im moment.

    Edit: Doug die Lösung ist deutlich eleganter...

    -Adam

    • dies ist sehr nahe an dem, was ich im Sinn hatte. Aber abgesehen von der barrel-shifter, der priority-encoder ist auch ganz schön teuer, nicht wahr?
    • Eine priority-encoder ist nicht Billig, aber es ist kleiner als ein barrel-shifter. Noch immer werden die Lösungen vorgestellt, die in anderen Antworten sollten die Ausbeute eines insgesamt kleineren Lösung, obwohl die ideale VHDL-compiler der karnaugh-map-Analyse und minimieren Sie jede Lösung auf die gleichen kleinen Gleichung...
    InformationsquelleAutor Adam Davis
  5. 2

    Wieder entfernen 1 ist die grundlegende Idee hier. Es wird benutzt, um cascade 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 eine Schleife verwenden, die intern aber...

    InformationsquelleAutor Jules
  6. 2

    Vorausgesetzt, zweier-Komplement-Darstellung ist, rufen Sie Ihre zwei Worte mask und current im 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
    • Downvoted, da der Algorithmus nicht funktioniert. Es wird wieder die niedrigste bit-set Maske, die nicht auch in aktuellen. Beispiel: Maske = 01100001, current = 00000100, wird es wieder 00000001
    • eJames, sind Sie sich da sicher? Ich denke, es wird zurück 00100000.
    • Ist der | | - operator garantiert halt nach (Maske & mask_hi) wenn Sie, dass der Betrieb stellt sich heraus, dass nicht-null?
    • Wie geschrieben, weiter verwendet || die bewertet, zu 0 oder 1 in C, so ist das Ergebnis entweder 0 oder 1. verwenden Sie next = (Maske & mask_hi) ? (Maske & mask_hi) : (Maske & mask_lo);
    • Ja, das würde es tun. Auch die zweite Zeile muss sein << 1 << 2
    • eJames - Sie haben einen Punkt hier. Wenn || wird verwendet in seinen C Kurzschluss Weise, Doug Recht. aber wenn es in die "hardware" interpretation, Sie habe ein Gegenbeispiel.
    • In aller fairness, die Idee für den Algorithmus ist der Klang. Ich werde Bearbeiten Sie die änderungen, und ersetzen Sie meine downvote mit einem upvote.
    • obwohl, ich denke in hardware kann man sich ganz einfach implementieren, short-circuiting "oder" wie gut
    • Ich habe die änderungen gemacht und Umgekehrt meine Stimme. Getestet habe ich die neue version mit gcc3.4.5 und es funktioniert wie ein Charme.
    • Ich habe auch eine Logik/hardware-Lösung: stackoverflow.com/questions/480405/...

    InformationsquelleAutor Doug Currie
  7. 1

    Sollte dies 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 Sie die bits für die nächste Aufgabe, die Maske, maskieren der bits, die wir nicht berücksichtigen möchten, finden Sie die niedrigste gesetzte bit, Falten Sie die high-bits zurück, dann nehmen Sie das niedrigste bit gesetzt. Diese läuft in konstanter Zeit.

    Edit: Update zu berücksichtigen current == 00010000 und next_mask == 00111000

    InformationsquelleAutor MSN
  8. 1

    Ungetestet, aber aus der Spitze von meinem Kopf, ich würde mich Wundern, wenn diese nicht produzieren ma vernünftige Synthese... Hat den Vorteil, dass Sie relativ gut lesbar (für mich jedenfalls) im Gegensatz zu den typischen 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;
    InformationsquelleAutor Martin Thompson
  9. 0

    Komplette parametrizable Schiedsrichter-Implementierung konfiguriert werden können für das round-robin oder Priorität der Schiedsverfahren:

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

    Dieses design verwendet ein paar von priority-Encoder zur Auswahl der nächsten Ausgabe in der Reihenfolge. Der priority Encoder verwendet werden effizient umgesetzt, wie Bäume.

    InformationsquelleAutor alex.forencich
Schreibe einen Kommentar