starpu-max/doc/doxygen/chapters/10scheduling_context_hypervisor.doxy

/*
 * This file is part of the StarPU Handbook.
 * Copyright (C) 2009--2011  Universit@'e de Bordeaux 1
 * Copyright (C) 2010, 2011, 2012, 2013, 2014  Centre National de la Recherche Scientifique
 * Copyright (C) 2011, 2012 Institut National de Recherche en Informatique et Automatique
 * See the file version.doxy for copying conditions.
 */

/*! \page SchedulingContextHypervisor Scheduling Context Hypervisor

\section WhatIsTheHypervisor 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 the user knows exactly how
many workers each scheduling context needs, he 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 the 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.

\section StartTheHypervisor 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.

\section InterrogateTheRuntime 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 <c>performance_counters</c> which represent callbacks indicating 
when the resources are idle or not efficient, when the application 
submits tasks or when it becomes to slow.

\section TriggerTheHypervisor Trigger the Hypervisor

The resizing is triggered either when the application requires it 
(<c> sc_hypervisor_resize_ctxs </c>) 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 <c>SC_HYPERVISOR_TRIGGER_RESIZE</c> is set to <c>speed</c> 
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 <c>idle</c> 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.

\section ResizingStrategies Resizing Strategies

The plugin proposes several strategies for resizing the scheduling context.

The <b>Application driven</b> strategy uses the user's input concerning the moment when he wants to resize the contexts.
Thus, the users tags the task that should trigger the resizing
process. We can set directly the field starpu_task::hypervisor_tag or
use the macro ::STARPU_HYPERVISOR_TAG in the function
starpu_task_insert().

\code{.c}
task.hypervisor_tag = 2;
\endcode

or

\code{.c}
starpu_task_insert(&codelet,
		    ...,
		    STARPU_HYPERVISOR_TAG, 2,
                    0);
\endcode

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

\code{.c}
sc_hypervisor_resize(sched_ctx, 2);
\endcode

The user can use the same tag to change the resizing configuration of the contexts if he considers it necessary.

\code{.c}
sc_hypervisor_ctl(sched_ctx,
                    SC_HYPERVISOR_MIN_WORKERS, 6,
                    SC_HYPERVISOR_MAX_WORKERS, 12,
                    SC_HYPERVISOR_TIME_TO_APPLY, 2,
                    NULL);
\endcode


The <b>Idleness</b> based strategy moves workers unused in a certain context to another one needing them.
(see \ref UsersInputInTheResizingProcess "Users’ Input In The Resizing Process")

\code{.c}
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);
\endcode

The <b>Gflops rate</b> 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 the user has 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,
 (<c>sc_hypervisor_register_ctx(sched_ctx_id, flops)</c>) 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
 (<b>Caution</b>: 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.

\code{.c}
task.flops = 100;
\endcode

or

\code{.c}
starpu_task_insert(&codelet,
                    ...,
                    STARPU_FLOPS, (double) 100,
                    0);
\endcode

The <b>Feft</b> 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 <b>Gflops rate </b>
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 <c>sc_hypervisor_update_diff_total_flop </c> is called in order add or 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 <b>Teft</b> 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
<c> sc_hypervisor_set_type_of_task </c> will just inform the hypervisor about future tasks
without submitting them right away.

The <b>Ispeed </b> 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 the user as
the hypervisor requires only the size of the frame in terms of flops.

\code{.c}
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);
\endcode

The <b>Throughput </b> 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).

\section DefiningANewHypervisorPolicy Defining A New Hypervisor Policy

While Scheduling Context Hypervisor Plugin comes with a variety of
resizing policies (see \ref ResizingStrategies), 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

\code{.c}
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"
};
\endcode


*/