Parallelprogramming mit Future

[Craiten]

Moin moin Java-Forum,

momentan sitze ich an einem Problem, welches mich etwas verzweifeln lässt.

Ich habe in Java ein Programm entwickelt, welches zwei Matrizen Multipliziert.
Einmal sequentiell, einmal parallel.

Jetzt bei Schnelligkeitstests, stellt sich heraus, dass die sequentielle Programmierung schneller ist (Selbst bei 1000x1000 Matrizen).

Könnt ihr mir vielleicht dort weitehelfen?


BTW: (Matrix.java hilft der schönen Programmierung, dort sind nur getter und setter drin)

DoubleCallable.java

public class DoubleCallable implements Callable<Double> {
	private Matrix m1, m2;
	private int i, j;

	public DoubleCallable(Matrix m1, Matrix m2, int i, int j) {
		this.m1 = m1;
		this.m2 = m2;
		this.i = i;
		this.j = j;
	}

	@Override
	public Double call() {		
		double tmp = 0;
		
		for(int k=0; k<m1.getRows(); k++) {			
			tmp += m1.getValue(k, i) * m2.getValue(j, k);
			
			//System.out.printf("i=%d j=%d k=%d || %.1f * %.1f = %.1f || tmp=%.1f\n", i, j, k, m1.getValue(k, i), m2.getValue(j, k), m1.getValue(k, i) * m2.getValue(j, k), tmp);
		}
		
		return tmp;
	}

}

ParMulti.java

public class ParMulti {
	private Matrix m3;
	private Matrix m1;
	private Matrix m2;
	private String test;
	
	public ParMulti (Matrix m1, Matrix m2, String test) {
		this.m1 = m1;
		this.m2 = m2;
		this.test = test;
		
		double[][] tmp = new double[m1.getColumns()][m2.getRows()];
		
		m3 = new Matrix(tmp);
	}
        public Matrix runExample() throws Exception {			
		
		ExecutorService pool = Executors.newCachedThreadPool();
		Collection<Callable<Double>> tasks = new ArrayList<Callable<Double>>();
		
		long time1 = System.currentTimeMillis();
		
		
		
		for (int i=0; i<m1.getColumns(); i++)
			for(int j=0; j<m2.getRows(); j++) {
                	tasks.add(new DoubleCallable(m1, m2, i, j));
			}
		
		List<Future<Double>> results = pool.invokeAll(tasks); 
		//System.out.println("all tasks submitted...");
		
		int i=0, j=0;
		
		for(Future<Double> result: results) {
			//System.out.printf("result %s \n",result.get());
			m3.setValue(j, i, result.get());
			j++;
			
			if(j==m3.getRows()) {
				j=0; i++;
			}
			
			//m3.setValue(i, j, result.get());
		}
		time1 = System.currentTimeMillis() - time1;		
		//System.out.println("WorkerExample finished...");
		System.out.printf(Zeit: " + time1 + "ms\n\n"); 
		
		return m3;
	}
}

Test.

public class ParMultiTest extends TestCase {
    private ParMulti parObj;

    public void testRandom1000() throws Exception {
        int menge = 1000;
        double rand = Math.random();
        int i,j;
        double m1[][] = new double[menge][menge+1];
        double m2[][] = new double[menge+1][menge];
        Matrix matrix1;
        Matrix matrix2;
       
        for ( i = 0; i < m1.length; i++ ) {
            for ( j = 0; j < m1[i].length; j++) {
                m1[i][j] = rand;
            }
        }
       
        for ( i = 0; i < m2.length; i++ ) {
            for ( j = 0; j < m2[i].length; j++) {
                m2[i][j] = rand;
            }
        }
        matrix1 = new Matrix(m1);
        matrix2 = new Matrix(m2);
        parObj = new ParMulti(matrix1, matrix2, "1000");
        parObj.runExample();
    }

Warum es mit Futures langsamer ist, kann ich mir nicht erklären.
Liegt es vielleicht daran, dass Future darauf wartet, dass alle tasks durch sind?

 

[Attila]

Liegt es vielleicht daran, dass Future darauf wartet, dass alle tasks durch sind?

Richtig.

Vielleicht wäre es besser, eine sequentielle Verarbeitung zu nutzen, aber
parallele Verarbeitung hätte noch eine weitere Lösung: ExecutorCompletionService.

ExecutorService executor = Executors.newFixedThreadPool(3);
List<Callable<Double>> tasks = new ArrayList<Callable<Double>>();
//...
CompletionService<Double> completionService = 
        new ExecutorCompletionService<Double>(executor);
for (Callable<Double> task: tasks){
    completionService.submit(task);
}
//...Ergebnisse:
for (int i = 0; i < tasks.size(); i++){
    try {
        Future<Double> future = completionService.take();
        //...
    } catch (InterruptedException ex) { 
    } catch (ExecutionException ex) { }
}
executor.shutdown();

 

[Marco13]

Richtig.

Was veranlasst dich zu dieser Aussage? Die Methode 'invokeAll' wartet, bis alle fertig sind. Wenn sie parallel arbeiten, sollten sie (alle) schneller fertig sein, als ein einzelner Task.
Warum es tatsächlich langsamer ist, ... woh-ho, poste mal die sequentielle Version und die Matrix (am besten alles gleich als KSKB). Ein heißer Kandidat wäre die Granularität. Bei einer 1000x1000-Matrix werden dort, wenn ich das richtig sehe, 1000 Threads erstellt :autsch: Fang vielleicht erstmal damit an, eine 1000x1000-Matrix mit 4 oder 8 Threads abzuarbeiten.

 

[Attila]

Ich bin einverstanden, das größte Problem besteht darin, es ist zu viel Threads erstellt worden.

 

[Marco13]

*nochmal drauschaut* - hups, es sind wohl 1000000 Threads... Ja, so viel dazu...