Scheduling

# Task Scheduling Policies

The basics of the scheduling policy are the following:

- The scheduler gets to schedule tasks (`push` operation) when they become ready to be executed, i.e. they are not waiting for some tags, data dependencies or task dependencies.
- Workers pull tasks (`pop` operation) one by one from the scheduler.

This means scheduling policies usually contain at least one queue of tasks to store them between the time when they become available, and the time when a worker gets to grab them.

By default, StarPU uses the work-stealing scheduler `lws`. This is because it provides correct load balance and locality even if the application codelets do not have performance models. Other non-modelling scheduling policies can be selected among the list below, thanks to the environment variable STARPU_SCHED. For instance `export STARPU_SCHED=dmda` . Use `help` to get the list of available schedulers.

## Non Performance Modelling Policies

- The eager scheduler uses a central task queue, from which all workers draw tasks to work on concurrently. This however does not permit to prefetch data since the scheduling decision is taken late. If a task has a non-0 priority, it is put at the front of the queue.
- The random scheduler uses a queue per worker, and distributes tasks randomly according to assumed worker overall performance.
- The ws (work stealing) scheduler uses a queue per worker, and schedules a task on the worker which released it by default. When a worker becomes idle, it steals a task from the most loaded worker.
- The lws (locality work stealing) scheduler uses a queue per worker, and schedules a task on the worker which released it by default. When a worker becomes idle, it steals a task from neighbour workers. It also takes into account priorities.
- The prio scheduler also uses a central task queue, but sorts tasks by priority specified by the programmer (between -5 and 5).
- The heteroprio scheduler uses different priorities for the different processing units. This scheduler must be configured to work correclty and to expect high-performance as described in the corresponding section.

## Performance Model-Based Task Scheduling Policies

If (and only if) your application codelets have performance models (Performance Model Example), you should change the scheduler thanks to the environment variable STARPU_SCHED, to select one of the policies below, in order to take advantage of StarPU's performance modelling. For instance `export STARPU_SCHED=dmda` . Use `help` to get the list of available schedulers.

Note: Depending on the performance model type chosen, some preliminary calibration runs may be needed for the model to converge. If the calibration has not been done, or is insufficient yet, or if no performance model is specified for a codelet, every task built from this codelet will be scheduled using an eager fallback policy.

Troubleshooting: Configuring and recompiling StarPU using the --enable-verbose `configure` option displays some statistics at the end of execution about the percentage of tasks which have been scheduled by a DM* family policy using performance model hints. A low or zero percentage may be the sign that performance models are not converging or that codelets do not have performance models enabled.

- The dm (deque model) scheduler takes task execution performance models into account to perform a HEFT-similar scheduling strategy: it schedules tasks where their termination time will be minimal. The difference with HEFT is that dm schedules tasks as soon as they become available, and thus in the order they become available, without taking priorities into account.
- The dmda (deque model data aware) scheduler is similar to dm, but it also takes into account data transfer time.
- The dmdap (deque model data aware prio) scheduler is similar to dmda, except that it sorts tasks by priority order, which allows to become even closer to HEFT by respecting priorities after having made the scheduling decision (but it still schedules tasks in the order they become available).
- The dmdar (deque model data aware ready) scheduler is similar to dmda, but it also privileges tasks whose data buffers are already available on the target device.
- The dmdas combines dmdap and dmdas: it sorts tasks by priority order, but for a given priority it will privilege tasks whose data buffers are already available on the target device.
- The dmdasd (deque model data aware sorted decision) scheduler is similar to dmdas, except that when scheduling a task, it takes into account its priority when computing the minimum completion time, since this task may get executed before others, and thus the latter should be ignored.
- The heft (heterogeneous earliest finish time) scheduler is a deprecated alias for dmda.
- The pheft (parallel HEFT) scheduler is similar to dmda, it also supports parallel tasks (still experimental). Should not be used when several contexts using it are being executed simultaneously.
- The peager (parallel eager) scheduler is similar to eager, it also supports parallel tasks (still experimental). Should not be used when several contexts using it are being executed simultaneously.

