FPGA statt MCU Selbstgebauter Koprozessor für geometrische Summe

Eine geometrische Summe findet Anwendung in der Elektrotechnik z.B. bei der Berechnung des Effektivwerts. Die Berechnung ist keine leichte Aufgabe für einen kleinen Mikrocontroller, vor allem wenn das Ganze sehr schnell gehen soll und er keine Gleitkommaeinheit hat. Was tun?

Es gibt Anwendungsfälle, bei denen der Wechsel auf einen leistungsfähigeren Mikrocontroller keine der möglichen Optionen ist. Platzbedarf, elektrische Leistung oder Kosten mögen Gründe sein, warum man beim einmal gewählten Schmalspur-Controller bleiben muss. Und wenn dieser mit gestiegenen Rechenanforderungen nicht mithalten kann, ist guter Rat teuer. Eine einfache Berechnung wie die der geometrischen Summe kann dann zum Problem werden.

Zur Theorie. Die Formel für die Berechnung der geometrischen Summe zweier Zahlen lautet: 

Kleine Mikrocontroller haben meist kein Rechenwerk für Fließkommazahlen, also muss die Berechnung der geometrischen Summe in Software erfolgen. Es würde oft ausreichen, das Ergebnis als Ganzzahl zu berechnen, aber auch hier liegt die Tücke im Detail. So ist die geometrische Summe zwar stets kleiner als die arithmetische Summe, aber bei der Berechnung kommen Zwischenergebnisse vor, die deutlich größer sind. Liegen die beiden Werte a und b beispielsweise in einer Auflösung von 20 bit vor, so sind die Quadrate bereits 40 bit breit, die Summe somit 41 bit. Selbst bei Größen mit nur 16 bit Auflösung hat der Radikand, aus dem die Wurzel gezogen werden muss, einen Wertebereich von 33 bit und liegt damit außerhalb des üblichen Rechenbereichs moderner 32-bit Mikrocontroller.

Ein weiteres Problemfeld ist der Zeitbedarf für die Berechnung. Zwar können moderne Mikrocontroller eine Summe oder ein Produkt in nur einem Taktzyklus berechnen, aber die Berechnung einer Wurzel in Software braucht viel Zeit. Als groben Schätzwert kann man bei einem aktuellem 32-bit-Mikrocontroller mit 50 MHz Taktfrequenz eine Rechenzeit von 10 μs annehmen, falls 32-bit Arithmetik ausreicht.

Ein alternativer Ansatz ist die Entwicklung eines eigenen Rechenwerks für die Ermittlung der geometrischen Summe in einem kleinen FPGA. Dieses kann das Ergebnis nicht nur sehr schnell berechnen, es kann auch hinsichtlich der Wortbreite so dimensioniert werden, dass keine Überläufe auftreten können. Das kleine FPGA bindet man irgendwie, zum Beispiel via SPI, an den Mikrocontroller an, übermittelt über diese Schnittstelle die Operanden und holt danach das Ergebnis ab. Das FPGA ist somit ein dedizierter, nummerischer Coprozessor, den man lediglich diejenigen Aufgaben machen lässt, für die der Hauptprozessor nicht geeignet ist.

Das Quadrieren und die Addition sind kein Hexenwerk, aber das Radizieren hat es in sich. Die Suche nach einem passenden Algorithmus liefert einige Ansätze, von denen sich zwei besonders für die Implementierung in einem kleinen FPGA eignen. Das sind zum einen das Verfahren von Heron und zum anderen die schrittweise Annäherung mittels Quadrieren.

Beim Verfahren von Heron wird die Quadratwurzel mittels eines iterativen Algorithmus berechnet. Die Formel für einen Iterationsschritt lautet:

Der Algorithmus konvergiert in jedem Fall zum einem Endwert, sofern mit einem positiven Startwert begonnen wurde. Dabei kann man durchaus Ganzzahlarithmetik einsetzen, wenn man mit einem ganzzahligen Ergebnis zufrieden ist. Bei Ganzzahlarithmetik kann es dabei vorkommen, dass das Ergebnis zwischen zwei benachbarten Zahlen oszilliert (Tabelle).

nxna/xnZählerErgebnis
11353618
2181199
393126
465115
557126
665115

 

Tabelle. Osziallation der Ergebnisse beim Verfahren von Heron.Beispiel für a = 35, Startwert = 1. 

Einen Nachteil hat das Verfahren allerdings: Es erfordert einen Dividierer, und so etwas gibt es in FPGAs üblicherweise nicht. Zwar kann ein sequenzielles Rechenwerk mit geringem Ressourcenverbrauch einen Quotienten berechnen, benötigt dafür aber etwa so viele Takte wie der Dividend bits hat. Bei 20 bit Breite und angenommenen 6 Iterationen kommen so ca. 150 Taktzyklen zusammen, was bei einer angenommenen Taktfrequenz von 50 MHz einen Zeitbedarf von 3 μs ergibt. Das ist auch nicht viel besser als eine Berechnung in Software.

