How to select optimum number of threads

Question

Actually I wrote a Java program for calculating a particular number on the Fibonacci series.

The problem is right now is that I am using number of cores as number of threads required. But I have observed that as the input size increases I get better performance by increasing the number of threads.

Is there an existing formula/Theory on how to divide the problem into multiple threads?

Below is the source code:

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

One important factor to consider for the optimal number of threads is the degree of parallelism in the problem. For a problem where you can only perform say 4 tasks at a time there is no point having more than 4 threads (and it may even be slower)

As you know the formula for the fibonacci series is

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)

The only degrees of parallelism are for values below 3. For numbers greater than this each value cannot be calculated until the previous value has. This means the optimal number of thread is one and only one.

You might say, why might more thread appear to improve performance. This would be because you have taken an inefficient strategy and its the inefficiencies you are speeding up.

If you take the most efficient strategy from the start, the optimal number of threads is one.

Answer 2

In case you haven't already realized this, Fibonacci numbers are not a good candidate for parallelization. You will get (increasingly) better performance:

• by using a single threaded recursive algorithm,
• by using a single threaded recursive algorithm with memoization, and
• by solving the recurrence relation and implementing the resulting formula.

---

The basic problem is that the naive Fibonacci calculation requires an exponential number of computation steps. You can't make an impact on that (in terms of performance) with multi-threading because you have a bounded number of processors.

Even if you did have an infinite number of processors, the thread setup / task creation overheads exceed the time for doing a step in the calculation.

Finally, there is a particular problem with doing Fibonacci using the executor service and a bounded thread pool. If the thread pool is too small (or N is too large) the computation is liable to get stuck. For instance, the way that you've coded it needs ~N threads in the pool to calculate fibonacci(N), even though most of them will be blocked most of the time. (The best way to understand this is to "hand execute" the application, paying attention to how many threads are in use at each point in time ... and what they are doing.)

---

So the simple answer to your question is (for this particular application) that you need at least N threads in the pool to even complete the computation of Fibonacci(N). (This is not a general answer. It is mandated by the details of the algorithm that you've implemented.)

---

There are lots of other SO questions / answers on calculating Fibonacci numbers using threads. I suggest you read them as well.

Answer 3

I don't think there's an existing formula for how many threads to create. You have to look at factors such as I/O. If your thread is going to be blocked on I/O calls (which are much, much slower), then the CPU can run another thread during that time. On the other hand, if your threads are computation heavy, and require little/no I/O, then matching the number of threads to the number of cores is a good idea, as you prevent the overhead of switching between threads.

Answer 4

No formula, because it depends on your problem, your operating system, etc. You'll reach a point where the overhead of context switching doesn't help your cause. If every task is the same, more threads on the same process will just mean context switching.

Best to experiment your way to an optimum here.