Улучшить производительность параллельного вычисления числа Эйлера

Question

Я пытаюсь вычислить e=∑(3−4k^2/(2k+1)!); k=0..10000 Однако я застрял и не могу получить желаемое повышение производительности с помощью многопоточности.

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

ExecutorService executor = Executors.newFixedThreadPool(numberOfThreads);
List<Future<BigDecimal>> futures = new ArrayList<>(numberOfThreads);
int step = k / numberOfThreads ;
BigDecimal result = BigDecimal.ZERO;
for (int j = 0; j <= k; j += step) {
    Future<BigDecimal> future = executor.submit(new EulerCalculator(j, j + step));
    futures.add(future);
}
for (Future<BigDecimal> future : futures) {
    result = result.add(future.get());
}

public class EulerCalculator implements Callable<BigDecimal> {
    private int start;
    private int end;

    public BigDecimal call() {
        long numerator = 3 - 4 * start * start;
        BigDecimal denominator = factorial(2 * start + 1);
        BigDecimal partialSum = BigDecimal.valueOf(numerator)
                                .divide(denominator, 1000, RoundingMode.HALF_EVEN);
        for (int i = start + 1 ; i < end; i++) {
            numerator = 3 - 4 * i * i;
            denominator = denominator.multiply(BigDecimal.valueOf(2 * i * (2*i + 1)));
            partialSum = partialSum.add(BigDecimal.valueOf(numerator)
                                        .divide(fact, 1000, RoundingMode.HALF_EVEN));
        }

        return partialSum;
    }

    private BigDecimal factorial(int cur) {
        BigDecimal fact = BigDecimal.ONE;
        for (int i = 2; i <= cur; i++) {
            fact = fact.multiply(BigDecimal.valueOf(i));
        }

        return fact;
    }
}

Наилучшие результаты за несколько запусков на четырехъядерном процессоре:

k = 10000

потоков = 1: 345 мс

потоков = 2: 216мс

потоков = 4: 184 мс

потоков = 8: 225 мс

Answer 1

Поскольку вам нужны все denominator s, и каждый из них зависит от ALL previous, у меня будет один выделенный поток для вычисления всех из них;и для каждого вычисленного denominator отправьте отдельную задачу в ваш пул потоков для параллельного вычисления конкретной частичной суммы.Наконец, агрегируйте все результаты, используя параллельный поток .Следующий код показывает эти детали:

    public static BigDecimal calculate(int k, int numberOfThreads) {
        ExecutorService executor = Executors.newFixedThreadPool(numberOfThreads);
        List<Future<BigDecimal>> futures = new ArrayList<>(numberOfThreads);

        BigDecimal denominator = BigDecimal.ONE;
        for (int j = 1; j <= k; j++) {
            denominator = denominator.multiply(BigDecimal.valueOf(4 * j * j + 2 * j));
            Future<BigDecimal> future = executor.submit(computePartialSum(j, denominator));
            futures.add(future);
        }

        return futures.stream().parallel()
            .map(future.get())
            .reduce(BigDecimal.ZERO, BigDecimal::add).add(BigDecimal.valueOf(3));
    }

    public static Callable<BigDecimal> computePartialSum(int curr, BigDecimal denominator) {
        return () -> {
            long numerator = 3 - 4 * curr * curr;
            return BigDecimal.valueOf(numerator).divide(denominator, 1000, RoundingMode.HALF_EVEN);
        };
    }

Тем не менее, вашим узким местом будет вычисление факториалов;который вы можете разделить на более мелкие факторные сегменты и кэшировать их, чтобы объединить в их истинные значения, мои два цента.

Answer 2

Ваша факторная часть - это не операция с постоянным временем, а O (n). Это означает, что ваш первый поток будет иметь значительно меньше работы, чем последний поток. Поэтому вы не распределяете работу равномерно.

Как правило, есть три способа решения этой проблемы.

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

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

Другим способом является создание большого массива, содержащего все факториалы, которые могут использоваться в вычислениях, которые должны быть запущены перед отправкой какой-либо задачи. Этот метод кэширования теряет меньше точности. См. Комментарий ниже о том, как распараллелить этот процесс.

Answer 3

Спасибо за ответы!Я кэшировал факториалы с помощью простого цикла for и получил хорошие результаты для другого вычисления:

1 thread = 17ms
2 threads  = 10ms
4 threads = 7ms

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

Я проверил этот алгоритм n!:

public BigDecimal calculate(int number) {
        if (number == 0 || number == 1) {
            return BigDecimal.ONE;
        }
        List<Callable<BigDecimal>> callables = new ArrayList<>();
        int step = number / processors;
        for (int i = 2; i <= number; i += step + 1) {
            callables.add(new FactorialPartCalculator(i, i + step >= number ? number : i + step));
        }
        List<Future<BigDecimal>> futures = executor.invokeAll(callables);
        BigDecimal result = BigDecimal.ONE;
        for (Future<BigDecimal> future : futures) {
            result = result.multiply(future.get());
        }
        return result;
    }
public class FactorialPartCalculator implements Callable<BigDecimal> {
    @Override
    public BigDecimal call() throws Exception {
        BigDecimal factorialPart = BigDecimal.ONE;
        for (int i = start; i <= end; i++) {
            factorialPart = factorialPart.multiply(BigDecimal.valueOf(i));
        }

        return factorialPart;
    }

Я получил ускорение в 6,4 разас 6 нитками для 20000!.Поэтому мне нужно кэшировать факториалы и включить процесс кэширования в общее время.Программа будет протестирована на 32 процессорах, и я должен получить как можно большее ускорение

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