Java Threads

XHotSniperX · 18. Dezember 2011

Hallo Leute

ich möchte mein Mandelbrotprogramm in mehrere Threads unterteilen.
Genauer möchte ich, dass die horizontale Bildberechnung ind Threads aufgeteilt werden soll und man soll die gewünschte Threadanzahl mit einem Parameter übergeben können.
Ich habe mich über Threads informiert und weiss, dass man die Klasse von Thread ableiten muss, den Code in einen "run(){***}" Block einfügen muss und die Threads mit start ausführen muss. Aber bei mir geht das so nicht.

Wie kann ich das bei mir am einfachsten machen? Sollte eigenltich ganz easy sein.

Code:

public class Mandelbrot extends Thread{

  public static void show_mandelbrot(Complex c_origin, double c_step, int max_iter, int wposx, int wposy) {
    ImageWindow sourceWindow= new ImageWindow(640,480);
    sourceWindow.openWindow("mandelbrot",wposx,wposy);
    sourceWindow.resizeImage(640,480);

    /* Implementieren des Mandelbrot Algorithmus */
    
    Complex[][] pixelarray = new Complex[480][640];		//Hier für jeden Pixel c speichern
    int[][] fluchtarray = new int[480][640];		//Hier für jeden Pixel die Fluchtgeschwindigkeit speichern
    Complex k = new Complex(0,0);
    
    for(int y=0; y<480; y++){
    	for(int x=0; x<640; x++){
              //Hier würde ich nen run() hinzufügen für die horizontale X-Achse in der For Schleife.             <-------------------
    		double re = c_origin.real()+c_step*x;    
    		double im = c_origin.imag()+c_step*y;
    		Complex c = new Complex(re, im);
    		pixelarray[y][x] = c;
    		for(int i=0; i<max_iter; i++){
    			if(Math.sqrt(k.real()*k.real()+k.imag()*k.imag())  <  2){
    				k=(k.sqr()).add(c);
    			}
    			else{
    				fluchtarray[y][x] = i;
    				k = new Complex(0,0);
    				break;
    			}	
    		}
        //Bis hier <---------------------------------------------------------
    	}
    }    
    
    for(int y=0; y<480; y++){
    	for(int x=0; x<640; x++){
    		int farbe = (int)(Math.log10(fluchtarray[y][x]));
    		sourceWindow.setPixel(x, y, 255-farbe*60, farbe*40, farbe*60);
    	}
    }

    sourceWindow.redraw();	

  }
  

  

  public static void main(String[] args) {
    double t1 = System.currentTimeMillis();  
    show_mandelbrot(new Complex(-2.5, -1.3),   0.005, 1000, 0, 0);
    show_mandelbrot(new Complex(-0.755, -0.1), 0.00002, 1000, 0, 520);
    double t2 = System.currentTimeMillis();
    System.out.println("Der Methodenaufruf 'show_mandelbrot()' hat " +(t2-t1)/1000 +" Sekunden gebraucht.");
  }
}

Darlis · 18. Dezember 2011

XHotSniperX schrieb:
Ich habe mich über Threads informiert und weiss, dass man die Klasse von Thread ableiten muss, den Code in einen "run(){***}" Block einfügen muss und die Threads mit start ausführen muss. Aber bei mir geht das so nicht.

Dein Code enthält auch keine überschriebene run() Methode. Wenn du die run() Methode manuell aufrufst, läuft dein Programm auch nicht automatisch in mehreren Threads.

Wenn du Thread.start() aufrufst, wird ein neuer Thread erstellt wobei die run() Methode der Einstiegspunkt ist, so ähnlich wie die main-Methode.

carom · 18. Dezember 2011

Du kannst doch nicht einfach irgendwo im Programmfluss innerhalb einer deiner Methoden plötzlich die Definition der run-Methode einbauen, an dieser Stelle befindest du dich bereits in der Show-Mandelbrot-Methode.

Rossie · 18. Dezember 2011

XHotSniperX schrieb:
Genauer möchte ich, dass die horizontale Bildberechnung ind Threads aufgeteilt werden soll und man soll die gewünschte Threadanzahl mit einem Parameter übergeben können.

Das sind zwei Aufgaben. Du sorgst Dich erst einmal nur um die Parallelisierung?

XHotSniperX schrieb:
Ich habe mich über Threads informiert und weiss, dass man die Klasse von Thread ableiten muss, den Code in einen "run(){***}" Block einfügen muss und die Threads mit start ausführen muss.

