Hallo Leute, ich hoffe, ihr könnt mir etwas dabei helfen, ein Problem mit FPGA(s) zu lösen. Genauer gesagt habe ich folgenden Algorithmus. Ich habe zwei Konstante X,Y und drei Variablen A, B und counter. => Anfang A = X, B = Eingabe, counter = 0 ===> Loop Nimm A, B und mache damit etwas und schiebe das Ergebnis in A counter++ Wenn Counter <=4096 gehe zu ===>Loop Vergleiche A mit Y, wenn gleich, dann sag bescheid, wenn nicht, hole gehe zum Anfang. Also nochmal zusammengefasst. Ich habe eine Schleife, die 4096 Mal mit dem vorhergehenden Ergebnis rechnet und dann einen Vergleich am Ende. Nun könnte ich so etwas auf zwei Weisen implementieren. 1) Ich habe sagen wir mal 100 Einheiten, bei der jede den Algorithmus selbstständig ausführt und dann auch ein Ergebnis zurückliefest. 2) Ich habe eine Pipeline mit 4096 Stufen und bekomme dann sequenziell Ergebnisse zurück. Was ist da allgemein besser? Und dann noch eine andere Frage: Macht es bei den FPGAs eher Sinn einen größeren Chip mit mehr logischen Units zu nehmen oder macht es Sinn, mehrere FPGAs zu nehmen?
Mathias Braun schrieb: > 1) Ich habe sagen wir mal 100 Einheiten, bei der jede den Algorithmus > selbstständig ausführt und dann auch ein Ergebnis zurückliefest. 100 "Einheiten" rechnen EIN Ergebnis aus? > Was ist da allgemein besser? Kommt darauf an, ob du eine Latenz von 4096 Takten erlauben kannst, und auch darauf, wo die Daten herkommen und wohin sie müssen und darauf, mit welcher Geschwindigkeit das Ganze laufen soll und, und, und... > Macht es bei den FPGAs eher Sinn einen größeren Chip mit mehr logischen > Units zu nehmen oder macht es Sinn, mehrere FPGAs zu nehmen? Das kommt darauf an, wie du die Aufgabe aufteilen kannst. I.A. ist es einfacher, so viel wie möglich in 1 Chip zu packen, denn dann hast du die Schnittstelle zur Aussenwelt nur 1x. Es kann aber billiger und sicherer (Redundanz) sein, mehrere kleine FPGA zu einem Cluster zusammenzupacken.
Lothar Miller schrieb: > 100 "Einheiten" rechnen EIN Ergebnis aus? Ich meine, dass 100 Einheiten an 100 verschiedenen Aufgaben rechnen. Wobei da mathematisch alle aufgaben gleich schnell erledigt werden können, somit alle 100 bzw. n Einheiten gleichzeitig fertig werden, es beim Füttern mit neuen Daten zu einem Flaschenhals kommen könnte. Lothar Miller schrieb: > Kommt darauf an, ob du eine Latenz von 4096 Takten erlauben kannst, und > auch darauf, wo die Daten herkommen und wohin sie müssen und darauf, mit > welcher Geschwindigkeit das Ganze laufen soll und, und, und... Also eine Latenz ist unwichtig. Die Konstanten werden ein Mal eingegeben (am besten irgendwie per USB) und sollten irgendwo im FPGA gespeichert werden. Das sind die Werte, an denen in den nächsten Stunden gearbeitet werden soll. Der Hostrechner soll dann quasi immer B liefern. Wobei ich auch ca. 1.000 Werte für B in einen FIFO Speicher reinwerfen kann, und der FPGA die Werte dann rausholt um daran zu arbeiten. Wohin müssen die Daten? Nun, in 99,9% aller fälle werden Daten weggeworfen. Wichtig ist nur eine Meldung, und zwar wenn der letzte Vergleich des A mit Y ein True zurückliefert. Wichtig wäre an der Stelle das B. Das müsste an den Rechner zurück. Mehr Daten fließen da nicht.
Im Prinzip gibt es nur eine Eingangsvariable. Und nur eine Schleife bis 4096. Wenn jetzt ein 2GHz PC eine Berechnung pro Tekt macht, könnte er fast 500000 Eingangswerte die Sekunde rechnen. Bei einem maximalen Wertevorat von 32 Bit, würde er dafür 8500 Sekunden für alle möglichen Ergebnisse brauchen. Das ist unter 3 Stunden. Lohnt sich dafür noch ein FPGA-Umsetzung?
PittyJ schrieb: > Bei einem maximalen Wertevorat von 32 Bit Und jetzt nimm mal 512 Bit als Wertevorrat (ist jetzt kein Scherz)... Da macht die Umsetzung auf dem FPGA schon mehr Sinn. Und dann sagen wir mal, dass ich diese Berechnung nicht nur ein Mal machen werde, sondern 2-3 pro Monat.......
Mache doch einfach eine kleine FSM mit 3 States. Im ersten State wird initialisiert. im zweiten State wird 4096mal deine Operation durchgeführt. Und dabei jedesmal der Zähler inkrementiert. Ist der Zählerendwert erreicht, springst du in den letzten State, wo du dann das Ergebnis auswertest. Wenn die Operation mit A und B innerhalb eines Taktes erfolgen kann, dann biste mit nem 50MHz Systemtakt in ca 80µs fertig. Oder denke ich gerade zu einfach?
Schlumpf schrieb: > Oder denke ich gerade zu einfach? Ja, denn eine zweite Möglichkeit wäre tatsächlich diese FSM in der Breite aufzuteilen. Dann hätte ich eine Pipeline. Also den Beginn als eine Stufe, dann 4096 Stufen in denen rumgerechnet wird dann am Ende die Abschlussstufe. Was hätte es für Vorteile? Bei deiner Version würde die Logik der Rumrechnerei langweilen, wenn man die Rechnung beginnt bzw. abschließt, also im ersten und letzten State. Das wären jetzt 0,05% Verlust der Rechenzeit im vergleich zu der Pipeline pro FSM. Wenn ich jetzt annehme, dass ich analog zur Pipeline 4096 FSM habe, dann habe ich noch mehr Logik, die einfach nichts macht. Deshalb erscheint mir die Pipeline effizienter. Auf der anderen Seite brauche ich für den ganzen Prozess eben diese 4096+2 Abschnitte in der Pipeline. Das dürfte schon sehr viel Platz wegnehmen. vll. kann ich auf einem FPGA jetzt 3 Stück unterbringen, im worst case fehlen mir wenige Logic Units für eine weitere Pipeline und ich nutze vorhandene Logik nicht. Deshalb denke ich, dass ich mit den kleinen FSMs die Fläche des Chips besser ausnutzen kann.
Wenn du 4096mal das gleiche machst (also die gleiche Operation, nur mit veränderten Werten), dann brauchst du doch die Schaltung nicht 4000 mal parallel im FPGA abbilden, sondern nur einmal. Mit jedem Takt kopierst du das Ergebnis dieser Operation in ein Register, dessen Wert du beim nächsten Takt als Eingangswert an die Schaltung anlegst. Dann brauchst du die Logik für die Berechnung nur ein einziges mal. zzg. eines Counters, der auf 4096 zählt und eines 2 Bit breiten State-Counters.
Schlumpf schrieb: > Dann brauchst du die Logik für die Berechnung nur ein einziges mal. zzg. > eines Counters, der auf 4096 zählt und eines 2 Bit breiten > State-Counters. ähm... aber genau darum geht es doch beim FPGA. Wenn ich die Logik nur ein Mal im FPGA habe, dann kann ich einen Wert gleichzeitig berechnen. Wenn ich die Logik zwei Mal im FPGA habe, dann kann ich zwei Werte gleichzeitig berechnen und brauche insgesamt für die die Erfüllung der Aufgabe die hälfte der Zeit. usw.
Mathias Braun schrieb: > ähm... aber genau darum geht es doch beim FPGA. Kommt drauf an.. FPGA heißt nicht zwangsläufig, dass ALLES auf Biegen und Brechen parallelisiert werden muss. Hast du nicht geschrieben, dass Latenz nicht das Problem sei? Ich würde mal behaupten, dass deine Steuerlogik mit < 20 Registern auskommt. Hinzu kommen dann die Register, die du für deine Operation und zum zwischenspeichern der Ergebnisse brauchst. Also angenommen, deine Operation kann innerhalb eines Taktes ausgeführt werden, dann braucht die Berechnung an sich gar keine Register. Annahme, dass A und B jeweils 32 Bit groß sind, dann würde ich behaupten, dass die Realisierung deiner Aufgabe mit < 100 Registern zu schaffen ist. Und wenn deine Operation recht komplex ist, so dass die Logiktiefe recht groß wird, dann kannst du entweder die Operation pipelinen (2 oder 3 Stufen) oder eben die Taktrate reduzieren. Also so würde ich jedenfalls die Sache angehen.
Schlumpf schrieb: > FPGA heißt nicht zwangsläufig, dass ALLES auf Biegen und Brechen > parallelisiert werden muss. Ich kann deine Argumentation in dem Punkt leider nicht nachvollziehen. Ich habe eine Aufgabe, bei der ich im Worst case 2^512 Berechnungen durchführen muss. Und jede Berechnung kann ich in 4096 Teile aufteilen. Wieso sollte ich dann nicht alles parallelisieren um schnellstmöglich Ergebnisse zu erhalten?
Mathias Braun schrieb: > Nimm A, B und mache damit etwas und schiebe das Ergebnis in A Daraus geht nicht hervor, dass dieses "etwas" dann am Ende 2^512 Berechnungen sind. Schreibe doch einfach mal hin, was dieses "etwas" ist. Vielleicht hat man dann eine Basis auf der man eine sinnvolle Lösung suchen kann. Also welche Operation ist mit A und B durchzuführen?
Mathias Braun schrieb: > Ich habe zwei Konstante X,Y und drei Variablen A, B und counter. > > => Anfang > A = X, B = Eingabe, counter = 0 > ===> Loop > Nimm A, B und mache damit etwas und schiebe das Ergebnis in A > counter++ > Wenn Counter <=4096 gehe zu ===>Loop > Vergleiche A mit Y, wenn gleich, dann sag bescheid, wenn nicht, hole > gehe zum Anfang. Die Aufgabenstellung liest sich für mich jedenfalls so: 1. Schritt: Übernehme A und B 2. Schritt: Wiederhole 4096 mal A = f(A,B) 3. Schritt: Auswertung von A Daher kann ich nicht nachvollziehen, warum hier 2^512 Berechnungen durchgeführt werden müssen.
Schlumpf schrieb: > warum hier 2^512 Berechnungen durchgeführt werden müssen. Ratestunde: die werden wohl in der f() drin stecken...
Lothar Miller schrieb: > Ratestunde: die werden wohl in der f() drin stecken... Ich befürchte es auch ;-)
Ob jetzt Ansatz 1:Parallel oder 2:Pipelining schneller ist, lässt sich iA nicht sagen. Aber: bei 1 hast Du nach ca. 4096 Schritten für alle Einheiten je ein Ergebnis, d.h. sie müssen dann noch zusammengefasst werden (Nachbearbeitung, die aber einfach sein sollte). Bei 2 hast Du nach 4096 Schritten erst das erste Ergebnis, dann aber je Schritt ein weiteres und kannst je Schritt eine neue Suche starten (keine Nachbearbeitung). Das Beste wird wahrscheinlich sein, beide Ansätze zu implementieren und dann entscheiden, was schneller geht bzw. und auch weniger "Platz" braucht.
2^512: Oben hat der TO was von 512 Bit Wortbreite geschrieben (A,B oder A+B?). Wenn alles systematisch durchsucht werden soll, dann sind's halt 2^512.
Sigi schrieb: > Wenn alles systematisch durchsucht werden soll, > dann sind's halt 2^512. Klar, wenn A und B 512 Bit breit sind und der Algorithmus darin besteht, jede erdenkliche Kombination der Eingänge nach irgendeinem Muster durchzuspielen, dann hast du recht. Aber nachdem der TO darüber nichts verlauten lässt, sondern schreibt, dass er mit A und B "irgendwas" macht und dann das Ergebnis dieses "irgendwas" nach A schiebt, bin ich davon ausgegangen, dass hinter "irgendwas" eine überschaubare mathematische oder logische Funktion steckt, die parallel abgearbeitet werden kann. (z.B. A <= A+B oder sowas in der Art). Darum ja auch meine Bitte an den TO, etwas präziser zu beschreiben, was er vor hat. Denn aufgrund einer sehr allgemeinen Formulierung kann man kaum eine Aussage darüber treffen, welches der cleverste Ansatz wäre.
Solange die Datenbreite der Variablen und die f(A,B) unbekannt sind kann man schlecht etwas sagen. Auch ist noch unklar ob die Konstanten für alle parallelen Einheiten gleich wären. Wenn alles von einer DSP Einheit innerhalb des FPGAs verarbeitet werden kann, braucht er sich nur eine FPGA mit viel DSPs zu kaufen. Vielleicht ist eine Grafikkarte sogar besser für sein Problem geeignet. Ich habe es so verstanden, das er keine 512 Bit Datenbreite hat sondern sein Algo variabel bis zu 2^512 Berechnungen braucht.
wenn er 2^512 berechnungen braucht ist es eh vorei, das könnte nichtmal ein idealer Computer der am thermodynamischen Limit arbeitet schaffen
.. ausserdem braucht man bei 2^512 (grob 10^170) "wie auch immer" Schritten nicht weiter rumzuphilosophieren, ist damit praktisch unlösbar.
Sigi schrieb: > 2^512 > ... > ist damit praktisch > unlösbar. Hehe ;-) gcalctool (Linux Taschenrechner) hat ja sogar einen Scrollbalken fürs Ergebnis - wusste ich noch gar nicht ;-)
Schlumpf schrieb: > "irgendwas" nach A schiebt, bin ich davon ausgegangen, dass hinter > "irgendwas" eine überschaubare mathematische oder logische Funktion > steckt, die parallel abgearbeitet werden kann. (z.B. A <= A+B oder sowas > in der Art). > > Darum ja auch meine Bitte an den TO, etwas präziser zu beschreiben, was > er vor hat. Denn aufgrund einer sehr allgemeinen Formulierung kann man > kaum eine Aussage darüber treffen, welches der cleverste Ansatz wäre. Ich habe "irgendwas" geschrieben, da es an der Stelle ganz egal sein sollte, was passiert. Denn darauf dürfte es da nicht ankommen. Tatsächlich passiert da etwas mehr Mathematik, was ich aber durchaus innerhalb eines Taktes abarbeiten kann. Hans-Georg Lehnard schrieb: > Solange die Datenbreite der Variablen und die f(A,B) unbekannt sind kann > man schlecht etwas sagen. Auch ist noch unklar ob die Konstanten für > alle parallelen Einheiten gleich wären. Okay, im Grunde geht es darum, einen Code zu knacken. Ich habe eine 256Bit lange Zahl (Konstante X) die mit einem 512 Bit langem Schlüssel verschlüsselt wurde und zwar nicht nur ein Mal, sondern 4096 Mal. Also 256 Bit Zahl + (surjektive Funktion) 512 Bit Schlüssel => 256 Bit Zahl, die wieder mit dem 512 Bit Schlüssel verschlüsselt wird. Am Ende habe ich folgendes: Die 256 Bit lange Zahl am Anfang, die in meine Konstante X reinkommt, das errechnete Ergebnis nach den 4096 Verschlüsselungen => mein Y. Gesucht wird der 512 Bit Schlüssel. Theoretisch muss ich alle 512 Bit durchprobieren, um auf den richtigen Schlüssel zu kommen. In der Praxis wird es aber nicht darauf hinauslaufen, dass einfach alle 512 Bit nacheinander ausprobiert werden, sondern dass ein Rechner eine clevere Auswahl trifft.
Mathias Braun schrieb: > Ich habe eine Aufgabe, bei der ich im Worst case 2^512 Berechnungen > durchführen muss. Und jede Berechnung kann ich in 4096 Teile aufteilen. Wenn er die Aufgabe hat, dann bekommt er vom Auftraggeber auch die Zeit und die Rechenkapazität ;)
:
Bearbeitet durch User
Hier bekommst du ein geeignetes Board für deine Experimente: http://www.prodesign-europe.com/proFPGA_Products_quadV7system_overview.html
Kam heute morgen im Radio, dass die Amis an einem "Supercomputer" entwickeln, mit dem sie Verschlüsselungen knacken wollen. Wusste gar nicht, dass die NSA hier über Mikrocontroller.net ihre Ideen holt gg
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.