Scheduling Context Hypervisor - Building a new resizing policy

## Data Structures

struct | sc_hypervisor_policy
struct | sc_hypervisor_resize_ack
struct | types_of_workers
struct | sc_hypervisor_policy_task_pool

## Macros

#define | HYPERVISOR_REDIM_SAMPLE
#define | HYPERVISOR_START_REDIM_SAMPLE
#define | SC_NOTHING
#define | SC_IDLE
#define | SC_SPEED

## Functions

void | sc_hypervisor_policy_add_task_to_pool (struct starpu_codelet *cl, unsigned sched_ctx, uint32_t footprint, struct sc_hypervisor_policy_task_pool **task_pools, size_t data_size)
void | sc_hypervisor_policy_remove_task_from_pool (struct starpu_task *task, uint32_t footprint, struct sc_hypervisor_policy_task_pool **task_pools)
struct sc_hypervisor_policy_task_pool * | sc_hypervisor_policy_clone_task_pool (struct sc_hypervisor_policy_task_pool *tp)
void | sc_hypervisor_get_tasks_times (int nw, int nt, double times[nw][nt], int *workers, unsigned size_ctxs, struct sc_hypervisor_policy_task_pool *task_pools)
unsigned | sc_hypervisor_find_lowest_prio_sched_ctx (unsigned req_sched_ctx, int nworkers_to_move)
int * | sc_hypervisor_get_idlest_workers (unsigned sched_ctx, int *nworkers, enum starpu_worker_archtype arch)
int * | sc_hypervisor_get_idlest_workers_in_list (int *start, int *workers, int nall_workers, int *nworkers, enum starpu_worker_archtype arch)
int | sc_hypervisor_get_movable_nworkers (struct sc_hypervisor_policy_config *config, unsigned sched_ctx, enum starpu_worker_archtype arch)
int | sc_hypervisor_compute_nworkers_to_move (unsigned req_sched_ctx)
unsigned | sc_hypervisor_policy_resize (unsigned sender_sched_ctx, unsigned receiver_sched_ctx, unsigned force_resize, unsigned now)
unsigned | sc_hypervisor_policy_resize_to_unknown_receiver (unsigned sender_sched_ctx, unsigned now)
double | sc_hypervisor_get_ctx_speed (struct sc_hypervisor_wrapper *sc_w)
double | sc_hypervisor_get_slowest_ctx_exec_time (void)
double | sc_hypervisor_get_fastest_ctx_exec_time (void)
double | sc_hypervisor_get_speed_per_worker (struct sc_hypervisor_wrapper *sc_w, unsigned worker)
double | sc_hypervisor_get_speed_per_worker_type (struct sc_hypervisor_wrapper *sc_w, enum starpu_worker_archtype arch)
double | sc_hypervisor_get_ref_speed_per_worker_type (struct sc_hypervisor_wrapper *sc_w, enum starpu_worker_archtype arch)
double | sc_hypervisor_get_avg_speed (enum starpu_worker_archtype arch)
void | sc_hypervisor_check_if_consider_max (struct types_of_workers *tw)
void | sc_hypervisor_group_workers_by_type (struct types_of_workers *tw, int *total_nw)
enum starpu_worker_archtype | sc_hypervisor_get_arch_for_index (unsigned w, struct types_of_workers *tw)
unsigned | sc_hypervisor_get_index_for_arch (enum starpu_worker_archtype arch, struct types_of_workers *tw)
unsigned | sc_hypervisor_criteria_fulfilled (unsigned sched_ctx, int worker)
unsigned | sc_hypervisor_check_idle (unsigned sched_ctx, int worker)
unsigned | sc_hypervisor_check_speed_gap_btw_ctxs (unsigned *sched_ctxs, int nsched_ctxs, int *workers, int nworkers)
unsigned | sc_hypervisor_check_speed_gap_btw_ctxs_on_level (int level, int *workers_in, int nworkers_in, unsigned father_sched_ctx_id, unsigned **sched_ctxs, int *nsched_ctxs)
unsigned | sc_hypervisor_get_resize_criteria ()
struct types_of_workers * | sc_hypervisor_get_types_of_workers (int *workers, unsigned nworkers)
struct sc_hypervisor_wrapper * | sc_hypervisor_get_wrapper (unsigned sched_ctx)
unsigned * | sc_hypervisor_get_sched_ctxs ()
int | sc_hypervisor_get_nsched_ctxs ()
double | sc_hypervisor_get_elapsed_flops_per_sched_ctx (struct sc_hypervisor_wrapper *sc_w)
int | sc_hypervisor_get_nworkers_ctx (unsigned sched_ctx, enum starpu_worker_archtype arch)
double | sc_hypervisor_get_total_elapsed_flops_per_sched_ctx (struct sc_hypervisor_wrapper *sc_w)
double | sc_hypervisorsc_hypervisor_get_speed_per_worker_type (struct sc_hypervisor_wrapper *sc_w, enum starpu_worker_archtype arch)
double | sc_hypervisor_get_speed (struct sc_hypervisor_wrapper *sc_w, enum starpu_worker_archtype arch)
void | sc_hypervisor_set_config (unsigned sched_ctx, void *config)
struct sc_hypervisor_policy_config * | sc_hypervisor_get_config (unsigned sched_ctx)
void | sc_hypervisor_ctl (unsigned sched_ctx,...)
#define | SC_HYPERVISOR_MAX_IDLE
#define | SC_HYPERVISOR_MIN_WORKING
#define | SC_HYPERVISOR_PRIORITY
#define | SC_HYPERVISOR_MIN_WORKERS
#define | SC_HYPERVISOR_MAX_WORKERS
#define | SC_HYPERVISOR_GRANULARITY
#define | SC_HYPERVISOR_FIXED_WORKERS
#define | SC_HYPERVISOR_MIN_TASKS
#define | SC_HYPERVISOR_NEW_WORKERS_MAX_IDLE
#define | SC_HYPERVISOR_TIME_TO_APPLY
#define | SC_HYPERVISOR_NULL
#define | SC_HYPERVISOR_ISPEED_W_SAMPLE
#define | SC_HYPERVISOR_ISPEED_CTX_SAMPLE
#define | SC_HYPERVISOR_TIME_SAMPLE
#define | MAX_IDLE_TIME
#define | MIN_WORKING_TIME

