Work fetch and GPUs

Problems with the current work fetch policy

The current work-fetch policy is essentially:

• Do a weighted round-robin simulation, computing the CPU shortfall (i.e., the idle CPU time we expect during the work-buffering period).
• If there's a CPU shortfall, request work from the project with highest long-term debt (LTD).

The scheduler request has a scalar "work_req_seconds" indicating the total duration of jobs being requested.

This policy has some problems. First:

• There's no way for the client to say "I have N idle CPUs; send me enough jobs to use them all".

And various problems related to GPUs:

• If there is no CPU shortfall, no work will be fetched even if GPUs are idle.
• If a GPU is idle, we should get work from a project that potentially has jobs for it.
• If a project has both CPU and GPU jobs, the client should be able to tell it to send only GPU (or only CPU) jobs.
• LTD is computed solely on the basis of CPU time used, so it doesn't provide a meaningful comparison between projects that use only GPUs, or between a GPU and CPU projects.

This document proposes a modification to the work-fetch system that solves these problems.

For simplicity, the design considers only one GPU type (CUDA). However, it is straightforward to extend the design to handle additional GPU types.

Example

Suppose that:

• Project A has only GPU jobs and project B has both GPU and CPU jobs.
• A host is attached to projects A and B with equal resource shares.
• The host's GPU is twice as fast as its CPU.

In this case, the target behavior is for the host to use 100% of the CPU for project B, 25% of the GPU for project B, and 75% of the GPU for project A. This provides equal processing to the two projects.

Terminology

A job sent to a client is associated with an app version, which uses some number (possibly fractional) of CPUs and CUDA devices.

• A CPU job is one that uses only CPU.
• A CUDA job is one that uses CUDA (and may use CPU as well).

Scheduler request and reply message

New fields in the scheduler request message:

double cpu_req_seconds: number of CPU seconds requested

double cuda_req_seconds: number of CUDA seconds requested

double ninstances_cpu: send enough jobs to occupy this many CPUs

double ninstances_cuda: send enough jobs to occupy this many CUDA devs

For compatibility with old servers, the message still has work_req_seconds, which is the max of (cpu,cuda)_req_seconds.

The semantics are: a scheduler should send jobs for a resource type only if the request for that type is nonzero.

New fields in the scheduler reply message (these are not currently used):

double have_cpu_jobs: this project sometimes has CPU jobs for this platform (although this reply may not include any).

double have_cuda_jobs: same, for CUDA jobs.

Client

New abstraction: processing resource or PRSC. There are two processing resource types: CPU and CUDA.

Long-term debt

We'll continue to use the idea of long-term debt (LTD). LTD represents how much work is "owed" to each project. This increases over time in proportion to its resource share, and decreases as it uses resources. Simplified summary: when we need work for a resource, we ask the project that may have that type of job and whose LTD is greatest.

The idea of using RAC as a surrogate for LTD was set aside for various reasons.

The notion of LTD needs to span resources; otherwise, in the above example, projects A and B would each get 50% of the GPU.

On the other hand, if there's a single cross-resource LTD, and only one project has GPU jobs, then its LTD would go unboundedly negative, and the others would go unboundedly positive. This is undesirable. It could be fixed by limiting the LTD to a finite range, but this would lose information.

So the current plan is:

• There is a separate LTD for each resource
• The "overall LTD", which is used in the work-fetch decision, is the sum of the resource LTDs, weighted by the speed of the resource (FLOPs per instance-second).

Per-resource-type backoff

We need to handle the situation where e.g. there's a GPU shortfall but no projects are supplying GPU work (for either permanent or transient reasons). We don't want an overall work-fetch backoff from those projects.

Instead, we maintain a separate backoff timer per (project, PRSC). This is doubled whenever we ask for only work of that type and don't get any work; it's cleared whenever we get a job of that type.

Work-fetch state

Each PRSC has its own set of data related to work fetch. This is stored in an object of class PRSC_WORK_FETCH.

Data members of PRSC_WORK_FETCH:

ninstances

Used/set by rr_simulation()):

double shortfall: shortfall for this resource

double nidle: number of currently idle instances

Member functions of PRSC_WORK_FETCH:

