www.mikrocontroller.net

Forum: FPGA, VHDL & Co. schnelles Vergleichen


Autor: Da Micha (damicha)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo.

Ich möchte zwei 64 Bit Zahlen miteinander vergleichen. Größer, kleiner
oder gleich soll das Ergebnis sein.
Bisher habe ich die oberen und unteren Hälften getrennt miteinander
verglichen. Je nach dem, ob die oberen Hälften gleich sind oder nicht,
wird das Ergebnis des unteren bzw. oberen Vergleichs genommen.
Das funktioniert auch schon ganz gut.
Es könnte aber immer noch ein wenig schneller sein ;-).

Vielleicht kennt jemand von Euch noch einen passenden Algorithmus, der
sich gut im FPGA implementieren lässt.

Gruß DaMicha.

Autor: Kest (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hast Du mit ">" "<" "=" ausprobiert (VHDL oder Verilog)? Ist es nicht 
schnell genug? Sind die Tools nicht intelliegent genug?

Fragen über Fragen...

Kest

Autor: FPGAküchle (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die synthese ist meist schon optimal was das einbauen von Comperatoren 
betrifft. wo stammen die 64 bit her, register, counter? Bei letzteren 
hasst du Optimierungsmöglichkeiten (Vergleich mit wert eins Kleiner 
(up-counter) und pipiline). Ansonsten kannst du ja versuchen spezielle 
FPGA Eigenheiten zu benutzen (LUT oder Carry chain). Oder du zerhackst 
den 64 bit vergleicher um RAMBlöcke als Lokkuptabelle für den vergleich 
zu verwenden. Aber da optimiert man weniger das VHDL (Synthese) als das 
man spitzfindig das Mapping und routing ausnutzt.

Wie schnell ist den dein bisheriger vergleicher?

Autor: Falk (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
???
Ein 64-Bit Subtrahierer (Für Grösser/kleiner) und ein 64 Bit XOR (für
gleich). Das XOR kann die Carry Chain nutzen (zumindest bei Xilinx), das
wird schon sehr schnell. Wenn schneller gehen soll (höherer Takt)
-> Pipelining

Was ist für dich "schnell" ?

MfG
Falk

Autor: Xilinxuser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wird denn die Synthese nicht schon automatisch bei der Prüfung auf 
"Gleich" ein XOR einsetzen? Wenn sie das nicht kann, was kann sie dann 
überhaupt? Ich habe mir darum noch nie Geanken gemacht.

Autor: Falk (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Xilinxuser

>Wird denn die Synthese nicht schon automatisch bei der Prüfung auf
>"Gleich" ein XOR einsetzen? Wenn sie das nicht kann, was kann sie dann

Das wird sie schon. AFAIK waren aber die älteren Versioen von XST nicht 
so schalu, auch die Carry-Chain zu benutzten(beim Vergeleicher).

>überhaupt? Ich habe mir darum noch nie Geanken gemacht.

Die kann schon einges ;-)

MFG
Falk

Autor: Da Micha (damicha)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo.

Erstmal danke für die Antworten.

@Kest: Mein Vergleich sieht folgendermaßen aus:
    if    (a < b) then
        v.cmp := CMP_LOWER;
    elsif (a > b) then
        v.cmp := CMP_HIGHER;
    else
        v.cmp := CMP_EQUAL;
    end if;

Alles andere war langsamer. Selbst ein (a = b fürs Equal) war nicht 
schneller.
Ich denke mal, dass die Carrypfade für <,> schon extrem schnell sind.

Die Werte a und b kommen aus Registern, das Vergleichsergebnis schaltet 
Adressen über einen Multiplexer und das Ergebnis landet wieder in einem 
Register.
Davor und danach sind Blockram-Zugriffe. Die Zeit von dem Blockram bzw. 
aus dem Blockram benötige ich für Netzdelays und weitere Multiplexer.
Mit dem vollen 64 Bit Vergleich kommen ich auf 155 MHz bei der Synthese 
bei 2x 32 Bit sind es 213 MHz bei der Synthese und 180 MHz nach dem 
Place&Route. Der Zielfpga ist ein Virtex 4 fx60 und die Zielfrequenz 156 
MHz bei momentan minimaler Auslastung (4% Slices und 10% Blockrams). Das 
ist soweit OK, aber man hat ja immer gerne etwas Luft.

Ich habe inzwischen noch weiter rumprobiert, aber leider lässt sich 
nicht mehr viel machen. Durch ein weiteres Aufteilen des Vergleiches in 
kleiner Werte wird das Design wieder langsamer.

Hatte gehofft, dass es noch einen Trick zum Vergleichen von großen Werte 
gibt...

@Falk: eine weitere Pipelinestufe ist eine Option würde aber durch die 
Latenzzeit mein Taktschema beeinflußen und wahrscheinlich den Durchsatz 
drücken, da ich einen Takt verliere, während ein RAM-Access läuft.

Danke nochmal,
 DaMicha.

Hier noch mal die 2x32 Bit Version:
    -- bit 63 downto 32 --
    if    (a_h < b_h) then
        cmp_h := CMP_LOWER;
    elsif (a_h > b_h) then
        cmp_h := CMP_HIGHER;
    else
        cmp_h := CMP_EQUAL;
    end if;

    -- bit 31 downto  0 --
    if    (a_l < b_l) then    
        cmp_l := CMP_LOWER;
    elsif (a_l > b_l) then
        cmp_l := CMP_HIGHER;
    else
        cmp_l := CMP_EQUAL;
    end if;

    if (cmp_h = CMP_EQUAL) then       -- use lower bits
        v.cmp := cmp_l;
    else
        v.cmp := cmp_h;
    end if;

  

Autor: Kest (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nur eine Idee:

ich würde ausprobieren auf "EQUAL" und auf "LOWER" gleichzeitig zu 
überprüfen. Der ausgang ist dann nur die Verknüpfung der beiden

Pseudocode:

EQUAL='1' when (a=b) else '0';

LOWER='1' when (a<b) else '0';

HIGHER='1' when (EQUAL='0' and LOWER='0) else '0';


(sorry, mag sein, dass mit Variablen das gleiche rauskommt, aber ich 
wollte nur was in den Raum werfen, was von den anderen ruhig "zerrissen" 
werden kann ;-))

Kest

Autor: Falk (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Da Micha

>Alles andere war langsamer. Selbst ein (a = b fürs Equal) war nicht
>schneller.

Hmm, dannscheint der Compiler schon recht gute Arbeit zu leisten, aber . 
.

>Ich denke mal, dass die Carrypfade für <,> schon extrem schnell sind.

Sicher, aber das ist nur die halbe Miete.

>Die Werte a und b kommen aus Registern, das Vergleichsergebnis schaltet
>Adressen über einen Multiplexer und das Ergebnis landet wieder in einem
>Register.

HA! Das ist ja schon ein recht langer Pfad. Ich würde das 
Vergleichsergebnis erstmal in ein Register packen und danch weiter 
nutzen. Klar, das braucht einen Takt länger, sollte aber deutlich 
schneller werden.

>bei 2x 32 Bit sind es 213 MHz bei der Synthese und 180 MHz nach dem
>Place&Route. Der Zielfpga ist ein Virtex 4 fx60 und die Zielfrequenz 156

Hmmmm, 180 MHz für nen 32 Bit Vergleich finde ich so rein aus dem Bauch 
heraus für Virtex4 nicht so dolle. Liegt aber whrscheinlich daran, dass 
du danach noch die MUX und Adressen schaltest.

MFG
Falk

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.