StarPU Handbook
Scheduling Policy

TODO. While StarPU comes with a variety of scheduling policies (see Task Scheduling Policies), it may sometimes be desirable to implement custom policies to address specific problems. The API described below allows users to write their own scheduling policy. More...

Data Structures

struct  starpu_sched_policy
 

Macros

#define STARPU_MAXIMPLEMENTATIONS
 

Functions

struct starpu_sched_policy ** starpu_sched_get_predefined_policies ()
 
void starpu_worker_get_sched_condition (int workerid, starpu_pthread_mutex_t **sched_mutex, starpu_pthread_cond_t **sched_cond)
 
int starpu_wake_worker (int workerid)
 
int starpu_sched_set_min_priority (int min_prio)
 
int starpu_sched_set_max_priority (int max_prio)
 
int starpu_sched_get_min_priority (void)
 
int starpu_sched_get_max_priority (void)
 
int starpu_push_local_task (int workerid, struct starpu_task *task, int back)
 
int starpu_push_task_end (struct starpu_task *task)
 
int starpu_worker_can_execute_task (unsigned workerid, struct starpu_task *task, unsigned nimpl)
 
int starpu_worker_can_execute_task_impl (unsigned workerid, struct starpu_task *task, unsigned *impl_mask)
 
int starpu_worker_can_execute_task_first_impl (unsigned workerid, struct starpu_task *task, unsigned *nimpl)
 
uint32_t starpu_task_footprint (struct starpu_perfmodel *model, struct starpu_task *task, struct starpu_perfmodel_arch *arch, unsigned nimpl)
 
uint32_t starpu_task_data_footprint (struct starpu_task *task)
 
double starpu_task_expected_length (struct starpu_task *task, struct starpu_perfmodel_arch *arch, unsigned nimpl)
 
double starpu_worker_get_relative_speedup (struct starpu_perfmodel_arch *perf_arch)
 
double starpu_task_expected_data_transfer_time (unsigned memory_node, struct starpu_task *task)
 
double starpu_data_expected_transfer_time (starpu_data_handle_t handle, unsigned memory_node, enum starpu_data_access_mode mode)
 
double starpu_task_expected_energy (struct starpu_task *task, struct starpu_perfmodel_arch *arch, unsigned nimpl)
 
double starpu_task_expected_conversion_time (struct starpu_task *task, struct starpu_perfmodel_arch *arch, unsigned nimpl)
 
int starpu_get_prefetch_flag (void)
 
int starpu_prefetch_task_input_on_node (struct starpu_task *task, unsigned node)
 
int starpu_idle_prefetch_task_input_on_node (struct starpu_task *task, unsigned node)
 
void starpu_sched_ctx_worker_shares_tasks_lists (int workerid, int sched_ctx_id)
 

Scheduling Contexts Basic API

#define STARPU_NMAX_SCHED_CTXS
 

Detailed Description

TODO. While StarPU comes with a variety of scheduling policies (see Task Scheduling Policies), it may sometimes be desirable to implement custom policies to address specific problems. The API described below allows users to write their own scheduling policy.


Data Structure Documentation

◆ starpu_sched_policy

struct starpu_sched_policy

This structure contains all the methods that implement a scheduling policy. An application may specify which scheduling strategy in the field starpu_conf::sched_policy passed to the function starpu_init().

For each task going through the scheduler, the following methods get called in the given order:

For each task not going through the scheduler (because starpu_task::execute_on_a_specific_worker was set), these get called:

Data Fields

void(* init_sched )(unsigned sched_ctx_id)
 
void(* deinit_sched )(unsigned sched_ctx_id)
 
int(* push_task )(struct starpu_task *)
 
double(* simulate_push_task )(struct starpu_task *)
 
void(* push_task_notify )(struct starpu_task *, int workerid, int perf_workerid, unsigned sched_ctx_id)
 
struct starpu_task *(* pop_task )(unsigned sched_ctx_id)
 
struct starpu_task *(* pop_every_task )(unsigned sched_ctx_id)
 
void(* submit_hook )(struct starpu_task *task)
 
void(* pre_exec_hook )(struct starpu_task *)
 
void(* post_exec_hook )(struct starpu_task *)
 
void(* do_schedule )(unsigned sched_ctx_id)
 
void(* add_workers )(unsigned sched_ctx_id, int *workerids, unsigned nworkers)
 
void(* remove_workers )(unsigned sched_ctx_id, int *workerids, unsigned nworkers)
 
const char * policy_name
 
const char * policy_description
 

Field Documentation

◆ init_sched

void(* starpu_sched_policy::init_sched)(unsigned sched_ctx_id)

Initialize the scheduling policy, called before any other method.

◆ deinit_sched

void(* starpu_sched_policy::deinit_sched)(unsigned sched_ctx_id)

Cleanup the scheduling policy, called before any other method.

◆ push_task

int(* starpu_sched_policy::push_task)(struct starpu_task *)

Insert a task into the scheduler, called when the task becomes ready for execution.

◆ push_task_notify

