mikrocontroller.net

Forum: FPGA, VHDL & Co. Schnelle Hashfunktion gesucht


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
Autor: VHDL hotline (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich möchte auf einem FPGA eine Hashfunktion implementieren, welche mir 
aus 512-Bit Eingangswerten möglichst gleichverteilte 11-bit 
Ausgangswerte generiert und das mit möglichst niedriger Latenz. Schön 
wäre 1 Takt bei >150 MHz auf aktueller FPGA-Technologie. 
Kryptographische Sicherheit ist nicht notwendig. Bei den Eingangswerten 
handelt es sich z.B. um Tupel aus 4 IPv6-Adressen, die möglichst 
gleichverteilt auf Speicheradressen abgebildet werden sollen. Es sind 
auch andere Tupel möglich, darauf kann also nicht optimiert werden. 
Gemeinsam ist, dass die Eingangswerte nicht gleichverteilt sind.

Nun gibt es für nicht-kryptographische Hashes einige Verfahren wie 
Murmur, FNV, Jenkins usw. . So wie ich das sehe, sind diese allerdings 
meist für x86 optimiert, operieren auf max. 32-64 bit Eingangsbreite und 
brauchen entsprechend mehrere Runden. Von der Natur der Operationen her 
(xor, +, -, shift, *) sehen die Verfahren grundsätzlich recht geeignet 
für eine FPGA-Umsetzung aus. Eine Variante wäre, die rundenbasierten 
Algorithmen in einer großen Kombinatorik aufzudröseln, aber so wirklich 
optimal ist das nicht. Ein Hash, welcher mit Blick auf die Möglichkeiten 
eines FPGA designt ist, lässt sich effizienter implementieren.

Nun könnte ich natürlich selbst einfach ein paar XOR/shift-Kombinationen 
zusammenbasteln, um die 512 Bit auf 11 Bit einzudampfen. Die Frage ist 
allerdings, wie ich dann sicherstellen kann, dass das ganze ausreichend 
gleichverteilt ist.

Frage: Kennt jemand derartige Hashalgorithmen, welche sich besonders gut 
für die Umsetzung auf FPGA eignen (sehr breite Eingangswerte und innere 
Zustände, massiv parallel, wenig bis keine Runden)?

Autor: Johnny B. (johnnyb)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
CRC16 lässt sich meines Wissens gut in Hardware bzw. Logik 
implementieren.

Autor: MaWin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus, bist du das? :-D

Autor: Nop (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Johnny B. schrieb:
> CRC16 lässt sich meines Wissens gut in Hardware bzw. Logik
> implementieren.

"wenig bis keine Runden"

Autor: Markus F. (mfro)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
Hmmm.

Wenn Du über die "nicht Gleichverteilung" der Eingangswerte nichts 
genaueres (ausser deren Wertebereich) weißt, kannst Du auch über die 
Verteilung der Hashwerte nichts genaueres sagen.

Dann kannst Du auch gleich 11 Bit abschneiden und die nehmen. Geht am 
flottesten.

: Bearbeitet durch User
Autor: VHDL hotline (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Johnny B. schrieb:
> CRC16 lässt sich meines Wissens gut in Hardware bzw. Logik
> implementieren.

Ja danke, das stimmt zwar. Grundsätzlich lassen sich die Hashalgorithmen 
alle irgendwie in Hardware implementieren. Das worauf es mir allerdings 
besonders ankommt ist die niedrige Latenz bei breitem Dateneingang und 
die Gleichverteilung. Die Prüfsumme erzeugt soweit ich weiß keine 
Gleichverteilung. Das Rundenproblem ist ähnlich gelagert, wie bei den 
bereits genannten Hashes.

MaWin schrieb:
> Markus, bist du das? :-D

Ja, wieso? Und wer bist du?

Autor: VHDL hotline (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus F. schrieb:
> Hmmm.
>
> Wenn Du über die "nicht Gleichverteilung" der Eingangswerte nichts
> genaueres (ausser deren Wertebereich) weißt, kannst Du auch über die
> Verteilung der Hashwerte nichts genaueres sagen.
>
> Dann kannst Du auch gleich 11 Bit abschneiden und die nehmen. Geht am
> flottesten.

?

Eine Hash-Funktion ist im Optimalfall so implementiert, dass eine 
Änderung eines Bits im Eingangswert sich auf ca. die Hälfte der Bits im 
Ausgangswert auswirkt. Was da an Daten reinkommt, sollte nicht 
zwangsläufig eine Rolle spielen.
Schneide ich nur die unteren 11 Bit ab, haben die oberen 501 Bit keine 
Auswirkung auf das Ergebnis.

Autor: Markus F. (mfro)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
VHDL hotline schrieb im Beitrag #5399643:
> Eine Hash-Funktion ist im Optimalfall so implementiert, dass eine
> Änderung eines Bits im Eingangswert sich auf ca. die Hälfte der Bits im
> Ausgangswert auswirkt. Was da an Daten reinkommt, sollte nicht
> zwangsläufig eine Rolle spielen.
> Schneide ich nur die unteren 11 Bit ab, haben die oberen 501 Bit keine
> Auswirkung auf das Ergebnis.

Ja. Stimmt. Wenn die Eingangswerte einigermassen gleichverteilt sind.

Hier wurde aber explizit gesagt, dass sie das nicht sind (und nichts 
weiter). Also könnte es genausogut sein, dass sich die oberen 501 bits 
gar nicht ändern und die abgeschnittenen 11 Bit damit optimal sind...

Autor: Fpga I. (fpga-ing)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
eine CRC lässt sich in einem Clk Cycle implementieren und sollte m.E. 
gleichverteilt sein (Nur dass die 0 nicht als CRC rauskommen darf/kann.)

Hier kannst du Dir ein entsprechendes Package generieren:
http://www.easics.com/webtools/crctool

Vielleicht findest du ja auch ein generator Polynom für eine CRC 11.

Ob sich eine CRC mit 512 Bit Eingang bei 150 MHz realisieren lässt, 
musst Du sehen, gefühlt könnte es sehr knapp werden. Alternativ mit 
Pipelining oder Multicycles arbeiten.
Einfacher wird es sicherlich, wenn Du den Datenbereich reduzierst (bei 
IP Adressen solltest du mit 32 Bit hinkommen)

Autor: VHDL hotline (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus F. schrieb:
> Ja. Stimmt. Wenn die Eingangswerte einigermassen gleichverteilt sind.
>
> Hier wurde aber explizit gesagt, dass sie das nicht sind (und nichts
> weiter). Also könnte es genausogut sein, dass sich die oberen 501 bits
> gar nicht ändern und die abgeschnittenen 11 Bit damit optimal sind...

Okay, ich gehe mit, dass eine Abhängigkeit vom Eingangswert immer da 
ist. Eine Hashfunktion verteilt einen gleichverteilten Eingang auf einen 
gleichverteilten Ausgang, indem auf jeden Ausgangswert etwa gleich viele 
der Eingangswerte gemappt werden. Ist der Eingang nicht gleichverteilt, 
muss die Hashfunktion eine andere Anzahl von Eingangswerten auf dasselbe 
Ergebnis mappen, um eine Gleichverteilung am Ausgang hinzubekommen. Als 
Nebenbedingung sollten die Eingangswerte, welche zum selben Ausgangswert 
führen, "möglichst verschieden" sein.

Wahrscheinlich reicht es für den oben genannten Fall mit den IP-Tupeln 
aus, von einer Gleichverteilung am Eingang auszugehen, so lange ähnliche 
Tupel zu ausreichend verschiedenen Ergebnissen führen.

Fpga I. schrieb:
> eine CRC lässt sich in einem Clk Cycle implementieren und sollte m.E.
> gleichverteilt sein (Nur dass die 0 nicht als CRC rauskommen darf/kann.)

Ja, so etwas habe ich schon mal implementiert. Allerdings noch nicht mit 
größeren Datenbreiten. Prinzipiell ist das ja ein XOR/Shift.

Fpga I. schrieb:
> Ob sich eine CRC mit 512 Bit Eingang bei 150 MHz realisieren lässt,
> musst Du sehen, gefühlt könnte es sehr knapp werden. Alternativ mit
> Pipelining oder Multicycles arbeiten.

Das wird dann wahrscheinlich das Problem sein. Multicycle ist mir zu 
langsam und Pipelining ist für Branching nicht geeignet. Aber ich schau 
mal, wie schnell es implementierbar ist.

Fpga I. schrieb:
> Einfacher wird es sicherlich, wenn Du den Datenbereich reduzierst (bei
> IP Adressen solltest du mit 32 Bit hinkommen)

Bei IPv6 könnte ich implizite Annahmen treffen, welcher Bereich der 
Adresse sinnvollerweise relevant ist. Grundsätzlich ist das aber nicht 
auf 32 Bit beschränkt. Außerdem kommen wahrscheinlich noch andere 
protokollspezifische Sachen zum Tupel dazu.


Danke erstmal für die Antworten.

Autor: Sigi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
VHDL hotline schrieb im Beitrag #5399531:
> ich möchte auf einem FPGA eine Hashfunktion implementieren, welche mir
> aus 512-Bit Eingangswerten möglichst gleichverteilte 11-bit
> Ausgangswerte generiert

Du schreibst hier nicht genau, auf was sich "gleichverteilt"
bezieht. Ist damit (1) hash=f(input) oder (2) hash=f(input(t))=g(t)
gemeint.
Für (1) ist obige Bemerkung, die ersten 11 Bits zu nehmen
schonmal eine interessante Wahl. Sie ist zwar keine Hashfunktion,
aber immerhin gleichverteilt. Wählt man jetzt eine geeignete
Verknüpfungsfunktion (meine Vermutung wäre eine Matrix auf Z2)
um z.B. 11 Bits mit weiteren 11 Bits zu gleichverteilten 11 Bits
verknüpft, dann hat man eine sehr gute Hashfunktion.
Matrix-Funktion: z.B. 11 unabhängige Z2-Polynome, die sich
sehr leicht in HDL giessen lassen.

Autor: Markus F. (mfro)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Eine völlig andere Frage stellt sich mir noch: wenn die Hasherei in 
einem Takt bei 150 MHz passieren soll, musst Du ja das Zeug auch 
irgendwie rein und auch wieder raus bringen.

Also entweder 523 Pins mit 150 MHz oder eben die Hälfte mit ALTDDIO.

Wer oder was soll da auf der anderen Seite ackern?.

Autor: Bernd K. (prof7bit)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nop schrieb:
> Johnny B. schrieb:
>> CRC16 lässt sich meines Wissens gut in Hardware bzw. Logik
>> implementieren.
>
> "wenig bis keine Runden"

Es gibt schon welche die sich schön optimieren lassen, zum Beispiel die:
uint16_t crc_ccitt_update (uint16_t crc, uint8_t data) {
    data ^= lo8 (crc);
    data ^= data << 4;
    return ((((uint16_t)data << 8) | hi8 (crc)) ^ (uint8_t)(data >> 4) 
            ^ ((uint16_t)data << 3));
}

Autor: VHDL hotline (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sigi schrieb:
> Du schreibst hier nicht genau, auf was sich "gleichverteilt"
> bezieht. Ist damit (1) hash=f(input) oder (2) hash=f(input(t))=g(t)
> gemeint.

Das Ergebnis soll gleichverteilt sein und ist unabhängig von der Zeit.

Sigi schrieb:
> Für (1) ist obige Bemerkung, die ersten 11 Bits zu nehmen
> schonmal eine interessante Wahl. Sie ist zwar keine Hashfunktion,
> aber immerhin gleichverteilt.

Für die Anwendung ist es keine Option, nur 11 Bit zu nehmen. Ich muss 
mal etwas weiter ausholen, um das eigentliche Problem zu beschreiben.

Markus F. schrieb:
> Eine völlig andere Frage stellt sich mir noch: wenn die Hasherei in
> einem Takt bei 150 MHz passieren soll, musst Du ja das Zeug auch
> irgendwie rein und auch wieder raus bringen.

Es geht um 100G Ethernet.



Das eigentliche Problem ist ein Packet-Classification-Problem. Das 
klassische Classification-Problem für einen Netzwerkknoten besteht 
darin, für ein Tupel von SrcIP/DstIP/Protokoll/SrcPort/DstPort 
nachzuschlagen, ob dafür eine Regel (routing-policy, traffic shaping, 
packet filter, ...) vorhanden ist und diese anzuwenden. IPs und Ports 
können in den Regeln als Masken oder Ranges eingetragen sein, das soll 
hier aber keine Rolle spielen. Mein Klassifikationsproblem ist ähnlich 
dem klassischen. Für IPv6 werden die Suchtupel jedenfalls schnell mal 
größer ~300 Bit.

Die Regeln sind in einer großen Tabelle in externem Speicher 
organisiert. Der Speicherzugriff ist ein Flaschenhals. Es geht nun 
darum, erst einmal herauszufinden, ob eine Regel für ein bestimmtes 
Tupel überhaupt vorhanden ist, bevor auf den externen Speicher 
zugegriffen wird. Dazu war meine (von diversen Papers abgeschaute) Idee, 
eine Datenstruktur namens Bloom-Filter im FPGA zu verwenden. Dafür 
werden für jedes Tupel mehrere unabhängige Hashwerte gebildet, die z.B. 
zwischen 0 und 2047 gleichverteilt sind. An der durch den Hash 
berechneten Stelle wird dann in einem 11-Bit-Vektor eine '1' gesetzt. 
Kommt nun ein Paket werden die Hashes berechnet und es wird im 
Bloom-Filter geschaut, ob die Bits gesetzt sind. Sind sie es, könnte das 
Tupel in den Bloom-Filter eingetragen worden sein (oder die Bits wurden 
durch ein anderes Tupel gesetzt) und der externe Speicherzugriff kann 
losgehen. Sind sie es nicht, kann man sich den Speicherzugriff sparen.

Mein Problem ist nun: Wie berechne ich möglischt schnell einen 
ausreichend gleichverteilten Hash aus entsprechenden Tupeln. Die 
Struktur der Tupel bzw. IP-Adressen ist zwar ungefähr klar, es ist 
allerdings aus meiner Sicht keine geeignete Option einfach nur einen 
Teil davon als Hash zu nehmen.

Autor: Markus F. (mfro)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dann reden wir wohl eher nicht von einem Hobby-Projekt und auch nicht 
von irgendeinem "Pups-FPGA", sondern eher von einem der "dicken 
Brocken".

In dem Fall würde ich mir da erst mal keinen Kopf an der Hashfunktion 
machen, sondern einfach ausprobieren, was dein Bolide so als 
Divisionsrest-Hash leistet.

Dein "dicker Brocken" wird bestimmt ein paar HW-Divider mitbringen, die 
Du für den Rest deiner Anwendung wahrscheinlich sowieso nicht brauchst. 
Wär' ja schade, wenn die ungenutzt vergammeln würden. Wenn das zu 
langsam ist, kannst Du ja immer noch darüber hirnen, wie es sich 
beschleunigen läßt.

Autor: Luther B. (luther-blissett)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Üblicherweise wird von einer guten Hashfunktion erwartet, dass jede 
Änderung eines Bits im Mittel die Hälfte der Bits des Hashes ändert.

Das könnte man in deiner Problemstellung (512=>11) so realisieren, dass 
für jedes Ausgangsbit ein statischer Term aufgestellt wird, der 256 
(vorher zufällige bestimmte) Eingangsbits XOR verknüpft, wobei jedes 
Eingangsbit im Mittel 5-6 Ausgangsbits mitbestimmt.

Die Verteilung generiert ein Programm, welches deine Hashfunktion auch 
gleich empirisch überprüfen kann.

Am Ende geht jedes Eingangsbit einfach nur durch 3-4 LUT, keine Ahnung 
ob das für deine 150Mhz reicht.

: Bearbeitet durch User
Autor: VHDL hotline (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus F. schrieb:
> Dann reden wir wohl eher nicht von einem Hobby-Projekt und auch nicht
> von irgendeinem "Pups-FPGA", sondern eher von einem der "dicken
> Brocken".

Ja, Virtex US+ und Datacenter. Das ist mir fürs Hobby zu teuer ;-) .

Markus F. schrieb:
> Dein "dicker Brocken" wird bestimmt ein paar HW-Divider mitbringen

DSP-Blöcke hat er ja und IP-Cores für Divider gibts. Für die Datenbreite 
muss ich mir aber noch was einfallen lassen. Danke erstmal für deine 
Anregungen.

Luther B. schrieb:
> Das könnte man in deiner Problemstellung (512=>11) so realisieren, dass
> für jedes Ausgangsbit ein statischer Term aufgestellt wird, der 256
> (vorher zufällige bestimmte) Eingangsbits XOR verknüpft, wobei jedes
> Eingangsbit im Mittel 5-6 Ausgangsbits mitbestimmt.

Ja genau, an so etwas habe ich gedacht, allerdings möglichst 
allgemeingültig und mit Nachweis über die Verteilung. Aber ich sehe so 
langsam ein, dass ich wohl doch selbst etwas basteln und verifizieren 
muss.

Autor: Jürgen S. (engineer) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bernd K. schrieb:
> Nop schrieb:
>> Johnny B. schrieb:
>>> CRC16 lässt sich meines Wissens gut in Hardware bzw. Logik
>>> implementieren.
>>
>> "wenig bis keine Runden"
>
> Es gibt schon welche die sich schön optimieren lassen, zum Beispiel die:

Bei der Abschätzung, wie schnell ein solcher Algo sein wird, muss man im 
Wesentlichen die LUTs beachten, die für die Implementierung verwendet 
werden und nicht nur die EXOR-Tiefen und Breiten zu beachten.

Und es gilt indirekt: CRCs, die gut zu implementieren sind, weil sie 
wenig binäre Tiefe haben, sind auch nicht so sicher.

Autor: Name H. (hacky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ein Satz von IPv6 Adressen ist ganz sicher nicht gleichverteilt. Ich 
wuerde die IPv6 Adressen in einer Baumstruktur speichern und jeweils 
direkt vergleichen. Intern kann man schon ueber indices arbeiten. Aus 
dem Baum heraus.

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.