Da ich demnᅵchst eine FFT fᅵr ein Projekt fᅵr den Beagle Bone brauche,
und letztens die Frage aufkam, habe ich mal die Kiss FFT Library auch
fᅵr mein STM3F4Discovery Devboard ausprobiert. Hier die Library:
http://kissfft.sourceforge.net
(KISS ist Programmiererslang und bedeutet soviel wie das Gegenteil von
Feature Creep, was man bei anderen FFT-Libraries gerne sieht:
http://de.wikipedia.org/wiki/KISS-Prinzip )
Hier das gesamte Testprojekt:
http://www.frank-buss.de/tmp/FFT-Test.zip
Ist recht groᅵ, da ich das gesamte Projekt mal zusammengepackt habe,
hier der relevante Sourcecode fᅵr den Test:
http://pastebin.com/0tPbWJjW
Ich habe es mit cs-make von CodeSourcery compiliert, mit einem GCC
4.6.1. Im Hintergrund habe ich noch zwei I2S Datentransfers per DMA
laufen lassen, mit 96 kHz Samplefrequenz und 32 Bit Wortbreite, Daten
gesendet und empfangen, im Full-Duplex und Double-Buffering Betrieb, mit
zusᅵtzlicher Zwischenspeicherung und Lesen aus einem Ringbuffer. Das
macht aber nicht viel aus, ohne Transfer lᅵuft es nur ca. 6% schneller.
Hier die Messergebnisse pro FFT-Berechnung, wenn der ARM-Core mit der
maximalen Geschwindigkeit von 168 MHz lᅵuft:
size: 256, time: 0.257400 ms, with dB: no, sum:
12798979072.000000
size: 256, time: 3.709400 ms, with dB: yes, sum: 252872096.000000
size: 512, time: 0.698600 ms, with dB: no, sum: 25597667328.000000
size: 512, time: 7.601900 ms, with dB: yes, sum: 526377920.000000
size: 1024, time: 1.164700 ms, with dB: no, sum: 51200745472.000000
size: 1024, time: 14.972600 ms, with dB: yes, sum: 1180834944.000000
size: 2048, time: 3.057900 ms, with dB: no, sum: 102385901568.000000
size: 2048, time: 30.673901 ms, with dB: yes, sum:
2318690560.000000
Ich habe einmal nur die FFT berechnen lassen und die Ergebnisse summiert
(damit eine eventuelle Optimierung das nicht wegoptimiert), was die
Angabe "with dB: no" ist. Ein etwas praxisrevelanteres Beispiel ist
dann, "10 * log10f(r * r + i * i)" auf jedem Ergebniswert zu berechnen.
Das scheint die Zeit ziemlich zu erhᅵhen.
Eigentlich hat der verwendete ARM eine Floating-Point Einheit, aber die
hat glaube ich keine transzendente oder logarithmischen Funktionen. Also
wenn man schnell bleiben will, sollte man in der quadratischen Ebene die
Daten weiterverarbeiten, oder ggf. eine schnellere Nᅵherung fᅵr den
Logarithmus verwenden. Sieht aber generell recht gut aus, wenn man
irgendwas realtime-mᅵᅵiges damit machen wollte. Ich will demnᅵchst mal
den FFT-Overlap-Add Algorithmus damit ausprobieren, da man damit lange
FIR-Filter sehr schnell in der Frequenzdomᅵne berechnen kann und dann in
Echtzeit Audiosignale damit bearbeiten.
Hier die Ergebnisse von einem Beagle Bone Black, mit dem darauf
installierten Compiler compiliert (und leicht modifiziertem Testcode mit
dem Qt-Framework fᅵr die Zeitmessung, da ich das fᅵr die eigentliche
Anwendung spᅵter auch brauche), der mit 1 GHz lᅵuft:
size: 256, time: 0.440500 ms, with dB: no, sum:
12798979072.000000
size: 256, time: 0.590400 ms, with dB: yes, sum: 252872096.000000
size: 512, time: 0.955500 ms, with dB: no, sum: 25597667328.000000
size: 512, time: 1.300000 ms, with dB: yes, sum: 526377920.000000
size: 1024, time: 2.060500 ms, with dB: no, sum: 51200745472.000000
size: 1024, time: 2.743500 ms, with dB: yes, sum: 1180834944.000000
size: 2048, time: 4.627700 ms, with dB: no, sum: 102385901568.000000
size: 2048, time: 5.991300 ms, with dB: yes, sum:
2318690560.000000
Interessanterweise langsamer, als auf dem STM3F4, aber der Logarithmus
lᅵuft merkwᅵrdigerweise bedeutend schneller. Ist bei der CodeSourcery
Library etwa die Mathematik-Library ohne die Floating-Point-Einheit
compiliert worden und auf dem Beagle Bone Black alles nur per Software
Emulation berechnet? Bin jetzt zu faul nachzuschauen, ob der eine
Hardware Floating-Point-Einheit hat, wie es der ARM Core auf dem
Raspberry Pi bietet und mit dem "hardfp" Debian Wheezy.
Und schlieᅵlich zum Vergleich die Messung mit dem gcc von mingw von Qt
Creator im Release-Modus fᅵr Windows compiliert, ausgefᅵhrt auf einem
Intel Xeon mit 2,4 GHz Takt:
size: 256, time: 0.008000 ms, with dB: no, sum:
12798615552.000000
size: 256, time: 0.014900 ms, with dB: yes, sum: 252872080.000000
size: 512, time: 0.019200 ms, with dB: no, sum: 25597716480.000000
size: 512, time: 0.034500 ms, with dB: yes, sum: 526377888.000000
size: 1024, time: 0.033800 ms, with dB: no, sum: 51195023360.000000
size: 1024, time: 0.064900 ms, with dB: yes, sum: 1180834944.000000
size: 2048, time: 0.085000 ms, with dB: no, sum: 102391111680.000000
size: 2048, time: 0.147700 ms, with dB: yes, sum:
2318690560.000000
Ist also 40 bis 250 mal (fᅵr die log10-Berechnung) schneller, als auf
dem STM32F4. Man sieht auch kleinere Unterschiede in der Summe, obwohl
alle ja eigentlich floats mit 4 Bytes verwenden, was vielleicht daran
liegt, daᅵ der Intel intern mit hᅵherer Genauigkeit rechnet.
Den I2S Datentransfer mit DMA Transfer zu programmieren war ᅵbrigens
nicht so einfach, da es kein genau passendes Beispiel fᅵr meinen
Anwendungsfall gab (ich wollte einen externen Chip per
I2S3/I2S3Ext-Modul ansprechen). Ich dachte bin ich vielleicht in 1-2
Stunden fertig, aber war dann 350 Zeilen und zwei Tage spᅵter froh, daᅵ
es endlich lᅵuft. Eine falsche Zeile und nichts lᅵuft mehr, was die
Fehlersuche interessant macht.
Die STM32 Library ist auch zu low-level, sodaᅵ man leicht Fehler machen
kann oder was vergessen kann (DMA_IT_TCIF5 statt DMA_FLAG_TCIF5 fᅵr den
DMA_ClearITPendingBit-Aufruf verwendet? Interrupt-Sturm). Und das
Datenblatt ist nicht immer genau: Reference-Manual sagt "examples of DMA
request mappings", "depends on the product implementation", aber man
findet es nicht im Datasheet des betreffenden Prozessors. Und es stellte
sich heraus, daᅵ es nicht nur ein Beispiel ist, sondern daᅵ es anders
als dort angegeben erst gar nicht lᅵuft. Wieder ein paar Stunden weg mit
Fehlersuche.
Mir sind auch noch ein paar Sachen etwas unklar, vielleicht werde ich
mal den Support anschreiben. Aber letztens meinte jemand, daᅵ der gar
nicht erst antwortet. Schade, denn der Microcontroller ist wirklich gut,
was ich bis jetzt so gesehen habe und ich konnte auch noch keinen
Chip-Fehler bei meinen Experimenten feststellen, wie man es schonmal bei
manchen Chips von Atmel hat. Fehlt nur noch eine einfacherere
anzuwendende Library, wenn man nicht die Register alle selbst
programmieren will.
Oder noch besser: ein GUI mit Codegenerator, wie es die PSoC IDE von
Cypress bietet. Da kann man schon von vorneherein keine Fehler bei der
Registerkonfiguration machen, da das GUI jeweils nur die gᅵltigen
Auswahlmᅵglichkeiten zur Verfᅵgung stellt. Ich bin ja eigentlich nicht
ein Fan von Codegeneratoren, aber die machen einem das
Programmiererleben wirklich leichter.
--
Frank Buss,
http://www.frank-buss.de
electronics and more:
http://www.youtube.com/user/frankbuss