wiki:ClientSchedOctTen

Version 6 (modified by Pepo, 13 years ago) (diff)

Typo while editing equation

Client scheduling changes

Design document for changes to the client work fetch and job scheduling policies, started Oct 2010.

This supercedes the following design docs:

Problems with current system

The current policies, described here, maintain long- and short-term debts for each (project, processor type) pair.

Job scheduling for a given processor type is based on STD. Projects with greater STD for the type are given priority.

Work fetch is based on a weighted sum of LTDs. Work is typically fetched from the project for which this sum is greatest, and typically work is requested for all processor types.

These policies fail to meet their goals in many cases. Here are two scenarios that illustrate the underlying problems:

Example 1

A host has a fast GPU and a slow CPU. Project A has apps for both GPU and CPU. Project B has apps only for CPU. Equal resource shares.

In the current system each project will get 50% of the CPU. The target behavior, which matches resource shares better, is that project B gets 100% of the CPU and project A gets 100% of the GPU.

Example 2

Same host. Additional project C has only CPU apps.

In this case A's CPU LTD will stay around zero, and the CPU LTD for B and C goes unboundedly negative, and gets clamped at the cutoff. All information about the relative debt of B and C is lost.

The bottom line

The current approach - extending the STD/LTD model to multiple processor types - seemed good at the time but turns out to be the wrong way.

Proposal: credit-driven scheduling

The idea is to make resource share apply to credit. If two projects have the same resource share, they should have the same RAC. Scheduling decisions should give preference to projects whose share of RAC is less than their resource share.

There are problems with using project-granted credit as a basis for this approach:

  • There may be a long and variable delay between completing a job and getting credit for it.
  • Jobs may fail to get credit, e.g. because they don't validate.

Hence we will use a surrogate called estimated credit that is maintained by the client. If projects grant credit fairly, and if all jobs validate, then estimated credit is roughly equal to granted credit over the long term.

Note: there is a potential advantage to using granted credit too. Doing so penalizes projects that grant inflated credit: the more credit a project grants, the less work a given host will do for it, assuming the host is attached to multiple projects. (The converse is potentially also true - a project would get more work done by granting less credit. This effect could be minimized by combining estimated credit with granted credit.)

Estimated credit

BOINC server software grants credit on the basis of peak FLOPS, with a scaling factor applied to GPUs to normalize them relative to CPUs. The normalized peak FLOPS of a GPU can be estimated.

The estimated credit for a T-second segment of job execution is given by

T * ninstances(P) * peak_flops(P)

summed over the processor types used by the job.

The recent estimated credit REC(P) f a project P is maintained by the client, with an averaging half-life of, say, a month.

Work fetch

The work fetch policy also needs to take into account the amount of work currently queued for a project, so that it doesn't keep getting work from the same project. To accomplish this, we define Q(P) as the number of FLOPS currently queued for P, normalized so that the sum over projects is 1.

We then define the work-fetch priority of a project as

WFP(P) = share(P) - (RAF(P) + A*Q(P))/(1+A)

where A is a parameter, probably around 1.

Job scheduling

As the job scheduling policy picks jobs to run (e.g. on a multiprocessor) it needs to take into account the jobs already scheduled, so that it doesn't always schedule multiple jobs from the same project. To accomplish this, as each job is scheduled we update RAF(P) as if the job had run for one scheduling period. The job-scheduling priority is then

JSP(P) = share(P) - B*RAF(P)

where B is a parameter, probably around 1.