I've cooked up another example of using Intel omp taskq to parallelize a recursive function application - this time Fibonacci.
I used the technique I described in my previous post on quicksort - namely writing a wrapper function to Fibonacci that counts recursive call depth and a task scheduler of sorts that determines when to create new tasks depending on recursive call depth. In this exercise I calculate the 44th Fibonacci number. Why the 44th? Because 43 or less took too little time and any more than 44 tried my patience - the time to execute almost doubles for every increment in Fibonacci number calculated with this algorithm.
serial baseline on 2x4 core Kentsfield (2x4=8 cores) - 14 seconds
parallel task1 version setting number of threads to 2 using OMP_SET_NUM_THREADS(2) - 21 seconds - Oops execution slowed down by 50% !!!
parallel taskq version on same machine (8 cores) - 5.5 seconds - ok nifty speed up - but only 3X on 8 cores - does not scale!!
So here's my challenge:
Beat my scaling of 3X on 8 cores OR get SOME speedup on 2 threads over baseline and youll be immortalized on the hallowed Academic Community Forums - here's another chance at fame & fortune ;-)
Attached is my code including all warts and blemishes. The zip includes a timer module for linux - lgettimeofday.c - and another tmer module for windows - wgettimeofday.c.
Use makefile on linux to build --> make all.
To build baseline on windows - icl fibserial.c wgettimeofday.c
To build parallel: icl fibparallel.c wgettimeofday.c /Qopenmp
Please beat this scaling and post your solution to this thread!