Queries for cyclic proportional assignment of work to hosts-CodePudding

Consider M pieces of work distributed over N hosts in a cyclic way where each host must get the amount of work proportional to its speed. Without proportions, this is implemented as:

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

Proportions are weights p[i] that sum up to 1.0, so that i-th host must get more or less p[i]*M pieces of work.

M is so large that storing M values doesn't fit in the memory of a single host (but a solution where it fits would be of interest too). N can be as large as 10 000. Ideally each host must store no more than O(M/N) values and the computational complexity of AssignWorkToHost() should be no more than O(N). Preprocessing is fine. The algorithm should be deterministic, meaning that each process within the distributed group must get the same assignment of work to hosts.

CodePudding user response：

I would suggest using a priority queue storing pairs of (estimated processing time, worker) with a custom comparator that compares in that order.

In pseudo-code, the body of assign to work looks like this:

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

This is deterministic, requires O(N) memory, and each assignment takes time O(log(N)).

Of course you set worker_time[i] = 1.0/worker_speed[i] and now how much worker i gets assigned is proportional to its speed.

For a query interface, we can avoid replaying all history by the simple trick of reconstructing a single point in history, then playing it forward. For that, at the time (i_work-1)/total_speed no more than i_work-1 can have been produced. Also, no less than i_work-N can have been produced. (Why? Each worker has failed to produce a fraction < 1 of the theoretical elapsed_time / worker_speed[i] limit. Therefore N workers have produced under N fewer than that theoretical limit. Since it has to be an integer, that puts it at most N-1 behind. And i_work-1 - (N-1) = i_work-N.) At that time, for each worker, we know how many that worker has produced, and we know when it next will produce another unit.

This is sufficient to produce the priority queue as of that moment of time. Then we play it forward. In no more than N steps, the k'th will pop out, correctly assigned.

Total running time for the query version is O(N log(N)). And as the saying goes, "For all intents and purposes, log(N) is a constant. For Google it is a somewhat larger constant."

(At the expense of considerably more complexity, I think you can make the query interface truly O(N).)

In pseudo-code that is almost valid 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