Ablieferungstermin und erreichbare Punktzahl für diese Aufgabe, sowie Voraussetzungen für die Prüfungszulassung entnehmen Sie bitte http://sar.informatik.hu-berlin.de.

In diesem Praktikum soll eine Anwendung zur Berechnung und Visualisierung von Fraktalen mit Hilfe der CORBA entwickelt werden. Konkret betrachten wir dabei die Mandelbrot-Menge, die im allgemeinen Sprachgebrauch als Apfelmännchen bezeichnet wird. Die folgende Abbildung stellt die Mandelbrot-Menge grafisch dar.

Mathematisch gesehen ist die Mandelbrot-Menge die Menge aller komplexen Zahlen c, für die die rekursiv definierte Folge komplexer Zahlen z(0), z(1), z(2), ... mit dem Bildungsgesetz

    z(n+1) = z(n)^2 + c, z(0) = 0

beschränkt bleibt. Die Mandelbrot-Menge kann in der komplexen Ebene dargestellt werden, indem man jedem Punkt einen Farbwert zuordnet, der dem Grad der Divergenz entspricht. Für die praktische Umsetzung wird dabei eine Maximalanzahl an Iterationen vorgegeben (Quelle: wikipedia.org).

Die Berechnung und Visualisierung ist für das Praktikum in Form einer Java-Anwendung vorgegeben (siehe Abbildung, Quellen sind hier). Mit den Eingabefeldern X, Y, Iterations, Zoom und Pixel können die Parameter der Berechnung angegeben werden. Die Schaltfläche Reset setzt diese Parameter auf den Anfangswert zurück und mit der Schaltfläche Refresh wird eine erneute Berechnung gestartet. Die für die Berechnung benötigte Zeit in Millisekunden ist in dem Feld Calc. time dargestellt.

Die Zeit für die Berechnung eines Punktes der komplexen Ebene ist dabei von dem Grad der Divergenz der Folge an der zugrunde liegenden Stelle abhängig. Aus diesem Grund soll in diesem Praktikum untersucht werden, welchen Vorteil man aus der dynamischen Aufteilung der Berechung auf mehrere Knoten ziehen kann. Dabei sollen verschiedene Techniken, die CORBA bereitstellt, evaluiert werden.

Bitte verwenden Sie die CORBA Implementierung JacORB (www.jacorb.org). Setzen Sie die Umgebungsvariable JACORB_HOME auf das Installationsverzeichnis des ORB. Anmerkung: Alle verschiedenen Server-Objekte (im Folgenden einzeln beschrieben) sollen innerhalb einer Java-Serveranwendung realisiert werden (Also nicht getrennte Java-Serveranwendung für synchronen, asynchronen, usw. Server).

Berechnung mittels synchronen CORBA Aufrufen

Als erster Schritt soll die Berechung auf eine dynamische Anzahl an Rechenknoten verteilt werden, die über synchrone CORBA Aufrufe (Static Invocation/Skeleton Interface) angesprochen werden. Entwerfen Sie geeignete Schnittstellen in IDL und implementieren Sie den Server. Achten Sie darauf, dass die Schnittstelle die Aufteilung der Berechung in kleinere Arbeitspakete (kleinere Bildausschnitte) unterstützt. Es soll möglich sein, mehrere Server für die Berechnung zu nutzen (Sowohl für diese als auch für alle folgenden Berechungen). Nutzen Sie den CORBA NameService für die Übergabe von Objektreferenzen für diese Berechungsart und auch für die noch Folgenden.

Integrieren Sie Ihre Lösung in die vorgegebene Anwendung. Dazu muss die Methode ApfelCalculatorFactory.create geändert und an der entsprechenden Stelle ein von ihnen implementiertes ApfelCalculator-Objekt eingefügt werden. Bitte verändern Sie die restlichen Teile der vorgegebenen Quellen nicht (Natürlich können neue Klassen hinzugefügt werden).

Berechnung mittels verzögert synchronen CORBA Aufrufen (Dynamic Invocation Interface DII)

Die Lösung mit synchronen CORBA Aufrufen verteilt die Berechung auf verschiedene Server. Allerdings kann die Berechnung nicht beschleunigt werden, da jeweils nur ein Knoten zur einem Zeitpunkt einen Ausschnitt des Bildes berechnet. Mit verzögert synchronen (deferred synchronous) Aufrufen können die Berechnungen auf verschiedenen Servern zeitlich verschränkt werden, so dass die gesamte Berechnung schneller durchgeführt ist. Entwickeln Sie einen weiteren ApfelCalculator, der das CORBA Dynamic Invocation Interface nutzt und damit verzögert synchrone Aufrufe an Ihren Berechnungsserver sendet. Verschränken Sie die Aufrufe zeitlich ineinander. Das sichtbare Resultat sollte sich nicht von den Vorgängern unterscheiden.

