schnelles Vergleichen

[Da M. (damicha)]

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.

[Kest (Gast)]

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

Fragen über Fragen...

Kest

[FPGAküchle (Gast)]

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?

[Falk (Gast)]

???
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

[Xilinxuser (Gast)]

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.

[Falk (Gast)]

@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

[Da M. (damicha)]

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;

[Kest (Gast)]

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

[Falk (Gast)]

@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