Блог

Я пишу реализацию метода сопряженного градиента.

Я использую многопоточность Java для обратной замены матрицы. Синхронизация производится с помощью CyclicBarrier, CountDownLatch.

Почему синхронизация потоков занимает так много времени? Есть ли другие способы сделать это?

фрагмент кода

 private void syncThreads() {

    // barrier.await();

    try {

        barrier.await();

    } catch (InterruptedException e) {

    } catch (BrokenBarrierException e) {

    }

}
  

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

Вот пример, когда накладные расходы на передачу задачи другому потоку намного перевешивают преимущества использования нескольких потоков.

 final double[] results = new double[10*1000*1000];
{
    long start = System.nanoTime();
    // using a plain loop.
    for(int i=0;i<results.length;i  ) {
        results[i] = (double) i * i;
    }
    long time = System.nanoTime() - start;
    System.out.printf("With one thread it took %.1f ns per square%n", (double) time / results.length);
}
{
    ExecutorService ex = Executors.newFixedThreadPool(4);
    long start = System.nanoTime();
    // using a plain loop.
    for(int i=0;i<results.length;i  ) {
        final int i2 = i;
        ex.execute(new Runnable() {
            @Override
            public void run() {
                results[i2] = i2 * i2;

            }
        });
    }
    ex.shutdown();
    ex.awaitTermination(1, TimeUnit.MINUTES);
    long time = System.nanoTime() - start;
    System.out.printf("With four threads it took %.1f ns per square%n", (double) time / results.length);
}
  

С принтами

 With one thread it took 1.4 ns per square
With four threads it took 715.6 ns per square
  

Использование нескольких потоков намного хуже.

Однако увеличьте объем работы, выполняемой каждым потоком, и

 final double[] results = new double[10 * 1000 * 1000];
{
    long start = System.nanoTime();
    // using a plain loop.
    for (int i = 0; i < results.length; i  ) {
        results[i] = Math.pow(i, 1.5);
    }
    long time = System.nanoTime() - start;
    System.out.printf("With one thread it took %.1f ns per pow 1.5%n", (double) time / results.length);
}
{
    int threads = 4;
    ExecutorService ex = Executors.newFixedThreadPool(threads);
    long start = System.nanoTime();
    int blockSize = results.length / threads;
    // using a plain loop.
    for (int i = 0; i < threads; i  ) {
        final int istart = i * blockSize;
        final int iend = (i   1) * blockSize;
        ex.execute(new Runnable() {
            @Override
            public void run() {
                for (int i = istart; i < iend; i  )
                    results[i] = Math.pow(i, 1.5);
            }
        });
    }
    ex.shutdown();
    ex.awaitTermination(1, TimeUnit.MINUTES);
    long time = System.nanoTime() - start;
    System.out.printf("With four threads it took %.1f ns per pow 1.5%n", (double) time / results.length);
}
  

С принтами

 With one thread it took 287.6 ns per pow 1.5
With four threads it took 77.3 ns per pow 1.5
  

Это улучшение почти в 4 раза.

Сколько потоков используется в общей сложности? Это, вероятно, источник вашей проблемы. Использование нескольких потоков действительно повысит производительность, только если:

• Каждая задача в потоке выполняет своего рода блокировку. Например, ожидание ввода-вывода. Использование нескольких потоков в этом случае позволяет использовать это время блокировки другими потоками.
• или у вас несколько ядер. Если у вас 4 ядра или 4 процессора, вы можете выполнять 4 задачи одновременно (или 4 потока).

Похоже, вы не блокируете потоки, поэтому я предполагаю, что вы используете слишком много потоков. Если вы, например, используете 10 разных потоков для выполнения работы одновременно, но имеете только 2 ядра, это, вероятно, будет намного медленнее, чем выполнение всех задач последовательно. Обычно запускайте количество потоков, равное вашему количеству ядер / процессоров. Медленно увеличивайте количество используемых потоков, каждый раз измеряя производительность. Это даст вам оптимальное количество потоков для использования.

Возможно, вы могли бы попытаться реализовать, чтобы повторно реализовать свой код с помощью fork / join из JDK 7 и посмотреть, что это дает?

По умолчанию создается пул потоков с точно таким же количеством потоков, сколько ядер в вашей системе. Если вы разумно выберете пороговое значение для разделения вашей работы на более мелкие фрагменты, это, вероятно, будет выполняться намного эффективнее.

Вы, скорее всего, знаете об этом, но в случае, если вы этого не знаете, пожалуйста, ознакомьтесь с Законом Амдала. Это дает взаимосвязь между ожидаемым ускорением программы при использовании параллелизма и последовательными сегментами программы.

синхронизация между ядрами происходит намного медленнее, чем в среде с одним ядром посмотрите, можете ли вы ограничить jvm одним ядром (см. Этот пост в блоге)

или вы можете использовать ExecuterorService и использовать invokeAll для запуска параллельных задач