void(* starpu_sched_policy::push_task_notify)(struct starpu_task *, int workerid, int perf_workerid, unsigned sched_ctx_id)

Notify the scheduler that a task was pushed on a given worker. This method is called when a task that was explicitly assigned to a worker becomes ready and is about to be executed by the worker. This method therefore permits to keep the state of the scheduler coherent even when StarPU bypasses the scheduling strategy.

◆ pop_task

struct starpu_task *(* starpu_sched_policy::pop_task)(unsigned sched_ctx_id)

Get a task from the scheduler. If this method returns NULL, the worker will start sleeping. If later on some task are pushed for this worker, starpu_wake_worker() must be called to wake the worker so it can call the pop_task() method again.

The mutex associated to the worker is already taken when this method is called. This method may release it (e.g. for scalability reasons when doing work stealing), but it must acquire it again before taking the decision whether to return a task or NULL, so the atomicity of deciding to return NULL and making the worker actually sleep is preserved. Otherwise in simgrid or blocking driver mode the worker might start sleeping while a task has just been pushed for it.

If this method is defined as NULL, the worker will only execute tasks from its local queue. In this case, the push_task method should use the starpu_push_local_task method to assign tasks to the different workers.

◆ pop_every_task

struct starpu_task *(* starpu_sched_policy::pop_every_task)(unsigned sched_ctx_id)

Remove all available tasks from the scheduler (tasks are chained by the means of the field starpu_task::prev and starpu_task::next). The mutex associated to the worker is already taken when this method is called. This is currently not used and can be discarded.

◆ submit_hook

void(* starpu_sched_policy::submit_hook)(struct starpu_task *)

Optional field. This method is called when a task is submitted.

◆ pre_exec_hook

void(* starpu_sched_policy::pre_exec_hook)(struct starpu_task *)

Optional field. This method is called every time a task is starting.

◆ post_exec_hook

void(* starpu_sched_policy::post_exec_hook)(struct starpu_task *)

Optional field. This method is called every time a task has been executed.

◆ do_schedule

void(* starpu_sched_policy::do_schedule)(unsigned sched_ctx_id)

Optional field. This method is called when it is a good time to start scheduling tasks. This is notably called when the application calls starpu_task_wait_for_all or starpu_do_schedule explicitly.

◆ add_workers

void(* starpu_sched_policy::add_workers)(unsigned sched_ctx_id, int *workerids, unsigned nworkers)

Initialize scheduling structures corresponding to each worker used by the policy.

◆ remove_workers

void(* starpu_sched_policy::remove_workers)(unsigned sched_ctx_id, int *workerids, unsigned nworkers)

Deinitialize scheduling structures corresponding to each worker used by the policy.

◆ policy_name

const char * starpu_sched_policy::policy_name

Optional field. Name of the policy.

◆ policy_description

const char * starpu_sched_policy::policy_description

Optional field. Human readable description of the policy.

Macro Definition Documentation

◆ STARPU_NMAX_SCHED_CTXS

#define STARPU_NMAX_SCHED_CTXS

Define the maximum number of scheduling contexts managed by StarPU. The default value can be modified at configure by using the option --enable-max-sched-ctxs.

◆ STARPU_MAXIMPLEMENTATIONS

#define STARPU_MAXIMPLEMENTATIONS

Define the maximum number of implementations per architecture. The default value can be modified at configure by using the option --enable-maximplementations.

Function Documentation

◆ starpu_sched_get_predefined_policies()

struct starpu_sched_policy ** starpu_sched_get_predefined_policies ( )

Return an NULL-terminated array of all the predefined scheduling policies.

◆ starpu_worker_get_sched_condition()

void starpu_worker_get_sched_condition ( int  workerid,
starpu_pthread_mutex_t **  sched_mutex,
starpu_pthread_cond_t **  sched_cond 
)

When there is no available task for a worker, StarPU blocks this worker on a condition variable. This function specifies which condition variable (and the associated mutex) should be used to block (and to wake up) a worker. Note that multiple workers may use the same condition variable. For instance, in the case of a scheduling strategy with a single task queue, the same condition variable would be used to block and wake up all workers.

◆ starpu_wake_worker()

int starpu_wake_worker ( int  workerid)

In simgrid or blocking driver mode, this should be called by push functions to wake the potential workers that are supposed to pick up the tasks which just have been pushed, otherwise they may remain sleeping.

◆ starpu_sched_set_min_priority()

int starpu_sched_set_min_priority ( int  min_prio)

TODO: check if this is correct Defines the minimum task priority level supported by the scheduling policy. The default minimum priority level is the same as the default priority level which is 0 by convention. The application may access that value by calling the function starpu_sched_get_min_priority(). This function should only be called from the initialization method of the scheduling policy, and should not be used directly from the application.

◆ starpu_sched_set_max_priority()

int starpu_sched_set_max_priority ( int  max_prio)

TODO: check if this is correct Defines the maximum priority level supported by the scheduling policy. The default maximum priority level is 1. The application may access that value by calling the function starpu_sched_get_max_priority(). This function should only be called from the initialization method of the scheduling policy, and should not be used directly from the application.

