Laufzeitoptimierung, MandelbrodtJuliaZoom

[Dipl Phys Ernst Winter]

Laufzeiteffektivität
Zeitkritisch wird ein Programm genannt, bei dem der Anwender darauf warten muß, daß das Programm seine Arbeit erledigt hat.
Es wird immer Probleme geben, für die der Computer zu langsam ist. Das sind numerisch komplexe Probleme, wie die des Handlungsreisenden, Probleme der pixelweisen Bildbearbeitung, wie die Erzeugung von Fraktalen, und Echtzeit-Probleme, die eine Lösung in kürzester Zeit erfordern, wie die Animation in einem Spiel.
Laufzeitoptimierung
Für zeitkrische Programme kommt der Laufzeitoptimierung hohe Priorität zu. Zur Zeit der 8-Bit Heimcomputer waren hier Assembleroutinen nahezu obligatorisch, aber wer kann heute noch einen Pentium in Assembler programmieren.
Ein konkretes Beispiel: MandelbrodtJulia Zoom
Die Zeit für die pixelweise Erzeugung eines Bildes der Mandelbrodt-Menge dauerte auf Grund des immensen Rechenaufwandes auf einem PC ohne Koprozessor Stunden. Auch mit Koprozessor ist die Erzeugung eines Mandelbrodt- bzw. Juliabildes ein Musterbeispiel für Laufzeitoptimierung geblieben. A. Schäpers widmet dem Thema in dem Buch Turbo PASCAL 6 Addinson-Wessley, 1991 einen eigenen Abschnitt.
Er beginnt mit der wichtigen Aussage, Zitat:
Bei jeder Optimierung sind die Eigenheiten des Problems zu berücksichtigen, bevor man beginnt das letzte aus dem Code herauszuholen.
um sich dann konsequent nicht daran zu halten.
1. Zunächst wird die einfachste Eigenschaft der Mandelbrodt-Menge ignoriert:
Die Mandelbrodt-Menge ist spiegelsymmetrisch zur reellen Achse Im=0
Das erfordert zur Wahrung der Richtigkeit, dass die reelle Achse mit einer Pixelzeile zusammenfällt. Da er nicht dafür sorgt, wird sein Programm Bilder erzeugen können, die nicht streng symmetrisch sind.
Die Symmetrie kann zur Verbesserung der Laufzeiteffektivität ausgenutzt werden: Bezeichnet man die Pixelzeile der reellen Achse mit y0, so braucht man (sofern y0 im Bildfenster liegt), nur die Punkte y≥y0 bzw. y≤y0zu iterieren und kann diese in den symmetrischen Bildteil kopieren. Beim Übersichtsbild spart man so die Hälfte der Iterationen.
Analog gilt für Julia-Mengen
Julia-Mengen sind zentral¬symmetrisch zum Koordinatenursprung.
Zur Wahrung der Richtigkeit, muss der Koordinatenurprung mit einem Pixel zusammenfallen. Auch hier braucht man kann zur Verbesserung der Laufzeiteffektivität nur Punkte mit y≥y0 bzw. y≤y0 zu iterieren und kann sie in den gegenüber liegenden Quadranten kopieren. Beim Übersichtsbild spart man so die Hälfte der Iterationen.
2. A. Schäpers beginnt die programmbezogene Optimierung mit dem inzwischen allgemeinen Wissen
Das Innere von Kopfkreis und Rumpfzykloide gehören zur Mandelbrodt-Menge.
Er folgt dann Werner Duranti, der in der Ausgabe 3/87 der Zeitschrift c’t zeigt, wie man die Iteration ihrer Punkte übergeht, indem man bei jedem Bildpixel zunächst testet, ob es einem Punkt in Kopfkreis oder Rumpfzykloide entspricht.
Dabei ist er jedoch vom Pferd auf den Esel gekommen! Die Rechenzeit für die Gesamtansicht geht infolge der eingesparten Iterationen trotz Testaufwand zwar auf ein Fünftel zurück, aber bei einem ganz außerhalb von Kopf und Rumpf liegendem Ausschnitt wird die Zeit zum Testen jedes Punktes unnütz hinterher geworfen.
Die Gesamtansicht ist jedoch keineswegs ‘Standardausschnitt’ im Sinne von häufig zu berechnen, sondern ein selten verwendeter Sonderfall. Standard sind Ausschnitte am Rande der Mandelbrodt-Menge, die oft keine inneren Punkte von Kopf und Rumpf enthalten.
Versuchen wir diese Optimierung zu retten: Nach einem einfachem Test, ob die Zeile den Kopf bzw. Körper überhaupt schneidet, sind die Schnittpunkte der Zeile mit Kopf und Körper zu bestimmen und die Iteration auf die äußeren Punkte zu beschränken. Das scheitert daran, dass sich Schnittpunkte der Zeile mit der Zykloide nicht berechnen lassen.
Aus den Formeln von W. Duranti erkennen wir jedoch, dass sich der Punkt der Zykloide für gegebenes x berechnen lässt. Wir organisieren den Bildaufbau daher spaltenweise, womit sich alles stark vereinfacht:
Ein einfacher Test ergibt, ob die Spalte Kopf bzw. Rumpf schneidet. Gegebenenfalls wird der Schnittpunkt der Spalte mit Kopfkreis oder Zykloide berechnet und die Iteration der Punkte bei diesem Wert begonnen. Der Zwickel unter dem Rumpf im Bereich Re = 0.25..0.38 ist gesondert zu behandeln.
Hinweis: Diese Optimierungen sind bei sehr starken Vergrößerungen, wenn der Wert für y0 den Wertebereich der Integerzahlen überschreitet, nicht mehr durchführbar. Das Bild wird dann über den ganzen Bildschirm zeilenweise aufgebaut.
3. Optimierung des Codes.
• Bei den Routinen zur Iteration helfen nur in Assembler geschriebene laufzeitoptimalen Prozeduren unter Verwendung des Arithmetikprozessors weiter. Die Funktionen ItMdl und ItJul (nach A. Schäpers) verlegen die gesamte Iteration in die Register des Koprozessors. Sie sind extrem schnell, da jeglicher Speicherzugriff während der Iteration vermieden wird.
• Das Setzen der Farbe eines Pixels mit der Canvas-Property Pixels wäre extrem langweilig und dem Programm nicht angepaßt, da die Farbe als Color und nicht als Farbindex übergeben wird.
Die Farbindices für die Bildpixel als Ergebnisse der Iteration werden daher in einem Byte-Array auf dem Heap gespeichert. Das ermöglicht eine optimal einfache Adressierung bei wahlfreier Folge, die infolge der Optimierung mit gespiegelten Punkte notwendig ist.
Zur Anzeige wird eine Bitmap mit 256 Farben verwendet, in der die Farbindices mit 1Byte/Pixel gespeichert sind. Das fertige Byte-Array kann blitzschnell über ein TFileStream Objekt in diese Bitmap-File kopiert werden.

