Wieso skalieren diese beiden Threads unterschiedlich gut?

[pocketom]

Hallo Leute,

gestern wollte ich eine Kalkulation auf mehrere Threads durchführen lassen da von 8 Kernen immer nur einer gelaufen ist, die restlichen 7 blieben kalt. Das ganze hat einen bioinformatischen Hintergrund, es geht um die dynamische Berechnung von Stringvergleichen (DNA). Dazu wollte ich den bekannten Needleman-Wunsch Algorithmus auf mehreren Kernen parallel arbeiten lassen (in Form von seperaten, von einander unabhängige(!) Kalkulationen). Irgendwann habe ich jedoch entnervt aufgegeben weil ich keinen bzw. nur einen sehr geringen Gewinn erzielen konnte. Die Gesamtrechenzeit liess sich leider nicht wirklich durch die Anzahl der Threads skalieren.

Irgendwann bin ich dann irgendwie darauf gekommen das große Arrays anscheinend die nebenläufige Berechnung behindern (kann das sein???). Erklären kann ich mir es nicht, RAM ist nämlich genug da (vmargs: -Xmx1024m -Xmx8192m). Ich habe hier mal ein einfaches Beispiel geschrieben das meiner Anwendung relativ ähnlich ist und die Problematik auf einfache Weise veranschaulicht:


Seht Euch bitte mal folgendes Beispiel an und helft mir ggfs. auf die Sprünge:


Ich habe 2 verschiedene Threads gebastelt.
Der erste skaliert quasi linear, also quasi perfekt :

// 1. The simple one...

public class TObject1 implements Runnable
{	
	long loops;
	
	public TObject1(long loops)
	{
		this.loops 	= loops;
	}
	
	// a lot of hard work...........
	public void run()
	{
		long x = 0;
		for (int i = 0; i < loops; i++)		
			x+=1;
	}	
}

Hier das zweite Beispiel, das skaliert leider maximal um den Faktor 2 (statt 8 wie bei T1 :-?)

// 2. The dynamic programming like (simplified)


public class TObject2 implements Runnable
{	
	long loops;
	int dim1;
	int dim2;
	
	public TObject2(long loops, int dim1, int dim2)
	{
		this.loops 	= loops;
		this.dim1 	= dim1;
		this.dim2 	= dim2;
	}
	
	// a lot of hard work...........
	public void run()
	{
		for(int i=0; i< loops; i++)
		{
			int[][] big = new int[dim1][dim2];		
			
			// init 1st row and column with 1
			for (int k = 0; k < dim1; k++)
				big[k][dim2-1] = 1;			
			for (int n = 0; n < dim2; n++)			
					big[dim1-1][n] = 1;	

			// calculate some stupid stuff over the array			
			for (int k = 1; k < dim1; k++)
			{
				for (int n = 1; n < dim2; n++)							
					big[k][n] += big[k-1][n-1];					
			}
		}
	}
}

Hier die Mainklasse:

import java.text.DecimalFormat;

public class maintest {

