Как быстрее вычислить число Эйлера с многопоточностью Java

Question

Итак, у меня есть задача вычислить число Эйлера с использованием нескольких потоков, используя эту формулу: sum (((3k) ^ 2 + 1) / ((3k)!)), Для k = 0 ... бесконечность.

import java.math.BigDecimal;
import java.math.BigInteger;
import java.io.FileWriter;
import java.io.IOException;
import java.math.RoundingMode;

class ECalculator {
  private BigDecimal sum;
  private BigDecimal[] series;
  private int length;
  
  public ECalculator(int threadCount) {
    this.length = threadCount;
    this.sum = new BigDecimal(0);
    this.series = new BigDecimal[threadCount];
    for (int i = 0; i < this.length; i++) {
      this.series[i] = BigDecimal.ZERO;
    }
  }
  
  public synchronized void addToSum(BigDecimal element) {
    this.sum = this.sum.add(element);
  }
  
  public void addToSeries(int id, BigDecimal element) {
    if (id - 1 < length) {
      this.series[id - 1] = this.series[id - 1].add(element);      
    }
  }
  
  public synchronized BigDecimal getSum() {
    return this.sum;
  }
  
  public BigDecimal getSeriesSum() {
    BigDecimal result = BigDecimal.ZERO;
    for (int i = 0; i < this.length; i++) {
      result = result.add(this.series[i]);
    }
    return result;
  }
}

class ERunnable implements Runnable {
  private final int id;
  private final int threadCount;
  private final int threadRemainder;
  private final int elements;
  private final boolean quietFlag;
  private ECalculator eCalc;

  public ERunnable(int threadCount, int threadRemainder, int id, int elements, boolean quietFlag, ECalculator eCalc) {
    this.id = id;
    this.threadCount = threadCount;
    this.threadRemainder = threadRemainder;
    this.elements = elements;
    this.quietFlag = quietFlag;
    this.eCalc = eCalc;
  }

  @Override
  public void run() {
    if (!quietFlag) {
      System.out.println(String.format("Thread-%d started.", this.id));      
    }
    long start = System.currentTimeMillis();
    int k = this.threadRemainder;
    int iteration = 0;
    BigInteger currentFactorial = BigInteger.valueOf(intFactorial(3 * k));
    
    while (iteration < this.elements) {
      if (iteration != 0) {
        for (int i = 3 * (k - threadCount) + 1; i <= 3 * k; i++) {
          currentFactorial = currentFactorial.multiply(BigInteger.valueOf(i));
        }
      }
      
      this.eCalc.addToSeries(this.id, new BigDecimal(Math.pow(3 * k, 2) + 1).divide(new BigDecimal(currentFactorial), 100, RoundingMode.HALF_UP));
      
      iteration += 1;
      k += this.threadCount;
    }
    
    long stop = System.currentTimeMillis();
    if (!quietFlag) {
      System.out.println(String.format("Thread-%d stopped.", this.id));
      System.out.println(String.format("Thread %d execution time: %d milliseconds", this.id, stop - start));      
    }
  }
  
  public int intFactorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
      result *= i;
    }
    return result;
  }
}

public class TaskRunner {
  public static final String DEFAULT_FILE_NAME = "result.txt";
  public static void main(String[] args) throws InterruptedException {

    int threadCount = 2;
    int precision = 10000;
    int elementsPerTask = precision / threadCount;
    int remainingElements = precision % threadCount;
    boolean quietFlag = false;
    
    calculate(threadCount, elementsPerTask, remainingElements, quietFlag, DEFAULT_FILE_NAME);
  }
  
  public static void writeResult(String filename, String result) {
    try {
      FileWriter writer = new FileWriter(filename);
      writer.write(result);
      writer.close();
    } catch (IOException e) {
      System.out.println("An error occurred.");
      e.printStackTrace();
    }
  }
  