rr_init(): called at the start of RR simulation. Compute project shares for this PRSC, and clear overall and per-project shortfalls.

set_nidle(): called by RR sim after initial job assignment. Set nidle to # of idle instances.

accumulate_shortfall(dt): called by RR sim for each time interval during work buf period.

shortfall += dt*(ninstances - instances in use)
for each project p not backed off for this PRSC
    p->PRSC_PROJECT_DATA.accumulate_shortfall(dt)

select_project(): select the best project to request this type of work from. It's the project not backed off for this PRSC, and for which LTD + p->shortfall is largest, also taking into consideration overworked projects etc.

accumulate_debt(dt): for each project p:

x = insts of this device used by P's running jobs
y = P's share of this device
update P's LTD

Each PRSC also needs to have some per-project data. This is stored in an object of class PRSC_PROJECT_DATA. It has the following "persistent" members (i.e., saved in state file):

backoff timer*: how long to wait until ask project for work specifically for this PRSC; double this any time we ask for work for this rsc and get none (maximum 24 hours). Clear it when we ask for work for this PRSC and get some job.

And the following transient members (used by rr_simulation()):

double share: # of instances this project should get based on resource share relative to the set of projects not backed off for this PRSC.

instances_used: # of instances currently being used

double shortfall

accumulate_shortfall(dt)

shortfall += dt*(share - instances_used)

Each project has the following work-fetch-related state:

double long_term_debt*: the amount of processing (including GPU, but expressed in terms of CPU seconds) owed to this project.

debt accounting

for each resource type R
   for each project P
      if P is not backed off for R
         P.R.LTD += share
   for each running job J, project P
      for each resource R used by J
         P.R.LTD -= share*dt

RR simulation

cpu_work_fetch.rr_init()
cuda_work_fetch.rr_init()

compute initial assignment of jobs
cpu_work_fetch.set_nidle();
cuda_work_fetch.set_nidle();

do simulation as current
on completion of an interval dt
   cpu_work_fetch.accumulate_shortfall(dt)
   cuda_work_fetch.accumulate_shortfall(dt)

Work fetch

rr_simulation()

if cuda_work_fetch.nidle
   cpu_work_fetch.shortfall = 0
   p = cuda_work_fetch.select_project()
   if p
      send_req(p)
      return
if cpu_work_fetch.nidle
   cuda_work_fetch.shortfall = 0
   p = cpu_work_fetch.select_project()
   if p
      send_req(p)
      return
if cuda_work_fetch.shortfall
   p = cuda_work_fetch.select_project()
   if p
      send_req(p)
      return
if cpu_work_fetch.shortfall
   p = cpu_work_fetch.select_project()
   if p
      send_req(p)
      return

void send_req(p)
   req.cpu_req_seconds = cpu_work_fetch.shortfall
   req.cpu_req_ninstances = cpu_work_fetch.nidle
   req.cuda_req_seconds = cuda_work_fetch.shortfall
   req.cuda_req_ninstances = cuda_work_fetch.nidle
   req.work_req_seconds = max(req.cpu_req_seconds, req.cuda_req_seconds)

Handling scheduler reply

if no jobs returned
   double backoff for each requested PRSC
else
   clear backoff for the PRSC of each returned job

Scheduler changes

global vars
   have_cpu_app_versions
   have_cuda_app_versions
per-request vars
   bool coproc_request
   ncpu_jobs_sending
   ncuda_jobs_sending
   ncpu_seconds_to_fill
   ncuda_seconds_to_fill
   seconds_to_fill
      (backwards compat; used if !coproc_request)
overall startup
   scan app versions, set have_x vars
req startup
   if send_only_cpu and no CPU app versions, don't send work
   if send_only_cuda and no CUDA app versions, don't send work
work_needed()
   need_more_cpu_jobs =
      n_cpu_jobs_sending < ninstances_cpu
      or cpu_seconds_to_fill > 0
   same for cuda
   return false if don't need more CPU or more CUDA
get_app_version
   if send_only_cpu, ignore CUDA versions
   if send_only_cuda, ignore CPU versions
when commit a job
   update n*_jobs_sending,
      n*_seconds_to_fill,
      seconds_to_fill