Arithmetik (vpa, fimath, benchmark...)

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

sddsmhr

Forum-Anfänger


	Beiträge: 19

	Anmeldedatum: 25.11.11

	Wohnort: ---

	Version: ---

Verfasst am: 25.11.2011, 21:30 Titel: Arithmetik (vpa, fimath, benchmark...)

Hallo erstmal...

Ich entwickle im Rahmen einer Semesterarbeit ein Programm zur Visualisierung der Mandelbrot- und Julia-Mengen.
Neben effizienten Algorithmen (siehe Peitgen, Saupe...) geht es mir insbesondere auch um eine hohe Rechengenauigkeit, um tiefer bspw. in die Mandelbrot-Menge hineinzoomen zu können.

Standardgemäß wird ja mit double-precision gemäß IEEE 754 gerechnet, womit bei Zahlendifferenzen < 10^(-15) Auslöschungseffekte auftreten.

MatLab stellt hier die vpa- und fimath-Pakete (floating/fixed point arithm. mit variabler Mantissenlänge) zur Verfügung welche hinsichtlich Rechenzeit doch erheblich von der mit double-Precision abweicht (selbst wenn man mit kleiner Mantissenlänge rechnet).

Nun habe ich ein wenig im Internet recherchiert und bin auf einige Algorithmen gestoßen, welche mit double-double- oder quad-double-precision rechnen... Siehe bspw. hier, oder hier für den theoretischen Background.

Meine Frage wäre nun, ob da jemand Erfahrung hinsichtlich der Leistungsfähigkeit (Performance) insbesondere des vpa-Paketes hat. Würde es sich lohnen, evtl. ausgetüfteltere C-Routinen in MatLab einzubinden? Oder ist hier das vpa-Paket hinreichend optimiert?

sddsmhr

Themenstarter

Forum-Anfänger


	Beiträge: 19

	Anmeldedatum: 25.11.11

	Wohnort: ---

	Version: ---

Verfasst am: 29.11.2011, 14:55 Titel:

Noch keine Antwort... Crying or Very sad

Mittlerweile habe ich ein paar Fortschritte gemacht und nebenbei mal ein paar kleine numerische Experimente hinsichtlich der Laufzeit gemacht.

Zunächst hat sich das fimath-Paket für mich als unrelevant (da: fixed-point arithmetic) herausgestellt.

Das vpa-Paket von MatLab stellt sowohl die Möglichkeit für symbolische Berechnung als auch die Berechnung mit Hilfe von Gleitkommazahlen zur Verfügung - beides mit variabler Mantissenlänge. Soweit müsste ich das richtig verstanden haben.

Nun habe ich den double-double-Algorithmus implementieren können welcher Berechnungen auf 32 Stellen Genauigkeit durchführen kann und auch gleich ein bisschen Benchmark betrieben.

Ein Vergleich von Laufzeiten (Addition, 1000 Loops) ergibt beispielsweise:

double (add, 1000 loops): 0.0159 sec.
double-double (add, 1000 loops): 0.0476 sec.
vpa (32) (add, 1000 loops): 8.2316 sec.

Also etwa 8ms pro Addition - ENIAC brauchte etwa 0,2ms pro Addition... Rolling Eyes

Erhöht man nun die Anzahl der Nachkommastellen mittels 'digits(D)' für vpa bspw. auf 100,500 oder 1000 Stellen, dann führt das vpa-Paket die Berechnungen mit zeittechnisch ziemlich dem gleichen Aufwand aus.

Insofern ist das vpa-Paket dann schon ziemlich effizient, sofern man es nicht in zeitkritischen Algorithmen verwendet, bzw. allzuviele Rechenoperationen ausführt.

Dass der Aufwand der Berechnungen mit vpa aber offenbar unabhängig von der Anzahl der Nachkommastellen ist, erschließt sich mir nicht ganz... Crying or Very sad

Offenbar stellt hier MatLab keine Zwischenlösung zwischen Laufzeit und Rechengenauigkeit zur Verfügung?! Shocked

sddsmhr

Themenstarter

