[mpich-discuss] how to design a efficient distributed load balance algorithm

[James Dinan]

Xiao,

If you know the T_i's and the speed of each machine, then a common 
approach is to pose this as a graph partitioning problem.  You could 
then feed the resulting graph into an existing partitioner (Zoltan, for 
example: http://www.cs.sandia.gov/Zoltan/).  One challenge you may have 
to look into is that the common use case is to give you an equiparition 
of the work, but you would actually want unequal partitions with less 
work for slow processors and more for the fast ones.

Clustering techniques have also been applied to problems like this and a 
simple clustering algorithm might also provide a good solution.

Best,
  ~Jim.

On 1/4/11 12:28 PM, Xiao Li wrote:
> Hi MPICH2 people,
>
> Suppose I have N jobs and M machines. Each job needs T_i time to finish.
> Now, the problem is I want an algorithm that quickly dispatch N jobs to
> M machines in the constrain that the slowest machine's completion time
> is minimal. Formally speaking, I need a function f:N->M that mapping N
> jobs to M machines with constrain *\argmin_f \max_j \sum_{f(i)=j}{T_i}.
> *Would anybody give me some tips for this algorithm?
>
> cheers
> Xiao
>
>
>
> _______________________________________________
> mpich-discuss mailing list
> mpich-discuss at mcs.anl.gov
> https://lists.mcs.anl.gov/mailman/listinfo/mpich-discuss