Forum: FPGA, VHDL & Co. Ein DSP - aber 2 Multiplikationen. David Copperfield?


von Bertram (Gast)


Lesenswert?

Wie realisiert der FPGA eine verkettete Multipliplikation?

Diese nicht-lineare offset-Korrektur benutze ich in einem Xilinx Artix 
mit VHDL, um das oct-signal zu korrigieren:

Wert = Rohdatum * ( 1 + (x*x+3*x)/1024 )

Es sind zwei Multiplikationen enthalten, es wird aber nur 1 DSP-Element 
verbaucht. Kann das jemand erklären? Die Multiplikation mit 3 habe ich 
händisch eingespart, die ist also plausibel. Das X-Quadrat und die 
Gesamt-Mul kann aber nicht eingespart werden.

Das ist der Code:
1
val_xx  <= std_logic_vector( signed (offs) * signed (offs));
2
val_3x  <= std_logic_vector( signed (offs(offs'HIGH) & offs & '0') + signed (offs) );
3
val_is  <= std_logic_vector( signed (val_xx(val_xx'HIGH) & val_xx(val_xx'HIGH) & val_xx(19 downto 10)) + signed (val_3x(11 downto 1)) + 1024);
4
5
oct_do  <= std_logic_vector( signed ('0' & oct) * signed (val_is));


Ich vermute eine Optimierung, es werden allerdings insgesamt nur 180 FFs 
und 205 LUTs in diesem Modul benutzt und die sind durch den Rest 
plausibel. Es wird auch nicht wesentlich weniger, wenn ich die 
Multiplikation rausnehme. Ich habe es testweise auch einmal alleine 
synthetisieren lassen und erhalte dasselbe Ergebnis. Es wird also nichts 
mit was anderem aus anderen Modulen zusammengepackt.

Auch liefert die Synthese schon ohne Implementierung, dass nur 1 DSP 
verwendet wird. Spezielle Optimierungen habe ich nicht eingeschaltet.

Wo steckt die Multiplikation?

Hat es gfs damit zu tun, das nur die dritte Zeile getaktet ist (sieht 
man hier nicht)? Die ersten Zeilen sind ungetaktet ohne Process.

Ist die innere Multiplikation gfs so klein, dass sie doch in LUTs 
verpackt wird? Block-RAMs werden keine aufgeführt.

Wichtigste Info: Die Rechung stimmt und funktioniert. Laut Simulation 
werden alle Signale durch gegeben. Es fehlt nichts und die Korrektur 
funktioniert.

von daniel__m (Gast)


Lesenswert?

Bertram schrieb:
> Ist die innere Multiplikation gfs so klein, dass sie doch in LUTs
> verpackt wird?

Wie breit sind denn die Vectoren (x und Rohdatum=oct)?

PS: Die Formel und der Code passen nicht zusammen. Wo ist z. B. die 
Division?

von Andi (Gast)


Lesenswert?

Ich kenne mich mit Artix nicht aus, aber Cyclone FPGAs können mit einem 
DSP entweder eine 18x18 Bit oder zwei 9x9 Bit Multiplikationen 
implementieren.

Wenn du da also mit 9 Bits rechnest, so werden wahrscheinlich auch bei 
Xilinx die zwei Muls in einen DSP Block verpackt.

von C. A. Rotwang (Gast)


Lesenswert?

Bertram schrieb:

> Wo steckt die Multiplikation?

Mglw. im Zeitmultiplex, zumindest wäre es eine gute möglichkeite mit 
einem Multiblitzer zwei Multiplikationen auszuführen.

> Hat es gfs damit zu tun, das nur die dritte Zeile getaktet ist (sieht
> man hier nicht)? Die ersten Zeilen sind ungetaktet ohne Process.

Bitte den vollständigen code anhängen, wie soll man sonst Pipelining 
oder oversampling erkennen.

Und dann mal mit ein paar basics wie Ressourcenallocation und data flow 
graph vertraut machen:
https://pdfs.semanticscholar.org/1bf7/61ed9a7cb4174852f0e4670dfa4fb95b8424.pdf
https://pdfs.semanticscholar.org/4738/10a42091912f622340e4b8094ec4a64c69cc.pdf

von Markus F. (mfro)


Lesenswert?

Wenn der gezeigte Code in einem Prozess läuft, dann hast Du den, so wie 
ich das sehe - versehentlich oder absichtlich - schon gepipelined.

Die zweite Multiplikation läuft mit dem Ergebnis der ersten aus dem 
vorherigen Prozessdurchlauf, das muss also irgendwo in einem Register 
zwischengespeichert werden. Dann gibt's keinen Grund, nicht dasselbe 
DSP-Element auch für die zweite Multiplikation zu verwenden.

von ich (Gast)


Lesenswert?

Ich würde mal behaupten, dass die x*x Rechnung keinen DSP verwendet. 
Erstens ist Quadrieren eh einfacher als Multiplizieren, und da Du auch 
nur 10-11 oder so Bits des Ergebnisses verwendest müsste das mit recht 
wenigen LUTs realisierbar sein.

Warum schaust Du dir das Ergebnis nicht einfach mal als Schematic an 
wenn du's genau wissen willst?

von daniel__m (Gast)


Lesenswert?

Markus F. schrieb:
> Dann gibt's keinen Grund, nicht dasselbe
> DSP-Element auch für die zweite Multiplikation zu verwenden.

Nicht ohne zusätzliche Beschreibung per Hand, da im 2. Takt ja wieder 
Daten für die erste Multiplikation vorliegen. Diese Beschreibung fehlt 
im o.g. Code.

Es eigentlich nur eine Möglichkeiten, wie nur 1 DSP daraus wird:
Die Bitbreiten sind gering (die Schwelle kennt nur die Synthese) und die 
Multiplikation wird durch LUTs (=Additionen) ersetzt.

ich schrieb:
> Warum schaust Du dir das Ergebnis nicht einfach mal als Schematic an
> wenn du's genau wissen willst?

Würde ich auch machen. Da sieht man recht schnell, was im DSP gerechnet 
wird, und was dann ausserhalb.


daniel__m schrieb:
> PS: Die Formel und der Code passen nicht zusammen. Wo ist z. B. die
> Division?

nehme ich zurück, passt alles.

von Helmut S. (helmuts)


Lesenswert?

Die Artix-FPGAS haben doch fest eingebaute DSP slices(multiplier, 
accumulator). Die tauchen bei der Anzahl benötigter LUTs gar nicht auf. 
Ob die ohne eigenes zutun bei der Synthese verwendet werden weiß ich 
nicht.

von Bertram (Gast)


Lesenswert?

Nochmal genauer: Die Daten kommen durchs FPGA auch wenn nur dieser Modul 
drin ist und die Korrektur funktioniert mit von aussen angelegten Werten 
über den vollen Bereich.

Es ist also kein pipeline oder Speichereffekt. Es geht mir voller 
Bandbreite.

Andi schrieb:
> Ich kenne mich mit Artix nicht aus, aber Cyclone FPGAs können mit einem
> DSP entweder eine 18x18 Bit oder zwei 9x9 Bit Multiplikationen
> implementieren.
Das wäre eine gute Erklärung, haut aber beim Xilinx  nicht hin glaube 
ich. Altera hat in der Tat 9x9 Muls verbaut, die zum doppelten 
zusammengefasst werden. Der Artix hat wie auch der Spartan 18x25 Bit 
festverdrahtete drin. Die kann man nicht teilen, soweit mir bekannt.

Ich habe es nochmals nachgesehen:

Es wird ausdrücklich 1 DSP-Element benutzt.

von Helmut S. (helmuts)


Lesenswert?

Zumindest x*(x+3) geht in einem DSP-slice.

Figure 1-1 auf Seite 9
https://www.xilinx.com/support/documentation/user_guides/ug479_7Series_DSP48E1.pdf

von Chip Inspector (Gast)


Lesenswert?

Bertram schrieb:
> Nochmal genauer: Die Daten kommen durchs FPGA auch wenn nur dieser Modul
> drin ist und die Korrektur funktioniert mit von aussen angelegten Werten
> über den vollen Bereich.
>
> Es ist also kein pipeline oder Speichereffekt. Es geht mir voller
> Bandbreite.

Bevor Du dir nicht im Device view das ge-map-te Design angeschaut oder 
in der Netzliste die Beschaltung des DSP slices angeschaut hast, kannst 
du nichts mit Sicherheit sagen.

http://svenand.blogdrives.com/comments?id=149

von Markus F. (mfro)


Lesenswert?

ich schrieb:
> Ich würde mal behaupten, dass die x*x Rechnung keinen DSP verwendet.
> Erstens ist Quadrieren eh einfacher als Multiplizieren,

Da stell' ich doch mal frech die Frage: wie?

Auf der Suche danach, was denn wohl zu vereinfachen wäre, wenn beide 
Faktoren einer Multiplikation identisch sind, ist mir jedenfalls auf die 
Schnelle nichts Vernünftiges eingefallen.

Eine entsprechende Internetrecherche hat auch nichts zutage gefördert.

von J. S. (engineer) Benutzerseite


Lesenswert?

Bertram schrieb:
> Wo steckt die Multiplikation?

Aus der Formel (19 downto 10) entnehme ich, dass es eine 10 Bit 
Multiplikation ist. Diese als Quadrat führt zu einem sehr einfachen 
Ergebnisvektor, der ins LUTRAM passen könnte. Die Ergebnisterme haben 
einen hohen Identitätsfaktor. Probiere mal,nicht zu quadrieren, sondern 
mit einem anderen variablen Faktor zu multiplizieren. Dann dürfte ein 
weiterer Mul herangezogen werden.

> Hat es gfs damit zu tun, das nur die dritte Zeile getaktet ist (sieht
> man hier nicht)? Die ersten Zeilen sind ungetaktet ohne Process.
Eher nicht, weil der auch über FF-Grenzen hinweg optimieren kann.

Markus F. schrieb:
> Auf der Suche danach, was denn wohl zu vereinfachen wäre, wenn beide
> Faktoren einer Multiplikation identisch sind, ist mir jedenfalls auf die
> Schnelle nichts Vernünftiges eingefallen.
Die Terme sind doch viel einfacher, weil es Lücken in der 
Multiplikationsmatrix gibt. Das kann sehr viel besser zusammengefasst 
werden, als eine Multi mit freien Faktoren. Das zweite Bit fällt z.B. 
komplett global raus:

1*1 =   0.1
2*2 =   1.0
3*3 =  10.1
4*4 = 100.0
5*5 = 110.0

Das sich die Terme in LUts abbilden gibt es auch da auch wieder viele 
Identitäten. Die Anzahl der zu belegenden LUTs, um das alles abzudecken, 
ist viel kleiner. Ich nehme schon an, dass die Synthese das weiss und 
solche x*x direkt in eine LUT abbildet.

von C. A. Rotwang (Gast)


Lesenswert?

Markus F. schrieb:
> ich schrieb:

>> Erstens ist Quadrieren eh einfacher als Multiplizieren,
>
> Da stell' ich doch mal frech die Frage: wie?
>
> Auf der Suche danach, was denn wohl zu vereinfachen wäre, wenn beide
> Faktoren einer Multiplikation identisch sind, ist mir jedenfalls auf die
> Schnelle nichts Vernünftiges eingefallen.
>
> Eine entsprechende Internetrecherche hat auch nichts zutage gefördert.

Wenn dir nach Nachdenken und "Recherche" nichts weiter als dämmliche 
Allerweltsausreden einfallen, wirst Du wohl dumm sterben müssen.

Es sollte doch auf den ersten Blick klar sein das ein Multiplizierer 
array höchstens halb so groß ist, wenn beide Argumente identisch sind, 
da in diesem Fall pro 6er LUT 6 bit Argument statt 3 bit pro Argument 
prozessiert werden.
Auch die Vereinfachung der unteren Resultbits wie y(0) <= x(0) und y(1) 
= 0 ist doch Abiturwissen herleitbar (Binomische Formel) und schließlich 
fördert eine simmple Googlesuch schnell das zu Tage:
http://www.rroij.com/open-access/a-high-speed-and-device-efficient-fpgabased-squaring-circuit.php?aid=42544
(52 LUT im XCV-4 für 32bit Input)

von Markus F. (mfro)


Lesenswert?

Vielen Dank für den Link.

Deine sprachlichen Entgleisungen drumrum darfst Du allerdings gerne 
behalten.

von C. A. Rotwang (Gast)


Lesenswert?

Markus F. schrieb:
> Vielen Dank für den Link.

Bitte.

> Deine sprachlichen Entgleisungen drumrum darfst Du allerdings gerne
> behalten.

Da spricht genau der richtige von sprachlichen Entgleisungen.
Wer hat eine Frage mit zwei völlig unnötigen Abschnitten Marke:  "Ich 
hab mich wirklich angestrengt, musst ihr mir glauben" aufgebläht, um 
sich als Unschuld von Lande darzustellen der man über die Strasse helfen 
muß?!

Mich erinnert dieses Getue um angeblich besonders schwierige Aufgaben 
und völligen Mangel an  freizugänglich Hilfestellungen an die 
Bauernschlaue Taugenichtse die am liebsten abschreiben und andere 
Probleme lösen lassen, als auch nur den Ansatz von nachhaltiger 
Eigeninitiative zu zeigen.

Kannst Du dich jetzt bitte selbst benühen deinen Wissenslücken aktiv 
selbst zu schliessen oder müssen wir weiter sachfremd diskutieren?!

von Markus F. (mfro)


Lesenswert?

C. A. Rotwang schrieb:
> Kannst Du dich jetzt bitte selbst benühen deinen Wissenslücken aktiv
> selbst zu schliessen oder müssen wir weiter sachfremd diskutieren?!

das werde ich wohl tun. Die Frage war eigentlich Teil des Plans...

Das "sachfremde Diskutieren" ist damit für mich aber noch nicht beendet. 
Ich finde es einfach - sagen wir mal - nicht nett, einen einfach als 
Deppen hinzustellen, nur weil ihm die altägyptische Art der 
Multiplikation (s. Link) nicht direkt geläufig ist.

Wenn es in einem Forum nicht mehr möglich ist, Fragen zu einem nicht 
trivialen Thema zu stellen, ohne in der Antwort brüsk mitgegeben zu 
bekommen, wie knalldoof und unnötig die Frage war (und ich habe hier 
durchaus schon blödere Fragen gesehen), dann frage ich mich, wozu das 
Forum eigentlich gut sein soll.

Auch darfst Du mich - natürlich - gerne für einen Idioten halten (wir 
haben ja Meinungsfreiheit), musst dich aber nicht wundern, wenn ich 
Hinweise in der Richtung nicht unkommentiert stehen lasse. Naturgemäss 
bin ich nämlich anderer Meinung (und lasse mir ungern den Mund 
verbieten)...

von Michael W. (Gast)


Lesenswert?

C. A. Rotwang schrieb:
> Wenn dir nach Nachdenken und "Recherche" nichts weiter als dämmliche
> Allerweltsausreden einfallen, wirst Du wohl dumm sterben müssen.
Eine kleine Zwischenfrage an den Herrn, der sich anonym unter dem 
Pseudonym Rotwang verbirgt? Würdest Du auch so reden, wenn Dir dein 
Gesprächspartner gegenüber sitzen würde und mangels Wissen so eine Frage 
stellen würde? Dann würde Ich dich nicht in meinem Team haben wollen.

C. A. Rotwang schrieb:
> Es sollte doch auf den ersten Blick klar sein das ein Multiplizierer
> array höchstens halb so groß ist,
"Auf den ersten Blick" ist mir überhaupt nicht klar, warum ein array nur 
halb so gross sein muss. Was ich auf den ersten Blick sehe ist, dass es 
statt eines arrays nur eine Linie gibt, die besetzt ist, d.h. ein array 
in dem die Ergebnisse stehen, wären nur die Wurzel der Grösse.

Ich hoffe Dir damit geholfen zu haben. Nicht, dass Du am Ende "dumm 
stirbst" :-)

von dfIas (Gast)


Lesenswert?

Helmut S. schrieb:
> Zumindest x*(x+3) geht in einem DSP-slice.
>
> Figure 1-1 auf Seite 9
> 
https://www.xilinx.com/support/documentation/user_guides/ug479_7Series_DSP48E1.pdf

Ob die Synthese das Distributivgesetz auch noch anwenden kann, wenn 
bereits x*x und x*3 fein säuberlich und taktweise getrennt wurden?

von J. S. (engineer) Benutzerseite


Lesenswert?

dfIas schrieb:
> Ob die Synthese das Distributivgesetz auch noch anwenden kann, wenn
> bereits x*x und x*3 fein säuberlich und taktweise getrennt wurden?
Grundsätzlich sind Taktgrenzen diesbezüglich kein Problem. Vivado 
erkennt inzwischen Register gleichen Inhalts sowie Terme gleichen 
Ursprungs und Ziels (=Ergebnis) auch über längere pipeline-Stufen 
hinweg. Das war z.B. in ISE so nicht der Fall.

Der Teil der Gleichung ist aber für die Problemstellung hier nicht im 
Fokus. Der Faktor 3 wurde ja durch eine Addition realisiert.

Es geht um die äußere Multiplikation sowie das X-Quadrat innen. Sonst 
wären es ja auch schon 3 DPSs. In eine LUT umsetzen kann er effektiv nur 
das X-Quadrat und auch nur dann, wenn es klein genug ist, bzw. nur dann 
lohnt es sich. Ich nehme an, die Syntheseeinstellungen hinsichtlich der 
Nutzung auf "auto". Man kann das an der Stelle dahingehend 
durchprobieren, als dass man dies auf z.B. off stellt. Dann werden die 
Multiplizierer komplett in fabric logic gebaut. Mit einer weiteren 
Synthesoption, nämlich der Nutzung der RAMs als Logikspeicher lässt sich 
wiederum verhindern, dass diese Struktur dann in die RAMS wandert. Dann 
kann man schauen, was da an Logik generiert wird, wenn ein MUL ersetzt 
wird. Das ist bei einer Quadratbildung sehr klein und auch noch bei 
einer freien MUL noch deutlich kleiner, als die eigentlich erwartbare 
Matrix, aber trotzdem enorm. Die MULs durch fabric zu ersetzen ist 
ziemlich resourcen- und stromfressend und eine  Notlösung, wenn einem 
2-3 MULs fehlen.

von C. A. Rotwang (Gast)


Lesenswert?

Jürgen S. schrieb:
> Das ist bei einer Quadratbildung sehr klein und auch noch bei
> einer freien MUL noch deutlich kleiner, als die eigentlich erwartbare
> Matrix, aber trotzdem enorm.

Sorry, aber die nicht-quantifizierte Rumeierei mit "deutlich kleiner 
aber immer noch enorm" ist bei der Problem-Analyse nicht unbedingt 
hilfreich.

Oben ist ein Beispiel einer LUT-Implementierung für das Quadrat einer 
32bit-Zahl angegeben, die mit 52 LUT'S auskommt, erwähnt. Das zähle ich 
persönlich nicht mehr unter "enorm", sondern passend zu den 
Gesamt-LUT-Angaben des TO.

Zumal vom TO nicht genannt wird, wieviel bits der Faktor breit ist. Es 
werden 10 bit vermutet, dann ist es wohl sicher eine kleine zweistellige 
Anzahl von LUT's. Ob auch in diesem Fall eine Implementierung mit einem 
Artix-DSP Slice (25x18 multiplier + Adder+einiges drumeherum) die 
bessere Lösung ist, ist IMHO nicht von vornherein sicher. In der UG479 
schlägt Xilinx selbst für kleine Multiplizierer die Benutzung der 
logic-fabric statt der DSP-slices vor.

Falls der TO mal einen synthesefähigen Satz an Designsources hier 
anfügt, könnte man mal verschiedenen Syntse-/Map-Optionen durchspielen.

von daniel__m (Gast)


Lesenswert?

C. A. Rotwang schrieb:

> http://www.rroij.com/open-access/a-high-speed-and-...
> (52 LUT im XCV-4 für 32bit Input)

Gilt das auch für signed? Und ich habe mal die 8x8=16 bit Version via 
copy&paste in eine Testbench gegeben und bekomme komische Ergebnisse. 
Z.b 5x5=17.

von J. S. (engineer) Benutzerseite


Lesenswert?

C. A. Rotwang schrieb:
> Oben ist ein Beispiel einer LUT-Implementierung für das Quadrat einer
> 32bit-Zahl angegeben, die mit 52 LUT'S auskommt, erwähnt. Das zähle ich
> persönlich nicht mehr unter "enorm", sondern passend zu den
> Gesamt-LUT-Angaben des TO.

Meine Aussage bezog sich ausdrücklich auf den allgemeinen Fall einer 
Multiplikation mit irgendeinem freien Faktor. Den speziellen Fall 
desselben Faktors hatten wir ja schon geklärt und auch warum das so 
klein werden kann. Wie ich in einem Nachsatz klarstellte, ist dies eine 
Frage der Auflösung. Ich habe jetzt gerade einen Fall, wo Ich eine 
nichtlineare Potifuktion nachbilde und von 0...1023 auf 0...16383 
abbilde. Der dort verwendete Multiplier wird bei den 
Defaulteinstellungen schon einmal nicht in eine LUT-Struktur übersetzt 
und wenn man es per constraint erzwingt, landet man bei 760 LUTs. Ich 
hatte das ursprünglich für meine Synthdesigns in Erwägung gezogen, um 
MULs zu sparen, später durch eine Anschnittslinearisierung ersetzt. 
Inzwischen bin ich wieder bei der Version MIT Multiplizierer gelandet, 
weil es in den neueren FPGAs keinen Mangel mehr hat.

von C. A. Rotwang (Gast)


Lesenswert?

Jürgen S. schrieb:
> C. A. Rotwang schrieb:
>> Oben ist ein Beispiel einer LUT-Implementierung für das Quadrat einer
>> 32bit-Zahl angegeben, die mit 52 LUT'S auskommt, erwähnt. Das zähle ich
>> persönlich nicht mehr unter "enorm", sondern passend zu den
>> Gesamt-LUT-Angaben des TO.
>
> Meine Aussage bezog sich ausdrücklich auf den allgemeinen Fall einer
> Multiplikation mit irgendeinem freien Faktor.

Da steht aber explizit "bei einer Quadratbildung" (siehe Zitat)- Typo?!

> Den speziellen Fall
> desselben Faktors hatten wir ja schon geklärt und auch warum das so
> klein werden kann.

Da steht "deutlich kleiner, ... aber trotzdem enorm." Das ist ein 
Widerspruch in sich, den ich gern mit konkreten Zahlen ausgeräumt sehen 
möchte.


> Frage der Auflösung. Ich habe jetzt gerade einen Fall, wo Ich eine
> nichtlineare Potifuktion nachbilde und von 0...1023 auf 0...16383
> abbilde. Der dort verwendete Multiplier wird bei den
> Defaulteinstellungen schon einmal nicht in eine LUT-Struktur übersetzt
> und wenn man es per constraint erzwingt, landet man bei 760 LUTs.

also 10bit * 4bit braucht 760 LUT's ?!
oder 10bit*14bit/1024 ??
Welches Fan-In haben die LUT's (4 und 6 sind wohl üblich?). Wurden die 
MUX7 und Mux8 mitbenutztz? Optimierung auf Speed oder Area?
So spontan, scheint mir der LUT-Bedarf suboptimal hoch, wenn für einen 
16*16bit multiplizierer
880 LUT's (BOOTH-multiplier) angegeben werden. BRAM-ROMS können auch zum 
Ersatz einiger LUT's eingesetzt werden. OK, BRAM's hat man auch selten 
frei.

@daniel__m
> Gilt das auch für signed?
Der Artikel bezieht sich wohl auf nichtnegative Zahlen. Es ist IMHO 
überlegenswert ob man signed Faktoren nicht aus Effizenzgründen 
vermeiden sollte, da man das Vorzeichen des Ergebnisses auch 
nachträglich als 2'er komplement einrechnen kann und die meisten(?) 
ADC's das Ergebniss die messwerte auch unsigned ausgeben können.


>)Und ich habe mal die 8x8=16 bit Version via
>copy&paste in eine Testbench gegeben und bekomme komische Ergebnisse.
>Z.b 5x5=17.

Versuch macht klug, der S(7)-Term bei 8x8bit ausdruck scheint in der Tat 
falsch zu sein. Oder das 'and' ist anders gemeint als binäres AND. 
Fehlende Klammern sind wohl nicht der Grund...Muss man sich mal bei 
gelegenheit genauer anschauen, 4x4 bit würde ja für 5**2 ausreichen und 
dort passt der S(7) Term fürs beispiel.

von Duke Scarring (Gast)


Lesenswert?

C. A. Rotwang schrieb:
> nachträglich als 2'er komplement einrechnen kann und die meisten(?)
> ADC's das Ergebniss die messwerte auch unsigned ausgeben können.
Selbst wenn die ADC das nicht können, ist die Umrechnung nur eine 
einzelne Subtraktion, kurz vor dem Ausgang. Wenn für den Verzicht auf 
signed einen kleineren Rechenpfad bekommt, ist das IMHO ok.

Duke

von daniel__m (Gast)


Lesenswert?

Duke Scarring schrieb:
> C. A. Rotwang schrieb:
>> nachträglich als 2'er komplement einrechnen kann und die meisten(?)
>> ADC's das Ergebniss die messwerte auch unsigned ausgeben können.
> Selbst wenn die ADC das nicht können, ist die Umrechnung nur eine
> einzelne Subtraktion, kurz vor dem Ausgang. Wenn für den Verzicht auf
> signed einen kleineren Rechenpfad bekommt, ist das IMHO ok.
>
> Duke

Die Umrechnung von signed auf unsigned ist mir klar, es ging mir nur 
darum, dass die ursprüngliche Gleichung signed's enthält und die 
Umrechnung auch wieder Resourcen bindet.

von Markus F. (mfro)


Lesenswert?

C. A. Rotwang schrieb:
> Oben ist ein Beispiel einer LUT-Implementierung für das Quadrat einer
> 32bit-Zahl angegeben, die mit 52 LUT'S auskommt, erwähnt. Das zähle ich
> persönlich nicht mehr unter "enorm", sondern passend zu den
> Gesamt-LUT-Angaben des TO.

Das Papier habe ich mittlerweile ausführlich studiert. Keine Ahnung, wie 
die das machen, ich bin jedenfalls nicht in der Lage, das auch nur 
ansatzweise praktisch nachzuvollziehen und mittlerweile so weit, die 
Seriösität des Papiers für mich ernsthaft in Frage zu stellen.

Den Algorithmus, denke ich, habe ich verstanden. (M)eine Implementierung 
(für beliebige Vektorbreiten) sieht so aus (und liefert - im Gegensatz 
zur Umsetzung vom freundlichen Inder - das richtige Ergebnis):
1
entity flex_square is
2
    generic
3
    (
4
        WIDTH   : integer := 8
5
    );
6
    port
7
    (
8
        a       : in unsigned(WIDTH - 1 downto 0);
9
        s       : out unsigned(WIDTH * 2 - 1 downto 0)
10
    );
11
end entity flex_square;
12
13
architecture rtl of flex_square is
14
begin
15
    p_calculate : process(all)
16
        variable result     : unsigned(WIDTH * 2 - 1 downto 0);
17
        variable v_left     : unsigned(WIDTH - 1 downto 0);
18
        variable v_right    : unsigned(WIDTH * 2 - 1 downto 0);
19
    begin
20
        result := (others => '0');
21
        v_left := a;
22
        v_right := resize(a, v_right'length);
23
24
        for i in 0 to WIDTH - 1 loop
25
            result := result + resize(v_right * v_left(0 downto 0), v_right'length);
26
            v_left := shift_right(v_left, 1);
27
            v_right := shift_left(v_right, 1);
28
        end loop;
29
30
        s <= result;
31
    end process p_calculate;
32
end architecture rtl;

und braucht 82 Logic Cells auf einem Cyclone III (im Gegensatz zu 99 der 
lpm_mult-Implementierung mit DSP-Verbot). Abgesehen vom fest 
verdrahteten Bit 1 sehe ich keine deutliche Einsparung gegenüber einem 
"normalen" Multiplizierer. Die 32-bittige Multiplikation belegt übrigens 
über 1500 LE's (was - auch wenn es keinen richtigen Umrechnungsfaktor 
dafür gibt - m.E. weit von den genannten 52 Xilinx-LUTs weg ist).

Dem Papier kann ich nicht folgen. Vielleicht bin ich ja wirklich zu 
blöd. Das "Kochrezept" (Table 1) führt für ungerade und gerade 
Bitnummern von 1 bis (2n-1) / 2 und darüber jeweils eine eigene 
Vorschrift an, die ich in den Beispielen allerdings nicht nachvollziehen 
kann.

Kurz: wenn die das wirklich so hingekriegt haben, würde ich gerne 
wissen, wie.

: Bearbeitet durch User
von C. A. Rotwang (Gast)


Lesenswert?

Markus F. schrieb:

> Abgesehen vom fest
> verdrahteten Bit 1 sehe ich keine deutliche Einsparung gegenüber einem
> "normalen" Multiplizierer.

Also ich sehe da deutlich mehr Einsparungen:

1) Nicht nur eins sondern beide lsb sind festverdrahtet:
y_0 = x_0
y_1 = 0

Das folgt aus dem Ansatz für gerade und ungerade Argumente:
(2*n)**2  = 4*n**2             -> das Quadrat einer geraden Zahl ist 
durch 4 teilbar
(2*n+1)**2  = 4*n**2 + 2*n +1  -> das Quadrat einer ungerade Zahl ist 
durch 4  mit Rest 1 teilbar


2) Die Anzahl der logischen Gleichungen  ist zwar gleich, aber  höchsten 
von halben FanIn:

Multipliaktion  y = x*z

y_0  = f_0(x_0,z_0)               --2'er Input

y_1  = f_1(x_0,z_0,x_1,z_1 )      --4'er Input

y_2  = f_2(x_0,z_0,x_1,z_1,x_2,z_2 )      --6'er Input

...

Quadrierung  y = x*x

y_0  = x_0                     --Draht

y_1  = 0                       --Draht

y_2  = f_2(x_0,x_1,x_2)      --3'er Input

y_3  = f_3(x_0,x_1,x_2,x_3)  --4'er Input
...

Je nach Architektur sind 4'er oder 6 LUT's vorhanden und meist noch 
dedizierte Multiplexer zu einfachen Realisierung von logischen 
Gleichungen mit 5 und 6 resp 7 oder 8 Eingängen:

xapp466 
https://www.xilinx.com/support/documentation/application_notes/xapp466.pdf
XAPP522 
http://s.eeweb.com/articles/2012/09/27/multiplexer-design-techniques-for-datapath-performance-1348763550.pdf

Für die ISE musste man dem mapper sagen, das er diese Multiplexer 
benutzen soll.
Für eine 8bit Quadrierung braucht es also beim Artix (6'er LUT) ohne 
weitere logische Optimierung im Worst case: 0 + 0 + 1 + 1 + 1 + 1 + 2 + 
4 -> 10 LUT's. Etwa der selbe Aufwand ist bereits für eine 4x4 
Multiplikation zu erwarten.

3)
Quadrate höhere bitanzahl lassen sich auf Quadrate, Produkte und Summe 
niedrigerer bitzahl zurückführen. Beispiel im Dezimalsystem:

79**2 = 7*7*100 + 2*7*9 + 9*9

-> damit ist das Quadrat einer zweistelligen Zahl auf die Produkte von 
einstelligen Zahlen zurückgeführt. Analoges gilt für das Binärsystem, 
auch hier kann eine beispielsweise 16bit Quadrierung (logische 
Gleichungen mit hohen FanIn dieviele LUT's benötigen) auf 
Produkte/Quadrate von 8 bit Zahlen zurückgeführt werden die sich 
wesentlich kleiner mit LUT's darstellen lassen.

Der "Trick" besteht eben darin, keine "SHIFT and ADD" Stufenstruktur 
aufzubauen, sondern für jedes Produkt die logische Gleichungen bezogen 
auf die Ausgangsbits aufzustellen.

--> Soweit meine Überlegungen, warum eine Quadrierung wesentlich kleiner 
sein muss als ein beliebiges Produkt bei gleicher Bitbreite.

Ich halte also die Angaben aus dem Paper weiterhin für nicht ganz 
unrealistisch, auch wenn ich (noch) nicht sagen kann, warum einige Terme 
wohl falsch oder zumindest missverständlich notiert sind.

von C. A. Rotwang (Gast)


Lesenswert?

Da noch ne ältere Diskussion, bei der noch ein paar Literaturstellen 
genannt werden:
Beitrag "Kann man quadrieren effizienter implementieren als multiplizieren?"

von J. S. (engineer) Benutzerseite


Lesenswert?

C. A. Rotwang schrieb:
> Da steht "deutlich kleiner, ... aber trotzdem enorm." Das ist ein
> Widerspruch in sich, den ich gern mit konkreten Zahlen ausgeräumt sehen
> möchte.

Bei "ernorm" hatte ich so ein wenig meine Anwendungen im Auge, wo ich 
mit 24 Bit Audio Daten arbeite. Der Unterschied zeigt sich qudratisch 
mit der Bit-Tiefe. Zudem galt das Beispiel für ~200MHz. Da müssen eben 
einige FFs reingepackt werden und die Terme können nicht so gut 
optimiert werden. Für geringere Frequenzen geht das kompakter.

Bei den hiesigen Zahlen sähe es so aus:

a*b als 10 Bit in LUT: 111
a*a als 10 Bit in LUT:  90

a*b als 16 Bit in LUT: 292
a*a als 16 Bit in LUT: 261

a*b als 24 Bit in LUT: 626
a*a als 24 Bit in LUT: 575

Gilt für 100MHz mit einem Wrapper, dass die Daten auch durch das FPGA 
kommen.


Ich habe auch mal das o.g. Konzept mit area optmization synthetisiert:

a*a als 10 Bit in LUT:  97
a*a als 16 Bit in LUT: 236
a*a als 24 Bit in LUT: 558

Bringt also was (bis auf den Fall der 10 Bit, warum immer.) Für hohe 
Frequenzen scheidet es aber aus, bzw man muss Register drübergiessen.
Müsste man mal genauer untersuchen, ob man da bei gleichen Verhältnissen 
wirklich relevant was spart. Dann könnte man einen kleinen 
Quadrierungs-Core verwenden, statt ein a*a. Es liessen sich sicher 
Anwendungen identifizieren, wo man trotz der Verfügbarkeit von MULs in 
heutigen FPGAs selbige sparen möchte und dann mit weniger resourcen 
rauskommt.

Die Frage ist allerdings, wie sich das abbildet, wenn Terme mit weiterer 
Schaltung zusammengefasst werden, denn die Ergebnisse einer MUL werden 
ja weiterverarbeitet. Vor allem werden bei vielen Multiplikationen auch 
Skalierungen verwendet und unter Bits wieder abgeschnitten oder vorher 
abgeschnitten und progressiv gerundet. Dann fallen die Unterschieder 
kleiner aus.

Interessant ist es aber in jedem Fall. Ich hätte jetzt erwartet, dass 
Xilinx da ein optimales Quadrat parat hat.

Was ich mir mal ansehen wollte, wäre die "indische" Lösung von weiter 
oben, aber die Seite lädt irgendwie nicht.

von C. A. Rotwang (Gast)


Lesenswert?

C. A. Rotwang schrieb:

> 3)
> Quadrate höhere bitanzahl lassen sich auf Quadrate, Produkte und Summe
> niedrigerer bitzahl zurückführen. Beispiel im Dezimalsystem:
>
> 79**2 = 7*7*100 + 2*7*9 + 9*9

Sorry,Typo:
79**2 = 70 + 9)**2
      = 7*7*10*10 + 2*7*10*9 + 9*9

