如何选择最佳线程数

Question

实际上我写了一个Java程序来计算Fibonacci系列上的特定数字.

现在的问题是我使用的核心数量是所需的线程数.但我观察到随着输入大小的增加,我通过增加线程数来获得更好的性能.

是否存在关于如何将问题划分为多个线程的现有公式/理论？

以下是源代码:

import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class Fibonacci {
    private static long[] value;

    public static void main(String args[]) throws InterruptedException {
        int n;
        try {
            n = Integer.parseInt(args[0]);
        } catch (Exception e) {
            throw new RuntimeException(
                    "Please enter in the form java n number ");
        }
        value = new long[n + 1];


        long start = System.nanoTime();
        int nThreads = Runtime.getRuntime().availableProcessors();
        ExecutorService executorService = Executors
                .newFixedThreadPool(nThreads);
        int result;
        try {
            result = fibonacciSum(n, executorService);
        } catch (ExecutionException e) {
            throw new RuntimeException("Thread Interuppted ");
        }
        System.out.print(" MultiThreading = " + result);
        long end = System.nanoTime();
        System.out.println("\t time = " + (end - start) + "ns");
    }


    private static class FibonacciThread implements Runnable {
        int index;
        int result;
        ExecutorService executorService;

        public FibonacciThread(int index) {
            this.index = index;
        }

        public void run() {
            try {
                this.result = fibonacciSum(index, executorService);
            } catch (Exception e) {
                throw new RuntimeException("Thread interupted");
            }
        }
    }

    private static int fibonacciSum(int index, ExecutorService executorService)
            throws InterruptedException, ExecutionException {
        if (index <= 2) {
            return 1;
        } else {

            FibonacciThread fibonacciThread1 = new FibonacciThread(index - 2);
            fibonacciThread1.executorService = executorService;
            Future future = executorService.submit(fibonacciThread1);
            Object object = future.get();
            int resultPart2 = fibonacciSum(index - 1, executorService);
            int result = fibonacciThread1.result + resultPart2;
            // executorService.shutdown();
            return result;
        }
    }

}

Answer 1

如果您还没有意识到这一点,Fibonacci数字不适合并行化.您将获得(越来越)更好的性能:

• 通过使用单线程递归算法,
• 通过使用具有memoization的单线程递归算法,和
• 通过求解递归关系并实现所得到的公式.

基本问题是天真的斐波纳契计算需要指数个计算步骤.您无法通过多线程对其(在性能方面)产生影响,因为您拥有有限数量的处理器.

即使您确实拥有无限数量的处理器,线程设置/任务创建开销也会超出执行计算步骤的时间.

最后,使用执行程序服务和有界线程池进行Fibonacci时存在一个特殊问题.如果线程池太小(或N太大),则计算可能会卡住.例如,您编码它的方式需要~N池中的线程来计算fibonacci(N),即使它们中的大多数都会在大多数时间被阻塞.(理解这一点的最好方法是"手动执行"应用程序,注意每个时间点正在使用的线程数......以及它们正在做什么.)

因此,对于您的问题的简单答案是(对于此特定应用程序),您至少需要N池中的线程来完成计算Fibonacci(N).(这不是一般性答案.它是由您实施的算法的细节强制实施的.)

使用线程计算Fibonacci数时还有很多其他的SO问题/答案.我建议你也阅读它们.