Das ist natürlich blanker Unsinn. Man kann eine Klasse von Thread ableiten. Dann muss man aber natürlich den Kontrakt einhalten und die run()-Methode entsprechend implementieren. Dass dieser Ansatz mit Deinem Code nicht so richtig harmoniert, hast Du bereits festgestellt.

Mir ist nicht klar, ob Du verstehst, was Parallelisierung hier bedeutet. Einmal abgesehen davon, wie Threads konkret anzuwenden wären. Beschreibe bitte, welchen Vorteil die Parallelisierung in diesem Beispiel bringt und wodurch das erreicht wird (bzw. erreicht werden soll).

XHotSniperX · 18. Dezember 2011

Naja das war der Grund des Threads. Es ist mir schon klar, dass man nicht ne run Methode da rein schreiben kann. Ich habe nur zeigen wollen, was ich in Threads aufteilen möchte.

Das bedeutet also, dass ich ne neue Klasse erstellen muss, wo nur dieser Code ausgeführt wird, damit ich dann mehrere Threads davon erstellen kann, richtig? Oder muss ich gar keine neue Klasse erstellen?

Ich muss eigentlich keine Threads für das Programm erstellen, ich möchte es aber einfach. Weil es eifnach zu langsam ist xD habe aber noch nie Threads erstellt.

Ergänzung (18. Dezember 2011)

Also wenn man z.B. 4 als Parameter übergibt, sollte die X-Achse in 4 Teile aufgeteilt werden und jeder Thread berechnet je ein Viertel. Am Schluss muss nur noch das Resultat gezeichnet werden und fertig.

Geht das dann nicht viel schneller?

Darlis · 18. Dezember 2011

Ob es schneller geht hängt von der Anzahl der (virtuellen) Kerne der CPU ab.
Du kannst auch in Java diese Anzahl ermitteln und die Arbeit entsprechend aufteilen um die CPU optimal auszulasten.

Rossie · 18. Dezember 2011

XHotSniperX schrieb:
Es ist mir schon klar, dass man nicht ne run Methode da rein schreiben kann. Ich habe nur zeigen wollen, was ich in Threads aufteilen möchte.

Bei Übungsaufgaben ist das Forum etwas sensibel. Deswegen meine Nachfrage.

XHotSniperX schrieb:
Das bedeutet also, dass ich ne neue Klasse erstellen muss, wo nur dieser Code ausgeführt wird, damit ich dann mehrere Threads davon erstellen kann, richtig? Oder muss ich gar keine neue Klasse erstellen?

Wenn Du direkt mit Java Threads arbeiten möchtest/musst, dann musst Du den Code, der parallel ausgeführt werden soll, irgendwie innerhalb von Thread#run() ausgeführt bekommen. Z.B. in dem Du eine eigene Klasse von Thread ableitest und die run()-Methode entsprechend implementierst.

Code:

public class Mandelbrot {
    ....

    private class Worker extends Thread {
        public void run() {
            ...
        }
    }
}

Den Worker-Thread rufst Du dann z.B. 4x auf, um den jeweiligen Bereich zu berechnen. Dabei gilt es zu beachten, dass Dein Main-Thread natürlich weiter läuft, Du aber warten möchtest, bis alle Worker-Threads fertig sind, bevor es weiter geht.

XHotSniperX schrieb:
Ergänzung (18. Dezember 2011)

Also wenn man z.B. 4 als Parameter übergibt, sollte die X-Achse in 4 Teile aufgeteilt werden und jeder Thread berechnet je ein Viertel. Am Schluss muss nur noch das Resultat gezeichnet werden und fertig.

Geht das dann nicht viel schneller?

Das ist die Idee. Ob es stimmt, kannst Du wenn Du damit fertig bist, selbst überprüfen. Immer vorausgesetzt, dass Du Zugriff auf eine Multi-Core-Maschine hast. Aber das ist heute ja die Regel.

XHotSniperX · 18. Dezember 2011

danke

wie kann man das machen, dass mehrere threads parallel laufen sollen und das programm erst dann weiter machn soll, wenn alle worker fertig sind. Hab es jetzt mit den threads gemacht aber das bild ist alles andere als gut, was dabei rauskommt xD

mit join kann man ja nur auf einzelne worker warten, was ja alles wieder langsam macht...

Rossie · 18. Dezember 2011

