并行 Delaunay 三角剖分

Question

我正在尝试使用OpenMP并行化Guibas Stolfi Delaunay三角剖分算法。

这里有两个需要并行化的部分 - 其中一个是mergesort()，我已经完成了；另一个是divide()，但我目前卡在这一步。

在divide()中采用的分治策略与mergesort()相同，但是应用相同的并行化技术(omp sections)只适用于mergesort()。

我尝试了这里展示的并行化技术，但它也不起作用。 我在某个地方读到过嵌套并行处理(nested parallelism)，但我不确定如何实现它。 有人能解释一下如何并行化分治算法吗？

代码：在主函数中调用了两次mergesort，并应用了sections结构。对于divide函数做同样的事情就不起作用。

#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);
}
}
}

- haxor

---

请找到完整的代码：http://pastebin.com/4nxbAts7 - haxor

Answer 1

我在Windows中使用CreateThread调用成功地进行了并行化，诀窍是将点分成2^n个缓冲区，在单独的线程中处理每个缓冲区，然后连续合并相邻的边，直到最后一次合并。

我有一个演示程序来创建随机数据并三角剖分和显示结果（对于较小的情况）。看起来这个网站不允许我下载程序和显示工具的.zip文件。如果您可以建议一个上传网站或提供电子邮件，我会把它发送给您。

- Handy

---

请发送邮件至 getanshub4u[AT]gmail[dot]com。 - haxor