  public static void calculate(int threadCount, int elementsPerTask, int remainingElements, boolean quietFlag, String outputFile) throws InterruptedException {
    long start = System.currentTimeMillis();
    Thread[] threads = new Thread[threadCount];
    ECalculator eCalc = new ECalculator(threadCount);
    
    for (int i = 0; i < threadCount; i++) {
      if (i == 0) {
        threads[i] = new Thread(new ERunnable(threadCount, i, i + 1, elementsPerTask + remainingElements, quietFlag, eCalc));
      } else {
        threads[i] = new Thread(new ERunnable(threadCount, i, i + 1, elementsPerTask, quietFlag, eCalc));        
      }
      threads[i].start();
    }
    
    for (int i = 0; i < threadCount; i++) {
      threads[i].join();
    }
    
    String result = eCalc.getSeriesSum().toString();
    
    if (!quietFlag) {
      System.out.println("E = " + result);      
    }
    
    writeResult(outputFile, result);
    
    long stop = System.currentTimeMillis();
    System.out.println("Calculated in: " + (stop - start) + " milliseconds" );
  }
}

Я удалил отпечатки и т.д. c. в коде, которые не действуют. Моя проблема в том, что чем больше потоков я использую, тем медленнее он работает. В настоящее время у меня самый быстрый запуск для 1 потока. Я уверен, что факторный расчет вызывает некоторые проблемы. Я пробовал использовать пул потоков, но все равно получил то же время.

1. Как я могу сделать так, чтобы его запуск с большим количеством потоков до определенного момента ускорил процесс вычислений?
2. Как можно go вычислить эти большие факториалы?
3. Передаваемый параметр точности - это количество элементов в сумме, которые используются. Могу ли я настроить масштаб BigDecimal так, чтобы он так или иначе зависел от этой точности, чтобы я не закодировал его жестко? запускается без внешних библиотек.

   РЕДАКТИРОВАТЬ 2 Я обнаружил, что факториальный код не соответствует времени. Если я позволю потокам увеличиваться до некоторой высокой точности без вычисления факториалов, время будет сокращаться с увеличением потоков. Тем не менее, я не могу каким-либо образом реализовать факториальное вычисление, продолжая уменьшать время. для 1 потока, но приводит к неправильному расчету для нескольких.

Answer 1

После просмотра обновленного кода я сделал следующие наблюдения:

Во-первых, программа запускается за доли секунды. Это означает, что это микро-тест. Некоторые ключевые особенности Java затрудняют надежное выполнение микротестов. См. Как мне написать правильный микротест в Java? Например, если программа не выполняет достаточного количества повторений, компилятор «точно вовремя» не успевает приступить к скомпилируйте его в машинный код, и вы закончите тестированием интерпретатора. Кажется возможным, что в вашем случае компилятору JIT требуется больше времени для запуска при наличии нескольких потоков,

В качестве примера, чтобы ваша программа выполняла больше работы, я изменил точность BigDecimal со 100 до 10,000. и добавил al oop вокруг основного метода. Время выполнения измерялось следующим образом:

1 поток:

Calculated in: 2803 milliseconds
Calculated in: 1116 milliseconds
Calculated in: 1040 milliseconds
Calculated in: 1066 milliseconds
Calculated in: 1036 milliseconds

2 потока:

Calculated in: 2354 milliseconds
Calculated in: 856 milliseconds
Calculated in: 624 milliseconds
Calculated in: 659 milliseconds
Calculated in: 664 milliseconds

4 потока:

Calculated in: 1961 milliseconds
Calculated in: 797 milliseconds
Calculated in: 623 milliseconds
Calculated in: 536 milliseconds
Calculated in: 497 milliseconds

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

Итак, как мы можем получить результат без вычисления факториалов? Один из способов - это метод Хорнера. В качестве примера рассмотрим более простой ряд sum(1/k!), который также преобразуется в e, но немного медленнее, чем ваш.

Допустим, вы хотите вычислить sum(1/k!) до k = 100. С помощью метода Хорнера вы можете начните с конца и извлеките общие множители:

