ACM通信

研究突出了

技术视角:最佳算法+最佳计算机=强大的匹配

威廉·Gropp
ACM通信，2012年5月，第55卷第5期，第100页
10.1145/2160718.2160739
评论

假设你想要模拟一个星系中恒星随时间的运动，以了解星系是如何形成的，以及为什么宇宙在我们看来是这样的。这似乎是一个简单的计算问题——运动定律受牛顿定律支配(让我们忽略相对论)，只需要计算每颗恒星对其他恒星的作用力。为N星星,这是N²操作，对于数十亿颗恒星来说，这是十亿亿亿个操作。在单个处理器上可行吗?遗憾的是，即使是今天最快的单处理器和单时刻的时间，答案也是“不”。更糟糕的是，随着每颗恒星的运动，这种计算必须重复数百万或数十亿次。(如果你更喜欢生物或材料科学，把“星星”换成“原子”。)

那么并行是答案吗?不幸的是没有。即使是当今最大的系统也不能提供足够的处理能力来处理这些问题(超级计算机可能很快，但它们不是无限快)。

我们能做什么?

Lashuk等人的以下论文说明了这一方法。解决这样一个难题需要利用一切可能的办法。作者从算法开始。而明显的计算方式是相互作用的N物体之间的相互作用在物体数量上需要二次元的时间，有一个聪明的方法，具有严格的误差边界，可以在线性时间内计算这些相互作用的任何指定精度!这个算法是25年前由格林加德和洛克林开发的，利用了力的层次表示。但是，即使是单处理器上的线性时间算法也不够快，无法解决科学家们想要解决的问题。因此，选择了一个优秀的算法，作者继续并行化它。然而，算法的选择并不容易。由于算法使用了层次表示，因此涉及的数据结构很自然地是树，而由于物体的分布(无论是恒星还是原子)是不均匀的，树是不平衡的。这使得有效的并行化非常困难，因为高效并行化的主要障碍是有效的负载平衡。然后，本文在多个层次上处理并行，从分布式内存并行开始，然后继续讨论多核进程，最后讨论gpu。使用混合并行编程模型(特别是MPI与OpenMP和/或CUDA的结合)是一个非常实用的论点:对于实际应用程序来说，单一的编程模型并不总是最好的解决方案。

---

你为什么要读下面这篇论文?因为它清楚地描述了如何有效地将最好的算法与最好的计算机相结合，同时使用最合适的并行化策略，从而解决一个困难的问题。

---

你为什么要读下面这篇论文?因为它清楚地描述了如何有效地将最好的算法与最好的计算机相结合，同时使用最合适的并行化策略，从而解决一个困难的问题。通过这项工作，您将发现使用简单而有效的复杂性分析来指导和解释所做的选择。这是在最大的机器上使用最佳算法的最佳高性能计算;使用复杂性分析工程师一种高性能的解决方案，使用分层编程模型，每个模型为并行计算机的某一部分提供高性能。其结果是一种工具，科学家可以用它来解决其他任何方法都无法解决的问题，这是计算如何成为科学进步的关键的一个例子。

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2012 ACM, Inc.

---

没有发现记录