I understand very well that bin packing is NP complete. However, we
usually do not have exactly enough work to fill the bins to capacity and so
have quite a bit of slack to play with. The key is to use that slack to
our best advantage.
Yes, EDF all the time is a pitfall that needs to be avoided as there are
scenarios where long running projects get starved. Note that in this case,
work fetch would be stopped until nearly the end of the scenario, and no
new work would be coming in.
Because the problem is NP complete it is very difficult to prove that there
is no case where there is a disaster with the proposed change. However,
heuristics are all about taking the probabilities of scenarios and
attempting to figure out which tool to use in each scenario.\\
Since the scenario that I indicated is actually happening on one of my
machines only a few weeks after the change to the scheduler, it has to be
at least moderately common.
If there is a set of tasks in deadline trouble, we need to run those tasks
in EDF in order to meet deadlines. Giving multi CPU tasks higher priority
in this list because they are multi CPU tasks is a way of ensuring an
arbitrary number of tasks are an arbitrary amount of time late. If the
scenario was such that the multi CPU task had an earlier deadline than one
of the single CPU tasks, the multi CPU task would run in preference to that
single CPU task.
The only scenarios that I can think of that get into trouble running single
CPU task with an earlier deadline in preference to a multiple CPU task with
a later deadline where both are in deadline trouble that I can think of
also have the feature that there is no way at all to do the packing in such
a way that both deadlines can be met under any circumstances. i.e.
impossible situations that we need to try to get work fetch to avoid for
us.
The CPU scheduling heuristic that we have been using up until multi CPU
tasks was added has been:
If there are tasks in deadline trouble
Run tasks in EDF.
If there are any CPUs still available
Run some tasks in RR.
Currently it appears to be:
If there is a multi CPU task in deadline trouble
Run the multi CPU task
else If there are any single CPU tasks in deadline trouble
Run the single CPU tasks in EDF.
If there are any CPUs remaining and there is a multi CPU task that is in
the top N tasks
run the multi CPU task.
else if there are any CPUs remaining
run some single CPU tasks in RR.
All I am proposing to do is to move back closer to the original heuristic
(which seemed to be working fairly well until multi CPU tasks were added).
The current method of determining what to run has a proven major problem.
BTW, rather than returning work late, I have currently suspended processing
on the multi CPU task in order to complete the tasks that are due today
that have not been started yet. All CPUs are currently busy doing work,
and doing it this way will allow the work to be returned.
jm7
David Anderson
<[email protected]
ey.edu> To
Sent by: [email protected]
<boinc_dev-bounce cc
[email protected] [email protected]
u> Subject
Re: [boinc_dev] CPU prioritization.
01/14/2010 04:28
PM
[email protected] wrote:
> I was thinking about the problem I was seeing, and I came up with a
simple
> scenario to demonstrate the problem.
>
...
The underlying problem is that bin-packing
(or multiprocessor scheduling) is NP-complete.
EDF is non-optimal in some cases on multiprocessors.
No matter what scheduling policy we use
(short of exponential-time exhaustive search)
there will be scenarios where it misses deadlines
that could be met by some other schedule.
This problem exists whether or not there are multi-CPU jobs.
In the example you give, suppose we reach the point where
we have a multi-CPU job and a 1-CPU both in deadline trouble.
Things work out better if we run the 1-CPU job.
But how do we know this? What policy says so?
If there is such a policy, how do we know it doesn't
fail disastrously in other scenarios?
_______________________________________________
boinc_dev mailing list
[email protected]
http://lists.ssl.berkeley.edu/mailman/listinfo/boinc_dev
To unsubscribe, visit the above URL and
(near bottom of page) enter your email address.
_______________________________________________
boinc_dev mailing list
[email protected]
http://lists.ssl.berkeley.edu/mailman/listinfo/boinc_dev
To unsubscribe, visit the above URL and
(near bottom of page) enter your email address.