sum(1/k!, k=0..n) = 1/100! + 1/99! + 1/98! + ... + 1/1! + 1/0!
= ((... (((1/100 + 1)/99 + 1)/98 + ...)/2 + 1)/1 + 1

Посмотрите, как вы начинаете с 1, делите на 100 и прибавляете 1, делите на 99 и прибавляете 1, делите на 98 и складываете 1 и так далее? Это делает программу очень простой:

private static BigDecimal serialHornerMethod() {
    BigDecimal accumulator = BigDecimal.ONE;
    for (int k = 10000; k > 0; k--) {
        BigDecimal divisor = new BigDecimal(k);
        accumulator = accumulator.divide(divisor, 10000, RoundingMode.HALF_EVEN)
                                 .add(BigDecimal.ONE);
    }
    return accumulator;
}

Хорошо, это последовательный метод, как вы заставите его использовать параллельный? Вот пример для двух потоков: сначала разделите ряд на четные и нечетные члены:

1/100! + 1/99! + 1/98! + 1/97! + ... + 1/1! + 1/0! =
(1/100! + 1/98! + ...  + 1/0!) + (1/99! + 1/97! + ... + 1/1!)

Затем примените метод Хорнера как к четным, так и к нечетным членам:

1/100! + 1/98! + 1/96! + ...  + 1/2! + 1/0! = 
((((1/(100*99) + 1)/(98*97) + 1)/(96*95) + ...)/(2*1) + 1

and:

1/99! + 1/97! + 1/95! + ... + 1/3! + 1/1! =
((((1/(99*98) + 1)/(97*96) + 1)/(95*94) + ...)/(3*2) + 1

Это просто так же легко реализовать, как последовательный метод, и вы довольно близко подбираетесь к линейному ускорению, переходя от 1 до 2 потоков:

    private static BigDecimal partialHornerMethod(int start) {
        BigDecimal accumulator = BigDecimal.ONE;
        for (int i = start; i > 0; i -= 2) {
            int f = i * (i + 1);
            BigDecimal divisor = new BigDecimal(f);
            accumulator = accumulator.divide(divisor, 10000, RoundingMode.HALF_EVEN)
                                     .add(BigDecimal.ONE);
        }
        return accumulator;
    }

// Usage:

ExecutorService executorService = Executors.newFixedThreadPool(2);
Future<BigDecimal> submit = executorService.submit(() -> partialHornerMethod(10000));
Future<BigDecimal> submit1 = executorService.submit(() -> partialHornerMethod(9999));
BigDecimal result = submit1.get().add(submit.get());

Answer 2

Существует множество конфликтов между потоками: все они соревнуются за блокировку объекта ECalculator после каждого небольшого бита вычислений из-за этого метода:

  public synchronized void addToSum(BigDecimal element) {
    this.sum = this.sum.add(element);
  }

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

Чтобы исправить это, пусть потоки накапливают свои результаты отдельно и объединяют результаты после завершения потоков. То есть создайте переменную sum в ERunnable, а затем измените методы:

// ERunnable.run:
this.sum = this.sum.add(new BigDecimal(Math.pow(3 * k, 2) + 1).divide(new BigDecimal(factorial(3 * k)), 100, RoundingMode.HALF_UP));

// TaskRunner.calculate:
for (int i = 0; i < threadCount; i++) {
  threads[i].join();
  eCalc.addToSum(/* recover the sum computed by thread */);
}

Кстати было бы проще, если бы вы вместо этого использовали более высокий уровень java .util.concurrent API самостоятельного создания потоковых объектов. Вы можете заключить вычисление в Callable, которое может вернуть результат.

Q2 Как можно go вычислить эти большие факториалы?

Обычно вы этого не делаете. Вместо этого вы переформулируете проблему так, чтобы она не включала прямое вычисление факториалов. Один из методов - это метод Хорнера .

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

Конечно, почему бы и нет. Вы можете определить границу ошибки по количеству элементов (оно пропорционально последнему члену в ряду) и установить для этого масштаб BigDecimal.