## Modularized Schedulers

StarPU provides a powerful way to implement schedulers, as documented in Defining A New Modular Scheduling Policy . It is currently shipped with the following pre-defined Modularized Schedulers :

- modular-eager , modular-eager-prefetching are eager-based Schedulers (without and with prefetching)), they are
  naive schedulers, which try to map a task on the first available resource they find. The prefetching variant queues several tasks in advance to be able to do data prefetching. This may however degrade load balancing a bit.
- modular-prio, modular-prio-prefetching, modular-eager-prio are prio-based Schedulers (without / with prefetching):, similar to Eager-Based Schedulers. Can handle tasks which have a defined priority and schedule them accordingly. The modular-eager-prio variant integrates the eager and priority queue in a single component. This allows it to do a better job at pushing tasks.
- modular-random, modular-random-prio, modular-random-prefetching, modular-random-prio-prefetching are random-based Schedulers (without/with prefetching) :
  Select randomly a resource to be mapped on for each task.
- modular-ws) implements Work Stealing: Maps tasks to workers in round robin, but allows workers to steal work from other workers.
- modular-heft, modular-heft2, and modular-heft-prio are HEFT Schedulers :
  Maps tasks to workers using a heuristic very close to Heterogeneous Earliest Finish Time. It needs that every task submitted to StarPU have a defined performance model (Performance Model Calibration) to work efficiently, but can handle tasks without a performance model. modular-heft just takes tasks by priority order. modular-heft2 takes at most 5 tasks of the same priority and checks which one fits best. modular-heft-prio is similar to modular-heft, but only decides the memory node, not the exact worker, just pushing tasks to one central queue per memory node.
- modular-heteroprio is a Heteroprio Scheduler:
  Maps tasks to worker similarly to HEFT, but first attribute accelerated tasks to GPUs, then not-so-accelerated tasks to CPUs.

# Task Distribution Vs Data Transfer

Distributing tasks to balance the load induces data transfer penalty. StarPU thus needs to find a balance between both. The target function that the scheduler `dmda` of StarPU tries to minimize is `alpha * T_execution + beta * T_data_transfer`, where `T_execution` is the estimated execution time of the codelet (usually accurate), and `T_data_transfer` is the estimated data transfer time. The latter is estimated based on bus calibration before execution start, i.e. with an idle machine, thus without contention. You can force bus re-calibration by running the tool `starpu_calibrate_bus`. The beta parameter defaults to `1`, but it can be worth trying to tweak it by using `export STARPU_SCHED_BETA=2` (STARPU_SCHED_BETA) for instance, since during real application execution, contention makes transfer times bigger. This is of course imprecise, but in practice, a rough estimation already gives the good results that a precise estimation would give.

# Energy-based Scheduling

Note: by default StarPU does not let CPU workers sleep, to let them react to task release as quickly as possible. For idle time to really let CPU cores save energy, one needs to use the --enable-blocking-drivers configuration option.

If the application can provide some energy consumption performance model (through the field starpu_codelet::energy_model), StarPU will take it into account when distributing tasks. The target function that the scheduler `dmda` minimizes becomes `alpha * T_execution + beta * T_data_transfer + gamma * Consumption` , where `Consumption` is the estimated task consumption in Joules. To tune this parameter, use `export STARPU_SCHED_GAMMA=3000` (STARPU_SCHED_GAMMA) for instance, to express that each Joule (i.e kW during 1000us) is worth 3000us execution time penalty. Setting `alpha` and `beta` to zero permits to only take into account energy consumption.

This is however not sufficient to correctly optimize energy: the scheduler would simply tend to run all computations on the most energy-conservative processing unit. To account for the consumption of the whole machine (including idle processing units), the idle power of the machine should be given by setting `export STARPU_IDLE_POWER=200` (STARPU_IDLE_POWER) for 200W, for instance. This value can often be obtained from the machine power supplier, e.g. by running

`ipmitool -I lanplus -H mymachine-ipmi -U myuser -P mypasswd sdr type Current`