Forum-Anfänger


	Beiträge: 19

	Anmeldedatum: 25.11.11

	Wohnort: ---

	Version: ---

Verfasst am: 15.12.2011, 01:58 Titel:

Da:

Zitat:

Increasing the number of digits increases the accuracy, but also increases both the time and memory requirements.

Quelle

Was sich bei mir experimentell nicht bestätigen lässt. Weiß da echt keiner Rat? Sad

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 15.12.2011, 12:13 Titel:

Hallo sddsmhr,

Deine Frage ist sehr allgemein. Es läßt sich kaum über die Effizienz von Source-Code reden, den man nicht kennt. Eine Fehlende Pre-allocierung kann die schnellsten Berechnungen so stark ausbremsen, dass man Effekten von der Anzahl der Stellen nicht mehr messen kann.

Bei VPA geht die meiste Zeit für die Verwaltung der Zahlen drauf. Die eigentlichen Additionen und Mutliplikation dauern auch nicht länger als mit einer hoch-optimierten C-Funktion, da ja die gleiche Anzahl an Bits hin-und-her geschubst wird. Aber die Verwaltung für die variable Länge der Zahlen ist sehr aufwändig. Beispiel: Addiere zwei Zahlen die (irgendwie) mit einer beliebigen Nummer von Bits dargestellt werden. Das Testen, ob die Bit-Längen zusammen passen, die Behandlung unterschiedlicher Längen, die Erstellung der Ziel-Objekts mitsamt benötigtem Header: Das muss alles mehr oder weniger mühsam in Software erfolgen. Die eigentliche Addition läuft dann sehr schnell in der CPU-Hardware ab, multi-skalar, pipelined oder per SSE sogar mit mehreren Elementen per Cycle.

Ein anderes Beispiel: Ich habe in der FEX ein C-Mex zur fehler-kompensierten Summe gepostet: XSum. Die Summe mit double-double (128 bit) Genauigkeit benötigt 40% mehr Rechnenzeit als Matlabs SUM, mit 196 Bits sind es 70% mehr. Das Addieren läuft nämlich sehr schnell, der Zugriff auf das RAM ist hier bedeutender.

Gruß, Jan

sddsmhr

Themenstarter

Forum-Anfänger


	Beiträge: 19

	Anmeldedatum: 25.11.11

	Wohnort: ---

	Version: ---

Verfasst am: 15.12.2011, 20:51 Titel:

Hallo Jan,

vielen Dank erst einmal für die Antwort.

Jan S hat Folgendes geschrieben:

Bei VPA geht die meiste Zeit für die Verwaltung der Zahlen drauf. Die eigentlichen Additionen und Mutliplikation dauern auch nicht länger als mit einer hoch-optimierten C-Funktion, da ja die gleiche Anzahl an Bits hin-und-her geschubst wird.

Ja, die Laufzeiten scheinen hier in der gleichen Größenordnung zu liegen und der Einspareffekt - wenn überhaupt - eher minimal, wie ich mittlerweile herausfand. Insofern bin ich da auch nicht mehr so scharf darauf, alles in C auszulagern...

Jan S hat Folgendes geschrieben:

Aber die Verwaltung für die variable Länge der Zahlen ist sehr aufwändig.

Die Mantissenlänge will ich ja eben konkret vorgeben, was laut Dokumentation mit "digits(N)" geht.

Jan S hat Folgendes geschrieben:

Ein anderes Beispiel: Ich habe in der FEX ein C-Mex zur fehler-kompensierten Summe gepostet: XSum. Die Summe mit double-double (128 bit) Genauigkeit benötigt 40% mehr Rechnenzeit als Matlabs SUM, mit 196 Bits sind es 70% mehr. Das Addieren läuft nämlich sehr schnell, der Zugriff auf das RAM ist hier bedeutender.

Das schaue ich mir mal noch genauer an...

In der Zwischenzeit hätte ich folgenden Beispielcode anzubieten:

Code:

function vpa_bench
clc; clear all;
%digits(32);
digits(1000);
a=vpa('1'); b=vpa('1e-20');
tic; for i=1:1000, a+b; end; toc

