Parallel Delaunay Triangulation

Question

Ich versuche, die Guibas Stolfi delaunay triangulation mit openmp zu parallelisieren.

Es gibt zwei Dinge parallelisieren hier- die mergesort(), die ich habe und die divide() wo ich stecken bin. Ich habe alle möglichen Ansätze aber vergebens ausprobiert.

Der Ansatz folgt (divide n conquer) in divide() ist der gleiche wie der von mergesort(), aber die Anwendung der gleichen Parallelisierungstechnik (omp-Abschnitte) funktioniert nur für Mergesort.

Ich habe versucht, die parallelization technique shown here, aber auch das funktioniert nicht. Ich habe irgendwo etwas über verschachtelte Parallelität gelesen, aber ich bin mir nicht sicher, wie ich es implementieren soll. Kann jemand erklären, wie Divide and Conquer-Algorithmen parallelisiert werden?

Code: Genannt mergesort zweimal in Hauptfunktion und angewandte Abschnitte construct.Doing gleiche für Teilungsfunktion nicht

#pragma omp parallel 
{ 
#pragma omp sections nowait 
{ 
#pragma omp section 
{ 
merge_sort(p_sorted, p_temp, 0, n/2); 
} 
#pragma omp section 
{ 
merge_sort(p_sorted, p_temp, (n/2)+1, n-1); 
} 
} 
} 

Answer 1

ich mit erfolgreich war den Createthread in Parallelisierung funktioniert ruft in Windows, der Trick ist, um die Punkte in 2^n Puffer zu unterteilen, verarbeite jeden Puffer in einem separaten Thread und füge anschließend angrenzende Kanten sukzessive zusammen, bis eine endgültige Zusammenführung erfolgt.

Ich habe ein Demonstrationsprogramm, um Zufallsdaten zu erstellen und zu triangulieren und die Ergebnisse anzuzeigen (für kleinere Fälle). Es sieht nicht so aus, als ob diese Seite mir erlaubt, die .zip-Datei des Programm- und Anzeige-Tools herunterzuladen. Wenn Sie eine Upload-Website vorschlagen oder eine E-Mail senden können, sende ich diese Ihnen zu.