Ein Freiheitsgrad ist die Granularität, auf der die Parallelisierung stattfindet. Wenn mit jedem Aufruf jeweils nur ein Punkt berechnet wird, ist der voraussehbare Overhead zu groß, um die Gesamtberechung zu beschleunigen. Wenn allerdings jeder Knoten der n Knoten mit einem Aufruf 1/n der Punktmenge berechnet, findet keine Balancierung der Last statt, da sich die Berechungszeiten je nach Bildregion erheblich unterscheiden können. Finden Sie eine geeignete Granularität für die Parallelisierung.

Berechung mittels verzögert synchronen CORBA Aufrufen und Dynamic Skeleton Interface (DSI)

Die vorangegangene Berechung hat das Dynamic Invocation Interface zur Berechung genutzt. Eine analoge Schnittstelle auf der Serverseite ist das Dynamic Skeleton Interface. Implementieren Sie einen Server für die Berechung des Fraktals unter Benutzung des Dynamic Skeleton Interface. Realisieren Sie einen weiteren ApfelCalculator und binden Sie ihn in die Anwendung ein (ApfelCalculatorFactory.create).

Berechung mittels asynchronen Aufrufen

CORBA bietet neben synchronen auch asynchrone (oneway) Aufrufe an. Eine Methode, die mit dem Schlüsselwort oneway in IDL als asynchron markiert wurde, besitzt eine andere Aufrufsemantik. Wird sie aufgerufen, wird der Aufruf an das Server-Objekt weitergeleitet. Allerdings kehrt eine oneway Methode nicht zurück. Daher sind nur in Parameter und der Rückgabetyp void zulässig. Während der Abarbeitung wird der Aufrufer nicht blockiert. Ein synchroner Aufruf kann mit zwei oneway Operationen simuliert werden.

Realisieren Sie einen asynchronen Server. Entwerfen Sie die benötigten Schnittstellen in IDL und implementieren Sie den Servant und Server. Integrieren Sie diese Berechungsvariante in die gegebene Oberfläche durch einen weiteren ApfelCalculator.

Berechung mittels Asynchronous Method Invocation (AMI)

Der CORBA Standard definiert Asynchronous Method Invocation als ein weiteres Aufrufmodell. Der vorgegebene JacORB unterstützt AMI in der Variante Callback. Realisieren einen ApfelCalculator, der den Berechungsserver unter Nutzung von AMI abfragt, und integrieren Sie ihn (ApfelCalculatorFactory.create).

Leistungsmessung

Messen Sie die Laufzeiten der verschiedenen Varianten mit mindestens 1, 2, 3 und 4 verschiedenen Serverknoten. Stellen Sie die Laufzeiten und die sich daraus ergebenden Speedups in Form von Diagrammen dar und binden Sie diese in die Datei index.html ein. Bewerten Sie die verschiedenen Lösungen hinsichtlich ihrer Leistung. Nutzen Sie folgende Parameter für die Messung:

• x = -0.53262
• y = 0.6121
• Zoom = 2000
• Iterationen = 8000
• Pixel = 1.220703125E-6

Fragestellungen

• Wie groß kann der Speedup theoretisch maximal sein?
• Welche Faktoren kommen für die Abweichung von Theorie zu Praxis in Frage?
• Erläutern Sie kurz, wie sie eine dynamische Anzahl an Rechenknoten unterstützen.
• An welchen Stellen muss zusätzlich synchronisiert werden?
• Beschreiben Sie kurz, welches Granulat Sie für die Parallelisierung verwenden und welche theoretischen Überlegungen oder praktische Erkenntnisse dafür sprechen.

Abgabe und Bewertung

Begründen Sie die von Ihnen getroffenen Design-Entscheidungen und beschreiben Sie aufgetretene Besonderheiten und Probleme. Benutzen Sie dafür eine HTML Datei mit dem Namen index.html.

Abzugeben sind weiterhin die Quelltexte der Lösung und ein Ant-Script mit dem Namen build.xml, das die Quellen mit den gängigen Werkzeugen automatisiert übersetzt (Bitte die Targets compile, test und clean definieren). Schreiben sie zusätzlich ein Skript mit dem Namen run-server.sh, dass den Nameserver und eine Instanz des Berechnungsservers startet. Es kann dabei der Java-Nameservice tnameserv benutzt werden. Bitte reichen Sie die geforderten Dateien in ein ZIP Archiv gepackt ein.

Für Test und Bewertung kommt die Unit-Test-Bibliothek jUnit (www.junit.org) zum Einsatz. Die geforderte Funktionalität wird anhand von 5 Unit-Tests überprüft. Diese Tests sind in der vorgegebenen Anwendung enthalten und daher an dieser Stelle nicht aufgeführt. Weiterhin fließen Aspekte der Implementierung und die Beantwortung der Fragestellungen in die Bewertung ein.

Hinweise

• Nutzen Sie als Ausgangspunkt die vorgegebene Anwendung.
• Behandeln Sie auch Fehler- und Ausnahmesituationen entsprechend.
• Bedenke Sie, dass durch eine nebenläufige Ausführung Fehler entstehen können.