Funktion ohne Link?

Die Laufzeiten sind hier unabhängig von der Anzahl der angegeben Dezimalstellen gleich (abgesehen von Schwankungen bedingt durch CPU-Auslastung etc.).

Das gleiche Spiel kann man mit double-Zahlen machen mit der Erkenntnis, dass die Laufzeiten bei VPA um etwa einen Faktor 100000 höher liegen!

Gut, wenn man mit 1000 Stellen rechnet, ist das sicherlich recht effizient...

Mir genügen aber weit weniger Stellen Genauigkeit, wenn ich dafür Laufzeit einsparen kann, was hier ja eben nicht der Fall ist. Sad

/sddsmhr

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 16.12.2011, 00:10 Titel:

Hallo sddsmhr,

Auch wenn Du die Mantissenlänge fest vorgibst, enthalten die VPA-Befehle die Möglichkeit, verschiedene Mantissenlängen zu benutzen. Intern werden deshalb Schleifen aufgerufen um die Daten sequentiell zu bearbeiten.
Wenn Du die Anzahl der Stellen aber hart kodierst, kann hier viel Rechenzeit gespart werden - auf Kosten der Flexibilität. So kann man ein DOT-Produkt leicht so programmieren, dass es zwei DOUBLEs verwendet um die Elemente darzustellen, die Genauigkeit also zu verdoppeln. Aber die Anzahl der Stellen frei vorzugeben, wie mit digits(N) benötig deultich mehr Aufwand.

Ich würde aus dem vpa_bench-Programm -und allen anderen Programmen, die ich jemals in einem Forum gesehen habe- das "clear all" entfernen. Es löscht alle Funktionen, die bisher in den Speicher geladen wurden. Das erneute Lesen von der Festplatte kann schonmal eine halbe Sekunde dauern. Vorteile bringt es dagegen keine.
Zudem muss man darauf achten, dass die JIT-Beschleunigung nur ordentlich läuft, wenn innerhalb der Schleifen nur ein Befehl pro Zeile steht. Die Effekte hängen stark von der Matlab-Version ab.

Gruß, Jan

sddsmhr

Themenstarter

Forum-Anfänger


	Beiträge: 19

	Anmeldedatum: 25.11.11

	Wohnort: ---

	Version: ---

Verfasst am: 19.12.2011, 01:43 Titel:

Hallo Jan.

Jan S hat Folgendes geschrieben:

Wenn Du die Anzahl der Stellen aber hart kodierst, kann hier viel Rechenzeit gespart werden - auf Kosten der Flexibilität. So kann man ein DOT-Produkt leicht so programmieren, dass es zwei DOUBLEs verwendet um die Elemente darzustellen, die Genauigkeit also zu verdoppeln.

Das wäre meines Wissens dann doch im Prinzip der Double-Double-Algorithmus...?

Jan S hat Folgendes geschrieben:

Aber die Anzahl der Stellen frei vorzugeben, wie mit digits(N) benötig deultich mehr Aufwand.

Sicherlich. Nur steht hier die zusätzlich erzielte Genauigkeit leider in einem ziemlich krassem Verhältnis zur Performance...

Jan S hat Folgendes geschrieben:

Ich würde aus dem vpa_bench-Programm -und allen anderen Programmen, die ich jemals in einem Forum gesehen habe- das "clear all" entfernen. Es löscht alle Funktionen, die bisher in den Speicher geladen wurden. Das erneute Lesen von der Festplatte kann schonmal eine halbe Sekunde dauern. Vorteile bringt es dagegen keine.

Danke für den Tipp, macht den Kohl nur leider nicht fett... Wink

Letztlich steht und fällt alles mit der bereits oben zitierten Aussage:

Zitat:

Increasing the number of digits increases the accuracy, but also increases both the time and memory requirements.

Was eben durch obigen Beispielcode widerlegt wird. Sad

/sddsmhr

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 19.12.2011, 11:09 Titel:

Hallo sddsmhr,

Zitat:

Increasing the number of digits increases the accuracy, but also increases both the time and memory requirements.