Beim zweiten Ansatz, der schrittweisen Annäherung, wird versuchsweise ein geratener Wert quadriert und geprüft, ob das Quadrat des Werts größer oder kleiner ist als der Radikand, aus dem die Wurzel gezogen werden soll. Der erste geratene Wert ist dabei eine Binärzahl mit einer 1 an der höchsten Stelle, die restlichen bits sind alle 0. Je nach E wird diese Stelle des Ergebnisses auf 1 gelassen oder auf 0 gesetzt. Dann wird die nächst niedrigere Stelle geraten und so weiter. Der Algorithmus benötigt so viele Iterationen wie das Ergebnis bits hat, bei 41 bit Wortbreite des Radikanden also 21 Durchgänge.

Dieser Ansatz erfordert allerdings einen Multiplizierer, um den geratenen Wert mit sich selbst zu multiplizieren, sprich, das Quadrat zu ermitteln. Nicht jede FPGA-Familie bietet dies, vor allem kleine, kostengünstige Familien nicht. Das macht aber nichts, dann schreibt man die Multiplikation eben direkt in den Quellcode und lässt das Synthesetool die dafür nötige Gatterschaltung berechnen. Früher wurden hierfür spezielle Schaltungsgeneratoren mit grafischer Oberfläche benutzt, heute schreibt man sich einfach ein kleines Modul (Listing).

module int_sqr

        #(

        parameter integer piWidth = 1

       )

       (

       input wire                               clk_i,

       input wire                               rst_i, 

       input wire                               tic_i,         // input valid

      output wire                              tac_o,       // output valid

      input wire      [piWidth-1:0]      a_i         , // factor a

      output wire    [2*piWidth-1:0]   p_o        // square a *

a

    );

reg         [2*piWidth-1:0] p;

reg                                  tac;

always @(posedge clk_i)

      begin

      p     <= a_i * a_i; 

      tac   <= tic_i;

      end

assign p_o           = p;

assign tac_o        = tac;

endmodule

Listing: Modell eines getakteten Multiplizierers, wobei die Breite des Operanten und des Ergebnisses parametrierbar sind.

Dieses Modul ist das Modell eines getakteten Multiplizierers, wobei die Breite des Operanden und des Ergebnisses parametrierbar sind. Mit so einem Multiplizierer und dem Verfahren der schrittweisen Annäherung lässt sich die Wurzel einer Zahl im Wertebereich von 41 bit in etwa 45 Takten berechnen, also bei den angenommenen 50 MHz unter 1 µs.

Beispieldesign

In einem Beispieldesign für den Coprozessor wird genau das gemacht. Es ist ausgelegt für eine Operandenbreite von 20 bit. Der Mikrocontroller überträgt die Werte für a und b, indem er ein sechs Byte langes Datenpaket via SPI an den Coprozessor schickt. Kurze Zeit später kann er das Ergebnis der Berechnung abholen. Im Sinne einer sauberen Programmierung des Mikrocontrollers wäre es eigentlich notwendig, dabei zunächst das Signal busy des Coprozessors abzufragen, aber vermutlich dauert alleine der Rücksprung aus der SPI-TxRx-Funktion und der erneute Aufruf länger als die Berechnung des Ergebnisses durch den Coprozessor.

Erläuterung des Blockschaltbilds

Das Blockschaltbild (Bild 1) zeigt eine recht simple Anordnung der Module. Die über den SPI-Slave hereinkommenden Werte werden von der allgemeinen Steuereinheit (control) dem Quadrierer zugeführt und im Summenregister ( ∑ ) aufaddiert. Die Steuereinheit für das Radizieren nutzt den gleichen Quadrierer, der zuvor die Werte a und b quadriert hat.

Funktionale Simulation

Schon während des Empfangs des Datenpakets mit den Werten für a und b werden diese Zahlen quadriert und aufsummiert. Dann beginnt das Radizieren nach dem Verfahren der schrittweisen Annäherung (Bild 2).

Das Beispieldesign belegt ca. 900 LUTs im FPGA, wobei knapp die Hälfte davon für den Quadrierer benötigt wird. Es passt zum Beispiel in ein kleines FPGA der MachXO2-Familie von Lattice mit 1200 LUT im Gehäuse QFN32.

Fazit

Es muss ja nicht die geometrische Summe sein. Auch andere vermeintlich einfache Rechenaufgaben können einen kleinen Mikrocontroller überfordern, sei es wegen des Algorithmus oder wegen des Wertebereichs. Ein selbstgebauter nummerischer Coprozessor im FPGA kann dann helfen, gestiegene Anforderungen an ein System zu erfüllen, ohne deswegen ein großes Redesign mit allen Risiken durchführen zu müssen. (fr)