Over the weekend, I came up with a scenario that is worse than Shortest run
time first, and the means to deal with it in a very simple simulator.
On a 4 CPU system there are 8 tasks:
A: 1 hour
B: 1 Hour
C: 1 hour
D: 1 hour
E: 4 hours
F: 4 hours
G: 4 hours
H: 100 hours.
Shortest first would have
CPU0: A, E 5 hours
CPU1: B, F 5 hours
CPU2: C, G 5 hours
CPU3: D, H 101 hours
If the disconnected interval was 24 hours, this would indicate a shortage
of 19 * 3 = 57 hours or work.
If, on the other hand, the packing was:
CPU0: E 4 hours
CPU1: F 4 hours
CPU2: G 4 hours
CPU3: A, B, C, D, H 104 hours
The shortage would be 60 hours.
Pushing the "long pole" of 100 hours out as far as possible is the key to
making the work shortage be as bad as possible. The worst case for this is
actually the sum of the remaining tasks / n_cpus in this case. So, the
proposed algorithm is:
if results count <= n_cpus (degenerate case, just calculate the obvious
shortfall by sum(max(0, disconnected interval - result CPU time
remaining )) + ncpus - results count * disconnected interval.
else
Sort tasks by remaining cpu time. Largest first.
workfetch = 0;
if (ncpus < results count)
{
for (i = 0; i < ncpus && i < results count - n_cpus; ++i)
{
sum = 0;
for (j = i +1; j < results count)
{
sum += result[j].remaining cpu time;
}
m = sum / n_cpus;
w = 0
for (j = 0; j <= i; ++j)
{
w += max(0, disconnected interval - (result[j].remaining
cpu time + m);
}
if (w > workfetch) workfetch = w;
}
}
else
{
// degenerate case where there are no more tasks than CPUs.
for (i = 0, i < results.count; ++i)
{
workfetch += max(0, disconnected interval - result[i].remaining
cpu time);
}
}
Can anyone come up with a scenario where this fails to request enough work?
If so, what is it? Do you have a suggested means to cope with it?
jm7
_______________________________________________
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.
