## Parallelizing recursive function

General OpenMP discussion

### Parallelizing recursive function

Is there someone who has had success parallelizing a recursive function?

I'm working on this function but I can't parallel my code.
It's a function that solves the Travel salesman problem.

By the way, does someone know how to parallelize it if it's possible?

typedef struct {
int matdist[MAX_VERTICES][MAX_VERTICES];
int qtd_vertices;
int maior_dist;
int dist_total;
int vet_percurso[MAX_VERTICES];
int min_dist_total;
int min_vet_percurso[MAX_VERTICES];
} Mapa;

void Forca_Bruta(Mapa *mapa)
{
int u = mapa->vet_percurso[mapa->qtd_visitados - 1];
int v;

for (v = 0; v < mapa->qtd_vertices; v++) {

mapa->dist_total += mapa->matdist[u][v];

if (mapa->qtd_visitados == mapa->qtd_vertices - 1) {
int dist_total = mapa->dist_total + mapa->matdist[v][mapa->vet_percurso[0]];

if (mapa->min_dist_total > dist_total) {
mapa->min_dist_total = dist_total;
memcpy(&mapa->min_vet_percurso, &mapa->vet_percurso,mapa->qtd_vertices * sizeof(int));
}

} else {
Forca_Bruta(mapa);
}
mapa->dist_total -= mapa->matdist[u][v];
}
}
danieldlmt

### Re: Parallelizing recursive function

The most convenient way to parallelise recursive algorithms in OpenMP is to use the task construct. The specification contains a couple of examples (Section A.15 in version 3.1) which should give you the basic idea. You will most likely need to think carefully about the data attribute scoping of variables, though!
MarkB

Posts: 746
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh