查询将工作循环按比例分配给主机

Question

考虑 M 件工作以循环方式分布在 N 主机上，其中每个主机必须获得与其速度成正比的工作量。没有比例，这实现为：

int64_t AssignWorkToHost(const int64_t i_work) {
  return i_work % N;
}

比例是权重 p[i]，总和为 1.0，因此第 i 位主机必须获得或多或少的 p[i]*M 份工作。

M 太大以至于存储 M 值不适合单个主机的内存（但它适合的解决方案也很有趣）。 N 可以大到 10 000。理想情况下，每个主机必须存储不超过 O(M/N) 个值，并且 AssignWorkToHost() 的计算复杂度不应超过 O(N)。预处理很好。该算法应该是确定性的，这意味着分布式组中的每个进程必须将相同的工作分配给主机。

Answer 1

我建议使用 priority queue 存储 (estimated processing time, worker) 对和按该顺序进行比较的自定义比较器。

在伪代码中，assign to work 的主体如下所示：

(estimated_time, i) = queue.pop()
queue.push((estimated_time + worker_time[i], i))
return i

这是确定性的，需要 O(N) 内存，每次赋值需要时间 O(log(N))。

当然你设置了 worker_time[i] = 1.0/worker_speed[i] 现在分配了多少工人 i 是与其速度成正比的。

对于查询界面，我们可以通过重建历史中的单个点然后向前播放的简单技巧来避免重播所有历史。为此，当时(i_work-1)/total_speed最多只能生产i_work-1。还有，不少于i_work-N都可以生产出来。（为什么？每个工人的产量都低于理论 elapsed_time / worker_speed[i] 限值的一小部分。因此，N 名工人的产量低于 N 理论限值。因为它必须是整数，最多将它放在 N-1 后面。并且 i_work-1 - (N-1) = i_work-N.) 那时，对于每个工人，我们知道该工人生产了多少，并且我们知道下一次生产另一个单位的时间。

这足以生成当时的优先级队列。然后我们向前播放。在不超过 N 步内，第 k 个将弹出并正确分配。

查询版本的总运行时间为 O(N log(N))。俗话说，“就所有意图和目的而言，log(N) 是一个常数。对于 Google，它是一个更大的常数。”

（以相当复杂为代价，我认为你可以使查询界面真正O(N)。）

在几乎有效的伪代码中 Python:

total_worker_speed = sum(1/t for t in worker_time)
t = (i_work-1) / total_worker_speed
total_done = 0
todo = []
for i in 0..count_workers:
    # At time t, this is how many are left.
    done = floor(t/worker_time[i])
    # This is how long until this worker produces the next unit
    time_left = (done+1)*worker_time[i] - t
    todo.push([time_left, i])
    total_done += done

queue = heapify(todo) # turning array into priority queue is O(N)
while total_done < iwork:
    # Get the next one.
    (estimated_time, i) = queue.pop()
    queue.push((estimated_time + worker_time[i], i))
    total_done += 1

# i now has the job that produced the iwork job.
return i

查询将工作循环按比例分配给主机

Queries for cyclic proportional assignment of work to hosts

c++

algorithm

partitioning

deterministic

distributed-computing