c++ - 网格三角形上的复杂 OpenMP 并行化

Question

所以我有一个网格，我需要为每个三角形计算一些信息 -- computeInfo(triangle)。在我的顺序版本中，我只是使用迭代器遍历整个网格。

为了争取一些时间，我正在尝试将这部分与 OpenMP 并行化。诀窍是 computeInfo(T) 访问和修改围绕三角形 T 的一些三角形。

我的想法如下:首先计算网格的边界框。然后创建一个足够的 3D 网格(单元格足够大，因此 computeInfo(T) 不会导致任何问题)并将每个三角形分配给相应的网格单元格。

然后每个线程处理一个单元格中的所有三角形，其坐标可以表示为 (2*i, 2*j, 2*k) :这确保不会由于另一个线程而出现修改.我们等待所有对应的单元格都处理完，然后我们处理(2*i+1, 2*j, 2*k), (2*i, 2*j+1 , 2*k)，依此类推，直到我们处理了 (2*i+1, 2*j+1, 2*k+1)。

显然，我的并行代码几乎没有顺序代码快(我做的最好的是快 2 倍，使用 8 个线程...)。我认为这是由于我用于存储网格的结构、要处理的方面等等。

这是我的代码的简化版本:

vector<set<Index> > vsGrid(nX*nY*nZ); // vector that contains each "cells"
                                      // a cell is a set of the facet index
                                      // it contains
                                      // nX, nY, nZ = size of the grid
vector<vector<set<Index> > > vvsGrid(iNbOfThreads);
// one vector for each thread

#pragma omp parallel for
for(int i = 0; i < iNbOfThreads; ++i)
{
    vector<set<Index> > vsGrid(nX*nY*nZ);
    vvsGrid[i] = vsGrid;
}

#pragma omp parallel
{
    const int iThrdId = omp_get_thread_num();
    // each thread process a part of the total triangles (called facet)
    for(PlaneFinderAPI::Polyhedron::Facet_iterator f = vFStart[iThrdId]; f != vFEnd[iThrdId]; ++f)
    {
        Point_3d p = barycenterOf(f);
        int X = int((p.x() - minX)/(12*meanEdgeSize));
        int Y = int((p.y() - minY)/(12*meanEdgeSize));
        int Z = int((p.z() - minZ)/(12*meanEdgeSize));

        vvsGrid[iThrdId][X+nX*Y+nX*nY*Z].insert(f->index());
    }

    #pragma omp barrier

    for(int col = iThrdId; col < nX*nY*nZ; col+=iNbOfThreads)
    {
        for(int j = 0; j < iNbOfThreads; ++j)
        {
            // we merge the cells of all the threads
            vsGrid[col].insert(vvsGrid[j][col].begin(), vvsGrid[j][col].end());
        }
    }
}

for(int i = 0; i < vvCellToProcess.size(); ++i)
{
    #pragma omp parallel for
    for(int j = 0; j < vvCellToProcess[i].size(); ++j)
    // vvCellToProcess contains the cells to process, first vector contains all
    // the cells (2*i, 2*j, 2*k) and so on
    {
        const int iCellToProcess =  vvCellToProcess[i][j];
        for(set<Index>::iterator it = vsGrid[iCellToProcess].begin(); it != vsGrid[iCellToProcess].end(); ++it)
        {
            PlaneFinderAPI::Polyhedron::Facet_iterator f = facetMap.at(*it);
            computeInfo(f);
        }
    }
}

我认为主要问题在于过度使用集合 vector 的 vector 。我认为内存没有得到有效分配，这就是它速度慢的原因。那么我应该使用什么结构呢？有没有更有效的方法来解决我的问题？

序列号:

for (PlaneFinderAPI::Polyhedron::Facet_iterator f = P.facets_begin() ; f != P.facets_end() ; ++f)
{   
    computeInfo(f);
}

computeInfo 使用网格的标准半边数据结构查看 f 周围的顶点。为了避免多次查看同一个顶点，每个顶点都关联到一个 bool 值 visited。这就是为什么我不能简单地并行化 for 循环，因为在读取/写入 visited bool 值时会出现问题。

技术信息:我正在使用 Windows 7 和 Visual Studio 2010，i7 960 @ 3.20GHz，8 线程和 12GB 内存。

Answer 1

我建议您先对代码进行基准测试，然后再猜测什么是慢的，什么是快的。另外，根据 Index 是什么，每次分配和读取 vector 时，您可能都会有一份昂贵的拷贝。您可以尝试存储 Index 的指针。

例如这一行:

vvsGrid[i] = vsGrid;

将为 vector 中的每个集合创建多个索引的拷贝，然后将每个集合的拷贝和那些集合中的每个索引复制到新 vector 中。