ExecutorService не имеет рекурсивного детерминанта производительности. Java

Question

Я читал похожие вопросы, где проблема заключалась в использовании синхронизированных методов (например, Math.random()), или работа была слишком мала, чтобы оправдать накладные расходы, однако я не думаю, что это здесь имеет место.

Мой процессор имеет 4 физических/8 логических ядра. После одного разогрева я тестирую следующий код с n = 1; 2; 3; 4; 8 на матрице 11x11;

ExecutorService pool = Executors.newFixedThreadPool(n); 
long startTime = System.currentTimeMillis(); 
double result = pool.submit(new Solver(pool, matrix)).get(); 
System.out.println(result); 
long stopTime = System.currentTimeMillis(); 
long elapsedTime = stopTime - startTime; 
System.out.println(elapsedTime); 

Execution принимает respectivelly:

1 ~ 15500 2 ~ 13500 - 14000 3 ~ 14300 - 15500 4 ~ 14500 - 19000 8 ~ 19000 - 23000

Так я получаю небольшое повышение с 2, почти без повышения с 3, иногда почти без усиления, но иногда экстремальное замедление с 4 и полное замедление с 8;

Вот код:

import java.util.ArrayList; 
import java.util.concurrent.Callable; 
import java.util.concurrent.ExecutionException; 
import java.util.concurrent.ExecutorService; 
import java.util.concurrent.Future; 
import java.util.concurrent.ThreadPoolExecutor; 

public class Solver implements Callable<Double> { 

    private ExecutorService pool; 
    private double[][] matrix; 


    public Solver(ExecutorService pool, double[][] matrix){ 
     this.pool = pool; 
     this.matrix = matrix; 
    } 

    public double determinant(double[][] matrix) { 
     if (matrix.length == 1) 
      return (matrix[0][0]); 

     double coefficient; 
     double sum = 0; 
     int threadsCount = ((ThreadPoolExecutor) pool).getMaximumPoolSize(); 
     ArrayList<Double> coefficients = new ArrayList<Double>(); 
     ArrayList<Future<Double>> delayedDeterminants = new ArrayList<Future<Double>>(); 

     for (int k = 0; k < matrix.length; k++) { 
      double[][] smaller = new double[matrix.length - 1][matrix.length - 1]; 
      for (int i = 1; i < matrix.length; i++) { 
       for (int j = 0; j < matrix.length; j++) { 
        if (j < k) 
         smaller[i - 1][j] = matrix[i][j]; 
        else if (j > k) 
         smaller[i - 1][j - 1] = matrix[i][j]; 
       } 
      } 
      coefficient = ((k % 2 == 0) ? 1 : -1) * matrix[0][k]; 
      if (((ThreadPoolExecutor) pool).getActiveCount() < threadsCount 
        && matrix.length > 5) { 
       coefficients.add(coefficient); 
       delayedDeterminants.add(pool.submit(new Solver(pool, smaller))); 
      } else 
       sum += coefficient * (determinant(smaller)); 
     } 

     try { 
      for (int i = 0; i < coefficients.size(); i++) 
       sum += coefficients.get(i) * delayedDeterminants.get(i).get(); 
     } catch (InterruptedException | ExecutionException e) { 
      e.printStackTrace(); 
     } 

     return (sum); 
    } 

    @Override 
    public Double call() throws Exception { 
     return determinant(matrix); 
    } 

} 

Answer 1

Общий способ борьбы с таким разделяй и властвуй алгоритм опускаться до определенного уровня в одном потоке, пока не достаточно независимые задачи, а затем планировать все эти задачи в ExecutorService, позволяя дальнейшим уровням рекурсии выполняться в рамках одной задачи. Например, на одном уровне у вас есть 121 подматрицы для вычисления детерминанта, поэтому отправьте 121 задачу в ExecutorService. Или перейдите еще на один уровень, чтобы получить 12 100 подзадач и представить все это.

Опрос ExecutorService для подсчета активной задачи, вероятно, не самая лучшая идея. Создайте newFixedThreadPool(4) или любое количество потоков, с которыми вы хотите протестировать, и позвольте ExecutorService управлять выполнением задачи. Если то, что вы пытаетесь сделать, - это кража работы, после чего я хотел бы предложить вам потратить некоторое время, чтобы ознакомиться с картой Fork/Join, которая автоматически управляет работой. Он предназначен для обработки точно ваших задач.

Другое дело, прямо не связанное с вопросом: вы должны обязательно перепроектировать код, поэтому для всех вычислений используется только один 2D-массив. 1D-массив будет еще лучше.