ändert aber nichts an der Grundaussage, das Quadrate zweistelliger 
Dezimalzahlen auf das kleine Einmaleins rückführbar sind. Bei Ganzen 
Zehnern muss bekanntlich die = in der Einserposition nicht wirklich 
durch einen Multiplikator geschubst werden. Das selbe Verfahren sollte 
man bei Binärquadraten anwenden können um die LUT-fressenden 
Logikgleichungen mit hohen FanIn auf wesentlich kleiner implementierbare 
Logigleichungen mit kleinen FAN-In rückzuführen.

von J. S. (engineer) Benutzerseite


Lesenswert?

C. A. Rotwang schrieb:

> Quadrate höhere bitanzahl lassen sich auf Quadrate, Produkte und Summe
> niedrigerer bitzahl zurückführen. Beispiel im Dezimalsystem:
>
> 79**2 = 7*7*100 + 2*7*9 + 9*9
>
> -> damit ist das Quadrat einer zweistelligen Zahl auf die Produkte von
> einstelligen Zahlen zurückgeführt. Analoges gilt für das Binärsystem,

Das ist ja alles nichts Neues. Die Frage ist nur, ob das eine echte 
Vereinfachung ist und in welche Richtung. Weniger FPGA-Fläche ist sicher 
ein Punkt, um Leistung zu sparen. Praktisch muss bei der Bewertung aber 
auch das erzielbare Tempo mit in Betracht gezogen werden und da sehe ich 
bei den Vereinfachungen sehr schnell Probleme. Um das effektiv zu 
nutzen, müssten lokal im FPGA mehrere simple Quadrierer und Teilterme 
realisiert werden, was wenig Sinn macht. Das alles lokal in fabric 
aufzubauen, ist meistens nicht zielführend.