## Detailed Description

## Data Structure Documentation

## sc_hypervisor_policy

struct sc_hypervisor_policy

Methods to implement a hypervisor resizing policy.

### Data Fields

const char * | name
unsigned | custom
void(* | size_ctxs )(unsigned *sched_ctxs, int nsched_ctxs, int *workers, int nworkers)
void(* | resize_ctxs )(unsigned *sched_ctxs, int nsched_ctxs, int *workers, int nworkers)
void(* | handle_idle_cycle )(unsigned sched_ctx, int worker)
void(* | handle_pushed_task )(unsigned sched_ctx, int worker)
void(* | handle_poped_task )(unsigned sched_ctx, int worker, struct starpu_task *task, uint32_t footprint)
void(* | handle_idle_end )(unsigned sched_ctx, int worker)
void(* | handle_post_exec_hook )(unsigned sched_ctx, int task_tag)
void(* | handle_submitted_job )(struct starpu_codelet *cl, unsigned sched_ctx, uint32_t footprint, size_t data_size)
void(* | end_ctx )(unsigned sched_ctx)
void(* | start_ctx )(unsigned sched_ctx)
void(* | init_worker )(int workerid, unsigned sched_ctx)

#### Field Documentation

## name

const char* sc_hypervisor_policy::name

Indicate the name of the policy, if there is not a custom policy, the policy corresponding to this name will be used by the hypervisor

## custom

unsigned sc_hypervisor_policy::custom

Indicate whether the policy is custom or not

## size_ctxs

void(* sc_hypervisor_policy::size_ctxs) (unsigned *sched_ctxs, int nsched_ctxs, int *workers, int nworkers)

Distribute workers to contexts even at the begining of the program

## resize_ctxs

void(* sc_hypervisor_policy::resize_ctxs) (unsigned *sched_ctxs, int nsched_ctxs, int *workers, int nworkers)

Require explicit resizing

## handle_idle_cycle

void(* sc_hypervisor_policy::handle_idle_cycle) (unsigned sched_ctx, int worker)

