I recently posted a simulation that misbehaved because of short comings in the
rr_sim function. The problem in that case was that there was a single CPU task
that was running high priority (as it should), and a multi CPU task that was
longer than the minimum work buffer. The problem is that the client will not
in that case download any work from anywhere to fill the CPU that is idle.
One possible solution:
Run rr_sim in multiple passes, and track high priority tasks. Track High
Priority tasks and when they will complete. Assume that once a task is high
priority, it stays that way until complete (OK, not true in all cases, but I am
trying to avoid the expense of an even more accurate method).
Pseudo code.
Run rr_sim - this marks tasks as requiring EDF or not. Set a flag indicating
if any new tasks were marked as EDF by rr_sim.
Use the results to supply information to a new function that simulates EDF for
the tasks that are marked as requiring EDF. The output of this feeds back into
rr_sim. Rr_sim now has to cope with a staggered start for the remaining Non
High Priority tasks. Multi CPU tasks would not be allowed to start until such
a time as sufficient CPUs were available. Exit the loop when all CPUs are busy
with EDF work for minimum work buffer time. Gaps is information about forced
gaps due to EDF tasks and multi CPU tasks. When done, thee will be information
about saturation of all CPUs and forced gaps up the minimum work queue. This
can be used to generate appropriate work fetches.
Pseudo code:
Structure gap
{
Double duration;
Double start_time;
Int n_cpus;
}
Initialize tasks for a new rr_sim run
Bool newTasksMarkedEDF = false;
Double CPUSEDFBusyTill = now();
Double * CPUEDFBusyArray = new double(n_cpus);
Initialixe CPUEDFBusyArray to all 0;
Std::array<gap> gaps;
Do
{
newTasksMarkedEDF = rr_sim(CPUEDFBusyArray,
&gaps);
if (newTasksMarkedEDF)
CPUSEDFBusyTill =
edf_sim(CPUEDFBusyArray, &gaps);
}
While (newTasksMarkedEDF && CPUSEDFBusyTill < now() + min_work_buf)
Run time analysis:
Best case: No tasks needing EDF - single run of rr_sim.
Typical case ought to be a handful of runs through the loop. We might want to
cap the number of runs though as:
Worst case: One run of each per task.
NOTE: Projects would be marked with the number of tasks that need to run EDF
by rr_sim. Edf_sim and rr_sim both get shorter on each run as any task already
marked as consumed by edf_sim would not need to be inspected again. It is
already in the EDF array someplace. Both edf_sim and rr_sim can note a forced
gap due to EDF requirements. In both cases, it would be because there was not
enough work of a low enough count of CPUs to fill the hole.
_______________________________________________
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.
