问题标签 [reduction]

我有一个代码来计算我使用 OpenMP 并行化的素数：

我正在尝试将它移植到 GPU，并且我想像上面的 OpenMP 示例一样减少计数。以下是我的代码，除了给出不正确的结果外，它的速度也较慢：

首先，我如何让这个内核快，我认为瓶颈是for循环，我不知道如何替换它。接下来，我的计数不正确。我确实更改了 '%' 运算符并注意到了一些好处。

在flags数组中，我标记了从 2 到 sqroot(N) 的素数，在这个内核中我正在计算从 sqroot(N) 到 N 的素数，但我需要检查 {sqroot(N),N} 中的每个数字是否可被 {2,sqroot(N)} 中的素数整除。该o_flags数组存储每个块的部分和。

编辑：按照建议，我修改了我的代码（我现在更好地理解了关于同步线程的评论）；我意识到我不需要标志数组，只需要全局索引就可以了。在这一点上，我担心的是代码的缓慢（不仅仅是正确性），这可能归因于 for 循环。此外，在特定数据大小（100000）之后，内核对后续数据大小产生了不正确的结果。即使对于小于 100000 的数据大小，GPU 缩减结果也不正确（NVidia 论坛的一位成员指出，这可能是因为我的数据大小不是 2 的幂）。所以还有三个（可能是相关的）问题——

1. 我怎样才能让这个内核更快？在我必须遍历每个 tid 的情况下使用共享内存是个好主意吗？

2. 为什么它只对某些数据大小产生正确的结果？

3. 我怎样才能修改减少？

   /li>

我们知道 3SAT ≤p 3COLOR（即 3SAT 是多项式时间可简化为 3COLOR）。谁能给出一个简短的论据，为什么 3COLOR ≤p 3SAT？并给出一个实际的库克减少表明 3COLOR ≤p 3SAT 请。

我正在尝试对内核中的数组进行求和，而无需将数据发送回 CPU 主机，但我没有得到正确的结果。这是我使用的总和内核（对 NVIDIA 提供的内核稍作修改）：

我错过了什么吗？谢谢！

我在尝试编写 CUDA 程序时遇到了困难。我有一个大约 524k 浮点值 (1.0) 的数组，我正在使用归约技术来添加所有值。如果我只想运行一次，问题就可以解决，但我真的想多次运行内核，以便最终汇总超过 10 亿个值。

我以 524k 为单位执行此操作的原因是，当我在 gpu 上超过大约 100 万时，我总是得到零。这不应该超过卡上的内存，但它总是在那个时候失败。

无论如何，当我只循环一次内核时，一切正常。也就是说，没有循环是好的。当我使用循环运行时，它会返回零。我怀疑我会在某个地方越界，但我无法弄清楚。它快把我逼疯了。

任何帮助表示赞赏，

谢谢，

铝

这是代码：

好的，我想我已经将问题范围缩小到设备上的 V_d。我怀疑我以某种方式超出了数组的范围。如果我分配 2 倍于我实际需要的内存量，程序将以预期的结果结束。问题是，我无法弄清楚是什么导致了这些问题。

铝

我正在尝试创建迭代过程的代码，同时将 while 保持在并行区域内以最小化并行化开销。

代码是这样 的问题是它永远不会退出，所以如果可能的话，我希望您对此有想法

这很难，所以所有的帮助真的很感激！

我知道它是 NP-Complete，因此无法在多项式时间内解决，但在分析中寻求帮助，它减少到什么类型的 NP-Complete 问题，它提醒你的类似问题等等。

故事如下。我拥有一家拥有n辆卡车的冰淇淋卡车业务。我有m个站点进行交货。每个位置m _i都有p _i个人在等我。买了冰淇淋后，每个人都离开了。随着越来越多的人排队购买冰淇淋，pi 会随着时间的推移而增加_。

我如何才能确定接下来将卡车送到哪里以便在任何一天最大化我的利润？

要记住的事情：

• 两辆卡车在同一时间停在同一地点只会获得一次利润，即人们在一辆卡车到达后离开
• 卡车需要时间从一个地点到达另一个地点
• p _i在每个站点随时间增加，但某些站点的增长速度比其他站点快，即某些位置靠近商场（位置、位置、位置）

我尝试将其简化为多机调度问题、旅行销售人员问题、ILP 等，但主要问题是每个位置的p _i（即 TSP 中的距离或调度问题中的作业长度）是不断增加。

提前致谢！

这是对我之前的问题（关于一个旧的顶级编码器之谜）的跟进。

给定一串数字，找到该字符串等于某个目标数字所需的最小加法数。每次添加都相当于在数字字符串的某处插入一个加号。插入所有加号后，照常计算总和。

例如，考虑“303”和目标总和为 6。最佳策略是“3+03”。

我猜（虽然没有证明）问题是NP完全的。你怎么看？你如何将一个众所周知的 NP 完全问题简化为这个问题？

这是我要转换为 openCL 的循环。

这就是我到目前为止所拥有的，虽然，我知道它是不正确的并且遗漏了一些东西。

我是这类事情的完全初学者。首先，我知道我不能将全局双指针传递给 openCL 内核。如果可以的话，请在发布解决方案之前等待几天左右，我想自己解决这个问题，但如果你能帮助我指出正确的方向，我将不胜感激。

我被 Wikipedia 对 lambda 演算中前任函数的描述所困扰。

维基百科说的是以下内容：

有人可以逐步解释减少过程吗？

谢谢。

我一直在经历一些例子，将一组元素减少为一个元素，但没有成功。有人在 NVIDIA 论坛上发布了这个。我已从浮点变量更改为整数。

这看起来对吗？第三个参数“大小”，应该是本地工作大小还是全局工作大小？

我这样设置我的论点，

第一个参数是输入，我试图保留在它之前启动的内核的输出。

今天我打算尝试将以下 cuda 缩减示例转换为 openCL。

有一个更优化的，（完全展开+每个线程多个元素）。

http://developer.download.nvidia.com/compute/cuda/1_1/Website/projects/reduction/doc/reduction.pdf

这可以使用openCL吗？

灰熊前几天给了我这个建议，

“...使用对 n 元素进行操作的缩减内核并将它们缩减为 n / 16（或任何其他数字）。然后您迭代地调用该内核，直到您缩减到一个元素，这就是您的结果”

我也想试试这个，但我不知道从哪里开始，我想先做点什么。