Grundsätzliche Frage zur Realisation von Mathe im FPGA

[Oli P. (Gast)]

Ich habe eine Formel, die im FPGA gerechnet werden soll, weil der 
Prozessor zu langsam ist.

Dabei habe ich festgestellt, daß ich aufgrund der Tatsache, daß ich Core 
verwenden muss, recht gewaltige Delays erhalte.

Es ist z.B. so, daß ich die Wurzel aus der Summe zweier Thermen bilden 
muss, die dann ihrerseits mit weiteren Ergebnissen (Sinus und Tangen) 
verrechnet werden muss.

Jetzt kann man ja ein Ergebnis erst verwenden, wenn es aus dem Core 
herauskommt. Was macht man solange mit den anderen Werten?

In einer echten pipeline müssen ja alle Werte rechtzeitig vorliegen. 
Bisher habe ich alle Werte immer mit Registern verzögert, um sie dann 
zum richtigen Zeitpunkt parat zu haben. Geht das auch anders?

Ich benutzen z.B. den Xilinx Cordic Core, der je nach Funktion manchmal 
40-50 Takte Latenz aufweist. Das bedeutet, dass ich die anderen Daten, 
die ja auch bis zu 32Bit breite Vektoren dartellen, mit jeweils 32x50 
FFs oder RAMS verzögern muss. Geht das auch anders?

Wie macht man das mit den RAMSs?

Zu jedem Datensatz gibt es eine ganze Hand voll an Paramtern, die vom 
Prozessor zum selben Paket zusammengefasst gespeichert werden, z.B. 
Paket 1 ab Adresse 0, Paket 2 ab Adresse 32, u.s.w.

Wenn ich jetzt Paket 1 adressiere, bekomme ich ja nicht schlagartig alle 
Daten heraus, es sei denn ich bringe sie in parallelel Rams unter. Dann 
kommen sie alle zeitgleich heraus. Sie werden aber nicht alle gleich im 
ersten pipeline Schritt benötigt. Wie regelt man sowas?

[Frank B. (foobar)]

Du programmierst eine Statemachine, die das entsprechend verzögert und 
die Latenz für das RAM auch berücksichtigt, also Adresse anlegen, 
nächsten Takt nächste Adresse anlegen und nächsten Takt den Wert vom 
vorherigen Takt auslesen und nächste Adresse anlegen usw.

Ich frage mich aber, wenn du bis zu 50 Takte warten musst, warum soll 
dann der FPGA schneller sein? Wenn du noch Umwandlungen brauchst, da 
CORDIC ja nicht mit floating point rechnet und die Daten noch zum FPGA 
hin und zurücktransportieren willst, wird ein kleiner ARM 
Microcontroller nicht langsamer sein. Gibt sogar mittlerweile preiswerte 
Microcontroller mit floating point Einheit, da dauert das dann nur 
wenige Takte pro Berechunngen.

[Oli P. (Gast)]

Ein FPGA ist sowieso drauf und es soll als pipeline laufen. Bei einer 
state machine verschwende ich ja Zeit, weil manche Architekturteile 
nicht rechnen. Die Berechnerei muss in jedem Takt (50MHz, gfs sogar 
mehr) einen Kanal / Datum abarbeiten.

Die Daten kommen so, daß mit >80MHz / (14 Bit 6+x) = 5MHz parallele 
Daten kommen und das von momentan 2 Kanälen. Das sollen aber 4 oder 
sogar 8 werden. Somit kommen Daten mit bis zu 40Mhz.

Einfache Sachen, wie Gain-Offset habe ich ja schon gemacht, aber dort 
treten nur geringe Verzögerungen auf.

>Gibt sogar mittlerweile preiswerte
>Microcontroller mit floating point Einheit, da dauert das dann nur
>wenige Takte pro Berechunngen.

