7

给定一个数组 [x1, x2, x3, ..., xk ]，其中 xi 是盒子 i 中的项目数，我如何重新分配这些项目，以便没有一个盒子包含超过 N 个项目。N 接近 sum(xi)/k - 也就是说，N 接近于每个具有相同数量项目的框。中间箱子不应该用来搬运物品——如果 x1 有盈余，而 x2 和 x3 有赤字，x1 应该将一些物品发送给 x2 和 x3，但不要将其所有物品发送给 x2，然后让 x2 解决盈余.

实际问题是：每个计算节点都有一组样本，在重采样步骤之后，一些计算机节点可能有盈余，而另一些则有赤字，所以我想在最小化通信的同时重新分配样本。

我想这类问题有一个名字。

4

7 回答 7

3

我不相信你的问题（如前所述）复杂到足以吸引独立研究。如果机器计数（称为它C）为数千，并且您的样本计数甚至数万亿，那么将样本计数发送到协调主节点是微不足道的。

然后，主节点可以简单地 ( O(C)) 计算N、识别违反此界限的节点以及违反该界限的程度。请注意，超出界限的总和恰好是所需的最小通信量。通过在计算时插入一个松弛参数N（即通过接受不平衡），您可以控制这个数量。

使用排序，可以按样本计数对节点进行排序O(C log C)。从两端向中间移动两个光标。在每个步骤中，安排从大节点到小节点的传输，大小为大节点中剩余的多余部分或小节点中剩余的松弛部分的最小值。推进最后一句中具有活动约束的节点的指针并重复，直到新的大节点没有多余。（我相信这是@Noxville 的贪婪算法。）

假设N大于每个节点的平均样本数，很容易看出这是最小通信的理想值。

如果您的机器网络有任何限制，例如缺少链接或最大流量或跨边的可变成本，那么您需要分解图流的东西。但是，您没有提到这样的事情，并且同一数据中心内的计算机集群通常没有。

于 2011-12-11T02:35:32.560 回答
3

这个问题可以建模为最小成本流的一个实例。

设 G 是一个有向图，其顶点为 s, t, a 1 , ..., a k , b 1 , ..., b k和弧 s→a i容量为 x i且成本为 0，弧 a i →b j容量无限如果 i = j 则成本为 0，如果 i ≠ j 则成本为 1，并且弧 b j →t 的容量为 N 且成本为 0。我们想要将 ∑<sub>ix i个单位从 s 移动到 t的最小成本流。这个想法是，如果 y 个单位流动 a i →b j，则 y 个项目从盒子 i 移动到盒子 j（如果 i ≠ j；如果 i = j，则不会发生移动）。

使用最小成本流来解决这个简单的问题当然是使用大锤来破解难题，但是可以将几种变体建模为网络流问题。

  • 如果一对节点 i,j 不直接相连，则去掉 a i →b j弧。

  • 我们可以通过仅在“a”侧或“b”侧为节点提供顶点来启动和关闭节点。

  • 我们可以通过从统一调整成本来模拟通信速度的差异。

  • 我们可以通过限制弧的容量来限制两个节点交换的项目数量。

  • 我们可以引入更多的内部顶点并改变连接的完整二分拓扑来模拟网络竞争的影响。

于 2011-12-10T22:40:36.030 回答
1

听起来您想使用一致的哈希

http://en.wikipedia.org/wiki/Consistent_hashing

基本上，使用一个好的随机散列函数将允许您为您的样本获得唯一的 id，从而提供均匀分布。然后很容易将样本一致地分布在一组节点上。

看

http://www.lexemetech.com/2007/11/consistent-hashing.html http://www.tomkleinpeter.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/

了解更多信息。

于 2011-12-07T08:12:21.403 回答
1

我认为应该以这种方式澄清问题：

对于M剩余节点和K缺陷节点，我们应该将节点之间的样本重新分配到具有 0 个剩余节点和（可能）一些缺陷节点的状态。样品应以包装形式交换，并且应尽量减少这些包装的数量。

或者，在数学上，我们有M*K矩阵，它的每个单元格表示从节点传递到节点的样本数M，K每行中的元素总和为给定，每列中元素总和的最大值为给定。目标是最小化非零单元的数量。

这是一种“约束满足问题”。它是NP完全的。我发现了两个与这个问题类似的经典问题：“集装”和“广义精确覆盖”。

为了将问题减少到“设置打包”，我们需要（临时）添加几个带有N+1样本的剩余节点，以便在重新分配之后没有剩余节点。然后对于每个节点，我们需要为剩余元素和“不足”元素生成所有可能的分区。然后对盈余和赤字分区的笛卡尔积应用其“优化”版本中的“集打包”，它会找到最小数量的子集。

