覆盖内存范围的算法？

Question

我有一组范围,如{(2-8),(13-22),(380-7931),(40032-63278)}.为简单起见,我们可以假设它们不重叠(重叠范围已经合并).

我的目标是使用一组给定的"长度"组合来"覆盖"这些范围,例如{4,64,1024,16384}.我被限制使用最多N个长度,例如N = 32.我不关心我使用多少"长度",只要我低于我的最大值,但我想最小化总"额外"区域 - 数字"覆盖"长度不在初始范围集中.

由(2-66)覆盖的示例{(2-8)}(使用的一个长度为64)具有58个"额外"数字.由{(2-6),(6-10)}(两个长度为4)覆盖的{(2-8)}仅具有2个"额外"数字并且是优选的.

我的真实世界应用程序涉及对固定MMU TLB进行预编程,以确保只能访问某些范围的内存地址(TLB未命中因此代表禁止访问并且可以相应地处理).我想尽可能紧覆盖范围,从而侵犯被抓住宜早不宜迟,但我只有32个插槽,工作和4个固定页面大小.我可以手动调整我的代码到足够的性能水平,但我很好奇是否有更优雅/通用的解决方案.它似乎与背包问题有关,但不同的是它很难搜索.

Answer 1

这可以表述为最短路径问题的变体。

我们需要用最多N页来覆盖一组总长度为M的范围。页可能有L 个不同的长度，它们没有对齐（可以放置在任何地址）。总“额外”区域与页面总长度之间的差值等于常数M，这允许最小化页面总长度。

让我们构建一个与这个问题相关的图表。任何范围内的每个内存地址在图中都有对应的顶点。每个顶点有L 个出边，对应于L 个 页面，从给定地址开始。每条边的长度等于页面长度。每条边都到达图中的某个顶点，具体取决于相应页面的结束位置：

1. 页面结束于某个未被占用的位置。边到达顶点，对应于该位置之后的第一个范围的起始地址。
2. 页面在某个范围内结束。边到达顶点，对应页面的结束地址。
3. 页结束于未占用的位置，其地址大于任何范围的地址。边到达目标顶点。（第一个范围的起始地址对应于源顶点，我们应该找到这两个顶点之间的最短路径）。

由于生成的图是DAG，因此可以通过按拓扑顺序（或者更简单，按相应内存地址的顺序）处理顶点来在线性时间内找到最短路径。

对于每个顶点，保留一个由N对 {path-length, back-pointer} 组成的数组。当最短路径算法访问任何顶点时，用路径中的跳数索引该数组，如果路径短于存储的路径长度，则替换 {path-length, back-pointer}。当处理每个顶点时，在数组对中找到属于目标顶点的最短路径，然后使用后向指针重建路径。该路径描述了最佳覆盖。

最坏情况时间复杂度 O(L*M*N) 由最大边数 (L*M) 和数组中属于每个顶点的元素数 (N) 确定。如果范围稀疏，则大多数边到达某个范围的起始地址，对应于内部地址的大多数顶点未被使用，并且时间复杂度要小得多。

该算法需要 O(M*N) 空间，但对于稀疏范围，如果我们将所有图顶点（或者可能所有长度/指针对）放入哈希映射中，则可能会显着减少。