缓存不经意算法

当我在6.854(高级算法)第一次听说缓存无关算法时，它对我来说似乎是不可思议的。想象利用有关页面大小$B$和高速缓存大小$M$的信息来创建高效数据结构的算法相对简单。但是，缓存无关算法是在不知道$B$或$M$的情况下实现类似效率的算法。这意味着相同的缓存无关算法可以在具有不同缓存或页面大小的计算机上运行，并且仍然可以获得与为特定缓存量身定做的算法相同的渐近效率。其中许多算法的关键是递归的、类似分形的想法。我将描述一个在整数列表中进行搜索的缓存无关算法。

这是设置好的。(底部的TLDR)程序在处理器上执行，但输入数据驻留在磁盘上。我们可以认为磁盘是一个非常长的线性数据阵列，但是访问它的成本非常高。因此，我们发明了高速缓存的概念-$M$位的内存层要小得多，但读/写速度要快得多。出于性能原因，我们将磁盘和高速缓存划分为$B$位的块，称为页，并且我们将在高速缓存和磁盘之间一次一页地传输数据。

此高速缓存位于处理器和磁盘之间，处理器永远不会直接读取或写入磁盘。当处理器想要读取不在高速缓存上的一段数据时(这称为高速缓存未命中)，它将触发某种机制，该机制首先将相关页面从磁盘复制到高速缓存，如果高速缓存已满，则逐出另一个页面，然后从高速缓存读取。

这会有什么帮助呢？很简单，如果程序需要的整个数据集都可以放在高速缓存中，那么可以想象，处理器可以从高速缓存中取出所有数据，并支付一次性成本，然后对于程序的其余部分，处理器将永远不需要支付从磁盘读取的昂贵成本。当然，大多数程序需要更多的数据，因此我们希望设计能够最小化缓存未命中的算法。

然而，计算机的设置方式限制了我们实现这一目标所需的工具。在处理器上执行的程序对高速缓存没有显式控制。相反，从概念上讲，程序继续向磁盘发送读写请求，就好像没有缓存一样。处理器截取这些请求，并执行必要的缓存操作来服务信息。换句话说，缓存对程序是透明的。因此，减少高速缓存未命中的任务分解为两个正交的组成部分：通过巧妙地排序或指定存储器访问来编写高效算法，以及高效的高速缓存管理。

例如，一种有效的算法可能会尝试打乱存储器访问，以便将对特定存储器地址的存储器访问聚集在一起，从而增加缓存命中的可能性。事实上，由于分页系统的存在，如果将对同一空间区域的内存访问聚集在一起会有双重帮助，因为它们有可能在同一个页面上。

另一方面，高效的高速缓存管理需要尝试预测在发生高速缓存未命中并且我们想要将更多数据加载到已经满的高速缓存中时从高速缓存中逐出哪些数据。由于本文关注的是算法，因此我们假设缓存管理器具有神奇的Oracle功能，使其能够以最佳方式丢弃缓存，因此从算法设计的角度来看，如果存在实现我们所需性能的缓存加载/写入序列，我们假设缓存管理器会这样做。事实证明，这并不是不合理的，因为简单的技术，如最近最少使用的算法，工作得非常好。(关于这一点的阐述值得一篇单独的文章。)。

算法在处理器上运行。当需要数据时，如果存在高速缓存未命中，则处理器透明地将所需页面加载到高速缓存中，或者如果没有高速缓存未命中，则为高速缓存数据提供服务

有需要显式了解$B$和$M$的高效算法，也有同样高效的缓存模糊算法，但有些算法却不是这样。也就是说，无论$B$和$M$的实际大小是多少，算法执行相同的操作和请求相同的内存访问序列都是有效的。我们将在这里仔细研究一下后者。

比方说，我们要扫描$N$整数列表，以执行某项任务，比方说找到最大值。如果列表占用磁盘上连续的内存块，则可以通过一次加载一个页面，并在加载下一个页面之前扫描整个页面来高效地实现这一点。因此，这需要$O(N/B)$磁盘访问，显然是最优的。

