Efficient allocation of processes over a grid.
Hi all,
I have a problem here which involves spreading given processes over a network of CPUs to achieve minimum processing time. Description follows:
There aren different processes from P1 to Pn. Each process takes a fixed time to complete, say, T1 > T2 > T3 > ... > Tn.
And each process has to run a variable number of times, say, X1, X2, ... , Xn.
So total time, T = T1X1 + T2X2 + ... + TnXn.
We want to run these process in parallel. For this we have M number of CPUs. How will you distribute these processes over M CPUs and in what number as to achive minimum T?
Thanks,
-Vineet
Cross-posted on Concurrency forum. (http://forum.java.sun.com/thread.jspa?threadID=787501)
null
Sounds like a calculus problem - minimize T with the constraint that M <= N. The process times are fixed. Are all the processors the same speed, memory, and power? (Must be, if all processes run in the same amount of time.)%
> Sounds like a calculus problem - minimize T with the
> constraint that M <= N. The process times are fixed.
>
What I don't understand is what the OP's actual question is.
- They don't know the formula to figure this out
- The want to actually direct tasks to different processors with Java (good luck)
- something else
> That's a bin packing problem where you want to
> minimize the 'size' of
> the largest bin. You have M bins and sum(i, X_i)
> commodities, all of
> 'size' T_i.
>
> kind regards,
>
> Jos
This from a man who knows. Thanks, Jos.
%
All right Jos, I will look up the bin packaging problem. Just needed a direction to proceed. Im usually clueless about such things.
@cotton.m
>They want to actually direct tasks to different processors with Java
>(good luck)
Didnt want to go into name dropping so I generalised the problem. We are using a grid computation engine called Data Synapse (http://www.datasynapse.com/about/default.asp) for a commercial investment banking application. Right now the strategy is to vertically split all processes. I was wondering if we can optimally utilize the grid to do more.
Thanks for the good luck.