为了将问题简化为“广义精确覆盖”，对于每个节点，我们需要为剩余元素和“赤字”元素生成所有可能的分区。然后我们应该添加M, M+1, ... 优化节点以最小化封面中的子集数量。然后对盈余和赤字分区的笛卡尔积和优化节点应用“广义精确覆盖”。对于较少数量的优化节点，此算法将失败，对于较大数量的优化节点，它将找到最小数量的子集。

“广义精确覆盖”可以通过“Knuth's Algorithm X”解决。我不知道“设置包装”的任何算法。

所有这些解决方案都给出了准确的答案，但它们具有巨大的计算复杂性，不太可能有人在真正的调度程序中使用它们。实用的方法是使用一些启发式和贪心算法。只需对盈余节点和赤字节点进行排序并应用“最佳拟合”策略即可。

于 2011-12-11T10:32:57.207 回答
1

我通常只看到这称为数据重新分配，其理解是，如果您正在重新分配它，您希望分配在某些指标下是最佳的，例如任务之间的均匀性。

当您尝试进行计算负载平衡时，这确实出现在科学/技术计算中。即使您在多个维度上进行计算，如果您通过空间填充曲线重新分配分配给处理器的空间数据，就会出现这个确切的问题，并且您通常确实希望数据被均匀划分。

该过程非常简单；你首先取x i的唯一前缀总和，这样你就知道有多少项目在你的“左边”。例如，对于上面 Noxville 的示例，如果您有数据

[9, 6,  1,  6,  2]

前缀总和将是

[0, 9, 15, 16, 22]

你会发现（从最后一个处理器的总和加上它的数量）总共有 24 个项目。

然后你计算出你理想的分区有多大——比如 ceil(totitems / nprocs)。只要每个处理器都同意所有分区大小的大小，您就可以随意执行此操作。

现在，您有几种方法可以继续。如果数据项在某种意义上很大并且您不能在内存中拥有它们的两个副本，那么您可以开始将数据转移到最近的邻居。你知道你左边的项目数量和那个方向的“过剩”或“赤字”；而且你也知道你有多少（并且在你完成了你的部分来解决过剩或赤字之后将会有）。因此，您开始向您的左右邻居发送数据，并从您的左右邻居接收数据，直到左侧的处理器共同拥有正确数量的项目并且您也这样做。

但是，如果您有能力拥有两个数据副本，那么您可以采用另一种方法来最小化发送的消息数量。您可以将左侧的单元格数视为本地数据在“全局”数组中的起始索引。由于您知道每个处理器最终将处理多少个项目，因此您可以直接确定这些项目最终将在哪个进程中，并可以直接发送它们。（例如，在上面的示例中，处理器 0 - 具有项目 0..8 - 知道如果除了最后一个处理器之外的每个处理器都将结束 5 个数据项，那么值 5-8 可以发送到处理器 1。 ) 一旦发送了这些，您只需接收到您期望的数据量；你就完成了。

下面是一个在 C 和 MPI 中执行此操作的简单示例，但基本方法几乎​​可以在任何地方使用。MPI 的前缀扫描操作会生成包含和，因此我们必须减去我们自己的值数才能得到独占和：

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <time.h>

void initdata(const int rank, const int maxvals, char **data, int *nvals) {
    time_t t;
    unsigned seed;

    t = time(NULL);
    seed = (unsigned)(t * (rank + 1));

    srand(seed);
    *nvals = (rand() % (maxvals-1)) + 1;
    *data = malloc((*nvals+1) * sizeof(char));

    for (int i=0; i<*nvals; i++) {
        (*data)[i] = 'A' + (rank % 26);
    }
    (*data)[*nvals] = '\0';
}

int assignrank(const int globalid, const int totvals, const int size) {
    int nvalsperrank = (totvals + size - 1)/size;
    return (globalid/nvalsperrank);
}

void redistribute(char **data, const int totvals, const int curvals, const int globalstart,
                  const int rank, const int size, int *newnvals) {

    const int stag = 1;
    int nvalsperrank = (totvals + size - 1)/size;

    *newnvals = nvalsperrank;
    if (rank == size-1) *newnvals = totvals - (size-1)*nvalsperrank;

    char *newdata = malloc((*newnvals+1) * sizeof(char));
    newdata[(*newnvals)] = '\0';

    MPI_Request requests[curvals];

    int nmsgs=0;

    /* figure out whose data we have, redistribute it */
    int start=0;
    int newrank = assignrank(globalstart, totvals, size);
    for (int val=1; val<curvals; val++) {
        int nextrank = assignrank(globalstart+val, totvals, size);
        if (nextrank != newrank) {
            MPI_Isend(&((*data)[start]), (val-1)-start+1, MPI_CHAR, newrank, stag, MPI_COMM_WORLD, &(requests[nmsgs]));
            nmsgs++;
            start = val;
            newrank = nextrank;
        }
    }
    MPI_Isend(&((*data)[start]), curvals-start, MPI_CHAR, newrank, stag, MPI_COMM_WORLD, &(requests[nmsgs]));
    nmsgs++;

    /* now receive all of our data */
    int newvalssofar= 0;
    int count;
    MPI_Status status;
    while (newvalssofar != *newnvals) {
        MPI_Recv(&(newdata[newvalssofar]), *newnvals - newvalssofar, MPI_CHAR, MPI_ANY_SOURCE, stag, MPI_COMM_WORLD, &status);
        MPI_Get_count(&status, MPI_CHAR, &count);
        newvalssofar += count;
    }

    /* wait until all of our sends have been received */
    MPI_Status statuses[curvals];
    MPI_Waitall(nmsgs, requests, statuses);

    /* now we can get rid of data and relace it with newdata */
    free(*data);
    *data = newdata;
}