Ich denke, dass solche Optimierungen für AISCs interessant sein könnten.
Man darf aber davon ausgehen, dass das bereits intensivst genutzt wird.

Interessant wäre auch mal, was ein alternativer Synthesizer aus den 
Termen macht. Ein früherer Vergleich von Synplify und XST lieferte in 
gemischt Mathematisch-Kombinatorischen designs regelmässig um 10% 
kleinere Ergebnisse.

von C. A. Rotwang (Gast)


Lesenswert?

Jürgen S. schrieb:

> Interessant ist es aber in jedem Fall. Ich hätte jetzt erwartet, dass
> Xilinx da ein optimales Quadrat parat hat.

Naja, ich hab inzwischen gelern, das "Optimierung" von Computertools oft 
nru eine "Verbesserung" ist, aber so gut wie nie "optimal".

Und vielleicht ist eben Xilinx auch der meinung das man lieber die 
Xilinx-FPGA's mit vielen Multiplizierern kaufen sollte, als die alten 
Chips weiter auszulutschen ...
Vielleicht steckt ja das optimale Quadrat in den Tools die Xilinx nicht 
mehr oder nie verkaufte - die anderen Synthesetool Hersteller wollen 
schliesslich auch leben.

> Was ich mir mal ansehen wollte, wäre die "indische" Lösung von weiter
> oben, aber die Seite lädt irgendwie nicht.