XHotSniperX schrieb:
wie kann man das machen, dass mehrere threads parallel laufen sollen und das programm erst dann weiter machn soll, wenn alle worker fertig sind.

Möglichkeiten gibt es viele. Direkt mit Threads zu programmieren macht man heute üblicherweise ohnehin nicht mehr. Seit Java 5 bietet Java selbst eine API, die vieles vereinfacht. Man kann natürlich auch auf andere Libs zurückgreifen um z.B. das Actors-Modell zu verwenden. Für den Anfang macht es allerdings schon Sinn, sich direkt mit den Low-Level Grundlagen zu beschäftigen. Von daher...

XHotSniperX schrieb:
Hab es jetzt mit den threads gemacht aber das bild ist alles andere als gut, was dabei rauskommt xD

Weil nicht gewartet wird, bis alle Worker-Threads fertig sind?

XHotSniperX schrieb:
mit join kann man ja nur auf einzelne worker warten, was ja alles wieder langsam macht...

Nee, langsam wird da nix. Du startest erst alle Worker-Threads. Und dann wartest Du mittels join() bis alle Worker fertig sind. Du bist also auf der richtigen Spur...

Wie sieht denn der Code mittlerweile aus?

XHotSniperX · 19. Dezember 2011

Ergebnis:

Mit Threads: 30 Sekunden, schlechtes Bild (siehe Anhang)
ohne Threads: 7 Sekunden, normales Bild (siehe Anhang)

Code:

Code:

public class Mandelbrot {
	
	public Complex c_origin;
	public double c_step;
	public Complex[][] pixelarray = new Complex[480][640];
	public int max_iter;
	public Complex k = new Complex(0,0);
	public int[][] fluchtarray = new int[480][640];
	
	
  Mandelbrot (Complex c_origin, double c_step, int max_iter, int wposx, int wposy, int threadcount) {
    ImageWindow sourceWindow= new ImageWindow(640,480);
    sourceWindow.openWindow("source",wposx,wposy);
    sourceWindow.resizeImage(640,480);
    this.c_origin = c_origin;
    this.c_step = c_step;
    this.max_iter = max_iter;
    

    /* Implementieren des Mandelbrot Algorithmus */  
    
    int t = 0;
    Worker[] tarray = new Worker[threadcount];
    for(int j = 0; j<threadcount-1; j++){
    	tarray[j] = new Worker(t, threadcount);
    	tarray[j].start();
    	t += 640/threadcount;
    }
    
    for(int i = 0; i<tarray.length-1; i++){
    	try {
			tarray[i].join();
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
    }
    
    
    for(int y=0; y<480; y++){
    	for(int x=0; x<640; x++){
    		int farbe = (int)(Math.log10(fluchtarray[y][x]));
    		sourceWindow.setPixel(x, y, 255-farbe*60, farbe*40, farbe*60);
    	}
    }
    
    sourceWindow.redraw();	
  }
  
  private class Worker extends Thread {
	  
	  int count;
	  int threadcount;
	  
	  Worker(int count, int threadcount){
		  this.count = count;
		  this.threadcount = threadcount;
	  }
	  public void run() {
		  for(int y=0; y<480; y++){
		    	for(int x=count; x<count+(640/threadcount); x++){
		    		double re = c_origin.real()+c_step*x;
		    		double im = c_origin.imag()+c_step*y;
		    		Complex c = new Complex(re, im);
		    		pixelarray[y][x] = c;
		    		for(int i=0; i<max_iter; i++){
		    			if(Math.sqrt(k.real()*k.real()+k.imag()*k.imag())  <  2){
		    				k=(k.sqr_inplace()).add_inplace(c);
		    			}
		    			else{
		    				fluchtarray[y][x] = i;
		    				k = new Complex(0,0);
		    				break;
		    			}	
		    		}
		    	}
		    }
	  }
  }

  public static void main(String[] args) {
	  
    double t3 = System.currentTimeMillis();  
    new Mandelbrot(new Complex(-2.5, -1.3),   0.005, 10000, 660, 0, 10);
    new Mandelbrot(new Complex(-0.755, -0.1), 0.00002, 10000, 660, 520, 10);
    double t4 = System.currentTimeMillis(); 
    System.out.println("Der Methodenaufruf 'show_mandelbrot_inplace()' hat " +(t4-t3)/1000 +" Sekunden gebraucht.");
  }
}

Killkrog · 19. Dezember 2011

Hab gerade nur drübergelurt, aber ich denke mal, dass der Befehl "pixelarray[y][x] = c;" innerhalb der run() erzeugt den Effekt.
Alle vier Threads versuchen gleichzeitig in das Array zu schreiben, und "der jeweils" schnellste gewinnt halt. Da musst du dir was überlegen. (Entweder ein Array pro Thread und danach zusammenfügen, oder Zugriff auf das große Array synchronisieren)

Darlis · 19. Dezember 2011

Ich würde sagen der Fehler liegt bei der Variablen k, denn alle Threads greifen gleichzeitig lesend und schreibend(!) darauf zu. Warum muss k denn eine Instanzvariable sein und keine lokale Variable?

Das gleichzeitig in das selbe Array geschrieben wird halte ich für unkritisch, da nie gleichzeitig auf die selben Indizes zugegriffen wird.

Rossie · 19. Dezember 2011

Wie bereits geschrieben: Du musst bei der Parallelisierug natürlich beachten, dass die Datenkonsistenz gewahrt bleibt. Je nach Problem und Technik müssen die Zugriffe entweder synchronisiert werden. Oder die Daten so verteilt, dass keine Inkonsistenzen entstehen können.

XHotSniperX · 19. Dezember 2011

Hi Leute und vielen Dank euch allen für eure Mühe!!

Ich habe es jetzt dank euch geschafft, dass das Bild richtig rauskommt. Da waren noch zwei Fehler im Code. Einer war das mit der Variablen k und der andere war in der Schleife, da habe ich nämlich immer einen Worker im Array einfach nicht angesprochen (das mit dem Minus ind der For-Bedingung)

Jetzt kommt zwar wie gesagt das gleiche Bild raus und mein Prozessor (Siehe Signatur) wird auch recht ausgelastet aber dafür benötigt der PC mehr Zeit mit diesem Code als mit dem ohne Threads.

Wie kann das nur sein? Hier wird der PC immer langsamer je mehr Threads.. haha

Code:

public class Mandelbrot {
	
