Parallelizing recursive function

General OpenMP discussion

Parallelizing recursive function

Postby danieldlmt » Thu Dec 13, 2012 8:07 pm

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

Postby MarkB » Fri Dec 14, 2012 4:43 am

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


Return to Using OpenMP

Who is online

Users browsing this forum: No registered users and 10 guests