Du meinst die altägyptische Methode die von einem indischen Autor 
beschrieben wird?! Hier ein anderer Link:
http://www.ijareeie.com/upload/2013/november/28_A%20High.pdf

von C. A. Rotwang (Gast)


Lesenswert?

Jürgen S. schrieb:
> C. A. Rotwang schrieb:

>> -> damit ist das Quadrat einer zweistelligen Zahl auf die Produkte von
>> einstelligen Zahlen zurückgeführt. Analoges gilt für das Binärsystem,
>
> Das ist ja alles nichts Neues. Die Frage ist nur, ob das eine echte
> Vereinfachung ist und in welche Richtung.

IMHO ist der Ersatz einer Logiglichung mit 16 Inputs, die man in einem 
64kbit ROM nachbilden kann, durch drei Logikgleichung mit 8 Inputs die 
mit je 16 4'er LUT#s und zwei addern nachgestellt werden kann, eine 
deutliche Vereinfachung. Eine 4'er LUT fasst grad mal 16bit.

> Weniger FPGA-Fläche ist sicher
> ein Punkt, um Leistung zu sparen. Praktisch muss bei der Bewertung aber
> auch das erzielbare Tempo mit in Betracht gezogen werden und da sehe ich
> bei den Vereinfachungen sehr schnell Probleme.
Das Paper gibt für einen V4 15ns bei 32bit quadrat an. Selbst wenn es 
eine mikrosekunde dauert, für die angesprochene De-Linearisierung eines 
Potentiometers ist das doch schnell genug?!

von Markus F. (mfro)


Lesenswert?

C. A. Rotwang schrieb:
> Versuch macht klug, der S(7)-Term bei 8x8bit ausdruck scheint in der Tat
> falsch zu sein. Oder das 'and' ist anders gemeint als binäres AND.
> Fehlende Klammern sind wohl nicht der Grund...Muss man sich mal bei
> gelegenheit genauer anschauen, 4x4 bit würde ja für 5**2 ausreichen und
> dort passt der S(7) Term fürs beispiel.

Warum s(7)?

Das Ergebnis wird ab 5 x 5 verkehrt (17/10001 statt 25/11001). Also ist 
doch der Term für s(3) schon falsch?

Übrigens liefert auch das 4x4 Bit Beispiel bereits falsche Ergebnisse.

von J. S. (engineer) Benutzerseite


Lesenswert?