假设算法不知道$B$。它可以通过简单地按顺序读取列表的元素来实现相同的效率。然后，CPU会将包含元素$0$到$B-1$的第一页取到缓存中，并将其传递给程序，然后当程序需要元素$B$时，它将读入包含元素$B$到$2B-1$的下一页，这可能会覆盖前一页。这将一直持续到读取完所有$N/B$页面。这是缓存无关的，因为无论$B$是什么，顺序读取元素的算法都是相同的。

请注意，在本例中，列表必须存储在连续的内存块中。如果元素像链表一样分散在各处，那么每次访问都可能触发缓存未命中，因为不能保证相邻元素会在同一页上。这可能看起来很明显，但这是我们编写高效算法的主要机制-提出高效的数据布局。

现在，让我们考虑一下在列表中搜索整数的问题。我们将研究三种实现此目的的方法。

让我们假设数据以列表的形式进行排序，并连续打包到磁盘上。一种可能的算法是执行二进制搜索，这通常需要$O(\logN)$读取。可以将对分搜索看作是连续地缩小查询值可以驻留的间隔。然而，一旦二分搜索正在缩小的间隔是$O(B)$，则整个间隔可以驻留在页面中，并且不需要进一步的页面访问。因此，我们只需要$O(\log N-\log B)$页面访问。请注意，这是一个与缓存无关的算法，因为该算法不知道$B$是什么-对于该算法，它只是运行标准的二进制搜索。

假设我们提前知道$B$。我们可以实现$O(\log_B N)$页面访问。我们以B-树(一种广义的BST)的格式排列列表。与BST类似，当按值排序时，B-树的每个子树对应于列表元素的一个连续子集。然而，树的每个节点$V$包含的不是一个元素，而是$B$元素，这将对应于以节点$V$为根的子树的间隔拆分为$B+1$间隔，而不是2个间隔。然后，我们可以沿着BST向下遍历，每向下一个级别，我们就将间隔减少$B$。因此，这只需要$O(\log_B N)=O(\log N/\log B)$页面访问。当然，在现实中，我们必须在每个节点中存储指针和可能的其他元数据，因此我们不能在每个节点中恰好有$B$元素，但我们绝对可以按$\theta(B)$每个级别进行拆分。