[Medium]

Auch wenn manche Optimierungen in Anbetracht heutiger Rechner sehr weit führend erscheinen mögen, dennoch hübsch!
Edit: Nicht hübsch ist jedoch die sehr "eigene" Bedienung des ganzen. Insbesondere missfiel mir, dass in Eingabefeldern Backspace und Entfernen keine Wirkung haben, sowie teils nicht offensichtliche Optionen bzw. Reaktionen. Bsp.: Umschalten von Mandelbrot->Julia. Ich habe nicht verstanden dass ich via Klick einen Startwert aussuchen kann, und da die Augen soeben noch auf der Menuleiste waren fielen die neuen Buttons ganz rechts nicht auf. Ich habe erst gewartet ob etwas passiert, nach etwas "gelangweiltem" Umsehen erst habe ich die Buttons für die Aktualisierung entdeckt. Insgesamt fällt die Bedienung ziemlich eigenwillig aus, leider auch nicht im positiven Sinne (finde -ich-).
Das hat zwar nun in keiner Weise etwas mit dem eigentlichen Thema zu tun, aber ich hoffe dass es als konstruktive Kritik dennoch willkommen ist.

Bei derart hochgradig parallelisierbaren Aufgaben gibt es mittlerweile auch noch eine weitere Möglichkeit, die immense Unterschiede ausmacht: GPGPU. Ein Problem hat man bei Fraktalen hier allerdings (noch): Fast alle aktuellen GPUs arbeiten mit Single-Precision, wodurch entweder die Zoombarkeit schnell an ihre Grenzen kommt, oder man ist genötigt höhere Genauigkeit via Software (bzw. Shader) zu basteln, was der Geschwindigkeit wieder etwas nimmt - jedoch weit weniger als durch die Bearbeitung auf der GPU gewonnen wurde.
Hierzu empfiehlt sich zudem eine Grafikkarte mit mind. DirectX 9, da erst ab da die Shader genügend Komfort (= die nötigen Instruktionen) bieten. Mit DirectX 11 werden allerdings "Compute-Shader" in den Standard aufgenommen, die die Zweckentfremdung der GPU nativ möglich machen. Derzeit ist das noch etwas in den Kinderschuhen und bedarf manchem Kunstgriff (Array=Textur und dergleichen).