Called whenever the indicated worker executes another idle cycle in sched_ctx

## handle_pushed_task

void(* sc_hypervisor_policy::handle_pushed_task) (unsigned sched_ctx, int worker)

Called whenever a task is pushed on the worker’s queue corresponding to the context sched_ctx

## handle_poped_task

void(* sc_hypervisor_policy::handle_poped_task) (unsigned sched_ctx, int worker, struct starpu_task *task, uint32_t footprint)

Called whenever a task is poped from the worker’s queue corresponding to the context sched_ctx

## handle_idle_end

void(* sc_hypervisor_policy::handle_idle_end) (unsigned sched_ctx, int worker)

Called whenever a task is executed on the indicated worker and context after a long period of idle time

## handle_post_exec_hook

void(* sc_hypervisor_policy::handle_post_exec_hook) (unsigned sched_ctx, int task_tag)

Called whenever a tag task has just been executed. The table of resize requests is provided as well as the tag

## handle_submitted_job

void(* sc_hypervisor_policy::handle_submitted_job) (struct starpu_codelet *cl, unsigned sched_ctx, uint32_t footprint, size_t data_size)

the hypervisor takes a decision when a job was submitted in this ctx

## end_ctx

void(* sc_hypervisor_policy::end_ctx) (unsigned sched_ctx)

the hypervisor takes a decision when a certain ctx was deleted

## start_ctx

void(* sc_hypervisor_policy::start_ctx) (unsigned sched_ctx)

the hypervisor takes a decision when a certain ctx was registerd

## init_worker

void(* sc_hypervisor_policy::init_worker) (int workerid, unsigned sched_ctx)

the hypervisor initializes values for the workers

## sc_hypervisor_resize_ack

struct sc_hypervisor_resize_ack

Structure to check if the workers moved to another context are actually taken into account in that context.

Data Fields
int | receiver_sched_ctx | The context receiving the new workers
int * | moved_workers | List of workers required to be moved
int | nmoved_workers | Number of workers required to be moved
int * | acked_workers | List of workers that actually got in the receiver ctx. If the value corresponding to a worker is 1, this worker got moved in the new context.

## types_of_workers

struct types_of_workers

Data Fields
unsigned | ncpus |
unsigned | ncuda |
unsigned | nw |

## sc_hypervisor_policy_task_pool

struct sc_hypervisor_policy_task_pool

Task wrapper linked list

Data Fields
struct starpu_codelet * | cl | Which codelet has been executed
uint32_t | footprint | Task footprint key
unsigned | sched_ctx_id | Context the task belongs to
unsigned long | n | Number of tasks of this kind
size_t | data_size | The quantity of data(in bytes) needed by the task to execute
struct sc_hypervisor_policy_task_pool * | next | Other task kinds

## Macro Definition Documentation

## SC_HYPERVISOR_MAX_IDLE

#define SC_HYPERVISOR_MAX_IDLE

This macro is used when calling sc_hypervisor_ctl() and must be followed by 3 arguments: an array of int for the workerids to apply the condition, an int to indicate the size of the array, and a double value indicating the maximum idle time allowed for a worker before the resizing process should be triggered

## SC_HYPERVISOR_PRIORITY

#define SC_HYPERVISOR_PRIORITY

This macro is used when calling sc_hypervisor_ctl() and must be followed by 3 arguments: an array of int for the workerids to apply the condition, an int to indicate the size of the array, and an int value indicating the priority of the workers previously mentioned. The workers with the smallest priority are moved the first.

## SC_HYPERVISOR_MIN_WORKERS

#define SC_HYPERVISOR_MIN_WORKERS

This macro is used when calling sc_hypervisor_ctl() and must be followed by 1 argument(int) indicating the minimum number of workers a context should have, underneath this limit the context cannot execute.

## SC_HYPERVISOR_MAX_WORKERS

#define SC_HYPERVISOR_MAX_WORKERS

This macro is used when calling sc_hypervisor_ctl() and must be followed by 1 argument(int) indicating the maximum number of workers a context should have, above this limit the context would not be able to scale

## SC_HYPERVISOR_GRANULARITY

#define SC_HYPERVISOR_GRANULARITY

