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

Question

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

algorithmmemory-management

3

以下图片展示了多种大小的16个内存块所需寿命的可视化图像： enter image description here

我需要的是，给定数量为N、大小为size_i和生命周期为[begin_i, end_i)的内存块，返回在总时间间隔内包含它们所需的最小总内存块大小以及这些输入块的N个偏移量offset_i。

一个简单但不够优秀的算法如下：

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];
}

我们目前的算法是按块大小排序，然后从最大的块开始处理，找到第一个偏移量，该块不与已“分配”块重叠。这本质上是一种贪心算法，因此我感觉可能可以更好地实现。

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

- Andreas Brinck

这是一个非常模糊的提示，但不是欺骗贪心算法的规范方式吗？尝试多种可能的解决方案，引入随机性或其他偏离直接方法的因素，并查看是否有改进？（例如，对于TSP的成对交换等） - millimoose

（旁白：您的可视化有点混乱，使用“内存使用”而不是时间会更好吗？这可能或可能不会让您发现间隙以及如何填补它们。“分配ID”似乎并不是很重要。） - millimoose

你能详细说明一下吗？分配 ID 基本上代表不同的对象，而条形图表示程序执行期间它们处于活动状态的时间段，这非常重要。 - Andreas Brinck

好的，我现在意识到它是你输入结构的可视化。所以我的问题应该是，你是否能够（此外）制作一个贪婪算法提供的输出的可视化，其中一个轴是使用的内存（块从offset_i到offset_i+size），另一个轴是时间，就像这里一样。任何可见的空隙可能提供暗示，以消除这样的低效率。（或许这会是一场徒劳的追逐，我承认。) - millimoose

你的块大小也可以很好地离散化吗？在你的图中，它们看起来都是265k的小倍数。 - Falk Hüffner

为了本讨论的目的，我们假设大小是在1-50范围内的整数。 - Andreas Brinck

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kgraney · Answer 1

从您的开始和结束时间间隔列表中找到最小的开始时间和最大的结束时间。这是您感兴趣的时间总区间（t_min，t_max）。接下来，将时间间隔分成一些离散和均匀的间隔。让这个间隔的长度为u。这基本上是您内存管理的最大分辨率（您可以多久释放和/或声明一个内存块）。

对于每个时间单位，确定哪些分配ID需要内存以及它们在该时间点需要的大小，称之为s(t，id)。在所有分配ID上s(t，id)的总和是您在任何给定时间需要的总内存的下限。您不能做得比此函数的最大值更好，该函数未考虑保持在同一区域分配物品而不在每个时间步骤中移动它们的愿望。

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

一个值得尝试的启发式方法是首选大块占据先前由其他大块占据的空间，小块放置在对策略的最大内存使用贡献较小的位置。您还可以修剪任何比迄今为止看到的最佳策略更劣的策略，因为策略声明的最大内存随时间单调递增。

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