I need a decent algorithm to divide work amongst my workers (processors)
which I will use with OpenMP:
More precisely, I have a list of tasks (numbered 1,...n) requiring t_i
(i=1,..,n) time units (flops, whatever). I would like to assign each task
to one of my k workers (processors) so that all workers have about the
same
amount of work. Ideal would of course be if all workers have work for T/k
time units, T being the sum over the t_i. As I want the total time I have
to wait for all work to be completed to be minimal, the deviation of the
ideal work time for each worker should be "punished" in the max. norm (or
2-norm). I don't need the best solution, but a work load that is balanced
reasonably well - so I am looking for a heuristic and ideally for a C/C++
implementation that is available in the public domain.
I would be grateful for any hint as to where I can find such an algorithm
(either already implemented or described so that I can program it myself).
(Note: I do not want to use the various OpenMP scheduling techniques,
because I will adapt my data structure in advance so that the data will be
accessed sequentially by each processor. Furthemore, t_i varies
significantly (some may even be 0), and this is unknown to the OpenMP
scheduler...)
Thanks in advance.
Jan
|
