文章/答案/技术大牛

发布

社区首页 >问答首页 >如何使用CUDA实现2-for粒子相互作用循环，由此产生的复杂性是什么？

问如何使用CUDA实现2-for粒子相互作用循环，由此产生的复杂性是什么？
EN

Stack Overflow用户

提问于 2014-03-14 01:31:04

回答 1查看 148关注 0票数 1

该算法接收粒子的世界(列表)(三维向量)，并调用它们之间的交互函数.或者，在伪码中：

function tick(world)
     for i in range(world)
        for j in range(world)
            world[i] = interact(world[i], world[j])

其中，interact是一个函数，它接受两个粒子并返回另一个粒子，并且可以是任何东西，例如：

 function interact(a,b) = (a + b)*0.5

您可以很容易地确定这个算法在CPU上是O(N^2)。在我学习CUDA的尝试中，我不确定如何在GPU上实现这一点。这种算法的一般结构是什么，由此产生的复杂性是什么？如果我们知道如果2个粒子足够远的话，interact函数什么也不做呢？我们可以优化它的地方吗？

parallel-processing

gpu

c++

algorithm

cuda

回答 1

Stack Overflow用户

回答已采纳

发布于 2014-03-14 02:11:36

这种算法的一般结构是什么，由此产生的复杂性是什么？

这本质上是n体问题。用直接粒子-粒子方法求解。已经写了很多了。该算法在GPU上的顺序是O(N^2)，就像在CPU上一样。

在CUDA中实现的核心算法除了利用本地块内存并对其进行优化外，变化不大。从本质上说，实现仍然是对两个循环的实现。

下面的文章是一个很好的起点，第31章。基于CUDA的N体快速仿真。

我们能为局部性优化它吗？

是。许多n体算法试图优化局部性，因为引力和E力随着粒子之间距离的幂而减小，因此可以忽略它们的贡献或近似它们的贡献。这些近似方法中的哪一种在很大程度上取决于您试图模拟的系统类型。

下面是一些比较流行的方法，研讨会专题介绍，N体算法的一个很好的概述

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/22394466

复制

相似问题

问如何使用CUDA实现2-for粒子相互作用循环，由此产生的复杂性是什么？
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何使用CUDA实现2-for粒子相互作用循环，由此产生的复杂性是什么？EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何使用CUDA实现2-for粒子相互作用循环，由此产生的复杂性是什么？
EN