	public Complex c_origin;
	public double c_step;
	public Complex[][] pixelarray = new Complex[480][640];
	public int max_iter;
	public int[][] fluchtarray = new int[480][640];
	
	
  Mandelbrot (Complex c_origin, double c_step, int max_iter, int wposx, int wposy, int threadcount) {
    ImageWindow sourceWindow= new ImageWindow(640,480);
    sourceWindow.openWindow("source",wposx,wposy);
    sourceWindow.resizeImage(640,480);
    this.c_origin = c_origin;
    this.c_step = c_step;
    this.max_iter = max_iter;
    

    /* Implementieren des Mandelbrot Algorithmus */  
    
    int t = 0;
    Worker[] tarray = new Worker[threadcount];
    for(int j = 0; j<threadcount; j++){
    	tarray[j] = new Worker(t, threadcount);
    	tarray[j].start();
    	t += 640/threadcount;
    }
    
    for(int i = 0; i<tarray.length; i++){
    	try {
			tarray[i].join();
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
    }
    
    
    for(int y=0; y<480; y++){
    	for(int x=0; x<640; x++){
    		int farbe = (int)(Math.log10(fluchtarray[y][x]));
    		sourceWindow.setPixel(x, y, 255-farbe*60, farbe*40, farbe*60);
    	}
    }
    
    sourceWindow.redraw();	
  }
  
  private class Worker extends Thread {
	  
	  int count;
	  int threadcount;
	  Complex k = new Complex(0,0);
	  
	  Worker(int count, int threadcount){
		  this.count = count;
		  this.threadcount = threadcount;
	  }
	  public void run() {
		  for(int y=0; y<480; y++){
		    	for(int x=count; x<count+(640/threadcount); x++){
		    		double re = c_origin.real()+c_step*x;
		    		double im = c_origin.imag()+c_step*y;
		    		Complex c = new Complex(re, im);
		    		pixelarray[y][x] = c;
		    		for(int i=0; i<max_iter; i++){
		    			if(Math.sqrt(k.real()*k.real()+k.imag()*k.imag())  <  2){
		    				k=(k.sqr_inplace()).add_inplace(c);
		    			}
		    			else{
		    				fluchtarray[y][x] = i;
		    				k = new Complex(0,0);
		    				break;
		    			}	
		    		}
		    	}
		    }
	  }
  }

  public static void main(String[] args) {
	  
    double t3 = System.currentTimeMillis();  
    new Mandelbrot(new Complex(-2.5, -1.3),   0.005, 10000, 660, 0, 6);
    new Mandelbrot(new Complex(-0.755, -0.1), 0.00002, 10000, 660, 520, 6);
    double t4 = System.currentTimeMillis(); 
    System.out.println("Der Methodenaufruf 'show_mandelbrot_inplace()' hat " +(t4-t3)/1000 +" Sekunden gebraucht.");
  }
}

Hancock · 20. Dezember 2011

Also ich weiß net, was du für Zeitdauern hast, aber unter paar Millisekunden wirst du keine Beschelungigung beim Ausführen spüren, da Threads etwas großes, also heavy sind -> beim Verwalten aufwendig.

Was mir gerade auffällt: In der if kannste auch das sqrt weglassen und auf <4 vergleichen, das spart Rechenzeit.
Wozu verwendest du pixelarray?
Warum machst du k als Klassenvariable, wenn du sie nur in run verwendest?

XHotSniperX · 20. Dezember 2011

Heeeeey vielen dank.. durch deine tipps hat es jetzt endlich geklappt:

- 12 Threads ohne Optimierungen von Blitzmerker: über 13 Sekunden
- 12 Threads mit k optimiert: 4 Sekunden
- 12 Threads mit sqrt weglassen: 2.4 Sekunden

Hehe, jetzt bin ich also von den 8 Sekunden ohne Threads auf 2.4 Sekunden mit Threads gekommen und mache das gleiche Bild xD

Vielen Dank euch. Das Thema hat sich erledigt jetzt!

Rossie · 20. Dezember 2011

Es ist interessant zu sehen, wie stark sich bei den vielen Schleifendurchläufen der Zugriff auf lokale Variablen bzw. auf Instanzvariablen bemerkbar macht!

Bei Deinen ersten Messungen war vermutlich einfach die Anzahl der möglichen Iterationen in beiden Varianten unterschiedlich. Wenn es korrekt umgesetzt ist und man die Multi-Threaded Implementierung mit nur einem Thread startet, sollte sie minimal langsamer sein, als die Single-Threaded Variante.

Das Setzen der Farbe sollte auch innerhalb der Threads möglich sein. Dann kannst Du Dir das zweite Array sparen. Das meinte @Blitzmerker wohl.

Wenn Du noch weiter optimieren möchtest: Die Lastverteilung der Threads ist vermutlich nicht optimal. Ideal wäre es, wenn alle Threads etwa die gleiche Zeit benötigen.

7H3 N4C3R · 20. Dezember 2011

Wie lange läuft es denn mit Optimierungen mit einem Thread? Mein Bauchgefühl nach flüchtigem Blick auf den Code sagt mir, dass es schneller sein müsste.

XHotSniperX · 20. Dezember 2011

@soares: ja das mit pixelarray könnte man wirklich besser machen

@ 7h3:

Hab jetzt paar Tests versucht und zwar immer mit dem gleichen code und nur durch den Parameter für die Threads verschieden (und mit den Optimierungen):

Meine CPU hat 6 Kerne @ 3.5 GHz, vlt ist das wichtig, deswegen erwähne ich es.

1 Thread: 7.5 Sekunden
2 Threads: 6.9 Sekunden
3 Threads: 5.7 Sekunden
4 Threads: 5.2 Sekunden
6 Threads: 4.7 Sekunden
12 Threads: 2.5 Sekunden
24 Threads: 1.7 Sekunden
64 Threads: 1.4 Sekunden

Also das versteh ich jetzt überhaupt nicht!

7H3 N4C3R · 20. Dezember 2011

Ah, das macht natürlich Sinn und das ist auch das, was soares schon vermutet hat.

Hab das mal eben fix nachgebaut bei mir - man sieht deutlich, dass gegen Ende der Berechnungsphase nur noch einige wenige Threads zu tun haben und der Rest wartet. Der sichtbare Speedup kommt also durch die bessere Verteilung der Aufgaben.

Java Threads

Lt. Junior Grade

Commodore

carom

Gast

Rear Admiral

Lt. Junior Grade

Commodore

Rear Admiral

Lt. Junior Grade

Rear Admiral

Lt. Junior Grade

Anhänge

Lt. Junior Grade

Commodore

Rear Admiral

Lt. Junior Grade

Captain

Lt. Junior Grade

Rear Admiral

Lt. Commander

Lt. Junior Grade

Lt. Commander

Ähnliche Themen