C. A. Rotwang schrieb:
> IMHO ist der Ersatz einer Logiglichung mit 16 Inputs, die man in einem
> 64kbit ROM nachbilden kann, durch drei Logikgleichung mit 8 Inputs die
> mit je 16 4'er LUT#s und zwei addern nachgestellt werden kann,
Naja, das ist ja was ich meine: Elementare Mathe. Die Frage ist 
eigentlich nur, wie schnell eine solche Struktur ist und wie schlau die 
tools sind, bei ausreichend Platz im Zeitfenster darauf zurückzugreifen.

Das Beispiel vom Xilinx zeigt, dass es bei X4 wohl nicht klappt. Das ist 
durchaus bemerkenswert. Allerdings nutzt es nur bei schnellen 
8Bit-Rechnungen, weil die anderen rasch zu groß werden.

C. A. Rotwang schrieb:
> Das Paper gibt für einen V4 15ns bei 32bit quadrat an. Selbst wenn es
> eine mikrosekunde dauert, für die angesprochene De-Linearisierung eines
> Potentiometers ist das doch schnell genug?!

Ja für das Potentiometerbeispiel sicher. Ich habe aber noch mehr 
x-Quadrate. Praktisch in jedem Synthesemodul 3..5 Stk. und die laufen 
mit voller Taktfrequenz. Wie gesagt, baue ich ja schon seit Jahren mit 
dem Zeug herum und probiere allenthalben, was einzusparen. Früher in 
Zeiten des chronischen Multipliermangels war das ausgeprägter.

Ich habe Quadrate auch schon mit Pseudo-Linearisierung nachgebildet: Man 
baut abschnittsweise Geraden, die genau den Wert bringen, der nach einem 
MUL mit Abschneiden der neuen Stellen (bei x*2 Quadrat) auch herauskäme, 
setzt das Bit1 auf 0 und tooglt das Bit0. Das stimmt exakt. Das o.g. 
Beispiel mit dem logarythmisierten Poti ist nochmal einen Faktor 2-4 
gröber, reichte aber.


Was man auch nochmal ansehen könnte, wäre eine ausdrückliche Lösung für 
X4.

Die X3 lässt aus naheliegenden Gründen weniger Chancen zur Optimierung 
zu, aber bei X4 müsste was gehen.
Gefühlt hätte ich gedacht, dass das Quadrat der Ersparnis möglich sein 
sollte.

Das kriege ich aber aus der Xilinx-Synthese momentant nicht raus:

a*b*c*d mit 16 Bit = 64Bit : 1876 LUTs
a*a*a*a mit 16 Bit = 64Bit : 1843 LUTs

Beides über physische Resynthese.

von Markus F. (mfro)


Lesenswert?

Markus F. schrieb:
> Das Ergebnis wird ab 5 x 5 verkehrt (17/10001 statt 25/11001). Also ist
> doch der Term für s(3) schon falsch?

... und der ist auch falsch. Da fehlt die (kompliziertere) Hälfte.

Das Paper berücksichtigt anscheinend nicht, dass bei der 
"Bauernmultiplikation" an dieser Stelle bei der Addition ein Carry 
durchgeschoben werden kann/muss. Und genau das passiert eben bei 5*5 zum 
ersten Mal.

Fazit: das Paper ist Mist. Und die Zahlen dann ja wohl auch.

Womit wir wieder am Anfang wären...

von Bertram (Gast)


Lesenswert?

Zunächst einmal Danke für alle Diskutanten und ihre z.T. wertvollen 
Vorschläge und Ideen. Hätte gar nicht gedacht, das sich das so 
entwickeln kann. Ich bin jetzt auch der Überzeugung, dass der 
inferrierte Multiplizier in diesem Fall einfach als Tabelle gebaut wird.

Ich habe mich jetzt weger der Sache mehr damit befasst und nehme 
interessiert zur Kenntnis, dass das doch sehr hübsch klein sein kann.

Wobei:

Markus F. schrieb:
> Fazit: das Paper ist Mist. Und die Zahlen dann ja wohl auch.
> Womit wir wieder am Anfang wären...

.. wie so Vieles, was aus Indien und vergleichbaren Destinationen kommt. 
Den Kommentar kann man mal bringen glaube ich. Entweder bauen sie was 
nach, was es schon gibt, oder sie pfuschen.

Da ist es beruhigend zu sehen, dass es noch Leute gibt, die solche 
Pamphlete hinterfragen und zerpflücken.

Weiter so!

von T.U.Darmstadt (Gast)


Lesenswert?

C. A. Rotwang schrieb:
> Quadrate höhere bitanzahl lassen sich auf Quadrate, Produkte und Summe
> niedrigerer bitzahl zurückführen. Beispiel im Dezimalsystem:
>
> 79**2 = 7*7*100 + 2*7*9 + 9*9

Das erfordert aber die Kenntnis des einen Faktors und dessen Aufbaus. 
Wäre also eine Sonderlösung. -> konstanter Koeffizient.

von C. A. Rotwang (Gast)


Lesenswert?

Thomas U. schrieb:
> C. A. Rotwang schrieb:
>> Quadrate höhere bitanzahl lassen sich auf Quadrate, Produkte und Summe
>> niedrigerer bitzahl zurückführen. Beispiel im Dezimalsystem:
>>
>> 79**2 = 7*7*100 + 2*7*9 + 9*9
>
> Das erfordert aber die Kenntnis des einen Faktors und dessen Aufbaus.
> Wäre also eine Sonderlösung. -> konstanter Koeffizient.

???
Ich kann dieser Argumentation nicht im Geringsten folgen.
Weder macht die Zerlegung des Argumentes in zwei Summanden die nach der 
Biomialformel quadriert werden konstante Koeffizienten nötig, noch ist 
das Sonderfall der Multiplikation.
Falsches Zitat gewählt?

Die Zerlegung zeigt lediglich auf, wie man den quadratisch steigenden 
Aufwand durch zunehmende Bitbreite  beschränken kann, indem man das 
Argument in zwei mit halber Bitbreite aufspaltet, die auch besser in das 
FAN-IN der FPGA Grundelemente passt. Die "üblichen" "bit-slice" 
ASIC-Implementierungen nehmen darauf keine Rücksicht.

von Markus F. (mfro)


Lesenswert?

C. A. Rotwang schrieb:
> Die Zerlegung zeigt lediglich auf, wie man den quadratisch steigenden
> Aufwand durch zunehmende Bitbreite  beschränken kann, indem man das
> Argument in zwei mit halber Bitbreite aufspaltet, die auch besser in das
> FAN-IN der FPGA Grundelemente passt. Die "üblichen" "bit-slice"
> ASIC-Implementierungen nehmen darauf keine Rücksicht.

Mir scheint, Du versuchst, den Job der Synthesetools zu machen.

Die sollten aber doch wohl selbst am besten wissen, wie die interne 
Struktur des jeweiligen Ziel-FPGAs aussieht und - abhängig davon (und 
von der gewählten Optimierungsstrategie) - die "breite" oder "tiefe" 
Lösung wählen?

Wahrscheinlich sollten wir hier auch nicht die (mittlerweile ja 
korrigierte) falsche Rechnung mitschleppen. Richtig heisst es ja:

79 ** 2 = 7*7*100 + 2*7*10*9 + 9*9

von C. A. Rotwang (Gast)


Lesenswert?

Markus F. schrieb:
> C. A. Rotwang schrieb:

> Mir scheint, Du versuchst, den Job der Synthesetools zu machen.
>
> Die sollten aber doch wohl selbst am besten wissen, wie die interne
> Struktur des jeweiligen Ziel-FPGAs aussieht und - abhängig davon (und
> von der gewählten Optimierungsstrategie) - die "breite" oder "tiefe"
> Lösung wählen?

Mir scheint "die Synthesetools machen da ihren Job nicht" und viele User 
glauben blind, das Ergebnis eines, vom Marketing als "optimierendes 
Synthesetool" proklamierten, aber prinzipiell dummen und unwissenden 
tool wäre "Optimal".

Die Synthesetools setzen primär die Vorgaben des VHDL-codes so um, das 
sie mathematisch richtig sind und können Vereinfachungsmöglichkeiten 
nicht "sehen", wenn der designer diese nicht explizit im code hinterlegt 
hat. So wird ein synthesetool eher nicht prüfen und erkennen ob beide 
Faktoren identisch sind und man daher keine Multiplizier- sondern ein 
Quadrier-Algorithmus inferieren sollte.

So wie auch nicht zu erwarten ist, das  256*x durch ein Barellshifter 
oder SRL16 Makro ersetzt wird, insbesonders wenn an des produkt noch 
unnötige Reset-bedingungen geknüpft sind. Compiler besitzen keine 
Intelligenz, die sie selbstständig erkennen lässt das eine 
Multiplikation mit 2**n durch Shift ersetzbar ist, das muss der 
Compiler-Programmier extra als Sonderfall einprogrammieren. 
Synthesetools sind auch heute noch keine Menschen mit mehrjährigen 
Hochschulbildung und Berufspraxis.

Nach eigener Abschätzung und nach den Zahlen im zumindest partiell 
inkorrekten Paper  aus Indien (das auch den Resourcenbedarf nach 
andernen hoffentlich korrekten Quadrier-algos) nennt ist eine deutliche 
höhere Reduktion an LUT's erwartbar als die bisher genannten 
Syntheseergebnisse.

Es ist  an jedem selbst zu entscheiden, ob man eher der Praxis eines 
"dummen" tools  als der einer mathematisch fundierten 
Ressourcenabschätzung sein Vertrauen schenken sollte.

von Markus F. (mfro)


Lesenswert?

C. A. Rotwang schrieb:
> Nach eigener Abschätzung und nach den Zahlen im zumindest partiell
> inkorrekten Paper  aus Indien (das auch den Resourcenbedarf nach
> andernen hoffentlich korrekten Quadrier-algos) nennt ist eine deutliche
> höhere Reduktion an LUT's erwartbar als die bisher genannten
> Syntheseergebnisse.

den Beweis dafür (i.e., dass sich deine Abschätzung tatsächlich im 
Ressourcenbedarf der Praxis real wiederfindet) bist Du allerdings 
bislang - zumnidest soweit ich erkennen kann - schuldig geblieben.

M.E. müssen Synthesetools in der Lage sein, komplexe Ausdrücke in 
innerhalb der beschränkten Funktionalität ihrer Struktur abbildbare 
Teilausdrücke möglichst optimal zerlegen zu können. Genau das ist doch 
ihre Hauptaufgabe.

