verteiltes Sortieren

[maximilius]

Vorweg: Ich möchte nicht, dass ihr meine Hausaufgaben macht, sondern Erkenntnisse sammeln.

Eine Kommilitonin und ich haben den Auftrag, irgend ein verteiltes System zu entwickeln und entschieden uns in unserem jugendlichen Leichtsinn für verteiltes Sortieren.

Wir haben eine Anwendung geschrieben, die Strings aus einer Datei ausliest, sie nach QuickSort sortiert und sortiert in eine Zieldatei schreibt.
Darüber hinaus liest die Anwendung aus einer weiteren Datei beliebig viele IP Adressen und Ports aus, von Servern, die ebenfalls einen Quicksortalgorhitmus implementiert haben.
Jede Rekursionstiefe in der Anwendung nimmt ein Pivot-Element, sortiert die übrigen Elemente in zwei Vectoren nach größer und kleiner als Pivot-Element, startet für den Vector mit der größeren Elementanzahl die nächste Rekursionstiefe und gibt den anderen Vektor an einen Server ab, dass der sich darum kümmert.

Auf allen beteiligten Rechnern läuft die gleiche Anwendung. Das heißt, dass die Server wiederum Server aufrufen, um Teile der Arbeit abzugeben. So kann es passieren, dass ein Server etwas abgibt, was zur Hälfte wieder zurück kommt.
So entsteht zu viel Netzwerktraffic, sodass das verteilte Sortieren (mit 2 Rechnern) vier mal länger dauert, als das Sortieren auf nur einem Rechner.

Erkenntnis:
Das Hin- und Herschicken ist Overhead.

Idee:
Zwei unterschiedliche Anwendungen:
Ein Client, der die Datei einsliest und erstmal alleine rechnet, so lange, bis er gleich viele oder genauso viele zu sortierende Vectoren hat wie Server. Dann schickt er je einen Vector an je einen Server und übernimmt die übrigen Vectoren selbst.
Mehrere Server, die einen Vector empfangen, komplett nach QuickSort sortieren und zurückliefern.
Beispiel (es wird von 3 verfügbaren Servern ausgegangen)

Angst:
Dass auch hier das Sortieren auf einem Rechner schneller läuft, wegen Netzwerktraffic.

Frage:
Hat jemand von euch sich schonmal mit verteilten Algorithmen beschäftigt und kann uns Tips geben bzw. uns mit der Nase auf eine Schwachstelle stubsen?

lg Stephan

 

[Kaffeemaschinist]

Zwangsläufig wirst du dabei fast immer langsamer vorankommen als mit einem einzelnen Rechner. Problematisch ist IMHO, dass selbst bei sehr schneller Netzwerkverbindung ein Netzwerk immer noch I/O ist - und sowas ist bekanntlich sehr viel langsamer als Operationen im lokalen Speicher.

Bis du Kontakt mit dem anderen Rechner aufgenommen hast, die Liste mit den zu sortierenden Werten rübergeschickt hast (über eine Art Protokoll, das abermals Overhead produziert) und die Antworten zurück hast, vergeht vergleichsweise viel Zeit.

Deswegen den Performance-Gedanken etwas beiseite legen und das ganze als Aufgabe ansehen, bei dem die Beispielhaftigkeit im Vordergrund steckt.

In deinem Schaubild wird eines deutlich: Der Client rechnet relativ lange allein und gibt dann nur noch die kleinen Häppchen (in der untersten Stufe an die Server). Warum nicht eine zentrale Instanz (= Client), die die Server-Überwachung übergibt und den Servern immer dann was rüberschickt, wenn die rum-idle-n? In einem Thread kann der Client selbst rechnen, im anderen kann er auf die Server-Antworten horchen.

Das ganze dann vllt. noch etwas visualisieren (Verteilung, Datenverkehr), damit euer Prof auch was zu sehen hat und nicht nur am Ende ein Ergebnis bekommt.

 

[maximilius]

Das klingt Plausibel, was du sagst.

