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

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

Return to Using OpenMP

Who is online

Users browsing this forum: Google [Bot] and 2 guests