	public static void main(String[] args)
	{		
		try
		{				
			// number of simultaneous threads
			int tcount = 1;
			System.out.println("Number of Threads: "+tcount);			
			
			/*
			 *  TObjects1 - the simple ones 
			 *  (runtime scaling approximately linear with number of threads)
			 */
			long loops = 1000000000L;			
			
			Thread[] tarray = new Thread[tcount];
			for (int i = 0; i < tcount; i++)
				tarray[i] = new Thread(new TObject1(loops/tcount));			
			
			// cpu benchmark
			long startTime 	= System.nanoTime();
			long stopTime	= 0;
			long runTime	= 0;

			for (int i = 0; i < tcount; i++)
				tarray[i].start();
			for (int i = 0; i < tcount; i++)
				tarray[i].join();
			
			// cpu benchmark
			stopTime 				= System.nanoTime();								
			runTime 				= stopTime - startTime;
			
			System.out.println();
			System.out.println("1 ALL THREADS FINISHED for JOB 1. ");
			System.out.println("
			1 OVERALL Time:   "
			+new DecimalFormat("0.0000").format((double)runTime/1000000)+" ms");
			System.out.println("
			1 AVG LOOPTIME:    "
			+new DecimalFormat("0.0000").format((double)runTime/(loops))+" ns");
			System.out.println();					
			
			
			/*
			 *  TObjects2 - calculates over large array
			 *  (runtime doesn't scale good with number of threads)
			 */
			loops 		= 200;
			int dim1 	= 1000;
			int dim2 	= 1000;			
			
			tarray = new Thread[tcount];
			for (int i = 0; i < tcount; i++)
				tarray[i] = new Thread(new TObject2(loops/tcount, dim1, dim2));			
			
			// cpu benchmark
			startTime 	= System.nanoTime();

			for (int i = 0; i < tcount; i++)
				tarray[i].start();
			for (int i = 0; i < tcount; i++)
					tarray[i].join();		
	
			// cpu benchmark
			stopTime 				= System.nanoTime();								
			runTime 				= stopTime - startTime;
			
			System.out.println();
			System.out.println("2 ALL THREADS FINISHED for JOB 2. ");
			System.out.println("
			2 OVERALL Time:    "
			+new DecimalFormat("0.0000").format((double)runTime/1000000)+" ms");
			System.out.println("
			2 AVG LOOPTIME:    "
			+new DecimalFormat("0.0000").format((double)runTime/1000000/(loops))+" ms");		}
		catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Damit habe ich verschiedene Anzahlen von Threads durchprobiert (von 1-8), die jeweiligen Outputs:

Number of Threads: 1

1 ALL THREADS FINISHED for JOB 1.
1 OVERALL Time: 1014.9110 ms
1 AVG LOOPTIME: 1.0149 ns

2 ALL THREADS FINISHED for JOB 2.
2 OVERALL Time: 977.9630 ms
2 AVG LOOPTIME: 4.8898 ms

Hier brauchen beide ca. 1 Sekunde

-------------------------------------------

Number of Threads: 2

1 ALL THREADS FINISHED for JOB 1.
1 OVERALL Time: 513.0990 ms
1 AVG LOOPTIME: 0.5131 ns


2 ALL THREADS FINISHED for JOB 2.
2 OVERALL Time: 583.1790 ms
2 AVG LOOPTIME: 2.9159 ms

teilt man 2 Threads zu, so brauchen beide Berechnungen nur noch knapp die Hälfte (mein Needleman-Wunsch bekommt hier leider nur ein Plus von ca. maximal 10%)

-------------------------------------------

Number of Threads: 3

1 ALL THREADS FINISHED for JOB 1.
1 OVERALL Time: 343.2470 ms
1 AVG LOOPTIME: 0.3432 ns


2 ALL THREADS FINISHED for JOB 2.
2 OVERALL Time: 524.5810 ms
2 AVG LOOPTIME: 2.6229 ms

T1 skaliert weiterhin linear. T2 lässt spürbar nach.

-------------------------------------------

Number of Threads: 4

1 ALL THREADS FINISHED for JOB 1.
1 OVERALL Time: 256.6200 ms
1 AVG LOOPTIME: 0.2566 ns


2 ALL THREADS FINISHED for JOB 2.
2 OVERALL Time: 479.6200 ms
2 AVG LOOPTIME: 2.3981 ms

-------------------------------------------

Number of Threads: 5

1 ALL THREADS FINISHED for JOB 1.
1 OVERALL Time: 211.0260 ms
1 AVG LOOPTIME: 0.2110 ns


2 ALL THREADS FINISHED for JOB 2.
2 OVERALL Time: 462.9910 ms
2 AVG LOOPTIME: 2.3150 ms

T1 weiterhin linear, T2 stagniert.

-------------------------------------------

Number of Threads: 6

1 ALL THREADS FINISHED for JOB 1.
1 OVERALL Time: 173.1410 ms
1 AVG LOOPTIME: 0.1731 ns


2 ALL THREADS FINISHED for JOB 2.
2 OVERALL Time: 457.7810 ms
2 AVG LOOPTIME: 2.2889 ms

-------------------------------------------

1 ALL THREADS FINISHED for JOB 1.
1 OVERALL Time: 159.6470 ms
1 AVG LOOPTIME: 0.1596 ns


2 ALL THREADS FINISHED for JOB 2.
2 OVERALL Time: 492.2210 ms
2 AVG LOOPTIME: 2.4611 ms

T2 wird ab 7 sogar langsamer (viele Versuche getestet).

-------------------------------------------

Number of Threads: 8

1 ALL THREADS FINISHED for JOB 1.
1 OVERALL Time: 163.3790 ms
1 AVG LOOPTIME: 0.1634 ns


2 ALL THREADS FINISHED for JOB 2.
2 OVERALL Time: 544.1340 ms
2 AVG LOOPTIME: 2.7207 ms

Hier lässt auch T1 im Schnitt ein wenig nach (vermutlich weil ja der 8.te Thread schon vom aufrufenden Thread belegt ist, also ist der 8. eigentlich der 9.?)

-------------------------------------------
mehr als 8 ist eh Unsinn...........



Mach ich irgendwas falsch? Kann man das für dass Beispiel 2 auch irgendwie verbessern? In der Praxis sind meine Arrays ca. 100000 x 250 groß. Ein Stringvergleich dauert ca. 0,5 s. Ich würde sehr gerne 8 verschiedene Vergleiche gleichzeitig machen lassen, da ich insgesamt ca. 4 Mio. dieser Vergleiche durchführen muss. Das sind ca. 23 Tage Rechenzeit bei 1 Thread, im Gegensatz zu 3 Tagen bei 8. Leider skaliert mein Stringvergleich (dessen code ist leider etwas umfangreicher, Bsp. 2 ist ähnlich und hat das Problem auch) nicht mal um den Faktor 2 :-(

Ich würde mich sehr freuen wenn mir das einer erklären und mir irgendwie helfen könnte.

Schonmal vielen Dank!
Thomas

 

[tincup]

Hi, zu deinem eigentlichen Problem kann ich grad nichts sagen (das können andere hier bestimmt besser) aber mal eine andere Frage:

Wieso denn eigentlich so viele optimale Alignments alle durchrechnen. Das ist ja furchbar :wink: Wieso z.B. nicht mit BLAST oder FASTA die guten Hits vorfiltern und darauf dann die optimalen Alignments berechnen (was die Programme ja als post-processing Schritt teilweise sowieso machen).

 

[Guest]

Hi, darüber habe ich auch schon nachgedacht. Leider ist es ein n->1 Vergleich, nicht wie bei FASTA/BLAST üblich 1->n (bzw. k->n mit k<<n). D.h. die knapp 4 Mio. Sequenzschnipsel müssen alle auf eine (sehr lange) Referenzsequenz "gemappt" werden. Ich denke mit einem eigenen BLAST-Server könnte man da evtl. was drehen um vorzusortieren, den habe ich aber leider nicht. Zudem handelt sichs um einen modifizierten Needleman-Wunsch Algo, das Scoring erfolgt anders.

 

[tincup]

Hm also das mit dem "Blastserver" verstehe ich nicht ganz. Blast kann man sich runterladen und völlig problemlos über die Kommandozeile benutzen (zumindest unter Linux, in Ubuntu ists sogar direkt in den Paketquellen).

Vergleiche sind in auch problemlos n:m möglich, die "Datenbank" hat eh idr mehr als ein Entry, das Query-File darf auch mehrere Sequenzen enthalten. Das mit dem modifizieren NW ist ein Problem aber generell könnte das BLAST-Preprocessing dabei helfen, Vergleiche unähnlicher Sequencen zu verhindern (deren Alignment so oder so keinen Sinn macht)

 

[pocketom]

Das Problem ist wiegesagt das alle Sequenzen auf ein und die selbe Referenzsequenz (ein 120 kB BAC) gemapped werden müssen. Unähnliche Sequenzen gibts im Prinzip hierbei nicht, da alle Fragmente irgendwo auf der Referenz erwartet werden (paar Ausfälle sind natürlich immer dabei). Die Alignments sind also in min. 95% eh notwendig, die Dimension des ScoringArrays ist halt mit 120000 x 250 ziemlich unmenschlich...
Es handelt sich um eine statistische Untersuchung. Interessant sind nur die exakten Positionen wo das Fragment auf der Refseq zum Liegen kommt und dann muss die Abweichung von der Referenz jedes einzelnen Fragments so genau wie möglich erfasst werden. Deshalb die "semi-globalen" NW-Alignments...
Prinzipiell kann ich mir BLAST schon irgendwie vorstellen um den Suchraum auf der Refseq einzuschränken. Nur einen BLAST mit einer Datei die 4 Mio. Sequenzen beinhaltet zu füttern, kommt das so gut(ich kenn nur das auf NCBI ehrlich gesagt)?
Andersrum, also die ganzen Fragmente in die BLAST DB stecken und dann eine Suche mit der Referenzsequenz starten hab ich mir auch schon überlegt. Den Datensatz aufteilen bringt auch nix, bei 10.000er Päckchen wären das dann ca. 400 Dateien (ich glaub da kann ich mein JAVA Tool auch gleich 3 Wochen laufen lassen). Ein weiteres Problem an dem BLAST ist dass ich dann erstmal den MegaOutput parsen und für mein Tool aufbereiten muss. Hast du eine Ahnung ob es eine JAVA Package dafür gibt (so das ich auf das Resultat des blasts objektorientiert zugreifen könnte)?


/* nochmal zurück zum eigentlichen Problem */
Hat irgendwer ein Idee warum es multithreaded in meinem Beispiel No.2 nicht großartig schneller geht, obwohl die Threads völlig unabhängig voneinander laufen können? ???:L

 

[Niki]

Wird für jeden Thread ein Kern verwendet?
Wenn du nur einen Prozessor hättest würde ich ja sagen dass du einfach in deinen Schleifen Thread.sleep(10) oder Thread.yield() einbauen solltest, damit andere Threads auch Zeit bekommen. Wenn du aber mehrere Kerne hast verstehe ich auch nicht warum die nicht gleich gut arbeiten.

 

[pocketom]

Ja, es läuft nichts anderes nebenher. Jeder Thread bekommt genau einen Kern. Mach ich da irgendwas falsch oder ist die Java VM für sowas einfach nicht geeignet?

Edit: Im Systemmonitor sieht man deutlich das alle Kerne voll ausgelastet sind. Stellt man weniger Threads ein so sind auch dementsprechend weniger Kerne aktiv. Nur wofür wird blos die ganze Rechenzeit verbraten??? :autsch:

Ich verwende übrigens das neueste jdk 1.6.0_03 (EM64T) unter Linux.

 

[tincup]

Andersrum, also die ganzen Fragmente in die BLAST DB stecken und dann eine Suche mit der Referenzsequenz starten hab ich mir auch schon überlegt. Den Datensatz aufteilen bringt auch nix, bei 10.000er Päckchen wären das dann ca. 400 Dateien (ich glaub da kann ich mein JAVA Tool auch gleich 3 Wochen laufen lassen). Ein weiteres Problem an dem BLAST ist dass ich dann erstmal den MegaOutput parsen und für mein Tool aufbereiten muss. Hast du eine Ahnung ob es eine JAVA Package dafür gibt (so das ich auf das Resultat des blasts objektorientiert zugreifen könnte)?

Also ich hab mal einen kleinen Test gemacht, eine ähnlich große Sequenz gegen 4mio zufällige Schnipsel (aus der großen Sequenz). 50000 Schnipsel hatte ich auf meinem Rechner hier nach knapp 2 Minuten durch. Also auch mit langsameremr CPU/HDD sollte das ganze im schlimmsten Fall ein paar Stunden dauern. Durch die Hitkoordinaten hat man auch direkt das Mapping auf die große Sequenz.

Mit dem Output gibts auch kein Problem, die neuen Blast-Versionen können tab-delimited Outputs generieren, die parst man mit nem Fünfzeiler.

Aber das geht ganz schön off-topic hier, falls du noch mehr hören willst oder Hilfe brauchst mit dem Command line Blast, kannst du mir ja ne PM schicken.

Grüsse,
tin

 

[pocketom]

Okay, super dank dir! Ich kuck mal morgen in der Arbeit ob BLAST installiert ist, dann meld ich mich nochmal...

Und jetzt, Back2Topic! ;-)

 

[pocketom]

Sodele, den Übeltäter konnte ich mittlerweile identifizieren.

int[][] big = new int[dim1][dim2];

Das Dumme ist nur, die Dimensionen des Arrays ändern sich halt nunmal bei jeder Berechnung, da komme ich nicht drumrum. Wieso stört die Speicherallokation die nebenläufige Verarbeitung? Was kann dagegen tun?

 

[EgonOlsen]

Was genau stört da? Die Tatsache, dass es ein großes 2-Dimensionales Array ist oder die Tatsache, dass du es innerhalb der Schleife immer wieder neu erzeugst? In letztem Fall könnte man vielleicht ein Array anlegen, welches "groß genug" ist, dieses in jedem Lauf wieder verwenden aber immer nur in einem Teil davon rechnen. Wenn das bei diesem Problem anwendbar ist.

 

[trc]

les dir mal den artikel über micro-benchmark durch.

 

[pocketom]

In letztem Fall könnte man vielleicht ein Array anlegen, welches "groß genug" ist, dieses in jedem Lauf wieder verwenden aber immer nur in einem Teil davon rechnen. Wenn das bei diesem Problem anwendbar ist.

ganz genau! so habe ich es bereits umgesetzt. Das Ergebnis wird normalerweise aus der letzen Zeile/Spalte bestimmt, die muss man sich halt jetzt vorher merken. So braucht das Ganze halt wesentlich mehr RAM, aber das ist weniger das Problem. Ist halt nicht so elegant gelöst, aber so skaliert es plötzlich gut. Fällt jemanden was besseres ein?

Danke für den Link mit den Microbenchmarks! Mal sehen ob ich es mit der ein oder anderen Erkenntnis noch besser hinbekomme.

 

[schalentier]

Wieso brauchts jetzt wesentlich mehr RAM? Prinzipiell braucht es insgesamt genauso viel RAM, da du jetzt ein Array hast, was genauso gross ist, wie es vorher maximal werden konnte.

Der einzige Unterschied ist, dass dieses neue Array nur einmal pro Thread initialisiert wird, wohingegen es vorher bei jedem Schleifendurchlauf initialisiert wurde. Und dieses Initialisieren ist teuer. Immerhin muss Speicher angefordert, fehlender Speicher vom OS angefordert und dieser Speicher muss auf 0 gesetzt werden. Damit bringt reine CPU (durch mehr Threads) gar nix - das alles haengt am RAM, bzw. am Betriebssystem. Dieses muss evtl. noch mit swappen anfangen. Im Worst-Case faengt auch noch der Garbage Collector an und gibt alte Arrays frei. Dabei wird, glaube ich, die Java VM angehalten (mehr unter: http://www.petefreitag.com/articles/gctuning/). In jedem Fall hast du somit einen hohen Speicherdurchsatz -> Langsam. Gut zu sehen ist das mit einem Profiler deiner Wahl.

Ich hatte neulich an einem Projekt gesehen, die haben fuer Logausgaben die toString()-Methode benutzt. Diese Strings wurden aber ueberhaupt nicht ausgegeben - aber sie wurden generiert. Nach wenigen Minuten Programmlaufzeit gabs gigabyteweise RAM-Durchsatz, obwohl der eigentliche Speicherverbrauch relativ gering war.

 

[pocketom]

Ich denke mal das braucht deshalb mehr RAM weil nur wenige Ausnamen so große Arrays brauchen, im Schnitt ist ein Array ~ 150.000 x 250, im Extremfall 150.000 x 1000. Da es auf 8 Thread gleichzeitig läuft braucht es so permanent ca. 20 mal mehr RAM. Ist aber nicht so schlimm, davon hab ich zum Glück genug. Ist auf jeden Fall die Variante die richtig Geschwindigkeit bringt, so gehts ca. 4 Mal so schnell . Werde also in Zukunft bei Multithread Anwendungen besonders auf die Speicherallokation acht geben. An den JVM Parametern hab ich auch schon einiges gestestet, da bringts eigentlich nur den Xmx, Xms von Anfang an sehr hoch anzusetzen. GCs kann ich somit komplett vermeiden, das kam andauernd als ich jedes Mal ein neues Array generiert habe. So Sachen wie -server bringt komischerweise garnichts. Wahrscheinlich wird der rechenintensive Teil so oder so als HotSpot erkannt (denk ich mir mal?)

 

[schalentier]

Du koenntest pro Durchgang ueberpruefen, ob das bestehende Array ausreicht. Wenn nicht, machst du ein groesseres, ansonsten nimmst du das alte. Wenn du dann noch die Berechnungen so aufteilst, dass nur ein Thread die ganz grossen Arrays bekommst, sollte der Speicherverbrauch nur unmerklich hoeher sein, als mit der alten Variante (und trotzdem schneller).

Und sag jetzt nicht, du hast genug RAM. Die Frage ist naemlich NICHT, ob der Speicher reicht, sondern wann er voll ist. ;-)

 

[pocketom]

Nee, so wird der ja nicht voller mit der Zeit. Der ist einfach von Anfang an relativ konstant mit 1-4 GB belegt, die Werte in den Arrays werden ja jedesmal nur überschrieben. Und wenns doch mal mehr wird, ich hab letzte Woche nachgerüstet auf 24 GB. Denk das krieg ich so schnell nicht geknackt, falls doch, die Kiste ist bis auf 96 erweiterbar ;-). Mir liegt im Moment einfach besonders die Laufzeit am Herzen.