[Omp] Recursive routines

[Tian, Xinmin]

You can use parallel taskq model supported by Intel compiler. Below is a simple example how recursive routine is parallelized with taskq. 

#include <stdlib.h>
#include <stdio.h>
#include <omp.h>

#define TASKQ_DEPTH	4

int fib(int n, int d);

int fib_taskq(int n, int d) {
    int x, y;
    #pragma intel omp taskq
    {
      #pragma intel omp task
	{
	    x = fib(n - 1, d+1);
	}
	#pragma intel omp task
	{
	    y = fib(n - 2, d+1);
	}
    }
  return x+y;
}

int fib(int n, int d) {
     if (n < 2) {
	  return (n);
     } else if (d < TASKQ_DEPTH) {
	  return fib_taskq(n,d);
     } else {
	  int x, y;
          x = fib(n - 1, d+1);
          y = fib(n - 2, d+1);
	  return (x + y);
     }
}

int fib_iter(int n) {
     int f0, f1, f2, i;
     if (n < 2)
	  return n;
     f0 = 0;
     f1 = 1;
     f2 = 1;
     for (i = 2; i <= n; ++i) {
	  f2 = f0 + f1;
	  f0 = f1;
	  f1 = f2;
     }

     return f2;
}

int main(int argc, char *argv[]) {
     int n, answer;
     double start, end;

     if (argc < 2) {
	  fprintf(stderr, "Usage: fib n\n");
	  return -1;
     }
     n = atoi(argv[1]);

     #pragma omp parallel
         #pragma omp master
	     printf("Threads:      %d\n", omp_get_num_threads());
	 
#ifdef _OPENMP
     printf("Taskq Depth:  %d\n", TASKQ_DEPTH);
#endif

     start = omp_get_wtime();
     #pragma omp parallel
     {
         #pragma intel omp taskq
             #pragma intel omp task
                 answer = fib(n,0);
     }

     end = omp_get_wtime();

     printf("fib(%d) = %d\n", n, answer );
     if (answer != fib_iter(n))
	  printf("WRONG ANSWER!\n");

     printf("Compute Time: %f seconds\n", end - start);

     return 0;
}

-----Original Message-----
From: Omp-bounces at openmp.org [mailto:Omp-bounces at openmp.org] On Behalf Of Patricia Bittencourt Sampaio
Sent: Wednesday, April 06, 2005 4:57 AM
To: Omp at openmp.org
Subject: [Omp] Recursive routines


 Hello,
 
    I have been trying to write an openmp version of
some applications. One of them is the recursive
mergesort. I have not found out a way to parallelize
the recursive routine of mergesort since the recursive
mecanism is purelly data dependent.
 
    So, I conclude that a recursive routine can't be
parallelized with openmp so as to run the application
faster. Instead, it's necessary to convert this
routine for an iterative routine so as to be able to
use the directives of openmp more effective.
    Maybe for some other applications with a recursive
routine where more work has to be done on it, it
becames worth to parallelize a code inside the
recursive routine, but that is not the case for
mergesort. 
    I'd like to know your experiences with a recursive
routine using openmp...


best regards,

Patricia B. Sampaio
------------------------------------
Federal University of Rio de Janeiro


	
	
		
Yahoo! Acesso Grátis - Internet rápida e grátis. 
Instale o discador agora! http://br.acesso.yahoo.com/

_______________________________________________
Omp mailing list
Omp at openmp.org
http://openmp.org/mailman/listinfo/omp_openmp.org