Mag sein, dass das ein oder andere Tool da (noch) nicht (oder nicht 
immer) optimal vorgeht, aber 1500+ LUTs (mittlerweile mit ISE 
nachgestellt) gegenüber 52 (m.E. ziemlich aus der Luft gegriffenen) LUTs 
für eine 32x32 Bit-Multiplikation sind eine Hausnummer, die einen realen 
Beweis verdient hätte.

Über das indische Paper breiten wir ansonsten lieber mal den Mantel des 
Schweigens...

von Weltbester FPGA-Pongo (Gast)


Lesenswert?

C. A. Rotwang schrieb:
> Die Synthesetools setzen primär die Vorgaben des VHDL-codes so um, das
> sie mathematisch richtig sind und können Vereinfachungsmöglichkeiten
> nicht "sehen", wenn der designer diese nicht explizit im code hinterlegt
> hat.

Das stimmt so nur bei dem Schritt der Umsetzung von VHDL in die Xilinx 
Netzliste und ihren RTL-Sichtweise mit Addieren und Multiplizieren, 
Multiplexern und anderem. Weiter unten, wenn es auf die LUTs geht 
zerbröseln die in einzelne Gleichungen und dort können sehr wohl 
Vereinfachungen gefunden werden. Wenn sich z.B. bei manchen Signalen 
nichts tut, fallen die raus. Das gilt selbtverständlich auch für Stränge 
durch einen LUT-MUX und LUT-MUL.

Es kommt nur praktisch kaum vor, weil hier aus guten Gründen echte 
Multiplizier benutzt werden und sich da nichts mehr zum Optimieren 
anbietet.

Man könnte auch die Frage stellen, warum Xilnx nicht erkennt, dass eine 
Multiplikation sehr langsam ist und dann einfach durch eine sequenzielle 
Integration / Addition ersetzt. Die sähe so ähnlich aus, wie das was 
wieter oben eingeworfen wurde, arbeitet dann eben im FPGA.

von Markus F. (mfro)


Lesenswert?

Wenn man übrigens statt alt-ägyptisch nach der guten, alten Schulmethode
1
79 x 79
2
-------
3
   553
4
    711
5
=======
6
   6241

quadriert, kommt man für's 32x32-Bit Quadrieren mit etwa 2/3 (972) der 
LEs, aus:
1
library ieee;
2
use ieee.numeric_std.all;
3
use ieee.std_logic_1164.all;
4
5
entity simple_square is
6
    generic
7
    (
8
        WIDTH       : integer := 32
9
    );
10
    port
11
    (
12
        fact        : in unsigned(WIDTH - 1 downto 0);
13
        square      : out unsigned(WIDTH * 2 - 1 downto 0)
14
    );
15
end entity simple_square;
16
17
architecture rtl of simple_square is
18
begin
19
    p_square : process(all)
20
        variable res    : unsigned(square'range);
21
    begin
22
        res := (others => '0');
23
        for i in WIDTH - 1 downto 0 loop
24
            res := res + shift_left(fact * fact(i downto i), i);
25
        end loop;
26
        square <= res;
27
    end process p_square;
28
end architecture rtl;

von daniel__m (Gast)


Lesenswert?

Markus F. schrieb:
> for i in WIDTH - 1 downto 0 loop
>             res := res + shift_left(fact * fact(i downto i), i);
>         end loop;

das sind dann ~31 addierer kombinatorisch? Ich vermute, Fmax ist eher 
gering, dann doch lieber ein DSP, wenn ich pro Takt ein Ergebnis 
benötige (II=1).

von Markus F. (mfro)


Lesenswert?

Korrekt, schnell ist das nicht. Schafft gerade mal 20 MHz.

von J. S. (engineer) Benutzerseite


Lesenswert?

daniel__m schrieb:
> dann doch lieber ein DSP, wenn ich pro Takt ein Ergebnis

Der Tenor des threads war aber, "ohne einen DSP geht es auch". Das ist 
es ja, was hier "erforscht" wird. :-)

Ich finde das im Übrigen auch nach wie vor interessant, gerade für die 
kleinen Multiplikationen. Wie schon angedeutet, werden die 
Multiplikationsergebnisse ja auch irgendwo weiterverwendet und die 
dortige Kombinatorik kann u.U. Teilterme mitbenutzen.

Markus F. schrieb:
> Korrekt, schnell ist das nicht. Schafft gerade mal 20 MHz.
Kannst mal FFs ausgiessen und optimieren lassen, um es auf 200MHz zu 
bringen und mit den Xilinx-Ergebnissen von meinem Beitrag oben 
vergleichen.

von Markus F. (mfro)


Lesenswert?

Jürgen S. schrieb:
> Kannst mal FFs ausgiessen und optimieren lassen, um es auf 200MHz zu
> bringen und mit den Xilinx-Ergebnissen von meinem Beitrag oben
> vergleichen.

Die Additionen stumpf in 32 Pipeline-Steps verpackt: 185 MHz (mit 
entsprechender Latenz, natürlich). Etwa 1600 LEs.

von C. A. Rotwang (Gast)


Lesenswert?

Markus F. schrieb:
> quadriert, kommt man für's 32x32-Bit Quadrieren mit etwa 2/3 (972) der
> LEs, aus:
..
> Die Additionen stumpf in 32 Pipeline-Steps verpackt: 185 MHz (mit
> entsprechender Latenz, natürlich). Etwa 1600 LEs.

Also" ohne FF" 972 LE und "mit FF 1600LE" ?Das hört sich doch stark nach 
einer ungünstiger Mapper/Synthese-Option an. da zu jedem LE LUT's und FF 
gehören?

Zumal oben von 1500+ LE gesprochen wird:

>Mag sein, dass das ein oder andere Tool da (noch) nicht (oder nicht
>immer) optimal vorgeht, aber 1500+ LUTs (mittlerweile mit ISE
>nachgestellt)

Das würde wenigstens halbwegs den Zahlen von Jürgen S. entsprechen der 
bei 8/16/24 bits Squarer eine LUT-Differenz im zweistelligen bereich 
ermittelt hat.

Aber richtig vergleichbar werden die Zahlen erst, wenn die Bitbreite 
explizit genannt wird (bei Markus steht zu vermuten das es 32 bit sind, 
der TO hat sich immer noch nicht geäussert mit welcher Bitbreite er 
rechnet.


Nennt doch bitte die Bitbreite und den Typ der Faktoren 
(signed/Unsigned) und stellt die Ergebnisse bitte in einer Tabelle 
gegenüber. Besser, den Code und Auszüge der Logs die die Einstellungen 
nennen in eine Datei packen und Anhängen.

PS:
Ich halte weiterhin an der Abschätzung fest das ein squarer (bsp. 32 
bit-Input) bei gleicher Bitbreitehöchstens halb so groß wie ein 
Multiplizierer mit unterschiedlichen Faktoren (also bspw. 2 a 32 bit) 
aber gleich breiten Eingangsgrößen ist, da ich bisher keine 
substantiellen Gegenargumente gelesen habe und andere Literaturstellen 
die gleiche Abschätzung treffen.

An die die mit festen Glauben an die Logigoptimierung sei folgendes 
gerichtet:

1) Logik-reduktion wie "Quine-McCluskey" ist ein NP-hartes Problem, der 
Lösungsaufwand steigt also expotentiell. Wenn also eine Logikgleichung 
mit FanIn 10 noch flott auf kleine LUT's optimierbar ist, ist bei 
doppelter Breite (20bit statt 10) der Aufwand schon mal bei Faktor 1000 
angekommen.

2)Die Logikoptimierung ist, wenn sich wirklich die optimale Lösung 
finden soll, ein brute Force verfahren, es müssen alle Kombinationen der 
Eingangsbits durchgerechnet werden. So macht das auch Karnaugh. Es 
erkennt nicht wirklich daß sich die Optimierung ergibt da nur noch die 
beiden bitweisen Kombis "00" und "11" im Def.-bereich liegen und nicht 
"00" "01" "10" und "11".

3)
Ausschlagebend bei den FPGA's im Gegensatz zu einen (reinen" 
"Gate-Array"-ASIC ist das mapping auf die verschiedenen Resourcen BRAM, 
LUT, Carry-Chain, Carry-Mux, IO-FF. Eine Logicreduktion ersetzt viele 
LUT's durch weniger LUT's, falls die logischen Gleichungen allein auf 
die LUT's gemappt werden. Gesucht wird aber eine Lösung die die formale 
Beschreibung und zuhilfe Nahme aller Resourcen wie auch Carry-chains 
etc. auf die jeweilige FPGA-struktur abbildet. Ich bezweifle daher das 
die Logikoptimierung der Tools bspw. in der Lage ist, die Berechnung des 
Lsb eines Squares auf zugrundeliegenden Grössergleich-Vergleichmit einer 
Konstanten zurückzuführen, der sich simple mit einem Subtractor 
realisiern lässt. ("das höchste Bit eines Quadrates ist '1' wenn der 
Eingang grösser gleich der Quadratwurzel aus 2**(2*n-1) ist"; bei 24 bit 
also ein 24bit-vergleich x >= 11863283; statt umfänglicher 
Logiggleichung mit fanIn 48 wie bei einem Multiplizierer.

von J. S. (engineer) Benutzerseite


Lesenswert?

Markus F. schrieb:
> Die Additionen stumpf in 32 Pipeline-Steps verpackt: 185 MHz (mit
> entsprechender Latenz, natürlich). Etwa 1600 LEs.

Das bringt ja nichts. Dann haben wir ja wieder die "enorme" Zahl von 
LUTs/LEs die oben zur Sprache kamen :-)

Ich dachte mehr daran, hinten im Design FFs reinzupacken und Dr. Vivado 
oder in deinem Fall Herrn Quartus entscheiden zu lassen, wieviele er 
davon in die arithmetische Struktur zurück schiebt. Ich denke, es liefe 
auf jede zweite Stufe hinaus, unten vielleicht auf jede Dritte.

von Bertram (Gast)


Lesenswert?

Wo genau kann ich die benötigten Elemente im FPGA erkennen? Ich habe zum 
Vergleich einen einfachen Multiplizierer benutzt, bei der Ausgabe von 
Xilinx siehe ich aber nur:

DSP     1   240
IO     57   210
BUFG    1    32

Die Verschaltung ist aber : Eingänge über Takt auf Signale, Signale auf 
Multiplikation, Ausgang über Takt auf IO-Pins.

