c++ - 分配算法

Question

我需要将 N 个实体（每个实体都有可能的父母和可能的孩子）分配给 M 个计算节点，同时满足以下优化条件：

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

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

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

谢谢。

Answer 1

好吧，显然你必须预测每个进程平均有多少个子进程（或简单的总负载）。与您可以使用经典的分配算法相比，它们通常非常简单。

最重要的问题当然是决定要最小化什么。通常我们希望尽量减少迟到（我们得到多少“落后于计划”），但并不总是......

编辑：如果您事先知道所有的孩子/父母，并且一个进程的孩子必须在同一台机器上，您可以认为一个进程及其所有孩子一开始就是同一个进程。然后你可以使用一个非常简单的算法来最小化你想要最小化的任何东西。

编辑#2：阅读作业调度以获得更好的想法

Answer 2

我不确定 1 是否是硬性要求。如果是这样，作为第一步，您应该将实体分组到连接的组件中。如果不是，您应该指定 1 和 2 之间的权衡，例如作为成本函数。

如果将每个节点限制为 N/M 个实体，则将组件放在计算节点上是装箱问题。一个很好的近似是以下算法：

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