algorithm - 如何最小化固定分配方案所需的内存量？

Question

下图可视化了 16 个不同大小的内存块所需的生命周期:

我基本上要寻找的是一些 N block ，大小为 size_i 和 lifetime [begin_i, end_i)，返回最小大小的总内存块需要在我们的总时间间隔和 N 偏移量内包含它们，offset_i，进入输入 block 的总内存块。

一个简单的非最优算法如下:

int offsets[N];
offsets[0] = 0;
int total_size = size[0];
for (int i = 1; i < N; ++i)
{
    offsets[i] = offsets[i - 1] + size[i - 1];
    total_size += size[i];
}

我们当前的算法是按大小对 block 进行排序，然后从大到小处理它们，找到 block 不与已“分配”的 block 重叠的第一个偏移量。这本质上是一种贪心算法，所以我觉得可以做得更好。

该算法只需要在应用程序启动时运行一次，因此不必非常快。分配的数量大约为 10-50，为了我们的目的，时间可以离散化为大约 50 个固定大小的单位。

Answer 1

从您的begin 和end 时间间隔列表中找出最短开始时间和最长结束时间。这是您感兴趣的时间的总间隔 (t_min, t_max)。接下来，将时间间隔划分为一些离散且均匀的间隔。令此区间的长度为u。这基本上是内存管理的最大分辨率(您可以释放和/或申请一 block 内存的频率)。

对于每个时间单位，确定当时哪些Allocation ID需要内存以及它们各自需要的大小，称之为s(t, id)。 s(t, id) 在所有分配 ID 上的总和是您在任何给定时间需要多少总内存的下限。你不能比这个函数的最大值做得更好，它没有考虑到将事物保持在同一区域而不在每个时间步移动它们的愿望。

要为每个项目找到最佳位置，您可以使用启发式搜索。基本上，在每个内存块的所有可能起始地址的状态空间中搜索占用内存总量最小的解决方案，您可以通过模拟从 t_min 到 t_max 的时间进程来找到。

一个可能值得尝试的启发式方法是优先分配大块占用先前由其他大块占用的空间，而小块放置在对策略的最大内存使用贡献较小的位置。您还可以修剪任何发现的比迄今为止最好的策略更糟糕的策略，因为该策略要求的最大内存随着时间的推移是单调的。

启发式搜索方法可能很慢，但听起来您更关心优化内存使用而不是分配算法的运行时间。