Da es leider für Win32 Delphi keine brauchbare D3D Umsetzung gibt, ist man auf C++ angewiesen. Mit C# habe ich sowas in der Art schon einmal für .NET implementiert, wobei auch hier Hürden zu nehmen sind: Managed DirectX wurde komplett eingestellt, und wird von MS in keiner Weise mehr supported, geupdated noch sonst etwas. Statt dessen gibt es jetzt XNA, ein Spieleentwichlungs-Framework basierend auf .NET, was aber leider Crossplatform für PC und XBox gedacht ist. Da die XBox eine DX9 kompatible GPU hat, ist bis auf unbestimmte Zeit auf keine "native" D3D Unterstützung für .NET für DX10 und das bereits im Test befindliche DX11 zu erwarten.
Ziemlich ärgerlich, gäbe es da nicht eine kleine aber geniale OS Truppe, die mit SlimDX einen bislang DX9 und 10 unterstützenden Wrapper erstellt haben der dem Stil von Managed DirectX nahezu gleicht - und es ist erstaunlich komplett, sowie aktiv in Betreuung und Weiterentwicklung.

NVidia hat mit CUDA bereits ein Framework für GPGPU auf aktuellen (NV) GPUs geschaffen, dass ohne Compute-Shader oder Kunstgriffe auskommt. Um dieses sinnvoll einsetzen zu können ist jedoch mit einiger Einarbeitungszeit zu rechnen, insbesondere muss man sich die zu x86/x64 doch SEHR unterschiedliche Architektur der Grafikkarten zu eigen machen. Ob sich dieses mit der Aussicht auf die Compute-Shader noch lohnt wage ich allerdings zu bezweifeln, dennoch sind die Ansätze und Perspektiven ausgesprochen interessant.

CPU und GPU kommen sich immer näher (immer mehr Cores in einer CPU / immer generellere Verwendung von GPUs), und ich kann mir gut vorstellen dass wir in ein paar Jahren diese Unterscheidung gar nicht mehr machen. Daher lohnt es sich denke ich sehr, sich jetzt schon mit Parallel-Computing auch auf Einzelplatzrechnern zu befassen. Ich wittere eine kleine neue Ära in nicht allzu ferner Zukunft


Ich hoffe ich konnte damit zumindest ein wenig Lust auf diese recht spannenden und verhältnismäßig neuen Möglichkeiten machen, und Fraktalmengen sind eines der Paradebeispiele für diese Art der DV.

Schönen Gruß,
Medium


Edit: Schlechtschreibung

[Dipl Phys Ernst Winter]

Zitat:

Nicht hübsch ist jedoch die sehr "eigene" Bedienung des ganzen.

Vielleicht sollte man doch die mitgelieferte Hilfe eimal lesen!
Sie hat mir viel Arbeit gekostet.

Die "eigene" Bedienung gestattet
- ein müheloses Zoomen und Rückkehr zum Ausgangsbild
- einen mühelosen Wechsel von Mandelbrodt nach Julia und zurück.
- ein einfaches Umfärben des Bildes
- projektion des aktuellen Bildes auf eine Kugel

Ich denke das man das nicht einfacher realisieren kann.

[Mithrandir]

Zitat von Dipl Phys Ernst Winter:

Ich denke das man das nicht einfacher realisieren kann.

Nun ist es aber so, dass der durchschnittliche Windows-User von einem Eingabefeld erwartet, dass man es mit Backspace komplett löschen kann, und nicht mit den Pfeiltasten erst navigieren muss oder den Umweg um Strg+A und Entf gehen muss.

Kleiner Fehler, der mir noch aufgefallen ist:

• "Ausschnitt" => "aufziehen"
• Dann einfach auf das Bild klicken (also keinen Rahmen ziehen)
• Dann auf "OK" klicken

