c++ - 分配算法

Question

我需要将 N 个实体(每个实体都有可能的 parent 和可能的 child )分配给 M 个计算节点，同时满足以下优化条件:

1. 一个实体的子节点希望被分配到同一个计算节点(以最大化兄弟节点之间的数据局部性)
2. 实体的分布应尽可能均匀(即不要让单个节点负担过重)。

我正在寻找一些关于启发式方法的建议来解决这个问题。

我读过 http://en.wikipedia.org/wiki/Assignment%5Fproblem .

谢谢。

Answer 1

我不确定 1 是否是硬性要求。如果是这样，作为第一步，您应该将您的实体分组到 connected components 中。 .如果不是，您应该指定 1 和 2 之间的折衷是什么，例如作为成本函数。

将组件放置在计算节点上是 binpacking problem ，如果您将每个节点限制为 N/M 个实体。一个很好的近似是以下算法:

1. 按实体数量降序排列组件
2. 只要每个节点仍有可用容量，就将它们放置在节点上
3. 完成 2 后，您可能有尚未放置的组件。将它们放在迄今为止负载最小的节点上。