Frage: Wie macht ein DSP das in nur so wenigen Takten und noch dazu so 
schnell? Ist das alles asynchron verdrahtet und arbeitet ohne pipeline, 
ist aber wengen optimiertem Silikon so schnell? oder benutzen die DSPs 
andere Schaltungen?

Den Cordic will ich ja nicht unbedingt nehmen, ich habe nur im CoreGen 
nichts anderes. Bietet Xilinx da noch IP-Cores an? - die schneller sind?

Ich brauche eigentlich so ziemlich alles:

Quadrat von 24 Bit-Zahl, trivial
Addierer bis 25 Bit, trivial
Wurzel aus 48Bit-Zahl
Sinus (mit Phase von 0...2047)
Logarithmus zur Basis 2 (von 48 Bit-Zahl) mit Auflösung 256 digit
Logarithmus zur Basis 10 (von 24 Bit-Zahl) mit Auflösung 16384 digit
Exponent von 16Bit-Zahl (8+8 Auflösung) zur Basis 10, Ergebnis ist 
maximal 24Bit gross
Reziprokfunktion von 16Bit-Zahl, Auflösung aber 24 Bit genau
Division von 16Bit / 24Bit-Zahl, Auflösung 16 Bit genau

Insgesamt habe ich überschlagen, daß ich bei geschicktem Verteilen 13 
Rechenschritte brauche, von denen 7 "lange" Cores sind mit z.T. 50 
Takten, die anderen sind "+" , "-" und "*", also nur 2-3 Takte.

Das Ganze gibt ja eine Art Baum, wo alle Blätter in den Stamm münden, 
bei mir eine finale Division aus 2 Termen, die selber aus Einzeltermen 
aufgebaut sind.

Ich habe geschätzt, daß ich <500 Takte Latenz bekomme (auch für den 
letzen Kanal) -> das sind immerhin noch 100kHz. Da die 5MHz schnellen 
Daten sowieso durch Filter laufen , die Frequenzen um die 10kHz 
betrachten, ist das allemal schnell genug.

Ich mache mir nur Sorgen, um die Resourcen.

[Frank B. (foobar)]

Wieviel LEs hast du denn im Xilinx noch frei? Ein CORDIC brauchst ja 
nicht viel, ich habe sowas vor einiger Zeit mal zum Spaß selber 
programmiert mit 32 Bit Auflösung, für die Sinusgenerierung in meinem 
Funktionsgenerator:

http://www.frank-buss.de/SignalGenerator/index.html

Daher könntest du eine Pipeline implementieren mit x instatiierten 
CORDICs  (per VHDL "generate" und "loop") und wärst somit x-mal 
schneller, da du nun mit Eingangsfrequenz*x/CoreGenMax neue Werte 
berechnen kannst (mit deinen 40-50 Takte für CoreGenMax), statt 
Eingangsfrequenz/CoreGenMax. Die maximale Latenz wäre CoreGenMax, plus 
ein wenig Overhead für die Verwaltung.

DSPs arbeiten auch mit Pipelines, was auch der Grund ist, daß 
konditionale Sprünge meist teuer sind, da die Pipeline dann u.U. geleert 
werden müssen. Die Pipelines sind allerdings nicht so lang, da die 
mathematischen Operationen schneller als per CORDIC berechnet werden, 
aber sowas kostet eine ganze Menge Transistoren.

Gibt für deinen Fall bestimmt noch andere Optimierungen. Den Sinus mit 
2048 Werten könntest du per ROM implementieren. Für die Quadrierer hast 
du ja bereits meist Hardwaremultiplizierer je nach Xilinx Chip. 
Logarithmus zur Basis 2 müsstest du auch in einem Takt per Hardware 
berechnen können und für Logarithmus zur Basis 10 gibt es auch 
schnellere Verfahren als CORDIC, wenn du Multiplierer zur Verfügung 
hast. Nur die Division könnte aufwendiger werden.

[Harald (Gast)]

>Logarithmus zur Basis 2 müsstest du auch in einem Takt per Hardware
>berechnen können

Wie geht das denn bitte in einem Takt?

