1

我必须编写 Levenshtein 距离问题的优化多线程实现。它可以使用带有矩阵的动态规划来计算，Levenshtein distance 上的维基百科页面已经足够好。

现在，我可以同时计算对角线元素。没关系。

我的问题现在与缓存有关。c++ 中的矩阵通常逐行保存在内存中，对吗？好吧，这对我不利，因为我需要前一行的 2 个元素和当前行的 1 个元素来计算我的结果，这在缓存方面太可怕了。缓存将保存当前行（或其中的一部分），然后我要求它可能不再保存前一个。然后对于另一个，我需要对角线的不同部分，所以再一次，我要求完全不同的行，缓存不会为我准备好那些。

因此，我想将我的矩阵以块或对角线的形式保存到内存中。这将导致更少的缓存未命中，并使我的实现再次更快。

你是怎样做的？我尝试在互联网上搜索，但我找不到任何能告诉我方向的东西。是否可以告诉 c++ 如何在内存中订购该类型？

编辑：你们中的一些人似乎对我的问题的性质感到困惑。我想以自定义方式将矩阵（无论我将其设为 2D 数组还是任何其他方式）保存到 MEMORY 中。通常，二维数组将逐行保存，我需要使用对角线，因此缓存会在我将处理的巨大矩阵（可能数百万行和列）上丢失很多。

4

3 回答 3

4

我相信您可能对（CPU）缓存有误解。

确实，CPU 缓存是线性的——也就是说，如果你访问内存中的一个地址，它会将一些先前的和一些后续的内存位置带入缓存——这就像“猜测”后续访问将涉及一维关闭元素. 然而，在微观层面上确实如此。CPU 的高速缓存由大量的小“行”组成（在最新的 Intel CPU 中，所有高速缓存级别均为 64 字节）。地方仅限于线路；不同的缓存行可以来自内存中完全不同的位置。

因此，如果您的矩阵“需要前一行的两个元素和当前行的一个元素”，那么缓存应该非常适合您：一些缓存将保存前一行的元素，而另一些将保存当前行的元素。而当您前进到下一个元素时，整个缓存通常会包含您需要访问的矩阵元素。只需确保您的迭代顺序与缓存行中的进展顺序一致。

此外，在某些情况下，由于从主内存到缓存的映射，您可能会遇到不同线程正在颠簸相同的缓存行的情况。在不深入细节的情况下，这是您需要考虑的事情（但同样，与 2D 与 1D 数据无关）。

编辑：正如 geza 所指出的，如果您的矩阵行很长，您仍将使用简单的方法读取每个内存位置两次：一次作为当前行，然后再次作为上一行，因为每个值都将被逐出用作上一行值之前的缓存。如果您想避免这种情况，您可以遍历矩阵的图块，其大小（长度 x 宽度 x sizeof(element)）适合 L1 缓存（以及其他需要存在的内容）。您也可以考虑将数据存储在图块中，但我认为这不会太有用。

于 2019-03-27T13:00:59.480 回答
0

我不是很确定，但我认为一个矩阵一个接一个地存储为一个长数组，并用指针算术映射到一个矩阵，所以你总是引用相同的地址并计算你的内存中的距离值位于

否则，您可以轻松地将其实现为这种类型并为您的矩阵实现 operator[int, int]

于 2019-03-27T12:22:26.410 回答
0

初步评论：“Levenshtein distance”是编辑距离（在通用定义下）。这是一个非常普遍的问题；您可能甚至不需要自己编写解决方案。查找现有代码。

现在，最后，为了一个正确的答案......你实际上根本不需要一个矩阵，你当然不需要“保存”它：只保留动态编程矩阵的“前面”就足够了而不是整个事情。

但是你会选择什么“战线”，如何推进呢？我建议你使用反对角线作为你的正面，并给定每个反对角线，同时计算下一个反对角线。因此它将是 {(0,0)}，然后是 {(0,1),(1,0)}，然后是 {(0,2),(1,1),(2,0)} 等等上。每个对角线最多需要两个较早的对角线——如果我们将每个对角线的值连续保存在内存中，那么沿着下一个对角线向上的访问模式就是沿着前面的对角线的线性进展——这对缓存非常有用（请参阅我的其他答案）。

因此，您将“并发”计算，为每个线程提供一堆连续的对角线元素来计算；这应该够了吧。并且在任何时候，您只会在内存中保留 3 个对角线：您正在处理的一个和之前的两个。您可以在三个这样的缓冲区之间循环，这样您就不会一直重新分配内存（但请确保预先分配具有最大对角线长度的缓冲区）。

对于非方形情况，整个事情应该基本相同。

于 2019-03-27T20:17:49.303 回答