现在我们来看令人兴奋的部分。我们声称我们可以实现$O(\log_B N)$页面访问，但不需要提前知道$B$。我们使用的数据结构是一种很好的老式平衡二叉搜索树。但是，我们在内存中存储节点的顺序很重要。如果我们以常规的方式打包BST(比方说以宽度优先的顺序)，我们可能会遇到这样的情况：BST搜索路径中的几乎每个顶点(除了前几个顶点)都位于不同的页面中，因此我们将不得不使用$O(\logN-\logB)$页面访问。van Embde Boas布局基本上是以递归的、类似于分形的方式对二叉搜索树的顶点进行排序的一种聪明方式，这样每次页面访问都会获取接下来要查询的几个顶点，因此接下来的几次访问将包含在该页面中。(=

为方便起见，假设二叉树是完整的，并且高度为$H=2^K$。布局是二叉树的顶点的排列。将$T(x，k)$表示为高度为$2^k$的子树，以顶点$x$为根。如果$x$处的子树比$2^k$深，则$T(x，k)$将是截断到所需深度的子树。将$L(x，k)$表示为该子树的布局。然后，对于高度为$h=2^k$的(子)树的某个根顶点$x$，$L(x，k)$递归地定义为：

$$L(x，k)=L(x，k-1)\回路L(l_1，k-1)\回路L(l_2，k-1)\回路\圆点\回路L(l_{n}，k-1)$$。

其中，$l_1，\dots，l_{n}$是$T(x，k-1)$的叶子的$n=2^{h/2}$子代，$\cic$只是拼接。上面显示了这种递归的一个应用。

如果你没有注意到这一点，别担心。这是一个漫游。假设我们有一棵高度为$h=2^k$的完整二叉树，以$x$为根。我们要计算$L(x，k)$，它是这个二叉树中顶点的排列。它是这样做的：

剪切$2^{k-1}$-第$层和$2^{k-1}+1$-第$层之间的所有边缘。这给我们提供了：$2^{h/2}$较小的BST，高度为$2^{k-1}$。这些是现在与主子树断开连接的子树，它们以顶点$l_1$到$l_n$为根，其中$n=2^{h/2}$。

又一个高度为$2^{k-1}$的BST，这是主子树的剩余部分，现在深度被截断。

应用递归过程$L(\CDOT，k-1)$获取每个$n+1$BST的布局。

现在，这将告诉我们如何构建布局，但更有帮助的是对此布局的外观有一些直观的认识。

直观地看待这一点的方法是将其比喻为Sierpinski三角形，它可以通过对一个完整的三角形重复应用相同的划分过程来构建。我们可以将连续的分区视为随时间的演变。与Sierpinski三角形类似，布局将子树划分为较小的子树，然后递归地对每个较小的子树应用相同的过程。

这个比喻给了我们一些启示。递归通常被视为深度优先的过程，因为大多数编程语言都是这样实现的。这会让我们本能地越来越深入地跟踪递归分支，但这并不能真正给我们理解这一点所需的直觉。取而代之的是，我们可以采用Sierpinsiki三角形提供的视角，而不是限制递归深度。这类似于以广度优先而不是深度优先的方式扩展递归。

具体地说，让$t$作为递归深度限制。我们引入了一个术语‘ATOM’来表示递归在深度$t$处划分到的子树单元。对于$t=0$，递归是完全未展开的，原子就是整个树。非常简单的是，在最终布局中，此原子中的所有顶点都放置在一个连续的范围内。

接下来，为了步入$t=1$，我们评估递归的一层。原子现在是高度为$2^{k-1}$的子树。连接过程连接了单个原子的布局，因此我们可以安全地说，在最终布局中，同一原子中的所有顶点都在一个连续的线段中。请注意，为了保持这一性质，只要我们不拆分原子，我们以什么顺序连接原子布局就无关紧要了。

现在，我们计算$t=2$的另一层递归。原子现在是高度为$2^{k-2}$的子树。出于与前面相同的推理，在最终布局中，同一原子中的所有顶点都位于连续的线段中。

这样，如果我们限制递归深度，我们可以将对布局的递归调用看作是将树连续划分为越来越细的原子。更准确地说，在van Embde Boas布局的演化中，在应用$t$级别的递归调用之后，所有顶点都被划分为高度为$2^{K-t}$的子树。这个观点让我们可以说一些关于原子的强有力的东西：

在最终布局中，我们可以选择任何分辨率来查看布局。在此分辨率下，任何原子中的所有顶点都将位于连续的线段中。

此时，您可能已经很好地了解了算法是什么。在给定这种布局的情况下，缓存无关算法是遍历此BST的简单算法。现在，让我们更正式地分析为什么这是有效的。

假设页面大小为$B$。每走一步，原子的高度就减半。我们感兴趣的是第一个时间步的原子高度，整个原子可以放入一页。由于完全二叉树中的顶点数随高度呈指数增长，因此当原子高度为$\theta(\logB)$时就会发生这种情况。然后，分析此分辨率下的布局，我们可以使用1个页面加载将任何原子(高度均为$\theta(\log B)$)放入缓存。

然后，现在考虑一下搜索过程中会发生什么。搜索基本上由从BST的根到某个叶*的路径组成。这条路径将在第一个原子中停留一段时间，直到它到达原子的叶子并进入下一个原子，依此类推。由于路径始终从原子的根顶点开始，在叶子上结束，因此它将在该原子中花费$\theta(\logB)$个步长。因为整个搜索路径是$\log N$步长，所以我们需要$O(\frac{\log N}{\log B})=O(\log_B N)$ATOM，这就是我们需要的页面访问次数。

该算法的核心是van Embde Boas布局的分形性质，它提供了某种比例不变性。几何缩放的想法实际上是算法分析中一个非常常见的论点，但我发现这个特定的例子非常直观和生动。我在这里偷工减料是有罪的，我已经用Asterix标出了一些更糟糕的部分。尽管如此，我希望我能够传达这篇文章的主要直觉，如果您对我忽略的细节感兴趣，或者阅读更多关于缓存无关算法的内容，我会推荐Erik Demaine的精彩且易于理解的评论论文。