In meinem Rechner ist ein Duo Core.
Kann ich wenn ich zwei Threads in der VM laufen lasse, irgendwie beeinflussen, dass diese sich auf die Kerne verteilen?
Dann hätte ich Parallelität aber gleichen Speicherraum.
Das dürfte dann Geschwindigkeit bringen.

Wenn das ginge könnten wir zeigen, dass man mit Parallelität Geschwindigkeit bekommt, aber sobald diese sich im Netzwerk abspielt der Netzwerkoverhead Geschwindigkeitsverlust erzeugt.

lg Stephan

 

[Kaffeemaschinist]

Kann ich nicht genau sagen, aber ich vermute mal, in der Sprache selbst ist nichts verankert, um Threads gezielt auf bestimmten Kernen laufen zu lassen. Sind zwar Threads im User-Level-Kontext, aber trotzdem hat vermutlich nur die VM Entscheidungsgewalt, was gerade wo läuft.

Insgesamt würd ich mir da auch erst mal keine Gedanken drüber machen, lass das Java tun

Falls ihr euch noch nicht auf das Sortieren festgelegt habt, könnt ihr ja mal noch einem Problem Ausschau halten, das bei minimalen Grunddaten eine sehr lange Rechenzeit pro Teilproblemschritt benötigt (Mathematiker fragen). Sprich: Wenn die Berechnung pro Maschine lang genug dauert, amortisiert sich evtl. der Netzwerk-Overhead und du kannst wieder das zeigen, was du ursprünglich wolltest: Parallelität = Effizienz.

 

[maximilius]

Ich bin mir nicht sicher, ob die VM Einfluss darauf hat, auf wievielen Kernen sie läuft. Ich spekuliere mal, dass die die Resourcen abstrakt sieht.

Deswegen sprach ich von jugendlichem Leichtsinn, weil die Aufgabe nun schon als "verteiltes Sortieren" an den Prof weiter gegeben wurde und wir sie nun nicht mehr ändern können *g.

Ich habe heute in der Bibliothek ein Buch gefunden, was voll von Sortieralgorithmen ist (auch parallele). Das werde ich jetzt mal unter mein Kopfkissen legen und noch ein wenig herumprobieren.

Wenn ich nichts finden kann, wo die Netzwerklast geringer ist als der Geschwindigkeitsvorteil durch die Parallelisierung, dann muss ich das Phänomen eben bei der Präsentation erklären.

Ist ja auch eine nette Erkenntniss für die Kommilitonen, dass nicht alles Gold ist, was glänzt. .. oder eben schneller ist, was parallel läuft.

lg Stephan

 

[Kaffeemaschinist]

Yupp, deswegen meinte ich das noch mit der Visualisierung:

Messe einfach mal die Zeit, die ein Single-System benötigt und dann messe die Zeiten, die die Server benötigen (nur die reinen Rechenzeiten). Dann kannst du ja noch die restliche Zeit (Übertragung, Managment) versuchen zu messen und kannst das alles ausarbeiten und darlegen.

Falls es was Schriftliches werden soll, freut sich der Prof sicherlich drüber

 

[Distax]

Eine Möglichkeit, Quicksort auf einem Prozessor (UMA/SMP) zu parallelisieren ist, solange eine gewisse Mindestgröße nicht erreicht ist, einen der beiden Rekursionaufrufe auf einen neuen Thread auszulagern.
Das ist natürlich ein anderer Ansatz, als in deiner Zeichnung dargestellt (würde auch viel zuviel Traffic verursachen). Ich halte ein Master/Slave Modell für die verteilte Sortierung am effizientesten. Der Master ruft, bis eine gewisse Tiefe erreicht ist, Quicksort normal rekursiv auf. Wenn tiefe==schnitttiefe erzeugt der Master anstatt des erneuten Rekursionsaufrufes Task (->Taskpool,Tasks>Slaves), die er dann an die Slaves zur weiteren Sortierung verteilt, nachher wieder einsammelt und ggf neuen Task an Slave schickt (Wenn die Slaves Mehrkernprozessoren haben, kann man natürlich auch beide Ansätze kombinieren)