This macro is used when calling sc_hypervisor_ctl() and must be followed by 1 argument(int) indicating the granularity of the resizing process (the number of workers should be moved from the context once it is resized) This parameter is ignore for the Gflops rate based strategy (see Resizing Strategies), the number of workers that have to be moved is calculated by the strategy.

## SC_HYPERVISOR_FIXED_WORKERS

#define SC_HYPERVISOR_FIXED_WORKERS

This macro is used when calling sc_hypervisor_ctl() and must be followed by 2 arguments: an array of int for the workerids to apply the condition and an int to indicate the size of the array. These workers are not allowed to be moved from the context.

## SC_HYPERVISOR_MIN_TASKS

#define SC_HYPERVISOR_MIN_TASKS

This macro is used when calling sc_hypervisor_ctl() and must be followed by 1 argument (int) that indicated the minimum number of tasks that have to be executed before the context could be resized. This parameter is ignored for the Application Driven strategy (see Resizing Strategies) where the user indicates exactly when the resize should be done.

## SC_HYPERVISOR_NEW_WORKERS_MAX_IDLE

#define SC_HYPERVISOR_NEW_WORKERS_MAX_IDLE

This macro is used when calling sc_hypervisor_ctl() and must be followed by 1 argument, a double value indicating the maximum idle time allowed for workers that have just been moved from other contexts in the current context.

## SC_HYPERVISOR_TIME_TO_APPLY

#define SC_HYPERVISOR_TIME_TO_APPLY

This macro is used when calling sc_hypervisor_ctl() and must be followed by 1 argument (int) indicating the tag an executed task should have such that this configuration should be taken into account.

## SC_HYPERVISOR_NULL

#define SC_HYPERVISOR_NULL

This macro is used when calling sc_hypervisor_ctl() and must be followed by 1 argument

## SC_HYPERVISOR_ISPEED_W_SAMPLE

#define SC_HYPERVISOR_ISPEED_W_SAMPLE

This macro is used when calling sc_hypervisor_ctl() and must be followed by 1 argument, a double, that indicates the number of flops needed to be executed before computing the speed of a worker

## SC_HYPERVISOR_ISPEED_CTX_SAMPLE

#define SC_HYPERVISOR_ISPEED_CTX_SAMPLE

This macro is used when calling sc_hypervisor_ctl() and must be followed by 1 argument, a double, that indicates the number of flops needed to be executed before computing the speed of a context

## Function Documentation

## sc_hypervisor_get_wrapper()

struct sc_hypervisor_wrapper* sc_hypervisor_get_wrapper | ( | unsigned | sched_ctx | ) |

Return the wrapper of the given context

## sc_hypervisor_get_sched_ctxs()

unsigned* sc_hypervisor_get_sched_ctxs | ( |  | ) |

Get the list of registered contexts

## sc_hypervisor_get_nsched_ctxs()

int sc_hypervisor_get_nsched_ctxs | ( |  | ) |

Get the number of registered contexts

## sc_hypervisor_get_elapsed_flops_per_sched_ctx()

double sc_hypervisor_get_elapsed_flops_per_sched_ctx | ( | struct sc_hypervisor_wrapper * | sc_w | ) |

Get the number of flops executed by a context since last resizing (reset to 0 when a resizing is done)

## sc_hypervisor_policy_add_task_to_pool()

void sc_hypervisor_policy_add_task_to_pool | ( | struct starpu_codelet * | cl,
|  | unsigned | sched_ctx,
|  | uint32_t | footprint,
|  | struct sc_hypervisor_policy_task_pool ** | task_pools,
|  | size_t | data_size
| ) |  |

add task information to a task wrapper linked list

## sc_hypervisor_policy_remove_task_from_pool()

void sc_hypervisor_policy_remove_task_from_pool | ( | struct starpu_task * | task,
|  | uint32_t | footprint,
|  | struct sc_hypervisor_policy_task_pool ** | task_pools
| ) |  |

remove task information from a task wrapper linked list

## sc_hypervisor_policy_clone_task_pool()

struct sc_hypervisor_policy_task_pool* sc_hypervisor_policy_clone_task_pool | ( | struct sc_hypervisor_policy_task_pool * | tp | ) |