Was eben durch obigen Beispielcode widerlegt wird.

Ich sehe keine Widerlegung. Der Overhead bei VPA-Berechnungen für die Verwaltung der Mantissenlängen ist sehr groß. Die längere Laufzeit bei größerer Precision wird davon zunächst maskiert. Aber natürlich wird die Laufzeit und der Speicherbedarf größer, wenn die Anzahl der Stellen zunimmt. Messbar ist die bestimmt, wenn man mit Millionen von Stellen rechnet. 1000 Stellen sind einfach keine ernste Aufgabe für die VPA-Toolbox. Dafür würde ich eine schlankere Implementierung in C wählen. Man findet einige Mutli-Precision-Libs im Netz.

Wie genau können wir Dir nun weiterhelfen?

Gruß, Jan

sddsmhr

Themenstarter

Forum-Anfänger


	Beiträge: 19

	Anmeldedatum: 25.11.11

	Wohnort: ---

	Version: ---

Verfasst am: 11.01.2012, 16:02 Titel:

Hallo Jan.

Jan S hat Folgendes geschrieben:

Der Overhead bei VPA-Berechnungen für die Verwaltung der Mantissenlängen ist sehr groß. Die längere Laufzeit bei größerer Precision wird davon zunächst maskiert. Aber natürlich wird die Laufzeit und der Speicherbedarf größer, wenn die Anzahl der Stellen zunimmt. Messbar ist die bestimmt, wenn man mit Millionen von Stellen rechnet. 1000 Stellen sind einfach keine ernste Aufgabe für die VPA-Toolbox.

Das beantwortet ja meine Frage eigentlich, und ein paar Tests meinerseits konnten deine Aussage auch bestätigen. In diesem Fall ist die VPA-Toolbox für mich ungeeignet, da sie bei kleineren Mantissenlängen schlicht uneffizient ist. Schade. Sad

Jan S hat Folgendes geschrieben:

Dafür würde ich eine schlankere Implementierung in C wählen. Man findet einige Mutli-Precision-Libs im Netz.

Für das komplette Programm? Oder einzelne Algorithmen?

Die Demonstration meines Programms soll in MatLab erfolgen, das ist die Vorgabe. Allerdings scheitere ich bereits bei dem Versuch ein simples in C geschriebenes "Hello World"-Programm in MatLab auszuführen...

Jan S hat Folgendes geschrieben:

Wie genau können wir Dir nun weiterhelfen?

Gute Frage...

Nachdem nun zu Weihnachten auch noch mein Haupt-PC den Arsch hochgemacht hatte (Netzteil), sieht es wirklich äußerst finster aus. Mittlerweile läuft er zwar wieder, allerdings steht der Präsentationstermin für mein Programm bereits Ende nächster Woche.

Sämtliche Ansätze laufen komplett ins Leere... Egal, ob ich VPA nutzen will, meinen eigenen Double-Double-Algorithmus schreibe, oder auf C versuche auszuweichen... Null, niente, nado, nix. Nur einen Haufen Arbeit - natürlich umsonst, versteht sich.

Nun fiel mir noch ein, dass es bei C diese netten Inline-Funktionen gab... "Löst genau mein Problem!" - dachte ich. Denn es zeigte sich, dass bei meinem DD-Algorithmus insbesondere die vielen Funktionsaufrufe zur enormen Laufzeit beitragen. MatLab verspricht hier, selbst inline-Fkt. zur Verfügung zu stellen, aber auch hier Fehlanzeige... Funktioniert nämlich nur für MatLab-Ausdrücke und nicht für eigens deklarierte Funktionen.

Den Erfolg versprechendsten Ansatz sehe ich noch bei einer Auslagerung des zeitkritischen Codes in C. Da ich hier aber wohl kaum drumherum kommen werde, tagelang Tutorials zu wälzen, kann ich das auch knicken. Zumal der ganze Krempel auch noch auf einem Windows-Rechner entwickelt, aber auf einem Linux-System präsentiert werden soll... Sad

Dennoch Danke für die bisherige Hilfe.

Gruß,

Andre


Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:	Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2024 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.