[D. I. (Gast)]

Harald schrieb:
>>Logarithmus zur Basis 2 müsstest du auch in einem Takt per Hardware
>>berechnen können
>
> Wie geht das denn bitte in einem Takt?

z. B. mit ner Schleife

[Harald (Gast)]

Meines Erachtens muss man dann mindestens soviele Entscheider einbauen, 
wie der Ausgangsvektor an Breite braucht. Bei 16 Bit geht das dann 
sicher nicht mehr in einem Takt.

[D. I. (Gast)]

Harald schrieb:
> Meines Erachtens muss man dann mindestens soviele Entscheider einbauen,
> wie der Ausgangsvektor an Breite braucht. Bei 16 Bit geht das dann
> sicher nicht mehr in einem Takt.

Falsch und Falsch. Bzgl. Takt kommt es immer auf die Freuqenz an und 
zweitens kann man das logarithmisch lösen.

[Frank B. (foobar)]

Das hier wäre ein Beispiel für eine asynchrone Berechnung:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity main is
  generic(
    inputLength: natural := 16;
    outputLength: natural := 4
  );
  port(
    -- Dateneingang
    input: in unsigned(inputLength-1 downto 0);
    
    -- Logarithmus 2 Ausgang
    output: out unsigned(outputLength-1 downto 0)
  );
end main;