clone a task wrapper linked list

## sc_hypervisor_get_tasks_times()

void sc_hypervisor_get_tasks_times | ( | int | nw,
|  | int | nt,
|  | double | times[nw][nt],
|  | int * | workers,
|  | unsigned | size_ctxs,
|  | struct sc_hypervisor_policy_task_pool * | task_pools
| ) |  |

get the execution time of the submitted tasks out of starpu's calibration files

## sc_hypervisor_find_lowest_prio_sched_ctx()

unsigned sc_hypervisor_find_lowest_prio_sched_ctx | ( | unsigned | req_sched_ctx,
|  | int | nworkers_to_move
| ) |  |

find the context with the lowest priority in order to move some workers

## sc_hypervisor_get_idlest_workers()

int* sc_hypervisor_get_idlest_workers | ( | unsigned | sched_ctx,
|  | int * | nworkers,
|  | enum starpu_worker_archtype | arch
| ) |  |

find the first most idle workers of a contex

## sc_hypervisor_get_idlest_workers_in_list()

int* sc_hypervisor_get_idlest_workers_in_list | ( | int * | start,
|  | int * | workers,
|  | int | nall_workers,
|  | int * | nworkers,
|  | enum starpu_worker_archtype | arch
| ) |  |

find the first most idle workers in a list

## sc_hypervisor_get_movable_nworkers()

int sc_hypervisor_get_movable_nworkers | ( | struct sc_hypervisor_policy_config * | config,
|  | unsigned | sched_ctx,
|  | enum starpu_worker_archtype | arch
| ) |  |

find workers that can be moved from a context (if the constraints of min, max, etc allow this)

## sc_hypervisor_compute_nworkers_to_move()

int sc_hypervisor_compute_nworkers_to_move | ( | unsigned | req_sched_ctx | ) |

compute how many workers should be moved from this context

## sc_hypervisor_policy_resize()

unsigned sc_hypervisor_policy_resize | ( | unsigned | sender_sched_ctx,
|  | unsigned | receiver_sched_ctx,
|  | unsigned | force_resize,
|  | unsigned | now
| ) |  |

check the policy's constraints in order to resize

## sc_hypervisor_policy_resize_to_unknown_receiver()

unsigned sc_hypervisor_policy_resize_to_unknown_receiver | ( | unsigned | sender_sched_ctx,
|  | unsigned | now
| ) |  |

check the policy's constraints in order to resize and find a context willing the resources

## sc_hypervisor_get_ctx_speed()

double sc_hypervisor_get_ctx_speed | ( | struct sc_hypervisor_wrapper * | sc_w | ) |

compute the speed of a context

## sc_hypervisor_get_slowest_ctx_exec_time()

double sc_hypervisor_get_slowest_ctx_exec_time | ( | void |  | ) |

get the time of execution of the slowest context

## sc_hypervisor_get_fastest_ctx_exec_time()

double sc_hypervisor_get_fastest_ctx_exec_time | ( | void |  | ) |

get the time of execution of the fastest context

## sc_hypervisor_get_speed_per_worker()

double sc_hypervisor_get_speed_per_worker | ( | struct sc_hypervisor_wrapper * | sc_w,
|  | unsigned | worker
| ) |  |

compute the speed of a workers in a context

## sc_hypervisor_get_speed_per_worker_type()

double sc_hypervisor_get_speed_per_worker_type | ( | struct sc_hypervisor_wrapper * | sc_w,
|  | enum starpu_worker_archtype | arch
| ) |  |

compute the speed of a type of worker in a context

## sc_hypervisor_get_ref_speed_per_worker_type()

double sc_hypervisor_get_ref_speed_per_worker_type | ( | struct sc_hypervisor_wrapper * | sc_w,
|  | enum starpu_worker_archtype | arch
| ) |  |

compute the speed of a type of worker in a context depending on its history

## sc_hypervisor_get_avg_speed()

double sc_hypervisor_get_avg_speed | ( | enum starpu_worker_archtype | arch | ) |

compute the average speed of a type of worker in all ctxs from the begining of appl

## sc_hypervisor_check_if_consider_max()

