5

我正在创建一个需要超快的程序。它使用 CUDA 在 GPU 上运行一些东西，然后在 CPU 上进行一些计算。为此，我需要将高度优化的 GPU 数据结构转换为我可以在 CPU 上轻松使用的东西。我的数据基本上是一个以网格布局的图表。目前我正在使用 std::vector 作为 CPU 部分。因为我知道如果我做很多 s 会有相当大的开销，push_back()而且我至少知道因为我知道我的图中有多少个顶点，所以我现在为此使用以下代码：

new_graph.resize(blockSize * blockSize);
for (unsigned long long y = 0; y < blockSize; y++) {
    for (unsigned long long x = 0; x < blockSize; x++) {
        int idx = y * blockSize + x;
        new_graph[idx] = Vertex(x, y);
    }
}

之后我添加边缘。不幸的是，我不知道每个顶点有多少条边，但我知道它永远不会大于 8。因此，我reserve()在每个用于边的 std::vector 中都有 8 个。

但是，这两者似乎都非常缓慢。如果我对图形本身使用普通数组（所以基本上替换了外部 std::vector），那部分的速度提升是巨大的（比如 10 倍左右）。

对于图形这是可行的，但对于边缘不是真的，因为我在这些边缘上做了一些后处​​理，为此我真的需要像 std::vector 这样有点动态的东西（我添加了一些边缘）。

目前将数据转换为 std::vector 的速度比在 GPU 上运行我的算法（这是一种智能 MST 算法）慢 10 倍。这不是我真正想要的，因为现在开销太大了。

有人知道发生了什么或我该如何解决这个问题？

ps 我用-O2 编译，因为我已经发现这会产生很大的不同。也尝试使用-O3，没有真正的区别。

顶点定义如下：

struct Pos {
    int x, y;
    Pos() {
        x = 0;
        y = 0;
    }

    Pos(int x, int y) {
        this->x = x;
        this->y = y;
    }
};

struct Vertex {
    Pos pos;
    bool hidden;
    unsigned long long newIdx;
    Vertex() {
        this->pos = Pos();
        this->hidden = false;
        this->numEdges = 0;
        this->numRemovedEdges = 0;
    }

    Vertex(Pos &pos) {
        this->pos = pos;
        this->hidden = false;
        this->numEdges = 0;
        this->numRemovedEdges = 0;
    }

    Vertex(int x, int y) {
        this->pos = Pos(x, y);
        this->hidden = false;
        this->numEdges = 0;
        this->numRemovedEdges = 0;
    }
    int numEdges;
    int numRemovedEdges;
    std::vector<Edge> edges;
    std::vector<bool> removed;
    std::vector<bool> doNotWrite;
};
4

4 回答 4

3

也许您正在vector为为其元素保留空间的动态内存分配付费？

即使您reserve处于最佳状态，您也将至少为每个分配 3 个内存Vertex（一个 for edges，一个 forremoved和一个 for doNotWrite）。相对于您在此处尝试执行的高性能工作，动态内存分配可能很昂贵。

要么使用保证足够大的普通旧数组（可能会浪费空间），要么使用专门的内存分配器以及vector根据您的特定需求量身定制的 .

另外，您是否按内存顺序访问元素？您的示例似乎表明了这一点，但是您是否在所有情况下都这样做？

另外，你还需要Vertex.pos吗？不能从' 在网格中的位置推断出来吗？Vertex

于 2012-04-04T17:21:55.170 回答
1

我最近在类似情况下使用了另一种解决方案。在 llvm 包中有 SmallVector 类。它提供了与 std::vector 非常相似的接口，但它允许保持一些固定数量的元素内联（因此，除非向量增长超过初始限制，否则不会发生额外的内存分配）。如果 SmallVector 试图增长到超过该初始大小，则分配内存块，并将所有项目移到那里 - 所有这些都在一个透明的步骤中完成。

我必须在这个 SmallVector 中修复的几件事：

  1. 可以就地放置的最小项目数是 2，因此当在 99.99% 的情况下使用 1 个项目时，会有相当大的开销
  2. 通常使用 swap() 来释放内存（ SmallVector().swap(vec) ）不会释放内存，所以我必须自己实现它

只需查找最新版本的 llvm 即可获取 SmallVector 类的源代码

于 2012-04-04T20:39:46.990 回答
1

由于动态内存分配的数量、不必要的分配操作以及每个 Vertex 的整体大小，CPU 数据结构的效率极低。在考虑优化此结构之前，最好了解 CPU 数据结构和 GPU 数据结构之间的数据流，因为这两种格式之间的转换可能需要很长时间。这就引出了一个问题，为什么 CPU 端不使用 GPU 结构？

如果您只是从 CPU 端来看这个并且想要维护 AoS 数据结构，那么 1. 简化 Vertex 数据结构。2.删除所有动态内存分配。每个 std::vector 将执行 dynb 3. 将已删除和 doNotWrite 替换为 std::bitset<8>。4. 删除 numRemoveEdges。这是删除的.count()。5. 如果 Edge 很小，那么您可能会发现声明 Edge 边[8] 会更快。6. 如果您决定继续使用向量，请考虑使用池分配器。7.按大小对Vertex中的数据元素重新排序，以减小Vertex的大小。

所有这些建议很可能不是与 GPU 共享数据的最佳解决方案。如果您确实使用池分配器并使用 UVA (CUDA Linux)，您可以使用单个内存副本简单地将数据复制到 GPU。

于 2012-04-05T03:17:51.657 回答
0

您不能创建一个 Vertex 对象，将 x 和 y 值存储到其中（这样您就不必为每个循环调用构造函数），然后将整个 Vertex 存储到您的 std::vector 中吗？向量的内存保证像常规数组一样布局，因此您可以绕过所有抽象并直接操作内存。不需要复杂的东西。此外，也许您可​​以对从 GPU 返回的数据进行布局，以便您可以一次 memcpy 整个块，从而为您节省更多。

于 2012-04-04T16:09:31.877 回答