Er werden keine FFs angezeigt.

von Markus F. (mfro)


Lesenswert?

Bertram schrieb:
> DSP     1   240

Dein Synthesetool ist schlau und hat offensichtlich gemerkt, daß Du was 
multiplizieren willst ;).

Wenn Du die Multiplikation in LUTs ausprobieren willst, musst Du ihm 
irgendwie verbieten, DSP-Elemente zu verwenden.

von Bertram (Gast)


Lesenswert?

Markus F. schrieb:
> Dein Synthesetool ist schlau und hat offensichtlich gemerkt, daß Du was
> multiplizieren willst ;).

In diesem Fall hatte ich es ausdrücklich zugelassen. Es wurde auch nur 
eine einzige Multiplikatino benutzt. Mich wundert nur, wo die FlipFlops 
sind, die im Design drin sind. Es müssten vor und nach dem 
Multiplizierer jeweils welche sein.

Ich entnehme dem, dass nicht alle Resourcen, die verwendet werden, auch 
angezeigt werden.

von Markus F. (mfro)


Lesenswert?

Bertram schrieb:
> Markus F. schrieb:
>> Dein Synthesetool ist schlau und hat offensichtlich gemerkt, daß Du was
>> multiplizieren willst ;).
>
> In diesem Fall hatte ich es ausdrücklich zugelassen. Es wurde auch nur
> eine einzige Multiplikatino benutzt. Mich wundert nur, wo die FlipFlops
> sind, die im Design drin sind. Es müssten vor und nach dem
> Multiplizierer jeweils welche sein.
>

> IO     57   210

Dann war dein Synthesetool eben da auch schlau und hat deine Register in 
die I/O-Buffer verschoben...

von C. A. Rotwang (Gast)


Angehängte Dateien:

Lesenswert?

Anbei für den Anwendungsfall De-linearisierung-Inkrementalgeber (wozu 
ich Poti zähle) ein passender Quadrierer.

Dieser Quadrierer hat keinen Eingangsvector für das Argument x sondern 
zwei Steuersignale für Inkrement, Dekrement und 0-Setzen. Quadrierung 
erfolgt auf Basis einer Taylerreihenentwicklung von x**2 und kommt daher 
mit einem simplen Adder aus. Dazu kommen noch counter für X und die 2 
Vergleicher für ein Poti.

Beim "Start" des FPGA ist der Quadrier erstmal auf 0 zu setzen, dann 
wird solange inkrementiert bis die aktuelle Potipos beim Start erreicht 
wird. Braucht bei typischen Werten von 1024 Positionen fürs Poti und 
wenigen MHz FPGA-Takt keine milisekunde. Danach wird innerhalb eines 
Taktes für jedes Inkrement das Quadrat rausgeschmissen.

Der Code ist noch nicht richtig rund, insbesonders bzgl einstellbare 
bitbreite, auch Optimierungspotential ist noch nicht komplett 
ausgeschöpft.

Für komplexere Poti-Hüllkürven, sollte man IMHO auf B-Splines statt 
hoch-gradiger (n>2) Polynome zurückgreifen. 
http://www-lehre.informatik.uni-osnabrueck.de/~cg/2000/skript/7_4_B_Splines.html
Da kommt dann ein kleine RAM für die Koeffizenten der einzelnen Splines 
hinzu.

von Experte (Gast)


Lesenswert?

Wie passt dieser Beitrag zum Thema? Das ist ein ein extremer 
Spezialfall.

von C. A. Rotwang (Gast)


Lesenswert?

Experte schrieb:
> Wie passt dieser Beitrag zum Thema?

<Ctrl-F>Potentiometer ->
Beitrag "Re: Ein DSP - aber 2 Multiplikationen. David Copperfield?"  3./4. Abschnitt

> Das ist ein ein extremer
> Spezialfall.

Nö, es ist eher der normale Anwendungsfall, das man eine sich "langsame 
ändernde Messreihe" korrigiert. Reale Prozesse sind eben stetig, da hat 
man keine sich wild und sprunghafte ändernde Argumente.

Grosses Oversampling, also Abtastrate >> Signalfrequenz ergibt sich 
durch den technischen Fortschrit bei ADC's fast nebenher, die internen 
ADC's eines MAX10 oder des XADC von xilinx erreichen eine Abtastrate von 
1MS/s was für Sprachsignale bis 8 KHz eine Überabtastung von 128 ergibt 
und damit ein Fall wo die Differenz zweier benachbarter Samples sehr 
klein ist. Man hat also quasi ein Audio-DSP system quai geschenkt. Oder 
man bearbeitet damit Daten zum Systemhealth wie Drift von erzeugten 
Spannungen um Aussagen zur Planung des nächsten Wartungsintervalls zu 
generieren. Der TO hat keinerlei Angaben zu Samplerate und 
Eingangsgrenzfrequenz bzgl. der Daten die er Offset korrigieren will, 
gemacht.

Ferner ist die hier zugrundeliegende numerische Vereinfachung des 
numerischen Problems durch Taylorreihenentwicklung eine gängige Methode 
in der Ingenieursmathematik. FET-Kennlinien, Diodenkennlinien, 
Potentialintegral -> für alles wurde im Studium erst mal die ersten 
Taylorelemente berechnet um die Polynomterme höherer Ordnung loszuwerden 
ohne einen nichtüberschaubaren Fehler zu  risikieren. Es steht jedem 
frei das oben gezeigte Verfahren auf seine Eingangsdaten und geforderte 
Genauigkeit zu modifizieren.

Und schließlich zeichnet sich ein Ingenieur gerade dadurch aus, das er 
auch für spezielle Anforderungen passende Lösung kennt oder entwickeln 
kann. Ohne die "Erfindung" spezieller Lösungsansätze würde die 
Menschheit immer noch wild mit der Holzkeule um sich schlagen um ihr 
nacktes Leben zu retten. Für mich ist ein Gegen-Argument wie "Lösung ist 
zu speziell da man nicht alle denkbaren Problemszenarien damit 
erschlagen kann" etwas für denkfaule und auch sonst eher zur Untätigkeit 
neigende Zeitgenossen.

von J. S. (engineer) Benutzerseite


Lesenswert?

Die Schaltung könnte für eine reine Funktion eines 
Vorwärts-Rückwärts-Stellers schon taugen, meine ich. Allerdings wäre es 
in meinem Fall schon so, dass die Werte vom "Poti" auch von MIDI kommen 
und die sind linear, bzw. ich weiß nicht, wie sie sich real verhalten, 
ich sehe nur den Stellwert als solchen. Sie müssen aber manchmal deshalb 
auf eine logarithmische oder quadratische Funktion umgesetzt werden, 
weil z.B. Pegel auf diese Weise überblendet werden müssen und die 
Leistung konstant sein soll. Ich brauche also z.B. P(L) = I * x*x und 
P(R) = I *(1-x)*(1-x).

Das ist ein eigentlich simple Operation und es ist schade, wenn dafür 
DSP-Elemente für draufgehen. Damit nochmals generell zu der Möglichkeit, 
Quadrieren in LUTs zu verpacken:

Ich habe meine Synthesis-Module mal genauer angesehen und allein beim 
Phasengenerator gibt es eine Dynamik von 4 ...9 DSP Elementen, je 
nachdem, wie schnell er arbeiten muss (100MHz/200MHZ) und 
interessanterweise auch, wie man versucht, Takte einzusparen:

An einer Ecke ist mir aufgefallen, dass der Portamentodämpfer, der die 
eingehende Frequenz in 24 Bit mit dem nichtlinearen Parameter (16Bit aus 
vormals 10) multipliziert, um die Änderungen für den Akku zu berechnen, 
erstaunlicherweise gleich 4 neue DSPs erzeugen kann, obwohl die beiden 
MULs weniger als 25x18 breit sind.

Verschiebt man die Bildung von den dem Akku hinzuzufügenden Anteile und 
abzuziehenden Anteile aber in die Systemtaktschleife, dann kann er einen 
DSP sparen. Schiebt man die Taktschleife gegen der Rest nochmal um einen 
Takt, dann sind es wie erwartet 2. Ich habe eine Weile gebraucht, um es 
nachzuvollziehen:

Weiter unten fasst er nämlich solche Multiplikationen, die rechtzeitig 
fertig werden, je nach Takt in LUTs oder vereinigt sie mit dem 
vorherigen Design. Bei hohen Taktraten und/oder etwas weniger FFs zum 
Schieben, packt er das nicht und spendiert MULs. Oder ganz genau 
formuliert: Er schafft es in der retiming-Synthese und physischen 
Resynthese nicht mehr, sie auszutauschen und wegzuoptimieren.

Ich hatte auch mal einige Versuche gemacht und die Sprünge bei der 
Nutzung der MULs bei Multiplikationen untersucht. Man sah sehr schön, 
wie er probierte, Multiplikationen, die etwas mehr, als die MUL-Breite 
sind, mit LUTs hinzuzufummeln und es weiter oben aufgab. Die Sprünge 
sind in der Folge auch dadurch bedingt, weil ich immer mal zusätzliche 
FFs einbauen musste, um aufs timing zu kommen.

Es ist zudem stark strategieabhängig: Man findet für die Versionen, die 
viele LUTs mitbenutzen, durchaus auch andere Lösungen, die weniger LUTs 
und dafür mehr FFs brauchen, ohne dass sich das Design funktionell 
ändert.
Das sieht man dann auch im RTL-Ersatzschaltbild.

Die Strategien in Vivado scheinen mir im Übrigen nicht so 100% 
ausgereift. Ich habe z.B. gerade ein Modul, das mit "normaler" Strategie 
7 DSPs verbrät, richtig tüchtig FFs einsetzt und bei 200MHz locker ins 
Timing kommt. Wenn ich aber die retiming option der Synthese aklicke, 
dann werden freudig ein DSP und ganze 7% FFs wegspart, dafür aber das 
timing nicht getroffen. Super!

Da fragt man sich, wie er das retiming durchführt, wenn er bei der 
Prüfung auf den Trichter kommt, dass was nicht gepasst hat.

von J. S. (engineer) Benutzerseite


Lesenswert?

Noch was Nettes:

Vivado packt das Optimieren mitunter besser, als ISE:
Beispiel Bass-Treble-Filter: Die Funktion ist exakt dieselbe, die 
Multiplier wieder auf 18x25 optimiert. Trotzdem:

Spartan 6 @ 100MHz (ISE)
-- slices   37
-- regs     96
-- LUTs     110
-- DSPs     4

