Paralleles Rechnen

mr wong   google bookmarks   del.icio.us   yigg   digg   folkd
Apfelmännchen

Dieses Demo berechnet ein sogenanntes Apfelmännchen, dessen numerische Berechnung sich leicht parallelisieren lässt. Bis zu vier Threads, in je einer anderen Programmiersprache kodiert, errechnen einen horizontalen Teilbereich dieses fraktalen Gebildes. Mit Hilfe der Maus kann ein beliebiger Bereich dieser Grafik vergrößert werden:

  • Wenn sich der Mauszeiger über der fraktalen Grafik, beschriftet mit Apfelmännchen, befindet, erscheint ein Fadenkreuz.
  • Drücken Sie die linke Maustaste, um die linke obere Ecke des zu vergrößernden Bereichs festzulegen.
    Bewegen Sie nun den Mauszeiger zur gewünschten rechten unteren Ecke des zu vergrößernden Bereichs und drücken Sie noch einmal die linke Maustaste.
  • Nun wird der Wertebereich des Apfelmännchens dem ausgewählten Rechteck entsprechend neu berechnet.
  • Alternativ kann der Wertebereich auch manuell über die entsprechenden Eingabefelder geändert werden.
  • Mit der Schaltfläche Berechnen wird nun ein dem geänderten Wertebereich entsprechendes Apfelmännchen generiert.
  • Die Schaltfläche Zurücksetzen stellt den ursprünglichen Wertebereich und die entsprechende Grafik wieder her.
Fractal
Threadzeiten in Millisekunden
JAVA 31            
Wertebereich
x-Achse
y-Achse
Programmiersprache Java
C
FORTRAN77
Assembler (x86)

Bemerkungen

Bei der Interpretation der Thread-Laufzeiten müssen folgende technische Gegebenheiten berücksichtigt werden:

  • Da diese Demonstration auf einem Einprozessorsystem läuft, bringt die Parallelisierung in Form von Threads keinen Geschwindigkeitsvorteil.
  • Die in C, FORTRAN77 und Assembler kodierten Threads müssen - im Gegensatz zum Java-Thread - die berechneten Grafikdaten per JNI (Java Native Interface) an das Servlet weiterreichen. Diese Interaktion kann bei den kurzen Rechenzeiten die Geschwindigkeitsvorteile der nativen Programmiersprachen gegenüber dem JIT (Just In Time) Java-Code nivellieren.
  • Apfelmännchen, die mit Hilfe des manuell kodierten Assembler-Codes berechnet werden, können sich in feinen graphischen Details von den Ergebnissen der anderen Programmiersprachen (Java, C und FORTRAN77) unterscheiden. Der Assembler-Code führt durchgehend die Berechnungen mit 80-Bit-Genauigkeit über den Stapelspeicher der FPU (Floating Point Unit) durch, während der compilierte Code der anderen Programmiersprachen Zwischenergebnisse der FPU im Speicher (2*32 = 64 Bit) ablegt. Da ein Punkt des Apfelmännchens durch eine Rekursion bestimmt wird, kann sich der Unterschied in der Rechengenauigkeit (64/80 Bit) in Form einer unterschiedlichen Punktfarbe auswirken.

Mathematischer Hintergrund

Dieses bekannte fraktale Gebilde basiert auf der einfachen rekursiven Funktion z = z2 + c mit einem Startwert z0 = 0 und c als Konstante. z und c entsprechen komplexen Zahlen, die auch als Punkte in der Ebene dargestellt werden können. Für die Berechnung wird nun diese Rekursion für eine endliche Punktmenge aus dieser Ebene durchgeführt. Die Rekursion eines Punktes kann folgende Verhaltensweisen zeigen:

  • Die Werte eines Punktes verlassen ein bestimmtes Intervall nicht - die Werte bleiben endlich. In diesem Fall gehört der Punkt zur sogenannten Mandelbrot-Menge*, und es wird ihm die Farbe Schwarz zugeordnet.
  • Streben die Werte des Punktes ins Unendliche, dann ist der Punkt kein Element der Mandelbrot-Menge, und seine Farbe wird in Relation zur Anzahl der Iterationen gesetzt, nach denen seine Werte ins Unendliche streben.
* Die Menge ist nach dem französischen Mathematiker Benoît Mandelbrot benannt, der als erster diese Art von Bildern mit Hilfe eines Computers erstellte.