StarPU Handbook

Scheduling Context Hypervisor

# What Is The Hypervisor

StarPU proposes a platform to construct Scheduling Contexts, to delete and modify them dynamically. A parallel kernel, can thus be isolated into a scheduling context and interferences between several parallel kernels are avoided. If users know exactly how many workers each scheduling context needs, they can assign them to the contexts at their creation time or modify them during the execution of the program.

The Scheduling Context Hypervisor Plugin is available for users who do not dispose of a regular parallelism, who cannot know in advance the exact size of the context and need to resize the contexts according to the behavior of the parallel kernels.

The Hypervisor receives information from StarPU concerning the execution of the tasks, the efficiency of the resources, etc. and it decides accordingly when and how the contexts can be resized. Basic strategies of resizing scheduling contexts already exist but a platform for implementing additional custom ones is available.

# Start the Hypervisor

The Hypervisor must be initialized once at the beginning of the application. At this point a resizing policy should be indicated. This strategy depends on the information the application is able to provide to the hypervisor as well as on the accuracy needed for the resizing procedure. For example, the application may be able to provide an estimation of the workload of the contexts. In this situation the hypervisor may decide what resources the contexts need. However, if no information is provided the hypervisor evaluates the behavior of the resources and of the application and makes a guess about the future. The hypervisor resizes only the registered contexts.

# Interrogate The Runtime

The runtime provides the hypervisor with information concerning the behavior of the resources and the application. This is done by using the `performance_counters` which represent callbacks indicating when the resources are idle or not efficient, when the application submits tasks or when it becomes to slow.

# Trigger the Hypervisor

The resizing is triggered either when the application requires it (sc_hypervisor_resize_ctxs()) or when the initials distribution of resources alters the performance of the application (the application is to slow or the resource are idle for too long time). If the environment variable SC_HYPERVISOR_TRIGGER_RESIZE is set to `speed` the monitored speed of the contexts is compared to a theoretical value computed with a linear program, and the resizing is triggered whenever the two values do not correspond. Otherwise, if the environment variable is set to `idle` the hypervisor triggers the resizing algorithm whenever the workers are idle for a period longer than the threshold indicated by the programmer. When this happens different resizing strategy are applied that target minimizing the total execution of the application, the instant speed or the idle time of the resources.

# Resizing Strategies

The plugin proposes several strategies for resizing the scheduling context.

The Application driven strategy uses users's input concerning the moment when they want to resize the contexts. Thus, users tag the task that should trigger the resizing process. One can set directly the field starpu_task::hypervisor_tag or use the macro STARPU_HYPERVISOR_TAG in the function starpu_task_insert().

task.hypervisor_tag = 2;

or

starpu_task_insert(&codelet,
...,
STARPU_HYPERVISOR_TAG, 2,
0);
STARPU_HYPERVISOR_TAG
#define STARPU_HYPERVISOR_TAG
Definition: starpu_task_util.h:112
starpu_task_insert
int starpu_task_insert(struct starpu_codelet *cl,...)

Then users have to indicate that when a task with the specified tag is executed the contexts should resize.

sc_hypervisor_resize(sched_ctx, 2);

Users can use the same tag to change the resizing configuration of the contexts if they consider it necessary.

sc_hypervisor_ctl(sched_ctx,
SC_HYPERVISOR_MIN_WORKERS, 6,
SC_HYPERVISOR_MAX_WORKERS, 12,
SC_HYPERVISOR_TIME_TO_APPLY, 2,
NULL);
sc_hypervisor_ctl
void sc_hypervisor_ctl(unsigned sched_ctx,...)
SC_HYPERVISOR_MIN_WORKERS
#define SC_HYPERVISOR_MIN_WORKERS
Definition: sc_hypervisor_config.h:58
SC_HYPERVISOR_MAX_WORKERS
#define SC_HYPERVISOR_MAX_WORKERS
Definition: sc_hypervisor_config.h:66
SC_HYPERVISOR_TIME_TO_APPLY
#define SC_HYPERVISOR_TIME_TO_APPLY
Definition: sc_hypervisor_config.h:110

The Idleness based strategy moves workers unused in a certain context to another one needing them. (see Scheduling Context Hypervisor - Regular usage)

int workerids[3] = {1, 3, 10};
int workerids2[9] = {0, 2, 4, 5, 6, 7, 8, 9, 11};
sc_hypervisor_ctl(sched_ctx_id,
SC_HYPERVISOR_MAX_IDLE, workerids, 3, 10000.0,
SC_HYPERVISOR_MAX_IDLE, workerids2, 9, 50000.0,
NULL);
SC_HYPERVISOR_MAX_IDLE
#define SC_HYPERVISOR_MAX_IDLE
Definition: sc_hypervisor_config.h:39

