Intel® C++ Compiler
Support and discussions for creating C++ code that runs on platforms based on Intel® processors.
7650 Discussions

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

soulmaz_s_
Beginner
240 Views

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

 

 

 

 

 

 

 

0 Kudos
1 Solution
jimdempseyatthecove
Black Belt
240 Views

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

View solution in original post

4 Replies
jimdempseyatthecove
Black Belt
241 Views

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_
Beginner
240 Views

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
Black Belt
240 Views

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_
Beginner
240 Views

Thank you for the comment and your help  Jim Dempsey.

Reply