SMP:

public class QuickSortP extends Thread
{
	private int hi;
	private int lo;

	private static int[] array; //static, damit von allen Threads drauf zugegriffen werden kann
                                            //Threads bekommen nur die obere und untere Grenze ihre Teilarrays als Parameter
                                            //Und arbeiten alle parallel auf dem selben Array (geht bei verteilter Sortierung über
                                            //Netzwerk(DMM) natürlich nicht)
       public QuickSortP(int hi,int lo) {
		this.hi = hi;
		this.lo = lo;
	}
	
	public void run() {
		quicksort(hi,lo);
	}
...

...
// Rekursion
f(j-lo < MAXSIZE) {
   quicksort (lo, j);
   quicksort (i, hi);
} else {
  QuickSortP thread = new QuickSortP(lo,j);
  thread.start(); //Startet QS in einem neuen Thread
  quicksort(i,hi); //
  try{ thread.join();}
     catch(InterruptedException e){}
}
...

 

[maximilius]

@Distax
Ich habe nicht verstanden, warum erst ab einer Mindestgröße in Threads aufgespalten wird und nicht sofort.

Ich habe einen SMP mit 2 Prozessoren.
Die Idee mit Threads zu parallelisieren meinte ich 4 Beiträge über deinem.
Weißt du, ob sich die Threads dann auch wirklich auf die beiden Prozessoren verteilen? Denn wenn nicht, dürfte es genauso schnell laufen (Mal den Threaderzeugungsoverhead unbeachtet)

Im Moment schwebt mir die Idee vor, 3 mal sortieren zu lassen:
1) sequentiell
2) parallel via Threads mit 2 Kernen (wenn es geht)
3) parallel via 4 Computern

Dann die Zeiten vergleichen und erklären, dass es aufgrund der Netzwerkkommunikation bei 3. obwohl der größeren Prozessoranzahl langsamer läuft.

lg Stephan

 

[Distax]

BIS zur einer Mindestgröße (oder muss das Maximalgröße heißen). Man bekommt keinen Speedup mehr, da die Threaderzeugung die Zeit, die ein einzelner Thread zum Sortieren des kompletten TeilArrays braucht, übersteigen würde. Das bringt natürlich alles nur was, wenn die Größen sehr hoch gewählt werden
MAXSIZE = 100000
ARRAYSIZE = 50000000 (ggf mit "java -Xmx256m Quicksort" starten, sonst geht der VM der Speicher aus)

Ja, die Threads werden von der VM (oder vom BS, weiß ich nicht so genau) auf die Prozessoren verteilt.

import java.util.*;

public class Main extends Thread{

    public void run() {
        while(true);        
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        for(int i = 0;i < 2;i++) {
            Main thread = new Main();
			thread.start();
        }
    }

}

Kannst du bei Windows im Taskmanager->Leistung verfolgen. Kannst du ja mal mit i<1 vergleichen.
(Unter Linux liefert dir zB "top" eine CPU-Auslastung von 200% bei 2 Threads)

Edit:
Habe die SMP Lösung gerade noch einmal auf einem DualXeon 2Kern (=> 4 Kerne) System laufen lassen:
Arraysize: 50000000
Sequentiell:
--9.966 s
Parallel:
MAXSIZE:100000
--3.352
=> Speedup 3 (4 wäre natürlich optimal)
MAXSIZE:1000
--11.332


Habe mal das Springerproblem auf einem Cluster mit 4 DualXeon 2 Kern Knoten (16 Kerne) mit MPI (gibt es nur für C) und dem beschriebenen Master/Slave Modell parallelisiert. Da bekommt man einen Speedup von ca 15, allerdings haben die Kerne auch viel mehr zu tun als beim QS. Kann dir nicht sagen ob beim QS die Problemgröße groß genug ist, um Speedup zu bekommen oder ob wie schon vermutet der Kommunikationsoverhead überwiegt.
Das ist bei QS so ein Teufelskreis. Damit die Knoten genug Arbeit haben, müssen die Task groß genug sein, je größer die Tasks desto länger dauert die Kommunikation.
Du kannst ja auf jeden Fall (wenn du das Master/Slave Modell verwendest solltest) mit unterschiedlichen Schnitttiefen im Rekursionsbaum arbeiten und die Ergebnisse vergleichen oder die SlaveProzesse testweise alle lokal laufen lassen (Würde den Kommunikationsoverhead stark reduzieren).