The Gflops/s rate based strategy resizes the scheduling contexts such that they all finish at the same time. The speed of each of them is computed and once one of them is significantly slower the resizing process is triggered. In order to do these computations users have to input the total number of instructions needed to be executed by the parallel kernels and the number of instruction to be executed by each task.

The number of flops to be executed by a context are passed as parameter when they are registered to the hypervisor,

sc_hypervisor_register_ctx(sched_ctx_id, flops)
sc_hypervisor_register_ctx
void sc_hypervisor_register_ctx(unsigned sched_ctx, double total_flops)

and the one to be executed by each task are passed when the task is submitted. The corresponding field is starpu_task::flops and the corresponding macro in the function starpu_task_insert() is STARPU_FLOPS (Caution: but take care of passing a double, not an integer, otherwise parameter passing will be bogus). When the task is executed the resizing process is triggered.

task.flops = 100;

or

starpu_task_insert(&codelet,
...,
STARPU_FLOPS, (double) 100,
0);
STARPU_FLOPS
#define STARPU_FLOPS
Definition: starpu_task_util.h:120

The Feft strategy uses a linear program to predict the best distribution of resources such that the application finishes in a minimum amount of time. As for the Gflops/s rate strategy the programmers has to indicate the total number of flops to be executed when registering the context. This number of flops may be updated dynamically during the execution of the application whenever this information is not very accurate from the beginning. The function sc_hypervisor_update_diff_total_flops() is called in order to add or to remove a difference to the flops left to be executed. Tasks are provided also the number of flops corresponding to each one of them. During the execution of the application the hypervisor monitors the consumed flops and recomputes the time left and the number of resources to use. The speed of each type of resource is (re)evaluated and inserter in the linear program in order to better adapt to the needs of the application.

The Teft strategy uses a linear program too, that considers all the types of tasks and the number of each of them and it tries to allocates resources such that the application finishes in a minimum amount of time. A previous calibration of StarPU would be useful in order to have good predictions of the execution time of each type of task.

The types of tasks may be determines directly by the hypervisor when they are submitted. However there are applications that do not expose all the graph of tasks from the beginning. In this case in order to let the hypervisor know about all the tasks the function sc_hypervisor_set_type_of_task() will just inform the hypervisor about future tasks without submitting them right away.

The Ispeed strategy divides the execution of the application in several frames. For each frame the hypervisor computes the speed of the contexts and tries making them run at the same speed. The strategy requires less contribution from users as the hypervisor requires only the size of the frame in terms of flops.

int workerids[3] = {1, 3, 10};
int workerids2[9] = {0, 2, 4, 5, 6, 7, 8, 9, 11};
sc_hypervisor_ctl(sched_ctx_id,
SC_HYPERVISOR_ISPEED_W_SAMPLE, workerids, 3, 2000000000.0,
SC_HYPERVISOR_ISPEED_W_SAMPLE, workerids2, 9, 200000000000.0,
SC_HYPERVISOR_ISPEED_CTX_SAMPLE, 60000000000.0,
NULL);
SC_HYPERVISOR_ISPEED_CTX_SAMPLE
#define SC_HYPERVISOR_ISPEED_CTX_SAMPLE
Definition: sc_hypervisor_config.h:130
SC_HYPERVISOR_ISPEED_W_SAMPLE
#define SC_HYPERVISOR_ISPEED_W_SAMPLE
Definition: sc_hypervisor_config.h:123

The Throughput strategy focuses on maximizing the throughput of the resources and resizes the contexts such that the machine is running at its maximum efficiency (maximum instant speed of the workers).

# Defining A New Hypervisor Policy

While Scheduling Context Hypervisor Plugin comes with a variety of resizing policies (see Resizing Strategies), it may sometimes be desirable to implement custom policies to address specific problems. The API described below allows users to write their own resizing policy.

Here an example of how to define a new policy

struct sc_hypervisor_policy dummy_policy =
{
.handle_poped_task = dummy_handle_poped_task,
.handle_pushed_task = dummy_handle_pushed_task,
.handle_idle_cycle = dummy_handle_idle_cycle,
.handle_idle_end = dummy_handle_idle_end,
.handle_post_exec_hook = dummy_handle_post_exec_hook,
.custom = 1,
.name = "dummy"
};
sc_hypervisor_policy::handle_poped_task
void(* handle_poped_task)(unsigned sched_ctx, int worker, struct starpu_task *task, uint32_t footprint)
Definition: sc_hypervisor.h:76
sc_hypervisor_policy
Definition: sc_hypervisor.h:36