int main(int argc, char **argv) {
    const int maxvals=30;
    int size, rank;
    char *data;
    int mycurnvals, mylvals, myfinalnvals;
    int totvals;

    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);

    initdata(rank, maxvals, &data, &mycurnvals);

    MPI_Scan( &mycurnvals, &mylvals, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD );
    if (rank == size-1) totvals = mylvals;
    mylvals -= mycurnvals;

    MPI_Bcast( &totvals, 1, MPI_INT, size-1, MPI_COMM_WORLD );

    printf("%3d      : %s %d\n", rank, data, mylvals);

    redistribute(&data, totvals, mycurnvals, mylvals, rank, size, &myfinalnvals);


    printf("%3d after: %s\n", rank, data);

    free(data);
    MPI_Finalize();
    return 0;
}

运行这个你会得到预期的行为；请注意，我确定“所需”分区的方式（使用 ceil(totvals/nprocesses)）最终处理器通常会负载不足。另外，我没有尝试确保在重新分配中保留顺序（尽管如果顺序很重要，这很容易做到）：

$ mpirun -np 13 ./distribute 
  0      : AAAAAAAAAAA 0
  1      : BBBBBBBBBBBB 11
  2      : CCCCCCCCCCCCCCCCCCCCCCCCCC 23
  3      : DDDDDDD 49
  4      : EEEEEEEEE 56
  5      : FFFFFFFFFFFFFFFFFF 65
  6      : G 83
  7      : HHHHHHH 84
  8      : IIIIIIIIIIIIIIIIIIIII 91
  9      : JJJJJJJJJJJJJJJJJJ 112
 10      : KKKKKKKKKKKKKKKKKKKK 130
 11      : LLLLLLLLLLLLLLLLLLLLLLLLLLLL 150
 12      : MMMMMMMMMMMMMMMMMM 178

  0 after: AAAAAAAAAAABBBBB
  1 after: BBBBBBBCCCCCCCCC
  2 after: CCCCCCCCCCCCCCCC
  3 after: DDDDDDDCEEEEEEEE
  4 after: EFFFFFFFFFFFFFFF
  5 after: FFFHHHHHHHIIIIIG
  6 after: IIIIIIIIIIIIIIII
  7 after: JJJJJJJJJJJJJJJJ
  8 after: JJKKKKKKKKKKKKKK
  9 after: LLLLLLLLLLKKKKKK
 10 after: LLLLLLLLLLLLLLLL
 11 after: LLMMMMMMMMMMMMMM
 12 after: MMMM
于 2011-12-17T03:28:06.400 回答
0

基本上你想从

[9, 6, 1, 6, 2]

至

[5, 5, 4, 5, 5]

我认为最好的方法是计算 floor(sum(array)/len(array))，然后评估到达这个位置所需的差异。在这种情况下， floor( (9+6+1+6+2) / 5) = 4，因此我们正在查看 [-5, -2, +3, -2, +2] 的初始微分。然后，您可以贪婪地交换符号不同的相邻对中的值（例如从 array[2] -> arr[1] 传输 2 和从 array[4] -> array[3] 传输 2）。然后剩下 [-5,0,1,0,0] ，从这里你可以贪婪地分配剩余的位。

于 2011-12-07T13:16:10.860 回答
0

我认为这个重新分配问题与计算中的负载平衡有点不同。

负载平衡算法术语通常表示策略/启发式的集合，以确保未来负载（而不是当前负载）的相对均匀分布。

在这种情况下，负载均衡器不会重新分配来自现有服务器/系统的负载，但是任何新的请求都会尝试使用一些策略（即最小负载、循环等）进行分配，这将使服务器保持相对均匀从长远来看，加载。

http://en.wikipedia.org/wiki/Load_balancing_ (计算)

这个问题中的负载重新分配，也许可以通过迭代地将项目从最大负载移动到最小负载框来实现。

于 2011-12-07T14:11:47.520 回答