Умножение

Question

Я закодировал .... Я считаю, что мой подход прав, но я не уверен на 100%. Что касается потоков, я не понимаю, почему я не могу просто запустить (new MatrixThread(...)).start() вместо использования ExecutorService.

Кроме того, когда я тест и ... подход по сравнению с классическим подходом, классический это гораздо быстрее ...

Что я делаю неправильно?

P.S. Пожалуйста, дайте мне знать, требуется ли дальнейшее уточнение.

Answer 1

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

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

1. сделать ExecutorService статический элемент, размер его для текущего процессора, и отправить его ThreadFactory поэтому не хранит программу работы после того, как main закончил. (Это, вероятно, будет архитектурно уборщик, чтобы отправить его в качестве параметра метода, а не держать его в статическом поле, я оставляю это в качестве упражнения для читателя ☺.)

   private static final ExecutorService workerPool = 
       Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors(), new ThreadFactory() { 
        public Thread newThread(Runnable r) { 
         Thread t = new Thread(r); 
         t.setDaemon(true); 
         return t; 
        } 
       }); 
   

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

   private static class MatrixThread implements 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²), который является очень плохой знак. Перемещение внутреннего цикла на MatrixThread.run повысило бы производительность в craploads (в идеале вы не создаете больше задач, чем рабочие потоки).

---

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; 
     } 
    } 
} 

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

Answer 2

Существует множество накладных расходов, связанных с созданием потоков, даже при использовании ExecutorService. Я подозреваю, что причина, по которой вы используете многопоточный подход, настолько медленна, что вы тратите 99% на создание нового потока и только 1% или меньше, выполняете фактическую математику.

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

Answer 3

Прежде всего, вы должны использовать newFixedThreadPool такого размера, как у многих ядер, на четырехъядерном процессоре, который вы используете 4. Во-вторых, не создавайте новую для каждой матрицы.

Если сделать ExecutorService статическую переменную-член, я получаю почти последовательно быстрее выполнение многопоточной версии с размером матрицы 512.

Кроме того, изменить MatrixThread реализовать Runnable вместо простирающейся Thread также ускоряет выполнение программы где резьба на моей машине 2x так же быстро на 512