StarPU Handbook
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).

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 flag 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.

Performance Modelling Policies:

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 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 (deque model data aware sorted) scheduler is similar to dmdar, 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 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.

TODO: describe modular schedulers

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

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.

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

On-line task consumption measurement is currently only supported through the CL_PROFILING_POWER_CONSUMED OpenCL extension, implemented in the MoviSim simulator. 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().

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;

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.

Defining A New Scheduling Policy

A full example showing how to define a new scheduling policy is available in the StarPU sources in the directory examples/scheduler/.

The scheduler has to provide methods:

static struct starpu_sched_policy dummy_sched_policy =
{
.init_sched = init_dummy_sched,
.deinit_sched = deinit_dummy_sched,
.add_workers = dummy_sched_add_workers,
.remove_workers = dummy_sched_remove_workers,
.push_task = push_task_dummy,
.pop_task = pop_task_dummy,
.policy_name = "dummy",
.policy_description = "dummy scheduling strategy"
};

The idea is that when a task becomes ready for execution, the starpu_sched_policy::push_task method is called. When a worker is idle, the starpu_sched_policy::pop_task method is called to get a task. It is up to the scheduler to implement what is between. A simple eager scheduler is for instance to make starpu_sched_policy::push_task push the task to a global list, and make starpu_sched_policy::pop_task pop from this list.

The starpu_sched_policy section provides the exact rules that govern the methods of the policy.

Make sure to have a look at the Scheduling Policy section, which provides a list of the available functions for writing advanced schedulers, such as starpu_task_expected_length(), starpu_task_expected_data_transfer_time_for(), starpu_task_expected_energy(), etc. Other useful functions include starpu_transfer_bandwidth(), starpu_transfer_latency(), starpu_transfer_predict(), ...

Usual functions can also be used on tasks, for instance one can do

size = 0;
write = 0;
if (task->cl)
for (i = 0; i < STARPU_TASK_GET_NBUFFERS(task); i++)
{
size_t datasize = starpu_data_get_size(data);
size += datasize;
write += datasize;
}

And various queues can be used in schedulers. A variety of examples of schedulers can be read in src/sched_policies, for instance random_policy.c, eager_central_policy.c, work_stealing_policy.c

Graph-based Scheduling

For performance reasons, most of the schedulers shipped with StarPU use simple list-scheduling heuristics, assuming that the application has already set priorities. This is why they do their scheduling between when tasks become available for execution and when a worker becomes idle, without looking at the task graph.

Other heuristics can however look at the task graph. Recording the task graph is expensive, so it is not available by default, the scheduling heuristic has to set _starpu_graph_record to 1 from the initialization function, to make it available. Then the _starpu_graph* functions can be used.

src/sched_policies/graph_test_policy.c is an example of simple greedy policy which automatically computes priorities by bottom-up rank.

The idea is that while the application submits tasks, they are only pushed to a bag of tasks. When the application is finished with submitting tasks, it calls starpu_do_schedule() (or starpu_task_wait_for_all(), which calls starpu_do_schedule()), and the starpu_sched_policy::do_schedule method of the scheduler is called. This method calls _starpu_graph_compute_depths to compute the bottom-up ranks, and then uses these rank to set priorities over tasks.

It then has two priority queues, one for CPUs, and one for GPUs, and uses a dumb heuristic based on the duration of the task over CPUs and GPUs to decide between the two queues. CPU workers can then pop from the CPU priority queue, and GPU workers from the GPU priority queue.

Debugging Scheduling

All the Online Performance Tools and Offline Performance Tools can be used to get information about how well the execution proceeded, and thus the overall quality of the execution.

Precise debugging can also be performed by using the STARPU_TASK_BREAK_ON_PUSH, STARPU_TASK_BREAK_ON_SCHED, STARPU_TASK_BREAK_ON_POP, and STARPU_TASK_BREAK_ON_EXEC environment variables. By setting the job_id of a task in these environment variables, StarPU will raise SIGTRAP when the task is being scheduled, pushed, or popped by the scheduler. This means that when one notices that a task is being scheduled in a seemingly odd way, one can just reexecute the application in a debugger, with some of those variables set, and the execution will stop exactly at the scheduling points of this task, thus allowing to inspect the scheduler state, etc.