5

我想知道有效存储（并随后访问）具有可变长度的多维数据数组集的最佳实践。重点是性能，但我还需要能够在运行时处理更改单个数据集的长度，而不会产生太多开销。

注意：我知道这是一个有点冗长的问题，但我已经环顾四周，找不到足够准确地描述手头问题的解决方案或示例。

背景

上下文是基于不连续 Galerkin 谱元法 (DGSEM) 的计算流体动力学 (CFD) 代码（参见 Kopriva (2009)，实现偏微分方程的谱方法）。为简单起见，让我们假设一个 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_k28
nVars510

要求

性能是这里的关键问题。我需要能够以一种有效的方式以有序的方式定期迭代所有单元格的所有网格点（即没有太多的缓存未命中）。通常，K并且N_k在模拟过程中不会经常更改，因此例如可以选择用于所有单元和数据点的大型连续内存块。

但是，我确实需要能够在运行时细化或粗化网格（即删除单元格并创建新单元格，新单元格可能会附加到末尾）。我还需要能够更改近似顺序N_k，因此我为每个单元存储的数据点数量也可以在运行时更改。

结论

任何输入表示赞赏。如果您有自己的经验，或者只是知道一些我可以查看的好资源，请告诉我。然而，虽然解决方案对最终程序的性能至关重要，但这只是众多问题之一，因此解决方案需要具有应用性，而不是纯粹的学术性。

如果这是问这个问题的错误地点，请告诉我更合适的地点。

4

2 回答 2

3

通常，这些类型的动态网格结构很难有效处理，但在块结构自适应网格细化代码（在天体物理学中很常见，其中复杂的几何形状并不重要）或具有大块大小的光谱元素代码中，这通常不是一个问题。每个块/元素都有很多工作要做（在您的情况下至少有 10^5 个单元 x 2 个点/单元），因此在块之间切换的成本相对较小。

还要记住，在每个元素或块的大量数据已经在缓存中之前，您通常不能对每个元素或块做太多的努力。无论如何，在对块 N+1 完成大量工作之前，您已经必须将块 N 的大部分数据从缓存中清除。（您的代码中可能有一些操作是例外的，但这些操作可能不是您花费大量时间的操作，缓存或不缓存，因为没有很多数据重用 - 例如，元素操作单元格值）。因此，将每个块/元素放在一起并不一定是一件大事；另一方面，您肯定希望块/元素本身是连续的。

另请注意，您可以移动块以使它们在调整大小时保持连续，但不仅所有这些内存副本也会擦除您的缓存，而且内存副本本身也会变得非常昂贵。如果您的问题是填充了很大一部分内存（我们不总是这样吗？），比如说 1GB，并且您必须在改进后移动 20% 的内存以使事情再次连续，那就是 0.2 GB（读取 + 写入) / ~20 GB/s ~ 20 ms 与以 ~100ns 每个 ~ 1.5 ms 重新加载（例如）16k 缓存线相比。无论如何，您的缓存在洗牌后都会被丢弃。如果您知道您将很少进行细化/取消细化，这可能仍然值得做。

但实际上，天体物理流体动力学中的大多数自适应网格代码（我对代码非常了解）只是维护一个块列表及其元数据，而不用担心它们的连续性。当然是 YMMV。我的建议是——在花太多时间制作完美的数据结构之前——首先测试两个元素的操作，两次；第一个，按顺序排列元素并计算它们 1-2，第二个，以“错误”的顺序执行操作，2-1，并多次计时两次计算。

于 2012-07-10T14:57:55.350 回答
1

对于每个单元格，将要在其中查找单元格数据的偏移量存储在一个连续数组中。这种偏移映射非常有效并且被广泛使用。您可以重新排序单元格以在遍历中重用缓存。当单元格的顺序或数量发生变化时，创建一个新数组并进行插值，然后丢弃旧数组。这种存储对于外部分析要好得多，因为可以在不参考网格的情况下管理 Krylov 方法中的内积和 Runge-Kutta 方法中的阶段等操作。它还需要每个向量的最小内存（例如，在 Krylov 基础和时间积分中）。

于 2012-08-26T04:18:10.833 回答