A flexible algorithm for calculating pair interactions on SIMD architectures
A flexible algorithm for calculating pair interactions on SIMD architectures
复制标题
DOI：
10.1016/j.cpc.2013.06.003
复制
发表时间：
2013-12-01
影响因子：
6.3
通讯作者：
Hess, Berk
中科院分区：
文献类型：
--
作者：
Pall, Szilard;Hess, Berk
计算粒子对之间的相互作用或相关性通常是粒子模拟或相关性分析中最耗时的任务。在粒子对上使用双循环的简单实现传统上工作得很好，特别是因为编译器通常会很好地展开内部循环。为了在现代CPU和加速器架构上达到高性能，单指令多数据（SIMD）并行化已经成为。具有本质意义避免内存瓶颈也越来越重要，需要降低内存与算术运算的比率。此外，当对仅在特定截止距离内交互时，仅通过重新排序输入和输出数据才能实现良好的SIMD利用率，这很快成为限制因素。在这里，我们提出了一个算法的SIMD并行化的基础上分组固定数量的粒子，例如2，4，或8，到空间集群。与传统方案相比，计算一对这样的集群中的粒子之间的所有相互作用提高了数据重用，并导致更有效的SIMD并行化。调整簇大小允许算法映射到各种宽度的SIMD单元。这种灵活性不仅可以在当前的CPU和加速器架构（如GPU或Intel MIC）上快速有效地实现，而且还可以使算法面向未来。我们提出的算法与应用分子动力学模拟，在那里我们也可以利用有效的缓冲方法介绍。(C)2013爱思唯尔有限公司版权所有。
Calculating interactions or correlations between pairs of particles is typically the most time-consuming task in particle simulation or correlation analysis. Straightforward implementations using a double loop over particle pairs have traditionally worked well, especially since compilers usually do a good job of unrolling the inner loop. In order to reach high performance on modern CPU and accelerator architectures, single-instruction multiple-data (SIMD) parallelization has become. essential. Avoiding memory bottlenecks is also increasingly important and requires reducing the ratio of memory to arithmetic operations. Moreover, when pairs only interact within a certain cut-off distance, good SIMD utilization can only be achieved by reordering input and output data, which quickly becomes a limiting factor. Here we present an algorithm for SIMD parallelization based on grouping a fixed number of particles, e.g. 2, 4, or 8, into spatial clusters. Calculating all interactions between particles in a pair of such clusters improves data reuse compared to the traditional scheme and results in a more efficient SIMD parallelization. Adjusting the cluster size allows the algorithm to map to SIMD units of various widths. This flexibility not only enables fast and efficient implementation on current CPUs and accelerator architectures like GPUs or Intel MIC, but it also makes the algorithm future-proof. We present the algorithm with an application to molecular dynamics simulations, where we can also make use of the effective buffering the method introduces. (C) 2013 Elsevier B.V. All rights reserved.