◆ starpu_sched_get_min_priority()

int starpu_sched_get_min_priority ( void  )

TODO: check if this is correct Returns the current minimum priority level supported by the scheduling policy

◆ starpu_sched_get_max_priority()

int starpu_sched_get_max_priority ( void  )

TODO: check if this is correct Returns the current maximum priority level supported by the scheduling policy

◆ starpu_push_local_task()

int starpu_push_local_task ( int  workerid,
struct starpu_task task,
int  back 
)

The scheduling policy may put tasks directly into a worker’s local queue so that it is not always necessary to create its own queue when the local queue is sufficient. If back is not 0, task is put at the back of the queue where the worker will pop tasks first. Setting back to 0 therefore ensures a FIFO ordering.

◆ starpu_push_task_end()

int starpu_push_task_end ( struct starpu_task task)

This function must be called by a scheduler to notify that the given task has just been pushed.

◆ starpu_worker_can_execute_task()

int starpu_worker_can_execute_task ( unsigned  workerid,
struct starpu_task task,
unsigned  nimpl 
)

Check if the worker specified by workerid can execute the codelet. Schedulers need to call it before assigning a task to a worker, otherwise the task may fail to execute.

◆ starpu_worker_can_execute_task_impl()

int starpu_worker_can_execute_task_impl ( unsigned  workerid,
struct starpu_task task,
unsigned *  impl_mask 
)

Check if the worker specified by workerid can execute the codelet and returns which implementation numbers can be used. Schedulers need to call it before assigning a task to a worker, otherwise the task may fail to execute. This should be preferred rather than calling starpu_worker_can_execute_task for each and every implementation. It can also be used with impl_mask == NULL to check for at least one implementation without determining which.

◆ starpu_worker_can_execute_task_first_impl()

int starpu_worker_can_execute_task_first_impl ( unsigned  workerid,
struct starpu_task task,
unsigned *  nimpl 
)

Check if the worker specified by workerid can execute the codelet and returns the first implementation which can be used. Schedulers need to call it before assigning a task to a worker, otherwise the task may fail to execute. This should be preferred rather than calling starpu_worker_can_execute_task for each and every implementation. It can also be used with impl_mask == NULL to check for at least one implementation without determining which.

◆ starpu_task_footprint()

uint32_t starpu_task_footprint ( struct starpu_perfmodel model,
struct starpu_task task,
struct starpu_perfmodel_arch arch,
unsigned  nimpl 
)

Returns the footprint for a given task, taking into account user-provided perfmodel footprint or size_base functions.

◆ starpu_task_data_footprint()

uint32_t starpu_task_data_footprint ( struct starpu_task task)

Returns the raw footprint for the data of a given task (without taking into account user-provided functions).

◆ starpu_task_expected_length()

double starpu_task_expected_length ( struct starpu_task task,
struct starpu_perfmodel_arch arch,
unsigned  nimpl 
)

Returns expected task duration in micro-seconds.

◆ starpu_worker_get_relative_speedup()

double starpu_worker_get_relative_speedup ( struct starpu_perfmodel_arch perf_arch)

Returns an estimated speedup factor relative to CPU speed

◆ starpu_task_expected_data_transfer_time()

double starpu_task_expected_data_transfer_time ( unsigned  memory_node,
struct starpu_task task 
)

Returns expected data transfer time in micro-seconds.

◆ starpu_data_expected_transfer_time()

double starpu_data_expected_transfer_time ( starpu_data_handle_t  handle,
unsigned  memory_node,
enum starpu_data_access_mode  mode 
)

Predict the transfer time (in micro-seconds) to move handle to a memory node

◆ starpu_task_expected_energy()

double starpu_task_expected_energy ( struct starpu_task task,
struct starpu_perfmodel_arch arch,
unsigned  nimpl 
)

Returns expected energy consumption in J

◆ starpu_task_expected_conversion_time()

double starpu_task_expected_conversion_time ( struct starpu_task task,
struct starpu_perfmodel_arch arch,
unsigned  nimpl 
)

Returns expected conversion time in ms (multiformat interface only)

◆ starpu_get_prefetch_flag()

int starpu_get_prefetch_flag ( void  )

Whether STARPU_PREFETCH was set

◆ starpu_prefetch_task_input_on_node()

int starpu_prefetch_task_input_on_node ( struct starpu_task task,
unsigned  node 
)

Prefetch data for a given task on a given node

◆ starpu_idle_prefetch_task_input_on_node()

int starpu_idle_prefetch_task_input_on_node ( struct starpu_task task,
unsigned  node 
)

Prefetch data for a given task on a given node when the bus is idle

◆ starpu_sched_ctx_worker_shares_tasks_lists()

void starpu_sched_ctx_worker_shares_tasks_lists ( int  workerid,
int  sched_ctx_id 
)

The scheduling policies indicates if the worker may pop tasks from the list of other workers or if there is a central list with task for all the workers