Challenge - Parallelize recursive fibonacci with openmp to beat my scaling numbers

Challenge - Parallelize recursive fibonacci with openmp to beat my scaling numbers

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.

The result:


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!

Bob C

Download fibwarts.zip2.8 KB
1 post / 0 new
For more complete information about compiler optimizations, see our Optimization Notice.