The energy actually consumed by the total execution can be displayed by setting `export STARPU_PROFILING=1 STARPU_WORKER_STATS=1` (STARPU_PROFILING and STARPU_WORKER_STATS).

For OpenCL devices, on-line task consumption measurement is currently supported through the `CL_PROFILING_POWER_CONSUMED` OpenCL extension, implemented in the MoviSim simulator.

For CUDA devices, on-line task consumption measurement is supported on V100 cards and beyond. This however only works for quite long tasks, since the measurement granularity is about 10ms.

Applications can however provide explicit measurements by using the function starpu_perfmodel_update_history() (examplified in Performance Model Example with the `energy_model` performance model). Fine-grain measurement is often not feasible with the feedback provided by the hardware, so the user can for instance run a given task a thousand times, measure the global consumption for that series of tasks, divide it by a thousand, repeat for varying kinds of tasks and task sizes, and eventually feed StarPU with these manual measurements through starpu_perfmodel_update_history(). For instance, for CUDA devices, `nvidia-smi -q -d POWER` can be used to get the current consumption in Watt. Multiplying this value by the average duration of a single task gives the consumption of the task in Joules, which can be given to starpu_perfmodel_update_history().

Another way to provide the energy performance is to define a perfmodel with starpu_perfmodel::type STARPU_PER_ARCH, and set the starpu_perfmodel::arch_cost_function field to a function which shall return the estimated consumption of the task in Joules. Such a function can for instance use starpu_task_expected_length() on the task (in µs), multiplied by the typical power consumption of the device, e.g. in W, and divided by 1000000. to get Joules.

# Static Scheduling

In some cases, one may want to force some scheduling, for instance force a given set of tasks to GPU0, another set to GPU1, etc. while letting some other tasks be scheduled on any other device. This can indeed be useful to guide StarPU into some work distribution, while still letting some degree of dynamism. For instance, to force execution of a task on CUDA0:

task->execute_on_a_specific_worker = 1;
task->workerid = starpu_worker_get_by_type(STARPU_CUDA_WORKER, 0);
starpu_worker_get_by_type
int starpu_worker_get_by_type(enum starpu_worker_archtype type, int num)
STARPU_CUDA_WORKER
@ STARPU_CUDA_WORKER
Definition: starpu_worker.h:65

or equivalently

starpu_task_insert(&cl, ..., STARPU_EXECUTE_ON_WORKER, starpu_worker_get_by_type(STARPU_CUDA_WORKER, 0), ...);
STARPU_EXECUTE_ON_WORKER
#define STARPU_EXECUTE_ON_WORKER
Definition: starpu_task_util.h:159
starpu_task_insert
int starpu_task_insert(struct starpu_codelet *cl,...)

One can also specify a set worker(s) which are allowed to take the task, as an array of bit, for instance to allow workers 2 and 42:

task->workerids = calloc(2,sizeof(uint32_t));
task->workerids[2/32] |= (1 << (2%32));
task->workerids[42/32] |= (1 << (42%32));
task->workerids_len = 2;

One can also specify the order in which tasks must be executed by setting the starpu_task::workerorder field. If this field is set to a non-zero value, it provides the per-worker consecutive order in which tasks will be executed, starting from 1. For a given of such task, the worker will thus not execute it before all the tasks with smaller order value have been executed, notably in case those tasks are not available yet due to some dependencies. This eventually gives total control of task scheduling, and StarPU will only serve as a "self-timed" task runtime. Of course, the provided order has to be runnable, i.e. a task should should not depend on another task bound to the same worker with a bigger order.

Note however that using scheduling contexts while statically scheduling tasks on workers could be tricky. Be careful to schedule the tasks exactly on the workers of the corresponding contexts, otherwise the workers' corresponding scheduling structures may not be allocated or the execution of the application may deadlock. Moreover, the hypervisor should not be used when statically scheduling tasks.

# Heteroprio