Artix 7 @ 100MHz(ISE)
-- LUT     17
-- FF        97
-- DSP     3


Das der HF und der NF-Pfad symmetrisch sind, sollten eigentlich eine 
gerade Anzahl von MULs benutzt werden. Irgendwo wird einer umgebaut und 
mathematisch aus der Gleichung vorgezogen. Wie auch immer, soviel also 
zu den Möglichkeiten des Bausteins in der schnelleren Technologie.

Aber dann dies:

Artix 7 @ 200MHz (ISE)
-- LUT     21
-- FF        104
-- DSP     4

Artix 7 @ 200MHz (Vivado)
-- LUT     51
-- FF        131
-- DSP     3

Vivado spart also defaultmässig MULs ein.

... und macht das Design auch noch etwas kleiner, als ISE:

Artix 7 @ 100MHz (Vivado)
-- LUT     11
-- FF        94
-- DSP     3

Kann allerdings auch daran gelegen haben, dass der Artix zu ISE-Zeiten 
noch nicht 100% im tool etabliert war und konservativ gerechnet wurde.

von C. A. Rotwang (Gast)


Lesenswert?

Jürgen S. schrieb:
> Noch was Nettes:
>
> Vivado packt das Optimieren mitunter besser, als ISE:
> Beispiel Bass-Treble-Filter: Die Funktion ist exakt dieselbe, die
> Multiplier wieder auf 18x25 optimiert. Trotzdem:
>
> Spartan 6 @ 100MHz (ISE)
> -- slices   37
> -- regs     96
> -- LUTs     110
> -- DSPs     4
>
> Artix 7 @ 100MHz(ISE)
> -- LUT     17
> -- FF        97
> -- DSP     3

Interessant, ich hätte erst auf unterschiedliche CLB-Architektur 
getippt, die sind aber in grossen teilen gleich:
https://www.xilinx.com/support/documentation/user_guides/ug384.pdf S.42
https://www.xilinx.com/support/documentation/user_guides/ug474_7Series_CLB.pdf 
S.20


Das DSPE1 im Artix scheint ein paar FF mehr mitzubringen als  der 
DSP48A1 im Spartan6
https://www.xilinx.com/support/documentation/user_guides/ug389.pdf S.14
https://www.xilinx.com/support/documentation/user_guides/ug479_7Series_DSP48E1.pdf 
S.14
Vielleicht begründen doch Architekturunterschiede die unterschiedliche 
Anzahl von Ressourcen, mit dem Zusammenschalten von mehreren DSP-Blöcken 
hab ich noch nicht so die Erfahrung. Zu dem Thema "Large multiplier with 
fewer DSP Blocks" ist mir dieses paper über den Weg gelaufen:
https://www.researchgate.net/publication/224597240_Large_multipliers_with_fewer_DSP_blocks

Das schaut seriöser aus als die berüchtigten Inder/Ägypter, und bringt 
den Aspekt  der Granularität (DSP-"Atome"/Adder mit geringer Bitbreite 
versus grosse DSP-Blöcke mit hoher Bitbreite) in die Diskussion ein, was 
ich bisher in der Diskussion um die Verwendungen von "ASIC-Algorithmen" 
wie Wallace Tree in FPGA-Architekturen vermisse.


Zum Thema Audio und Logarithmus möchte ich folgendes bemerken.
In der frühen Rechentechnik war es nicht unüblich Multiplikation durch 
Addition der log's zu ersetzen, nicht umgekehrt. Beispiel Wang LOCI-2 
von 1965 https://www.oldcalculatormuseum.com/wangloci.html und der 
sinclair Taschenrechner von 1972 
https://hackaday.com/2017/11/01/a-teardown-with-a-twist-1975-sinclair-scientific-calculator/ 
Wie eine Log-berechnung in die mickrigen Controller gepresst wurde kann 
man in den damaligen patentschriften nachlesen: 
https://patents.google.com/patent/US3934233

Irgendwo, ich glöaube es war bei ISDN hab ich ich auch mal gelesen wie 
eine log-funktion mit 13(?) Geradeabschnitten genähert wurde.

Bei Audio sollte man IMHO spezifizieren wieviel Zeit für eine Berechnung 
man hat und dann schauen, wie man das in ein Rechenwerk auslagert. Bei 
100 kSamples/sekunde und 100 MHz takt wären das 1000 Takte, das sollte 
für eine Softwarelösung reichen. Zum Vergleich, Hardware-multiplizierer 
stammen aus einer Zeit (intel 2920) wo 1-8 MHz schon schnell war, da kam 
man um Hardware-Multiplikation als Beschleuniger nicht umhin.

Stellt sich die Frage, ob ein µC Core wirklich kleiner als ein 
LUT-Muliplier ist.
Und da scheinen mir die protegierten 32bit cores wie µblaze etwas "zu 
dick" und die schlanken 8bit wie picoblaze (kanapp 100 LUT's) zu schmal. 
Es sollte aber möglich sein, um einen 24 bit shifter und adder ein 
kleine Programmsteuerung aus einer Handvoll Op-Codes zu stricken um mit 
einem kleinen ROM (ca. 100 Wörter) beliebige Polynomapprox etc. zu 
basteln.
Das sollte auch noch ohne C-Compiler etc. machbar sein und im Bereich 
von 100-200 LUT's liegen. Statt Bit-test und Sprung könnte man die 
cycle-Anzahl durch bedingte ausführung je nach Wert der aktuellen 
Bitposition beschleunigen.

von Weltbester FPGA-Pongno (Gast)


Lesenswert?

C. A. Rotwang schrieb:
> Stellt sich die Frage, ob ein µC Core wirklich kleiner als ein
> LUT-Muliplier ist.

Kommt auf die Größe an, hätte ich jetzt getippt. Irgendwann werden die 
Bitbreiten zu groß. Ich frage mich aber bei dem gesamten thread schon, 
wie wichtig das heute noch ist. Die FPGAs haben doch Multiplizierer in 
Massen und billig.


Jürgen S. schrieb:
> Ich hatte auch mal einige Versuche gemacht und die Sprünge bei der
> Nutzung der MULs bei Multiplikationen untersucht. Man sah sehr schön,
> wie er probierte, Multiplikationen, die etwas mehr, als die MUL-Breite
> sind, mit LUTs hinzuzufummeln

Und wie schnell ist der dann noch? Die DSP-Elemente der modernen FPGAs 
können bis zu 500MHz. Eine LUT verbrät zwischen 30ps und 90ps zzgl 
interconnection. Nehme ich einfach 150ps, dann darf man 10-15 Stück in 
Kette betreiben.


Helmut S. schrieb:
> Die Artix-FPGAS haben doch fest eingebaute DSP slices(multiplier,
> accumulator). Die tauchen bei der Anzahl benötigter LUTs gar nicht auf.
Also bei mir im Synthesebericht sind sowohl die LUTs also auch die DSPs 
ausdrücklich aufgeführt. Fehlen tun sie nur, wenn keine verwendet 
wurden.
Das ist auch bei den LUTRAMs und Block-RAMs so, bzw bei dem 
Ultra-RAM-Typ im Ultrascale.

von Berti (Gast)


Lesenswert?

Jürgen S. schrieb:
> Artix 7 @ 200MHz (ISE)
> -- LUT     21
> -- FF        104
> -- DSP     4
>
> Artix 7 @ 200MHz (Vivado)
> -- LUT     51
> -- FF        131
> -- DSP     3

Das war jener Beweggrund für mich zu fragen. Wie kann es sein, dass so 
wenig Kombinatorik gebraucht wird, für den Ersatz eines solchen 
DSP-Elements?

von J. S. (engineer) Benutzerseite


Lesenswert?

C. A. Rotwang schrieb:
> Das schaut seriöser aus als die berüchtigten Inder/Ägypter, und bringt
> den Aspekt  der Granularität (DSP-"Atome"/Adder mit geringer Bitbreite
> versus grosse DSP-Blöcke mit hoher Bitbreite)
Ein guter link zum Verständnis. Man könnte jetzt sagen, das bitte das 
tool das alles beherzigt und nett optimiert, funzt aber aus solchen 
Erwägungen heraus nicht. Man muss designtechnisch nach wie vor Denken, 
wenn man resourcen sparen möchte und richtig bauen. Scheint nur aus der 
Mode gekommen.

> Zum Thema Audio und Logarithmus möchte ich folgendes bemerken.
> In der frühen Rechentechnik war es nicht unüblich Multiplikation durch
> Addition der log's zu ersetzen, nicht umgekehrt.
Ja, siehe "Analog-Multiplizierer" und du wirst lachen, aber so was habe 
ich schon in Software nachgebaut, mitsamt den Schwächen der 
Diodenkennlinien. Inzwischen steckt das als VHDL in meinem Synth, wenn 
er echte FM-Synthese macht, so wie es die analogen Synthies machen.

> Irgendwo, ich glöaube es war bei ISDN hab ich ich auch mal gelesen wie
> eine log-funktion mit 13(?) Geradeabschnitten genähert wurde.
Das hatten wir sogar schon hier im Forum mal diskutiert. Es gab sogar 
ein Patent drauf, meine ich mich zu erinnern. Ich finde es gerade nicht. 
Befasst habe ich mich mal hiermit:
https://patents.google.com/patent/EP0464777B1

Logarithmus an sich ist einfach, weil es eine monotone Funktion ist. In 
der Binärdarstellung reichen die jeweils höchsten 3-4 Bits eines 24 Bit 
Wertes, um einen verschachtelten Multiplexer zu bauen, der direkt ein 
VU-Meter realisiert. Genauer geht es dann iterativ nach unten. In 13 
Takt-Schritten habe ich den fertig. Läuft in einem 
Teilchenbeschleuniger. Das Original von Altera braucht doppelt so lange 
:-)

Lustig: Die Firma Bosch hat sogar ein Patent auf einen 
Logarithmus-Schätzer: https://patents.google.com/patent/DE102014200465A1
Ich erkenne allerdings den Vorteil nicht so recht.

> Bei Audio sollte man IMHO spezifizieren wieviel Zeit für eine Berechnung
> man hat und dann schauen, wie man das in ein Rechenwerk auslagert. Bei
> 100 kSamples/sekunde und 100 MHz takt wären das 1000 Takte, das sollte
> für eine Softwarelösung reichen.
Sofern man nur einen Kanal berechnen möchte, ja. :-)

Bitte 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
Noch kein Account? Hier anmelden.