Многопоточное умножение матриц

Вы создаете много потоков. Мало того, что создавать потоки дорого, но для приложения с привязкой к ЦП вам не нужно больше потоков, чем у вас есть доступные процессоры (если вы это сделаете, вам придется тратить вычислительную мощность на переключение между потоками, что также может вызвать кеш пропуски, которые очень дороги).

Также нет необходимости отправлять поток на выполнить ; все, что ему нужно, это Runnable . Вы получите значительный прирост производительности, применив следующие изменения:

1. Сделайте ExecutorService статическим членом, установите размер для текущего процессора и отправьте ему ThreadFactory , чтобы он не работал. Не продолжать выполнение программы после завершения main . Executors.newFixedThreadPool (Runtime.getRuntime (). AvailableProcessors (), new ThreadFactory () { public Thread newThread (Runnable r) { Тема t = новая тема (r); t.setDaemon (правда); return t; } });

2. Сделайте так, чтобы MatrixThread реализовал Runnable , а не наследовал Thread . Создание потоков дорогое удовольствие; POJO очень дешевы. Вы также можете сделать его статическим , что сделает экземпляры меньше (поскольку нестатические классы получают неявную ссылку на включающий объект).

    частный статический класс MatrixThread реализует Runnable
   

3. Из изменения (1) вы больше не можете awaitTermination , чтобы убедиться, что все задачи завершены (как этот пул рабочих). Вместо этого используйте метод submit , который возвращает Future . Соберите все будущие объекты в список, а когда вы отправите все задачи, выполните итерацию по списку и вызовите get для каждого объекта.

Ваш метод multiply теперь должен выглядеть примерно так:

public Matrix multiply(Matrix multiplier) throws InterruptedException {
    Matrix result = new Matrix(dimension);
    List<Future<?>> futures = new ArrayList<Future<?>>();
    for(int currRow = 0; currRow < multiplier.dimension; currRow++) {
        for(int currCol = 0; currCol < multiplier.dimension; currCol++) {            
            Runnable worker = new MatrixThread(this, multiplier, currRow, currCol, result);
            futures.add(workerPool.submit(worker));
        }
    }
    for (Future<?> f : futures) {
        try {
            f.get();
        } catch (ExecutionException e){
            throw new RuntimeException(e); // shouldn't happen, but might do
        }
    }
    return result;
}

Будет ли он быстрее, чем однопоточная версия? Что ж, на моем, возможно, паршивом ящике многопоточная версия работает медленнее при значениях n <1024.

Однако это только поверхностный анализ. Настоящая проблема заключается в том, что вы создаете лот из MatrixThread экземпляров - потребление памяти составляет O (n²) , что является очень плохой знак . Перемещение внутреннего цикла for в MatrixThread.run повысит производительность в раз раз (в идеале вы не создаете больше задач, чем у вас есть рабочих потоков).

---

Edit : Поскольку у меня есть более неотложные дела, я не мог удержаться от дальнейшей оптимизации. Я придумал этот (... ужасно уродливый фрагмент кода), который «только» создает O (n) заданий:

 public Matrix multiply(Matrix multiplier) throws InterruptedException {
     Matrix result = new Matrix(dimension);
     List<Future<?>> futures = new ArrayList<Future<?>>();
     for(int currRow = 0; currRow < multiplier.dimension; currRow++) {
         Runnable worker = new MatrixThread2(this, multiplier, currRow, result);
         futures.add(workerPool.submit(worker)); 
     }
     for (Future<?> f : futures) {
         try {
             f.get();
         } catch (ExecutionException e){
             throw new RuntimeException(e); // shouldn't happen, but might do
         }
     }
     return result;
 }


private static class MatrixThread2 implements Runnable
{
   private Matrix self, mul, result;
   private int row, col;      

   private MatrixThread2(Matrix a, Matrix b, int row, Matrix result)
   {         
      this.self = a;
      this.mul = b;
      this.row = row;
      this.result = result;
   }

