Hallo Leute, ich habe in Verilog ein Register-Array mit 16 Bit Breite, die Anzahl der 16 Bit Register ist variabel. Ziel ist es mit reiner logik den Index des Registers zu finden, in dem der numerisch kleinste Wert steht. Also ich darf nicht "mehrere" Taktzyklen für so etwas benötigen. Später soll daraus eine Art dynmisch gewichtete Arbitrierung implementiert werden. Hat jemand eine Idee wie das mit reiner Logik funktioniert? Danke & Gruß
Markus schrieb: > ich habe in Verilog ein Register-Array mit 16 Bit Breite, > die Anzahl der 16 Bit Register ist variabel. Hmmmmmmm...... wie variabel? Muss das auf Hardware laufen? > Hat jemand eine Idee wie das mit reiner Logik funktioniert? Mit Vergleichern, Prioritätsencodern und Multipexern... Oder wie war die Frage gemeint? Das Blöde an "reiner Logik" ist, dass du parallelen Zugriff auf all diese Register brauchst und daher kein RAM verwenden kannst. Es wird wohl sehr aufwändig und langsam werden, das Ganze. > Ziel ist es Und was ist die Aufgabe? Wo kommen die Daten her? Kommen die parallel auf einen Schlag an, oder ein Wort nach dem Anderen? Wie schnell kommen die Daten an?
Dann mußt du halt Register 0 mit Register 1 vergleichen, Register 0 mit 2, register 0 mit Register 3 usw. Danahc mußt du Register 1 mit Register 2 vergleichen weil (mit Register 0 hast du ja schon mal). Den Index des Jeweils kleineren kommt als Ergebnis in nen paar FlipFlops. Also brauchst du n²-n 16Bit Komperatoren und ein Ergebnisregister.
uwe schrieb: > Also brauchst du n²-n 16Bit Komperatoren und ein Ergebnisregister. Und natürlich einen (Monster-)Multiplexer um die richtigen Daten an das Ergebnisregister (das natürlich kein richtiges Register sein darf, sonst haben wir einen Takt Latency) auszugeben... > Komperatoren Sind das die Dinger mit 2 'a' und 1 'e'?
>> Komperatoren >Sind das die Dinger mit 2 'a' und 1 'e'? Jupp =;) Komparatoren
Wollte nur klarmachen, daß man nur für 1000 Werte ca 1000000 16Bit Komparatoren benötigt. Das könnte selbst mit einem Mittelklassewagen-FPGA schwer werden. Mit Mittelklassewagen-FPGA meien ich sowas: http://www.mouser.de/ProductDetail/Altera-Corporation/5SGTMC7K2F40C2ES/?qs=sGAEpiMZZMuPkEnZOVpBOBHTmId9mQ6IJy2d5itDR3A%3d
Ja, deshalb auch meine Fragen... ;-)
bist du sicher das es n²-n mögliche Vergleiche gibt?? also ich erinnere mich nur ganz wage und es ist noch früh, aber sollte nicht irgendwie 16! (Fakultät) oder sowas drin vorkommen?? Irgendwas in Richtung 16 (über) 2 oder so
Für 1000 Werte braucht es 999 16bit Komparatoren , 999 16bit 2-zu-1 Multiplexer und einen Prioritätsencoder mit 1000 Eingängen. Da die Komparatoren und die Multiplexer eine Kette bilden addieren sich die Signallaufzeiten. Dementsprechend langsam wird das Konstrukt. Bei mehreren gleichen Werten bekommt man, je nach Konfiguration der Komparatoren, den ersten oder den letzten Wert in der Kette.
Trundle Trollkönig schrieb: > bist du sicher das es n²-n mögliche Vergleiche gibt?? Es sind mindestens n-1 Vergleicher nötig: 1. Vergleich: Element 1 mit Element 2 2. Vergleich: das kleinere der beiden verglichen mit Element 3 3. Vergleich: das kleinere der beiden verglichen mit Element 4 4. Vergleich: das kleinere der beiden verglichen mit Element 5 usw. Diese Vergleiche müssen dann aber hintereinender kaskadiert werden, was sicher nicht ganz laufzeitoptimal ist (auch wenn der Synthesizer das Ganze plattklopft). Und vor Allem: danach braucht man noch den Multiplexer, der das Kleinste Element ausgibt. Denn sonst wissen wir zwar, welches das kleinste Element ist, haben es aber noch nicht am Ausgang... EDIT: Pech, Zweiter... ;-)
:
Bearbeitet durch Moderator
ok das was Lothar beschreibt ist ja ne Sequenz, die kann man sicher auch irgendwie in einem takt ablaufen lassen, aber ich dachte das man die ganzen Vergleiche irgendwie parallel ablaufen lassen kann. Ich dachte mehr an: Vergleiche Element 1 mit Elemente 2-16 und finde alle Elemente kleiner als Elemente 1 parallel dazu vergleiche Elemente 2 mit 3 - 16 und finde alle Elemente kleiner Element 2 parallel dazu Elemente 3 mit.... usw. Und am Ende müsste sich doch aus diesem Vergleichen relativ easy das kleinste Elemente ermitteln lassen... wie weiß ich jetzt auch nicht, wie gesagt ist zu früh.. ;) aber das Ganze würde ich dann in 2 Takte packen. Und das sollte zwar viel Logik ergeben aber die Taktfrequenz sollte nicht so stark in den Boden gehen. Ps. Also eins fällt mir gerade auf das Elemente wo sich beim Vergleich kein kleineres findet ist sicher, das kleinste und der Algorithmus ist mehr geeignet die Elemente komplett zu sortieren als nur das kleinste zu finden.
>...der das Kleinste Element ausgibt... Da der letzte Schritt der Kette ja ist, Vergleich: das kleinere der beiden verglichen mit Element x hast du das kleinste Element ja zwangsläufig am ende der Kette verfügbar. Das Problem ist, dass der TE nicht das kleinste Element selber sondern dessen Index haben will. Dafür braucht es einen Prioritätsencoder dessen Eingänge mit den Ausgängen der einzelnen Komaratoren verschaltet sind. >Pech, Zweiter... ;-) Dafür aber anschaulicher erklärt :-)
Trundle Trollkönig schrieb: > ok das was Lothar beschreibt ist ja ne Sequenz, die kann man sicher auch > irgendwie in einem takt ablaufen lassen, aber ich dachte das man die > ganzen Vergleiche irgendwie parallel ablaufen lassen kann. Eine Sequenz in Hardware ist einfach das Hintereinanderschalten von Vergleichern:
1 | Element0 -. |
2 | V1--. |
3 | Element1 -´ \ |
4 | V2--. |
5 | Element2 ------´ \ |
6 | V3--- |
7 | Element3 -----------´ |
Wenn man den Vergleicher als Binärbaum aufbaut, erhält man sogar den gewünschten Index kostenlos dazu, man muss nur schauen, wie die Vergleicherbits von "hinten her" gesetzt sind:
1 | Element0 -. |
2 | V1--. |
3 | Element1 -´ \ |
4 | V3-- |
5 | Element2 -. / |
6 | V2--´ |
7 | Element3 -´ |
Und zum Thema "Sortieren" mal das da. Ist zwar VHDL, aber die Hardwaregrundlagen sind ja die selben: http://www.lothar-miller.de/s9y/archives/78-Bubblesort.html
ok, ja das verstehe ich. aber sind dann auch viele Logikstufen hintereinander. Das müsste die Taktfrequenz runterziehen oder ?? Gibt es keine Möglichkeit diesen Baum so zu verändern das man die Anzahl der Vergleiche erhöht aber die Logikstufen reduziert?? Ich dachte das sucht der TO.
>aber sind dann auch viele Logikstufen hintereinander.
Bei der Baumstruktur eigentlich nicht. Da sind es nur noch log2(n)
Stufen hintereinander. Bei 1000 Werten sind das 10 Stufen. Im Vergleich
zur Kettenstruktur doch super.
Trundle Trollkönig schrieb: > Gibt es keine Möglichkeit diesen Baum so zu verändern das man die Anzahl > der Vergleiche erhöht aber die Logikstufen reduziert?? Ich dachte das > sucht der TO. Nicht, wenn man einfach eine "fertige" Tabelle präsentiert bekommt. Aber wenn man die Daten nacheinander "hereinbekommt", dann ließe sich da noch was machen. Deshalb meine Fragen da oben im Beitrag "Re: 2D-Register Array, Index geringster Wert, Logik"
Hallo, ich bins nochmal (der Threadersteller :D ) Ich habe das ganze jetzt mit einem einzigen Register gelöst. Die Werte zum Vergleichen stehen jetzt alle in einem Register (alle X-Bits fängt ein neuer Wert an). Via generate wird ein Vergleicher-Netzwerk aufgebaut, wie es Lothar Miller vorgeschlagen hat. Habe mir dazu ein Vergleicher-Modul geschrieben wo vorne die zwei Werte und die zwei Index-Werte reinkommen. Am Ende der Vergleicherkette wird der Index ausgespuckt. Läuft einwandfrei! Danke nochmals :)
Jo wäre trotzdem noch interessant woher die Werte mit welcher Geschwindigkeit kommen und ob das in Hardware umsetzbar sein muss.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.