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)?
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.
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?
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.
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...
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)
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.
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.
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?.
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:
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.
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.
Ü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.
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.
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.
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.