   @Override
   public void run()
   {
      for(int col = 0; col < mul.dimension; col++) {
         int cellResult = 0;
         for (int i = 0; i < self.getMatrixDimension(); i++)
            cellResult += self.template[row][i] * mul.template[i][col];
         result.template[row][col] = cellResult;
      }
   }
}

Это все еще не очень хорошо, но в основном многопоточная версия может вычислить что угодно у вас хватит терпения дождаться, и он сделает это быстрее, чем однопоточная версия.

run повысит производительность в раз (в идеале вы не создаете больше задач, чем рабочих потоков).

---

Изменить: Поскольку у меня есть более важные дела да, я не удержался от дальнейшей оптимизации. Я придумал этот (... ужасно уродливый фрагмент кода), который «только» создает O (n) заданий:

 public Matrix multiply(Matrix multiplier) throws InterruptedException {
     Matrix result = new Matrix(dimension);
     List<Future<?>> futures = new ArrayList<Future<?>>();
     for(int currRow = 0; currRow < multiplier.dimension; currRow++) {
         Runnable worker = new MatrixThread2(this, multiplier, currRow, result);
         futures.add(workerPool.submit(worker)); 
     }
     for (Future<?> f : futures) {
         try {
             f.get();
         } catch (ExecutionException e){
             throw new RuntimeException(e); // shouldn't happen, but might do
         }
     }
     return result;
 }


private static class MatrixThread2 implements Runnable
{
   private Matrix self, mul, result;
   private int row, col;      

   private MatrixThread2(Matrix a, Matrix b, int row, Matrix result)
   {         
      this.self = a;
      this.mul = b;
      this.row = row;
      this.result = result;
   }

   @Override
   public void run()
   {
      for(int col = 0; col < mul.dimension; col++) {
         int cellResult = 0;
         for (int i = 0; i < self.getMatrixDimension(); i++)
            cellResult += self.template[row][i] * mul.template[i][col];
         result.template[row][col] = cellResult;
      }
   }
}

Это все еще не очень хорошо, но в основном многопоточная версия может вычислить что угодно у вас хватит терпения дождаться, и он сделает это быстрее, чем однопоточная версия.

run повысит производительность в раз (в идеале вы не создаете больше задач, чем рабочих потоков).

---

Изменить: Поскольку у меня есть более важные дела да, я не мог удержаться от дальнейшей оптимизации. Я придумал этот (... ужасно уродливый фрагмент кода), который «только» создает O (n) заданий:

 public Matrix multiply(Matrix multiplier) throws InterruptedException {
     Matrix result = new Matrix(dimension);
     List<Future<?>> futures = new ArrayList<Future<?>>();
     for(int currRow = 0; currRow < multiplier.dimension; currRow++) {
         Runnable worker = new MatrixThread2(this, multiplier, currRow, result);
         futures.add(workerPool.submit(worker)); 
     }
     for (Future<?> f : futures) {
         try {
             f.get();
         } catch (ExecutionException e){
             throw new RuntimeException(e); // shouldn't happen, but might do
         }
     }
     return result;
 }


private static class MatrixThread2 implements Runnable
{
   private Matrix self, mul, result;
   private int row, col;      

   private MatrixThread2(Matrix a, Matrix b, int row, Matrix result)
   {         
      this.self = a;
      this.mul = b;
      this.row = row;
      this.result = result;
   }

   @Override
   public void run()
   {
      for(int col = 0; col < mul.dimension; col++) {
         int cellResult = 0;
         for (int i = 0; i < self.getMatrixDimension(); i++)
            cellResult += self.template[row][i] * mul.template[i][col];
         result.template[row][col] = cellResult;
      }
   }
}

Это все еще не очень хорошо, но в основном многопоточная версия может вычислить что угодно у вас будет достаточно терпения, чтобы дождаться, и он сделает это быстрее, чем однопоточная версия.