architecture rtl of main is
begin
  process(input)
    variable mask: unsigned(input'high downto 0);
  begin
    output <= (others => '0');
    mask := (others => '1');
    for i in 0 to input'length loop
      mask := mask(input'high-1 downto 0) & '0';
      if (input and mask) = to_unsigned(0, input'length) then
        output <= to_unsigned(i, output'length);
        exit;
      end if;
    end loop;
  end process;
end architecture rtl;

Für den langsamsten XC9572XL implementiert braucht das ca. 7% an 
Resourcen bei den 16 Bit und läuft bis zu ca. 90 MHz laut Timing Report 
(11 ns worst-case von input zu output). Es berechnet den Logarithmus zur 
Basis 2, jeweils abgerundet, sodaß Bit 0 des Eingangs nicht gebraucht 
wird.

Hier ein Testbench dazu:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.all;

entity testbench is
end entity testbench;

architecture test of testbench is
  signal input: unsigned(15 downto 0) := (others => '0');
  signal output: unsigned(3 downto 0) := (others => '0');

begin
  
  log_inst: entity main
  port map(
    input => input,
    output => output
  );

  process
  procedure test(inp: natural; expectedResult: natural) is
  begin
    input <= to_unsigned(inp, input'length);
    wait for 10ns;
    assert output = to_unsigned(expectedResult, output'length) report "Berechnungsfehler" severity failure;
  end;
  begin
    test(0, 0);
    test(1, 0);
    test(2, 1);
    test(3, 1);
    test(4, 2);
    test(12345, 13);
    test(32768, 15);
    test(65535, 15);
    assert false report "kein Fehler, Testbench ok" severity failure;
  end process;

end architecture test;

Der letzte "Fehler" per "assert false" ist übrigens ein guter Trick, um 
ein Testbench am Ende anhalten zu lassen.

Interessant übrigens auch, was der Synthetisierer daraus gemacht hat 
(sieht man im Text-Report von ISE) :

output(0) <= ((input(15))
  OR (NOT input(8) AND NOT input(12) AND NOT input(10) AND NOT input(14) AND 
  NOT input(6) AND input(5))
  OR (NOT input(8) AND NOT input(12) AND NOT input(10) AND NOT input(14) AND 
  NOT input(6) AND NOT input(4) AND input(3))
  OR (NOT input(8) AND NOT input(12) AND NOT input(10) AND NOT input(14) AND 
  NOT input(6) AND NOT input(4) AND NOT input(2) AND input(1))
  OR (NOT input(14) AND input(13))
  OR (NOT input(12) AND input(11) AND NOT input(14))
  OR (input(9) AND NOT input(12) AND NOT input(10) AND NOT input(14))
  OR (NOT input(8) AND NOT input(12) AND NOT input(10) AND NOT input(14) AND 
  input(7)));


output(1) <= NOT (((NOT input(11) AND NOT input(10) AND NOT input(15) AND NOT input(14) AND 
  NOT input(6) AND input(5) AND NOT input(7))
  OR (NOT input(11) AND NOT input(10) AND NOT input(15) AND NOT input(14) AND 
  NOT input(6) AND NOT input(2) AND NOT input(7) AND NOT input(3))
  OR (input(12) AND NOT input(15) AND NOT input(14))
  OR (NOT input(15) AND NOT input(14) AND input(13))
  OR (input(9) AND NOT input(11) AND NOT input(10) AND NOT input(15) AND 
  NOT input(14))
  OR (input(8) AND NOT input(11) AND NOT input(10) AND NOT input(15) AND 
  NOT input(14))
  OR (NOT input(11) AND NOT input(10) AND NOT input(15) AND NOT input(14) AND 
  NOT input(6) AND input(4) AND NOT input(7))));


output(2) <= NOT (((input(9) AND NOT input(12) AND NOT input(15) AND NOT input(14) AND 
  NOT input(13))
  OR (input(8) AND NOT input(12) AND NOT input(15) AND NOT input(14) AND 
  NOT input(13))
  OR (NOT input(12) AND input(11) AND NOT input(15) AND NOT input(14) AND 
  NOT input(13))
  OR (NOT input(12) AND input(10) AND NOT input(15) AND NOT input(14) AND 
  NOT input(13))
  OR (NOT input(12) AND NOT input(15) AND NOT input(14) AND NOT input(13) AND 
  NOT input(6) AND NOT input(5) AND NOT input(4) AND NOT input(7))));


output(3) <= NOT ((NOT input(9) AND NOT input(8) AND NOT input(12) AND NOT input(11) AND 
  NOT input(10) AND NOT input(15) AND NOT input(14) AND NOT input(13)));

Viel besser hätte ich es auch nicht selber machen können :-)

Man muß dazu aber nicht extra eine eigene Entity schreiben. Kann man 
auch einfach per Funktion berechnen, entweder parallel wie bei meinem 
Ansatz oder auch seriell, mit einem 0-Test pro Takt, was u.U. weniger 
LEs verbraucht:

Beitrag "log2 in VHDL auf integer?"

[D. I. (Gast)]

ein wait; am ende der Testbench tuts aber auch zum Anhalten eines 
prozesses

[Frank (Gast)]

Da möchte ich aber nicht wissen, wie schnell das wird, wenn mehr als nur 
4 Bit benötigt werden.

[Frank B. (foobar)]

Es wird nicht allzu viel langsamer. Habe es gerade mal mit 32 Eingängen 
und 8 Ausgängen probiert: belegt dann im CPLD 38% und geht bis 37 MHz. 
Der relativ starke Geschwindigkeitseinbruch (ich hätte mit 
logarithmischen Zuwachs relativ zur Anzahl Bits gerechnet) kommt wohl 
daher, daß ISE intern noch einen zusätzlichen Buffer synthesisieren 
musste, da die seitenlange Logikverknüpfungen nicht mehr alle in ein 
"function block" passten. Modernere FPGAs können sowas bestimmt 
problemlos noch mit über 100 MHz implementieren, wenn man bedenkt, daß 
z.B. bei einem Cyclone 3 der 18x18 Bit Multiplizierer mit mehreren 100 
MHz gut läuft.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Frank Buss schrieb:
> Habe es gerade mal mit 32 Eingängen und 8 Ausgängen probiert:
Da sind eigentlich nur 5 Ausgänge nötig. Eben der log2... ;-)

> Es wird nicht allzu viel langsamer. Habe es gerade mal mit 32 Eingängen
> und 8 Ausgängen probiert: belegt dann im CPLD 38% und geht bis 37 MHz.
In einem kleinen Spartan3AN 50k FPGA werden 25 von 704 Slices (=3%) der 
Ressourcen verbraucht bei einer Durchlaufzeit incl. IO-Buffer von
> Maximum combinational path delay: 18.855ns
Wenn die IO-Buffer wegfallen, dann sind die 100MHz nicht so abwegig...

Bei 64 Bits braucht das dann 31 ns, bei einem Ressourcenverbrauch von 
238 Slices (=33%). Man sieht, dass trotz der wesentlich aufwendigeren 
Logik nicht allzuviel zusätzliche Durchlaufzeit gebraucht wird...

[Johann (Gast)]

Wenn man dann einen Spartan 6 verwendet, dann ist da einiges mehr drin, 
da die 6Bit Lookup Table benutzen. Dann werden die ganzen AND und ODER 
Verknüpfungen in den Lookup Tablen gespeichert. Das bringt dann so 
einiges. Außerdem haben die Spartan 6 enorme Slice Reserven und kostet 
fast nichts ^^.

[Harald (Gast)]

30ns sind aber nur 30MHz. Wie spaltet man das so auf, daß es 150 werden?

[D. I. (Gast)]

Harald schrieb:
> 30ns sind aber nur 30MHz. Wie spaltet man das so auf, daß es 150 werden?

in dem mans pipelined

[T. (Gast)]

>Wenn man dann einen Spartan 6 verwendet, dann ist da einiges mehr drin,
Tolle Aussage eines Ingenieurs. Was ist denn "so einiges"?

>Dann werden die ganzen AND und ODER Verknüpfungen in den Lookup Tablen
>gespeichert.
Bei anderen FPGAs nicht?

>Das bringt dann so einiges.
Siehe oben.

>Außerdem haben die Spartan 6 enorme Slice Reserven und kostet fast nichts
Ich benutze "grosse" FPGAs mit "viel" Power für "wenig" Geld, in denen 
"enorm viel" Elektronik steckt, die "fast" keinen Strom verbraucht und 
"super schnell" rechnet. Im Ernst, hat jemand belastbare Zahlen?

Kann man davon ausgehen, daß ein FPGa mit 6fach LUTs im Vergleich zu 
einem mit 5fach oder 4fach nur 5/6 oder 4/6 der LUTs benötigt? Oder ist 
es noch weniger aufgrund der Verkettung?

In der Uni hat der Prof immer so abgeschätzt, daß je zusätzlicher 
serieller Stufe ein LUT-Eingang wegfällt, da dieser von der vorherigen 
kommt (Ergebnisverktor). Dann wäre das Verhältnis 4/5 bzw 3/5.

[Ollih (Gast)]

Also ich hab sowas auch mal gemacht.

Ich geh mal davon aus, dass du deine Formel möglichst schnell berechnet 
haben willst. Alle Latenzen deiner Cores insgesamt ergeben eine 
Verzögerung bis du dein erstes Ergebnis bekommst. Ab dann kann man es 
aber so machen, dass du jeden Takt ein neues Ergebnis deiner Formel 
bekommst.

Musst halt nur eine geschickte pipelining Variente deiner Statemachine 
schreiben.

Bei dem Floating Point Operator von Xilinx ist es ja so, dass man 
erstmal einpaar Takte warten muss, bis das erste Ergebnis kommt. Das 
gilt für alle Rechenoperationen. Sobald das erste Rechenergebnis da ist, 
bekommt man aber jeden Takt ein neues.

Ist natürlich nicht einfach eine Formel als gepipelinte Version in eine 
Statemachine zu packen. Aber gehn tut es :)

[Johann (Gast)]

Wenn einer ISE 12.3 installiert hat dann kann man den oben geposteten 
Code mal auf einen Spartan 6 routen und dann sehen wir wirklich wie viel 
die neue Struktur des Spartan 6 an Performance bringt.

[Johann (Gast)]

Es ist schade das keiner den Code mal auf einem Spartan 6 routen kann. 
Leider habe ich kein ISE 12 Version installiert. Mich würde mal die 
Performance auf einen Spartan 6 interessieren

[Frank B. (foobar)]

Ich habe es mal ohne UCF-Datei und für XC95* laufen lassen (also ISE 
sucht die Pins, Speed Grade und den konkreten Typ selbst aus) und da 
geht es laut Timing Report dann bis 166 MHz. Für Spartan 6 (xc6slx25) 
nur bis 82 MHz, aber vielleicht habe ich da nur noch nicht alles richtig 
eingestellt. Habe dann mal Virtex 6 probiert (xc6vlx75-t) und das läuft 
dann bis 142 MHz, also merkwürdigerweise auch nicht allzu schnell. Also 
besser ein CPLD für schnelle Designs einsetzen, statt ein Virtex :-)

Grundsätzlich sind so lange Logikkombinationen natürlich nicht sinnvoll 
und sollte man seriell implementieren, und zusätzlich per Pipelining, 
wenn man es wirklich schnell braucht.

[Johann (Gast)]

Das kann ich nicht nachvollziehen warum ein COLD da deutlich schneller 
sein soll ^^.

Kannst Du den gleichen Test auch mal für einen Spartan 3 durchführen, 
dann kann man den Unterschied zwischen Spartan 3 und Spartan 6 direkt 
vergleichen.

[Frank B. (foobar)]

Spartan 3 schafft mit meinem Test 64 MHz. Aber ich mache da bestimmt was 
falsch. Gibt auch keinen richtigen Timing-Report, wie beim CPLD, sondern 
nur bei "Report Navigation" ein "Timing report description". Vielleicht 
sollte man besser eine UCF-Datei anlegen? Die Pin-Bezeichnungen sind 
aber für die Chips immer anders, vielleicht möchte das ja mal ein 
anderer testen. Die ISE Webedition kann jeder nach einer kostenlosen 
Registrierung bei Xilinx frei herunterladen und installieren.

[Johann (Gast)]

Gut laut Deinem Test geht funktioniert die Schaltung beim Spartan 3 mit 
maximal 64MHz und beim Spartan 6 mit dis zu 82MHz. Dies ist doch schon 
mal sehrerfreulich. Dadurch kann man endlich mal sehen wie viel 
schneller der Spartan 6 gegenüber dem Spartan 3 ist.

Demnach ist der Spartan 6 28% schneller als der Spartan 3.  Dies ist 
doch schon mal sehr beachtlich wenn man bedenkt das auch die 
Stromaufnahme deutlich gerigner ist.

Vielen Dank für Deine Infos.

[Duke Scarring (Gast)]

Johann schrieb:
> Demnach ist der Spartan 6 28% schneller als der Spartan 3.

Das gilt aber nur für diesen speziellen Fall (leider) und darf nicht 
unbedingt verallgemeinert werden. Der Geschwindigkeitszuwachs kommt ja 
durch verschiedene Faktoren zu stande:

- neuere Prozesstechnologie (kleinere Strukturen -> kürzere Schalt- und 
Laufzeiten)
- andere Granularität (LUT6 statt LUT4, RAM256 statt RAM64)
- vermutlich einfacheres Routing, da die Granularität anders ist, evtl. 
auch andere Routingressourcen vorhanden sind

Durch größere Chips und komplexere Designs, kannst Du Dir den 
Geschwindigkeitsvorteil auch wieder zu nichte machen.
Andererseits gibt es für PCIe und DDR-Speicher integrierte Hard-IP, so 
das u.U. Logik frei wird, die vorher von IP-Cores belegt wurde...

Alles in allem, es ist nicht nur einfach auf eine Zahl zu reduzieren.

Duke

[Johann (Gast)]

Ich glaube ich werde mir mal ein Evaluation Board zulegen und ein wenig 
mit dem Spartan 6 spielen.