Bewirkt:

Code:

---------------------------
Mandeljuliazoom
---------------------------
Zu starke Vergrößerung! Weiter mit OldBild
---------------------------
OK
---------------------------

gefolgt von

Code:

---------------------------
Mandeljuliazoom
---------------------------
Fließkommadivision durch Null.
---------------------------
OK   
---------------------------

Danach lässt sich das Programm nicht mehr bedienen.

//Nachtrag: "Nicht mehr bedienen" ist nicht ganz korrekt. Es lässt sich wohl beenden, aber zahlreiche Funktionen bleiben noch ausgegraut und gezeichnet wird auch nichts mehr.

[Dipl Phys Ernst Winter]

Daniel G hat folgendes geschrieben]

Zitat:

Nun ist es aber so, dass der durchschnittliche Windows-User von einem Eingabefeld erwartet, dass man es mit Backspace komplett löschen kann, und nicht mit den Pfeiltasten erst navigieren muss oder den Umweg um Strg+A und Entf gehen muss.

Nun ich kenne den 'durchschnittliche Windows-User' wohl zu schlecht.
Bei einem Eingabefeld möchte ich aber unterscheiden, ob es zur Eingabe einer neuen Zahl dienen soll (im allgemeinen mit AutoSelect=true) oder ob es eine Zahl zur Edition durch Überschreiben bereitstellt. Genau das Letztere ist hier der Fall. Delete und Backspace sind bewußt unterdrückt, da sie zu einem nicht konvertierbaren String führen würden. Du brauchst auch nicht mit den Pfeiltaste zu navigieren: Mit Home steht der Cursor am Anfang des Feldes und Du kannst die Zahl überschreiben.

Zitat:

//Nachtrag: "Nicht mehr bedienen" ist nicht ganz korrekt. Es lässt sich wohl beenden, aber zahlreiche Funktionen bleiben noch ausgegraut und gezeichnet wird auch nichts mehr.

Es wurde doch 'Weiter mit OldBild' empfohlen

[Mithrandir]

Zitat von Dipl Phys Ernst Winter:

Delete und Backspace sind bewußt unterdrückt, da sie zu einem nicht konvertierbaren String führen würden.

Inwiefern?

Zitat von Dipl Phys Ernst Winter:

Es wurde doch 'Weiter mit OldBild' empfohlen

Ich hab mal das Bild der hängenden Anwendung angehängt. Die Meldung 'Weiter mit OldBild' ist für mich in diesem Falle nicht wirklich aussagekräftig...

[isilive]

Erstmal: Schönes Programm!! Und es rechnet auch richtig schnell!

Warum Backspace oder Delete in einem Edit problematisch sein sollten verstehe ich auch nicht. Es ist wichtig um eine normale Bedienbarkeit des Programms zu erhalten. Eventuelle Falscheingaben sollten sich problemlos abfangen lassen.

Ausserdem wenn ich 1.05 eingebe kommt eine Fehlermeldung "Ungültiger Wert". Bis ich 1.050000000000 eingebe. Das ist nicht sinnvoll, das ist Steinzeit. Da verhält sich mein TI-59 aus den Siebziger-Jahren kulanter

Wünschenswert wäre noch:
- Aufziehen des Bildes funktioniert mit 1-2 statt 4 Klicks
- Grösse des Bildes änderbar (auch grösser)
- grösserer Farbraum

Ansonsten, nix für ungut, tolles Programm!

[stoxx]

Zitat von Daniel G:

Nun ist es aber so, dass der durchschnittliche Windows-User von einem Eingabefeld erwartet, dass man es mit Backspace komplett löschen kann, und nicht mit den Pfeiltasten erst navigieren muss oder den Umweg um Strg+A und Entf gehen muss.

ach komm, bei dem Alter des Entwicklers darf man durchaus auch etwas nachsichtig sein, und sich in gute alte Zeiten zurücksetzen lassen. Besonders charmant fand ich die bevorzugte Unterstützung des des ASM Codes von 286'er Prozessoren

Was ich mich ja früher immer gefragt habe, ob man diese tollen Mandelbrot Bilder und Berechnungen auch für andere Dinge benutzen kann?

Ich kenn mich ja zu wenig damit aus, aber würden sich damit auch Zeitreihenprognosen erstellen lassen, denen man chaotisches Verhalten unterstellen möchte?