Within Heteroprio, one priority per processing unit type is assigned to each task, such that a task has several priorities. Each worker pops the task that has the highest priority for the hardware type it uses, which could be CPU or CUDA for example. Therefore, the priorities has to be used to manage the critical path, but also to promote the consumption of tasks by the more appropriate workers.

The tasks are stored inside buckets, where each bucket corresponds to a priority set. Then each worker uses an indirect access array to know the order in which it should access the buckets. Moreover, all the tasks inside a bucket must be compatible with all the processing units that may access it (at least).

As an example, see the following code where we have 5 types of tasks. CPU workers can compute all of them, but CUDA workers can only execute tasks of types 0 and 1, and is expected to go 20 and 30 time faster than the CPU, respectively.

#include <starpu_heteroprio.h>
struct starpu_conf conf;
starpu_conf_init(&conf);
conf.sched_policy_name = "heteroprio";
conf.sched_policy_init = &init_heteroprio;
starpu_init(&conf);
void init_heteroprio(unsigned sched_ctx) {
// CPU uses 5 buckets and visits them in the natural order
starpu_heteroprio_set_nb_prios(ctx, STARPU_CPU_IDX, 5);
// It uses direct mapping idx => idx
for(unsigned idx = 0; idx < 5; ++idx){
starpu_heteroprio_set_mapping(ctx, STARPU_CPU_IDX, idx, idx);
// If there is no CUDA worker we must tell that CPU is faster
starpu_heteroprio_set_faster_arch(ctx, STARPU_CPU_IDX, idx);
}
if(starpu_cuda_worker_get_count()){
// CUDA is enabled and uses 2 buckets
starpu_heteroprio_set_nb_prios(ctx, STARPU_CUDA_IDX, 2);
// CUDA will first look at bucket 1
starpu_heteroprio_set_mapping(ctx, STARPU_CUDA_IDX, 0, 1);
// CUDA will then look at bucket 2
starpu_heteroprio_set_mapping(ctx, STARPU_CUDA_IDX, 1, 2);
// For bucket 1 CUDA is the fastest
starpu_heteroprio_set_faster_arch(ctx, STARPU_CUDA_IDX, 1);
// And CPU is 30 times slower
starpu_heteroprio_set_arch_slow_factor(ctx, STARPU_CPU_IDX, 1, 30.0f);
// For bucket 0 CUDA is the fastest
starpu_heteroprio_set_faster_arch(ctx, STARPU_CUDA_IDX, 0);
// And CPU is 20 times slower
starpu_heteroprio_set_arch_slow_factor(ctx, STARPU_CPU_IDX, 0, 20.0f);
}
}
starpu_conf_init
int starpu_conf_init(struct starpu_conf *conf)
starpu_init
int starpu_init(struct starpu_conf *conf) STARPU_WARN_UNUSED_RESULT
starpu_conf
Definition: starpu.h:103
starpu_cuda_worker_get_count
unsigned starpu_cuda_worker_get_count(void)
starpu_heteroprio.h
starpu_heteroprio_set_mapping
void starpu_heteroprio_set_mapping(unsigned sched_ctx_id, enum starpu_heteroprio_types arch, unsigned source_prio, unsigned dest_bucket_id)
starpu_heteroprio_set_faster_arch
void starpu_heteroprio_set_faster_arch(unsigned sched_ctx_id, enum starpu_heteroprio_types arch, unsigned bucket_id)
starpu_heteroprio_set_nb_prios
void starpu_heteroprio_set_nb_prios(unsigned sched_ctx_id, enum starpu_heteroprio_types arch, unsigned max_prio)
starpu_heteroprio_set_arch_slow_factor
void starpu_heteroprio_set_arch_slow_factor(unsigned sched_ctx_id, enum starpu_heteroprio_types arch, unsigned bucket_id, float slow_factor)

Then, when a task is inserted the priority of the task will be used to select in which bucket is has to be stored. So, in the given example, the priority of a task will be between 0 and 4 included. However, tasks of priorities 0-1 must provide CPU and CUDA kernels, and tasks of priorities 2-4 must provide CPU kernels (at least).