Parallelverarbeitung UniSiegen

 

[maximilius]

Ach dann habe ich das falsch herum verstanden.
Ja das ist sinnvoll, wenn hinreichend wenig zu sortierende Elemente vorhanden sind, dass dann kein weiterer Thread geöffnet wird wegen des Threaderzeugungs- und Verwaltungsoverheads.

Während du deine Tests durchgeführt hast, habe ich auch ein wenig getestet.

Ich habe ein kleines Programm geschrieben, was sinnlose Operationen durchführt und einmal mit einem Thread und das andere mal mit zwei Threads gestartet, um meine Prozessoraktivität zu überwachen.

public class Test extends Thread {
	
	public void run() {
		int i = 0;
		long start = System.currentTimeMillis();
		while (System.currentTimeMillis() - start < 50000) {
			i++;
			if (i == 1000) {
				i = 0;
			}
		}
		System.out.println("fertig");
	}
	
	public static void main(String[] args) {
		Test t1 = new Test();
		t1.start();
		// folgender Teil war beim ersten Test auskommentiert:
		Test t2 = new Test();
		t2.start();
	}
}

Dabei war folgende Lastverteilung zu beobachten.

Es ist zu erkennen, dass im Leerlauf die erste CPU den großteil des Betriebssystems übernimmt.
Weiter ist zu erkennen, dass sowohl bei einem als auch bei zwei laufenden Threads beide CPU in Anspruch genommen werden. Ich vermute, dass das daran liegt, dass das Betreibssystem die Resourcen verteilt und den Thread beim wecken mal auf CPU 1 und das andere mal auf CPU 2 laufen lässt.
Letztendlich ist erkennbar, dass wenn zwei Threads laufen, beide CPUs mehr ausgelastet werden als mit einem laufenden Thread.
Ich kann demnach deine Beobachtung bestätigen, dass ein Geschwindigkeitsvorteil erkennbar sein wird.

lg Stephan

 

[maximilius]

Ich wollte ein kurzes Feedback abgeben und allen Beteiligten danken!

Die Präsentation ging eine gute halbe Stunde und ergab volle Punktzahl.

Wir führten Sortiertests durch:
mit je 2 millionen Datensätzen
- ganzer Sotriervorgang in einem Thread (mittel schnell)
- Sortiervorgang in mehreren Threads auf Dual-Core (am schnellsten)
- Sortiervorgang mit 3 Rechnern im Netzwerk (überproportional langsam)

mit je 50 Datensätzen aber simuliertem großen Rechenaufwand für den Vergleich zweier Datensätze:
- Sortiervorgang in mehreren Threads auf Dual-Core (13 Sekunden)
- Sortiervorgang im Netzwerk (11 Sekunden)

Es kamen auch viele Fragen seitens der Kommilitonen, also konnten wir alle dazu lernen.

Unsere Kernaussage in der Präsentation:
Algorithmen parallelisieren ist sinnvoll, wenn sie auf einem symmetrischen Mehrprozessorsystem laufen.
Dann erhält man einen Geschwindigkeitsvorteil (Wenn der Algorithmus überhaupt parallelisierbar ist)
Weiteres Verteilen des Algorithmus im Netzwerk, um noch mehr Prozessoren zusammenarbeiten zu lassen, birgt Gefahren durch die E/A-Operation Netzwerk und bringt nur einen Geschwindigkeitsvorteil, wenn das Verhältnis zwischen versendeten Daten und Rechenaufwand stark auf der Seite des Rechenaufwandes liegt und man daher bei jedem zu lösenden Problem nachdenken sollte, ob es sinnvoll ist, im Netzwerk zu verteilen.

lg Stephan