void sc_hypervisor_check_if_consider_max | ( | struct types_of_workers * | tw | ) |

verify if we need to consider the max in the lp

## sc_hypervisor_group_workers_by_type()

void sc_hypervisor_group_workers_by_type | ( | struct types_of_workers * | tw,
|  | int * | total_nw
| ) |  |

get the list of workers grouped by type

## sc_hypervisor_get_arch_for_index()

enum starpu_worker_archtype sc_hypervisor_get_arch_for_index | ( | unsigned | w,
|  | struct types_of_workers * | tw
| ) |  |

get what type of worker corresponds to a certain index of types of workers

## sc_hypervisor_get_index_for_arch()

unsigned sc_hypervisor_get_index_for_arch | ( | enum starpu_worker_archtype | arch,
|  | struct types_of_workers * | tw
| ) |  |

get the index of types of workers corresponding to the type of workers indicated

## sc_hypervisor_criteria_fulfilled()

unsigned sc_hypervisor_criteria_fulfilled | ( | unsigned | sched_ctx,
|  | int | worker
| ) |  |

check if we trigger resizing or not

## sc_hypervisor_check_idle()

unsigned sc_hypervisor_check_idle | ( | unsigned | sched_ctx,
|  | int | worker
| ) |  |

check if worker was idle long enough

## sc_hypervisor_check_speed_gap_btw_ctxs()

unsigned sc_hypervisor_check_speed_gap_btw_ctxs | ( | unsigned * | sched_ctxs,
|  | int | nsched_ctxs,
|  | int * | workers,
|  | int | nworkers
| ) |  |

check if there is a speed gap btw ctxs

## sc_hypervisor_check_speed_gap_btw_ctxs_on_level()

unsigned sc_hypervisor_check_speed_gap_btw_ctxs_on_level | ( | int | level,
|  | int * | workers_in,
|  | int | nworkers_in,
|  | unsigned | father_sched_ctx_id,
|  | unsigned ** | sched_ctxs,
|  | int * | nsched_ctxs
| ) |  |

check if there is a speed gap btw ctxs on one level

## sc_hypervisor_get_resize_criteria()

unsigned sc_hypervisor_get_resize_criteria | ( |  | ) |

check what triggers resizing (idle, speed, etc.

## sc_hypervisor_get_types_of_workers()

struct types_of_workers* sc_hypervisor_get_types_of_workers | ( | int * | workers,
|  | unsigned | nworkers
| ) |  |

load information concerning the type of workers into a types_of_workers struct

## sc_hypervisor_set_config()

void sc_hypervisor_set_config | ( | unsigned | sched_ctx,
|  | void * | config
| ) |  |

Specify the configuration for a context

## sc_hypervisor_get_config()

struct sc_hypervisor_policy_config* sc_hypervisor_get_config | ( | unsigned | sched_ctx | ) |

Return the configuration of a context

## sc_hypervisor_ctl()

void sc_hypervisor_ctl | ( | unsigned | sched_ctx,
|  |  | ...
| ) |  |

Specify different parameters for the configuration of a context. The list must be zero-terminated

## sc_hypervisor_get_nworkers_ctx()

int sc_hypervisor_get_nworkers_ctx | ( | unsigned | sched_ctx,
|  | enum starpu_worker_archtype | arch
| ) |  |

Get the number of workers of a certain architecture in a context

## sc_hypervisor_get_total_elapsed_flops_per_sched_ctx()

double sc_hypervisor_get_total_elapsed_flops_per_sched_ctx | ( | struct sc_hypervisor_wrapper * | sc_w | ) |

Get the number of flops executed by a context since the begining

## sc_hypervisorsc_hypervisor_get_speed_per_worker_type()

double sc_hypervisorsc_hypervisor_get_speed_per_worker_type | ( | struct sc_hypervisor_wrapper * | sc_w,
|  | enum starpu_worker_archtype | arch
| ) |  |

Compute an average value of the cpu/cuda speed

## sc_hypervisor_get_speed()

double sc_hypervisor_get_speed | ( | struct sc_hypervisor_wrapper * | sc_w,
|  | enum starpu_worker_archtype | arch
| ) |  |

Compte the actual speed of all workers of a specific type of worker