why the fib (c++async and c++thread) is not working when increasing n to 15-18 and above

[soulmaz_s_]

I have implemented Fibonacci in C++ by using  (c++async and c++thread)​, I run the code in a server which  has two CPU, total 36 cores, supporting 72 threads. But the implementations are not working for numbers higher that 18. The codes and the errors are shown below. Could you please let mw know what the reasons could be!?

void fib(int * result, int n)
 { int x,y;
        if (n < 2)
         *result = n;
    else{
        int x, y;
        std::thread t1 (fib, &x, n-1);
        //std::thread t2 (fib, &y, n-2);
        fib(&y, n-2);
        t1.join();
        //t2.join();
        *result = x+y;
    }
 }

Second implementation:

int fib(int n)

{
    if (n < 2) {
            return n;
       } else {
       int y;
       std::future<int> x=std::async(std::launch::async,fib,n-1);
           y = fib(n - 2);
           int z= x.get();
           return (z + y);
     }
  } 

error for ths codes for fib 20 is :

terminate called after throwing an instance of 'std::system_error'
  what():  Resource temporarily unavailable

[jimdempseyatthecove · Accepted solution]

What is happening is you are running out of resources. The way your code is written, a new thread is constructed at each partitioning. This is in opposition from TBB or Cilk+ or OpenMP taking a thread from a fixed size thread pool.

Estimated number of std::threads:

2^(20-2) + 2^(20-2-1) + 2^(20-2-2) ... 2^(20-2-17)

Using TBB or Cilk+ or OpenMP, those numbers of tasks are created (not necessarily all run concurrently), but the number of threads is limited by the thread pool size. Using std::threads this is not the case and you will attempt to create 18! number of threads.

Jim Dempsey

[soulmaz_s_]

Thank you Jim Dempsey for your kind reply. Do you have any suggestion that I can implement Fib by std::thread and async.

I would really appreciate if you could kindly give me some references about how their runtime is implemented to support C++ std::async and std::thread. 

Best Regards,

Soulmaz

[jimdempseyatthecove]

What you would do is one of two things:

a) Have:
  int fib(int level, int n);
  int fib(int n);
  start with call to fib(0, N);, and then test incoming level for less than threshold. If less than threshold, spawn thread with level+1 and new n, else call fib(n) with appropriate n.

b) Have:
  int fib_spawner(int n);
  int fib(int n);
  initialize a shared atomic variable (or volatile interlocked variable), perform an atomic xchgadd and if the return is less than desired thread count spawn thread with appropriate n else call fib(n) with appropriate n.

*** The above is an exercise in nested parallelism ***

// Serial non-recursive method to calculate Fibonacci series
// *** Note, several orders of magnitude faster than all
// *** recursive techniques.
long SerialFib2( long n )
{
 if( n<2 )
  return n;
 long fib0 = 1; // most recent
 long fib1 = 1; // 1 prior to most recent
 long fib2 = 0; // 2 prior to most recent
 long i;
 for(i=2; i<n; ++i)
 {
  fib2 = fib1;
  fib1 = fib0;
  fib0 = fib1 + fib2;
 }
 return fib0;
}

Jim Dempsey

[soulmaz_s_]

Thank you for the comment and your help  Jim Dempsey.