## 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 qtd_visitados;
int vet_percurso[MAX_VERTICES];
char vet_pegadas[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++) {
if (mapa->vet_pegadas[v] != NAO_VISITADO) continue;

mapa->vet_pegadas[v] = VISITADO;
mapa->vet_percurso[mapa->qtd_visitados] = 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 {
mapa->qtd_visitados++;
Forca_Bruta(mapa);
mapa->qtd_visitados--;
}
mapa->dist_total -= mapa->matdist[u][v];
mapa->vet_pegadas[v] = NAO_VISITADO;
}
}
danieldlmt

Posts: 1
Joined: Thu Dec 13, 2012 6:22 am

### 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: 557
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Return to Using OpenMP

### Who is online

Users browsing this forum: Exabot [Bot], Yahoo [Bot] and 11 guests