#Clocks für float division

[WarChild]

Hallo,

Ich habe folgendes Problem:
Ich habe leichten Zeitmangel bei der ausführung meiner Berechnungen.
Ich berechne viele Sinus, Cosinus, Arussinus, Akuskosinus, und einige Wurzeln mittles der AVR math.h bibliothek. außerdem muss ich gelegentlich von Rad in Grad umrechnen. wenn ich im simulator durchklicke, dann scheint es mir so, als würden für die berechnung Radian/M_PI*180 3000 Clocks und für die eigentliche Winkelfunktion nochmal 4000 Clocks drauf gehen. Um jetzt zeit zu sparen, dachte ich mir, dass ich einfach die umrechnung umgehe, indem ich eigene funktionen schreibe, die vlt nicht ganz so exakt sind wie die der Bibliothek, aber dafür noch schneller. Mehr als 0.05 Grad kann ich eh nicht auflösen.

Kann es also realistisch sein, dass eine float division 3000 Takte frisst? Wenn ja, dann sollte ich bei eigenen Algorithmen eine float division vermeiden. Wenn die nur 50 Takte frisst dann lohnt es kaum darüber nachzudenken.


vielen Dank für Euer Feedback!

mfg WarChild

[Besserwessi]

Ein paar Daten zur geschwingdigkeit von GCC findet man z.B. hier :
"avr-libc-user-manual.pdf" unter Benchmarks.
Sollte sich im doc-ordner von WINAVR befinden.

Danach sollte die Division etwa 466 Zyklen brauchen. Die 4000 Zyklen für die Winkelfunktion sind grob OK.

Man sollte beim Compilieren mit GCC-AVR darauf achten die das man die OPtion -Lm mit drin hat, damit die schnellere Mathe bibliothek genutzt wird. Das reduziert auch die Programmlänge.

Die Rechnung Winkel / Pi*180 sollte eigentlich im wesenlichen zur Compilezeit berechent werden. Notfalls als Winkel*(180/Pi) schreiben. Dann sollte zur Laufzeit nur eine Multiplication übrig bleiben.

[Felix G]

Kann es also realistisch sein, dass eine float division 3000 Takte frisst? Wenn ja, dann sollte ich bei eigenen Algorithmen eine float division vermeiden.

Float Divisionen sollte man eigentlich grundsätzlich immer vermeiden, vor allem auf einem 8Bit µC wie den AVRs.

Besser noch man vermeidet Floats allgemein, und berechnet so viel wie möglich mit Festkommaarithmetik.


Auch kann man mit ein paar Tricks bei spezielleren Problemen oftmals massenhaft Zyklen sparen. Nehmen wir mal an, man möchte einen Float mit 2^n multiplizieren, dann geht das am schnellsten indem man eine Funktion schreibt, die auf den Exponenten einfach n aufaddiert. Das ist z.B. auch hervorragend geeignet, wenn man einen Float in einen Int konvertieren und dabei gleich hochskalieren möchte (für mehr Genauigkeit).

Das ist nur ein Beispiel wie man schnellen Code schreiben kann, wenn man ein Problem erstmal genau betrachtet.

[WarChild]

-lm ist im makefile schon drin (große hoffnung kaputt), das umklammern kann ich nochmal ergänzen. Kann ich auch z.B. x*(1.0/(180*M_PI)) berechnen lassen?
eine float multiplikation sollte doch eigentlich nur zwei zyklen benötigen oder nicht? s.Datenblatt FMUL Anweisung. Jedoch dauert das bei mir ebenfalls wesenlich länger. 500 Takte.

Und ich habe noch eine frage zum AVR float format. Für eine signum(float x) funktion benötige ich die anzahl der bits, die eine float zahl einnimmt, da das erste bit das vorzeichen enthält.
Der normale vergleich der float zahl > 0 oder nicht benötigt 400 Takte.
Ich habe schon versucht einen simplen int8_t pointer auf die float Zahl zu setzen und dann nach größer oder kleiner null zu prüfen, aber das schien nicht zu funktionieren. Auf was zeigt die Adresse einer float zahl? auf eine struktur oder einfach nur einen zusammenhängenden 4Byte speicherbereich?

mfg Warchild

[Besserwessi]

Die Multiplication sollte gut 130 Zyklen dauern. Der ASM-befehl FMUL ist für Festkommazahlen, nicht für Fleißkomma. Der wird da nicht viel weiter helfen.

Es könnte sein, das der Vergleich x>0 immer noch als Test von (x-0) gemacht wird. Eine Subtraktion ist dabei nur unwesentlich schneller als die Multiplikation. Das liegt daran, da man zur addition die beiden Zahlen erst mal auf den gleichen exponenten bringen muß. Beim verschieben der Bits ist des AVR nicht besonders effektiv.

Bei den Routinen für Fließkomma soll es irgenwann bei etwa GCC Version 4 eine deutliche Verbesserung gegeben haben. Es könnte sich lohnen eine neuere VErsion von WINAVR zu nutzen.



Das Format der Floats sollte etwa so aussehen:
3 bytes für die mantisse, wobei das führende Bit fehlt, denn es ist immer eine 1.
1 byte für Vorzeichen, Exponent und Speziallwerte wie Null, Nan.

Fürs separieren des Vorzeichens gibt es in math.h sogar eine extra Funktion:
int signbit (double __x) __ATTR_CONST__;
Sonst sollte das Bit 7 im 4 ten Byte für das Vorzeichen stehen. Also nicht das erste Bit.

Die addresse ein float Zahl sollte auf das erste der 4 bytes zeigen. Man könnte das auch als Strucktur sehen, oder einfach nur als 4 bytes.

[Felix G]

Auf was zeigt die Adresse einer float zahl? auf eine struktur oder einfach nur einen zusammenhängenden 4Byte speicherbereich?

Im Normalfall auf einen 4Byte Speicherbereich, der eine IEEE 754 Single Precision Gleitkommazahl enthält.

Wie genau dieser Datentyp aufgebaut ist kannst du z.B. unter http://de.wikipedia.org/wiki/Gleitkommazahl nachlesen. Da steht unter anderem auch, daß es für ein und dieselbe Zahl mehrere mögliche Darstellungen geben kann (aber nicht muss), und was der Compiler alles beachten muss um zum Standard kompatibel zu sein. Spätestens wenn man sich das mal durchgelesen hat wird einem klar, wieso Float-Operationen so verdammt lange dauern.

Andererseits helfen einem diese Informationen aber eben auch, um für bestimmte Spezialfälle sehr schnelle Funktionen schreiben zu können (wie z.B. die von mir schon beschriebene Multiplikation mit 2^n).

[WarChild]

Ja, danke für eure tips.

Ich habe jetzt meinen Code bezüglich der Laufzeit optimiert und konnte folgende Ergebnisse erzielen:
Clocks
vorher / nachher Funktion
2500/325 Berechnung der benötigten Pulslängen (8 mal schneller)
34000/382 Berechnung der Translation (100 mal schneller)
175000/152000 Berechnung der Rotation (18% schneler)
400000/375000 Berechnung der Gelenkwinkel IK (8% schneller)

Alle anderen Funktionen benötigten bereits zuvor nur wenige hundert zyklen. Aber es bleibt die Problematik, dass die Rotation und die IK zu langsam sind. Ich werde die rotation, wenn meine Umrechnungen und meine eigene Sinus/Cosinus Funktion funktionieren wahrscheinlich ähnlich wie die Translation beschleunigen können, aber es bleibt das Problem der IK. Gibt es ein 32Bit Integer? ich habe das problem, dass meine zahlen, die im bereich -240 bis 240 liegen bei festkommadarstellung mit 16 Bit (7nachkomma Bits) beim quadrieren überlaufen, und meine funktionen nicht mehr funktionieren wenn ich vorm quadrieren selbst erst herabskaliere,dann können zahlen nahe der null einfach verschwinden.

mfg WarChild

[Besserwessi]

Natürlich gibt es 32 bit Integer Zahlen: long und unsigned long.

[Felix G]

Wenn du in C Integer Variablen mit definierter Länge brauchst (long kann bei der einen Architektur 32 Bit haben, bei einer anderen aber auch gern mal 16 oder 64), dann verwende die stdint.h oder inttypes.h (letztere bietet zusätzlich zu den neuen Typen noch ein paar mehr oder weniger nützliche Makros).

da drin sind Integer-Typen definiert wie uint8_t (= unsigned char) oder int32_t (= long int), bei denen man ganz genau weiss wie lang sie sind.

[WarChild]

Also Festpunktarithmetik ist schon so eine sache.
Auf dem PC funktionieren diese berechnungen, aber im µC nicht. Ich vermute da ist irgendwo ein Überlauf, den ich nicht sehe.
Ich habe alle Typen entsprechend umgewandelt.
hier meine Festpunkt sinus aproximation:

const int16_t	W=180; 		//Winkel eines Halbkreises
const int16_t	W2=360;		//Winkel eines Vollkreises
const int16_t 	Wd2=90; 		//Winkel eines Viertelkreises  

int16_t sinus(int16_t x)					//Eingabe mit Skalierung 128 = 7 Festkommabits Ausgabe 14 festkommabits
{

	if((x>>7)>W) x=-x+(W<<7);						//x wird auf das Intervall [-W;W] normiert (aufgrund der Achsensymmetrie um x=0)
    if((x>>7)<-W) x=-x-(W<<7);

 	//Parabel
	const int16_t B = 182; //2^-13	//(4/W);		//linearer Formfaktor der Parabel
    const int16_t C = -259;//2^-21	//(-4/(W*W));	//quadratischer Formfaktor der Parabel
	
	long y=((B*x)>>6)+((((C*x)>>11)*x*signi(x))>>10);	//2^-14 //Funktionswert der einfachen Parabel
    
    //Parabel Korrektur
	const int16_t Q = 99;	//2^-7	//0.775;		//Linearfaktor der einfachen parabel
    const int16_t P = 29;	//2^-7	//0.225;		//Linearfaktor der quadrierten korektur Parabel

    y=((Q*y)>>7)+((((P*y)>>7)*y*signl(y))>>14);	//2^-14	//Endergebnis nach gewichteter Summenbildung
	
	return y;
}

mfg Warchild