0

我正在研究一种算法，该算法必须在一定程度上独立地对大量小数组进行少量操作。

给出一个想法：

  • 对长度通常为 0.5k-1k 元素的数组进行 1k 次排序。
  • 1k 对 10-20 级矩阵的 LU 求解。

一切都在浮动。

然后，这个问题有一些横向性：上述操作必须在 10k 数组上独立进行。

此外，不需要存储中间结果：例如，我不需要保留已排序的数组，只需保留最小的 $m$ 元素的总和。

整个事情已经用c ++编程并运行了。我的问题是：您是否希望这样的问题能够通过 CUDA 获得显着的加速（因子 2 或更多）？

4

3 回答 3

1

如果您“仅”需要 2 倍的加速，我建议在考虑 GPGPU/CUDA 之前先查看更直接的优化可能性。例如，假设 x86 考虑使用 SSE 通过重写代码的性能关键部分以使用 4 路浮点 SIMD 来实现潜在的 4 倍加速。尽管这会将您绑定到 x86，但它会更便携，因为它不需要 nVidia GPU。

话虽如此，您的代码库中甚至可能有更简单的优化机会，例如消除冗余操作（无用的副本和初始化是最受欢迎的）或使您的内存访问模式对缓存更友好。尝试使用一个像样的分析器来分析你的代码，看看瓶颈在哪里。

但是请注意，通常排序不是特别适合 SIMD 或 CUDA，但其他操作（例如 LU 分解）可能会受益。

于 2012-07-18T11:10:41.297 回答
1

只需几个指针，您可能已经合并：

1）如果你只需要m个最小的元素，你最好只搜索最小的元素，删除它并重复m次。

2）您是否已经在 cpu 上并行化了代码？OpenMP 左右...

3）您是否考虑过购买更好的硬件？（我知道这不是一个好主意，但如果你想达到特定应用程序的性能目标，它有时是最便宜的可能性......）

如果你想在 CUDA 上做，它应该在概念上工作，所以不会出现大问题。但是，总有一些小事情，这取决于经验等。

考虑用于排序的推力库，希望其他人可以提出一些好的 LU 分解算法。

于 2012-07-18T12:51:09.510 回答
1

您可以在 5 行ArrayFire代码中运行它。我通过 CPU 获得了约 6 倍的加速。与 Thrust 相比，我得到了约 4 倍的加速（它是为向量设计的，而不是矩阵）。由于您只使用单个 GPU，因此您可以运行 ArrayFire 免费版。

array x = randu(512,1000,f32);
array y = sort(x); // sort each 512-element column independently
array x = randu(15,15,1000,f32), y;
gfor (array i, x.dim(2))
  y(span,span,i) = lu(x(span,span,i)); // LU-decomposition of each 15x15 matrix

请记住，当内存访问与 32 的倍数对齐时，GPU 性能最佳，因此一堆 32x32 矩阵的性能将优于一堆 31x31 矩阵。

于 2012-07-18T18:46:17.103 回答