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)?
CRC16 lässt sich meines Wissens gut in Hardware bzw. Logik implementieren.
Johnny B. schrieb: > CRC16 lässt sich meines Wissens gut in Hardware bzw. Logik > implementieren. "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.
:
Bearbeitet durch User
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:
1 | uint16_t crc_ccitt_update (uint16_t crc, uint8_t data) { |
2 | data ^= lo8 (crc); |
3 | data ^= data << 4; |
4 | return ((((uint16_t)data << 8) | hi8 (crc)) ^ (uint8_t)(data >> 4) |
5 | ^ ((uint16_t)data << 3)); |
6 | }
|
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.
:
Bearbeitet durch User
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.
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.