Mic*_*per 5 c++ performance caching hpc fluid-dynamics
我想知道有效存储(以及随后访问)具有可变长度的多维数据数组的最佳实践.重点是性能,但我还需要能够在运行时更改单个数据集的长度,而不会产生太多开销.
注意:我知道这是一个有点冗长的问题,但是我已经看了很多,并且找不到解决方案或示例来描述手头的问题并且具有足够的准确性.
背景
上下文是基于不连续Galerkin谱元素方法(DGSEM)的计算流体动力学(CFD)代码(参见Kopriva(2009),Workinging Spectral Methods for Partial Differential Equations).为简单起见,让我们假设一个2D数据布局(实际上它是三维的,但从2D到3D的扩展应该是直截了当的).
我有一个由K方形元素k(k = 0,...,K-1)组成的网格,可以是不同的(物理)大小.在每个网格元素(或"单元格")中k,我有N_k^2数据点.N_k是每个维度中的数据点的数量,并且可以在不同的网格单元之间变化.
在每个数据点n_k,i(其中i = 0,...,N_k^2-1)我必须存储一个解决方案值数组,它nVars在整个域中(即在任何地方)具有相同的长度,并且在运行时期间不会更改.
尺寸和变化
栅格单元的数量K是O(10^5)对O(10^6)与能够在运行期间改变.
数据点的数量N_k在每个网格单元之间2并8与可以在运行时期间改变(并且可以是用于每个小区不同的).
变量的数目nVars存储在每个网格点是左右5到10并不能在运行时期间改变(它也是对于每个网格单元是相同的).
要求
性能是这里的关键问题.我需要能够以有效的方式在所有单元的所有网格点上以有序的方式定期迭代(即,没有太多的高速缓存未命中).通常,K并且N_k在模拟期间不经常改变,因此例如可以选择用于所有单元和数据点的大的连续存储器块.
但是,我确实需要能够在运行时精炼或粗化网格(即删除单元格并创建新单元格,新的单元格可以附加到结尾).我还需要能够更改近似顺序N_k,因此我为每个单元格存储的数据点数量也可以在运行时更改.
结论
任何输入都表示赞赏.如果您有自己的经验,或者只是了解一些我可以看到的好资源,请告诉我.然而,虽然解决方案对最终程序的性能至关重要,但它只是众多问题中的一个,因此解决方案需要具有应用性,而不是纯粹的学术性.
如果这是一个提出这个问题的错误场所,请告诉我一个更合适的地方.
通常，这些类型的动态网格结构很难有效处理，但在块结构自适应网格细化代码（在天体物理学中常见，其中复杂的几何形状并不重要）或具有大块大小的光谱元素代码中，这通常不是一个问题。每个块/元素都有很多工作要做（在您的情况下至少有 10^5 个单元 x 2 个点/单元），因此块之间切换的成本相对较小。
还要记住，在每个元素或块的大量数据已经在缓存中之前，您通常不能对每个元素或块执行太多的艰苦工作。无论如何，在对块 N+1 进行大量工作之前，您已经必须将块 N 的大部分数据从缓存中刷新出来。（您的代码中可能有一些操作是例外，但这些操作可能不是您花费大量时间的操作，无论是否有缓存，因为没有大量数据重用 - 例如，单元格值）。因此，将每个块/元素保持在彼此旁边并不一定是一件大事；另一方面，您肯定希望块/元素本身是连续的。
另请注意，您可以在调整大小时移动块以保持它们连续，但不仅所有这些内存副本也会擦除您的缓存，而且内存副本本身会变得非常昂贵。如果您的问题是填充很大一部分内存（我们不是总是这样吗？），例如 1GB，并且您必须在优化后移动 20% 以使内存再次连续，那就是 0.2GB（读 + 写） ) / ~20 GB/s ~ 20 ms 相比之下，以 ~100ns 每个 ~ 1.5 ms 的速度重新加载（例如）16k 缓存行。无论如何，您的缓存在洗牌后就会被丢弃。如果您知道您很少进行细化/去定义，那么这可能仍然值得做。
但实际上，天体物理流体动力学中的大多数自适应网格代码（我很了解这些代码）只是维护块及其元数据的列表，而不用担心它们的连续性。当然是YMMV。我的建议是——在花费太多时间构建完美的数据结构之前——首先测试两个元素的操作，两次；第一个，按顺序排列元素并对它们进行 1-2 计算，第二个，以“错误”的顺序 2-1 进行操作，并对这两个计算进行多次计时。