Loading...
Searching...
No Matches
Scheduling Policy

TODO. While StarPU comes with a variety of scheduling policies (see TaskSchedulingPolicy), 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_NMAX_SCHED_CTXS
#define | STARPU_MAXIMPLEMENTATIONS

## Typedefs

typedef void(* | starpu_notify_ready_soon_func) (void *data, struct starpu_task *task, double delay)

## Functions

struct starpu_sched_policy ** | starpu_sched_get_predefined_policies (void)
struct starpu_sched_policy * | starpu_get_sched_lib_policy (const char *name)
struct starpu_sched_policy ** | starpu_get_sched_lib_policies (void)
struct starpu_sched_policy * | starpu_sched_get_sched_policy_in_ctx (unsigned sched_ctx_id)
struct starpu_sched_policy * | starpu_sched_get_sched_policy (void)
void | starpu_worker_get_sched_condition (int workerid, starpu_pthread_mutex_t **sched_mutex, starpu_pthread_cond_t **sched_cond)
unsigned long | starpu_task_get_job_id (struct starpu_task *task)
int | starpu_sched_get_min_priority (void)
int | starpu_sched_get_max_priority (void)
int | starpu_sched_set_min_priority (int min_prio)
int | starpu_sched_set_max_priority (int max_prio)
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)
int | starpu_push_local_task (int workerid, struct starpu_task *task, int back)
int | starpu_push_task_end (struct starpu_task *task)
int | starpu_get_prefetch_flag (void)
int | starpu_prefetch_task_input_on_node_prio (struct starpu_task *task, unsigned node, int prio)
int | starpu_prefetch_task_input_on_node (struct starpu_task *task, unsigned node)
int | starpu_idle_prefetch_task_input_on_node_prio (struct starpu_task *task, unsigned node, int prio)
int | starpu_idle_prefetch_task_input_on_node (struct starpu_task *task, unsigned node)
int | starpu_prefetch_task_input_for_prio (struct starpu_task *task, unsigned worker, int prio)
int | starpu_prefetch_task_input_for (struct starpu_task *task, unsigned worker)
int | starpu_idle_prefetch_task_input_for_prio (struct starpu_task *task, unsigned worker, int prio)
int | starpu_idle_prefetch_task_input_for (struct starpu_task *task, unsigned worker)
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_task_worker_expected_length (struct starpu_task *task, unsigned workerid, unsigned sched_ctx_id, unsigned nimpl)
double | starpu_task_expected_length_average (struct starpu_task *task, unsigned sched_ctx_id)
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_task_expected_data_transfer_time_for (struct starpu_task *task, unsigned worker)
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_worker_expected_energy (struct starpu_task *task, unsigned workerid, unsigned sched_ctx_id, unsigned nimpl)
double | starpu_task_expected_energy_average (struct starpu_task *task, unsigned sched_ctx_id)
double | starpu_task_expected_conversion_time (struct starpu_task *task, struct starpu_perfmodel_arch *arch, unsigned nimpl)
void | starpu_task_notify_ready_soon_register (starpu_notify_ready_soon_func f, void *data)
void | starpu_sched_ctx_worker_shares_tasks_lists (int workerid, int sched_ctx_id)
void | starpu_sched_task_break (struct starpu_task *task)

## Worker operations

int | starpu_wake_worker_relax (int workerid)
int | starpu_wake_worker_no_relax (int workerid)
int | starpu_wake_worker_locked (int workerid)
int | starpu_wake_worker_relax_light (int workerid)

## Detailed Description

TODO. While StarPU comes with a variety of scheduling policies (see TaskSchedulingPolicy), 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

Contain 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:

- starpu_sched_policy::submit_hook when the task is submitted
- starpu_sched_policy::push_task when the task becomes ready. The scheduler is here given the task
- starpu_sched_policy::pop_task when the worker is idle. The scheduler here gives back the task to the core. It must not access this task any more
- starpu_sched_policy::pre_exec_hook right before the worker actually starts the task computation (after transferring any missing data).
- starpu_sched_policy::post_exec_hook right after the worker actually completes the task computation.

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

- starpu_sched_policy::submit_hook when the task is submitted
- starpu_sched_policy::push_task_notify when the task becomes ready. This is just a notification, the scheduler does not have to do anything about the task.
- starpu_sched_policy::pre_exec_hook right before the worker actually starts the task computation (after transferring any missing data).
- starpu_sched_policy::post_exec_hook right after the worker actually completes the task computation.

Data Fields
void(*)(unsigned sched_ctx_id) | init_sched | Initialize the scheduling policy, called before any other method.
void(*)(unsigned sched_ctx_id) | deinit_sched | Cleanup the scheduling policy
int(*)(struct starpu_task *) | push_task | Insert a task into the scheduler, called when the task becomes ready for execution. This must call starpu_push_task_end() once it has effectively pushed the task to a queue (to note the time when this was done in the task), but before releasing mutexes (so that the task hasn't been already taken by a worker).
double(*)(struct starpu_task *) | simulate_push_task |

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

push_task_notify

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.

Note: to get an estimation of the task duration, `perf_workerid` needs to be used rather than `workerid`, for the case of parallel tasks.

struct starpu_task *(*)(unsigned sched_ctx_id)

pop_task

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.

void(*)(struct starpu_task *task) | submit_hook | Optional field. This method is called when a task is submitted.
void(*)(struct starpu_task *, unsigned sched_ctx_id) | pre_exec_hook | Optional field. This method is called every time a task is starting.
void(*)(struct starpu_task *, unsigned sched_ctx_id) | post_exec_hook | Optional field. This method is called every time a task has been executed.
void(*)(unsigned sched_ctx_id) | do_schedule | 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.
void(*)(unsigned sched_ctx_id, int *workerids, unsigned nworkers) | add_workers | Initialize scheduling structures corresponding to each worker used by the policy.
void(*)(unsigned sched_ctx_id, int *workerids, unsigned nworkers) | remove_workers | Deinitialize scheduling structures corresponding to each worker used by the policy.
int | prefetches | Whether this scheduling policy does data prefetching, and thus the core should not try to do it opportunistically.
const char * | policy_name | Optional field. Name of the policy.
const char * | policy_description | Optional field. Human readable description of the policy.
enum starpu_worker_collection_type | worker_type |

## 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 | ( | void |  | ) |

Return an `NULL`-terminated array of all the predefined scheduling policies. See TaskSchedulingPolicy for more details.

## starpu_get_sched_lib_policy()

struct starpu_sched_policy * starpu_get_sched_lib_policy | ( | const char * | name | ) |

Allow an external library to return a scheduling policy to be loaded dynamically. See Using a New Scheduling Policy for more details.

## starpu_get_sched_lib_policies()

struct starpu_sched_policy ** starpu_get_sched_lib_policies | ( | void |  | ) |

Allow an external library to return a list of scheduling policies to be loaded dynamically. See Using a New Scheduling Policy for more details.

## starpu_sched_get_sched_policy_in_ctx()

struct starpu_sched_policy * starpu_sched_get_sched_policy_in_ctx | ( | unsigned | sched_ctx_id | ) |

Return the scheduler policy of the default context. See TaskSchedulingPolicy for more details.

## starpu_sched_get_sched_policy()

struct starpu_sched_policy * starpu_sched_get_sched_policy | ( | void |  | ) |

Return the scheduler policy of the given context. See TaskSchedulingPolicy for more details.

## 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_task_get_job_id()

unsigned long starpu_task_get_job_id | ( | struct starpu_task * | task | ) |

Return the job identifier associated with the task. See TraceSchedTaskDetails for more details.

## starpu_sched_get_min_priority()

int starpu_sched_get_min_priority | ( | void |  | ) |

TODO: check if this is correct Return the current minimum priority level supported by the scheduling policy. See Defining A New Basic Scheduling Policy for more details.

## starpu_sched_get_max_priority()

int starpu_sched_get_max_priority | ( | void |  | ) |

TODO: check if this is correct Return the current maximum priority level supported by the scheduling policy. See Defining A New Basic Scheduling Policy for more details.

## starpu_sched_set_min_priority()

int starpu_sched_set_min_priority | ( | int | min_prio | ) |

TODO: check if this is correct Define 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. See Defining A New Basic Scheduling Policy for more details.

## starpu_sched_set_max_priority()

int starpu_sched_set_max_priority | ( | int | max_prio | ) |

TODO: check if this is correct Define 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. See Defining A New Basic Scheduling Policy for more details.

## 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. See Defining A New Basic Scheduling Policy for more details.

## 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 return 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. See Defining A New Basic Scheduling Policy for more details.

## 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 return 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. See Defining A New Basic Scheduling Policy for more details.

## 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. `back` is ignored: the task priority is used to order tasks in this queue. See Defining A New Basic Scheduling Policy for more details.

## starpu_push_task_end()

int starpu_push_task_end | ( | struct starpu_task * | task | ) |

Must be called by a scheduler to notify that the given task has just been pushed. See Defining A New Basic Scheduling Policy for more details.

## starpu_get_prefetch_flag()

int starpu_get_prefetch_flag | ( | void |  | ) |

Whether STARPU_PREFETCH was set. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_prefetch_task_input_on_node_prio()

int starpu_prefetch_task_input_on_node_prio | ( | struct starpu_task * | task,
|  | unsigned | node,
|  | int | prio )

Prefetch data for a given p task on a given p node with a given priority. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_prefetch_task_input_on_node()

int starpu_prefetch_task_input_on_node | ( | struct starpu_task * | task,
|  | unsigned | node )

Prefetch data for a given p task on a given p node. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_idle_prefetch_task_input_on_node_prio()

int starpu_idle_prefetch_task_input_on_node_prio | ( | struct starpu_task * | task,
|  | unsigned | node,
|  | int | prio )

Prefetch data for a given p task on a given p node when the bus is idle with a given priority. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## 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 p task on a given p node when the bus is idle. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_prefetch_task_input_for_prio()

int starpu_prefetch_task_input_for_prio | ( | struct starpu_task * | task,
|  | unsigned | worker,
|  | int | prio )

Prefetch data for a given p task on a given p worker with a given priority. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_prefetch_task_input_for()

int starpu_prefetch_task_input_for | ( | struct starpu_task * | task,
|  | unsigned | worker )

Prefetch data for a given p task on a given p worker. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_idle_prefetch_task_input_for_prio()

int starpu_idle_prefetch_task_input_for_prio | ( | struct starpu_task * | task,
|  | unsigned | worker,
|  | int | prio )

Prefetch data for a given p task on a given p worker when the bus is idle with a given priority. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_idle_prefetch_task_input_for()

int starpu_idle_prefetch_task_input_for | ( | struct starpu_task * | task,
|  | unsigned | worker )

Prefetch data for a given p task on a given p worker when the bus is idle. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_task_footprint()

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

Return the footprint for a given task, taking into account user-provided perfmodel footprint or size_base functions. See PerformanceModelExample for more details.

## starpu_task_data_footprint()

uint32_t starpu_task_data_footprint | ( | struct starpu_task * | task | ) |

Return the raw footprint for the data of a given task (without taking into account user-provided functions). See PerformanceModelExample for more details.

## starpu_task_expected_length()

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

Return expected task duration in micro-seconds on a given architecture `arch` using given implementation `nimpl`. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_task_worker_expected_length()

double starpu_task_worker_expected_length | ( | struct starpu_task * | task,
|  | unsigned | workerid,
|  | unsigned | sched_ctx_id,
|  | unsigned | nimpl )

Same as starpu_task_expected_length() but for a precise worker. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_task_expected_length_average()

double starpu_task_expected_length_average | ( | struct starpu_task * | task,
|  | unsigned | sched_ctx_id )

Return expected task duration in micro-seconds, averaged over the different workers driven by the scheduler `sched_ctx_id` Note: this is not just the average of the durations using the number of processing units as coefficients, but their efficiency at processing the task, thus the harmonic average of the durations. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_worker_get_relative_speedup()

double starpu_worker_get_relative_speedup | ( | struct starpu_perfmodel_arch * | perf_arch | ) |

Return an estimated speedup factor relative to CPU speed. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_task_expected_data_transfer_time()

double starpu_task_expected_data_transfer_time | ( | unsigned | memory_node,
|  | struct starpu_task * | task )

Return expected data transfer time in micro-seconds for the given `memory_node`. Prefer using starpu_task_expected_data_transfer_time_for() which is more precise. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_task_expected_data_transfer_time_for()

double starpu_task_expected_data_transfer_time_for | ( | struct starpu_task * | task,
|  | unsigned | worker )

Return expected data transfer time in micro-seconds for the given `worker`. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## 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. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_task_expected_energy()

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

Return expected energy use in J. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_task_worker_expected_energy()

double starpu_task_worker_expected_energy | ( | struct starpu_task * | task,
|  | unsigned | workerid,
|  | unsigned | sched_ctx_id,
|  | unsigned | nimpl )

Same as starpu_task_expected_energy but for a precise worker. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_task_expected_energy_average()

double starpu_task_expected_energy_average | ( | struct starpu_task * | task,
|  | unsigned | sched_ctx_id )

Return expected task energy use in J, averaged over the different workers driven by the scheduler `sched_ctx_id` Note: this is not just the average of the energy uses using the number of processing units as coefficients, but their efficiency at processing the task, thus the harmonic average of the energy uses. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_task_expected_conversion_time()

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

Return expected conversion time in ms (multiformat interface only). See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## starpu_task_notify_ready_soon_register()

void starpu_task_notify_ready_soon_register | ( | starpu_notify_ready_soon_func | f,
|  | void * | data )

Register a callback to be called when it is determined when a task will be ready an estimated amount of time from now, because its last dependency has just started and we know how long it will take. See Helper functions for defining a scheduling policy (Basic or modular) for more details.

## 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. See Defining A New Basic Scheduling Policy for more details.

## starpu_sched_task_break()

void starpu_sched_task_break | ( | struct starpu_task * | task | ) |

The scheduling policy should call this when it makes a scheduling decision for a task. This will possibly stop execution at this point, and then the programmer can inspect local variables etc. to determine why this scheduling decision was done.

See STARPU_TASK_BREAK_ON_SCHED See Defining A New Basic Scheduling Policy for more details.

## starpu_wake_worker_relax()

int starpu_wake_worker_relax | ( | int | workerid | ) |

Wake up `workerid` while temporarily entering the current worker relax state if needed during the waiting process. Return 1 if `workerid` has been woken up or its state_keep_awake flag has been set to `1`, and `0` otherwise (if `workerid` was not in the STATE_SLEEPING or in the STATE_SCHEDULING). See Defining A New Basic Scheduling Policy for more details.

## starpu_wake_worker_no_relax()

int starpu_wake_worker_no_relax | ( | int | workerid | ) |

Must be called to wake up a worker that is sleeping on the cond. Return 0 whenever the worker is not in a sleeping state or has the state_keep_awake flag on. See Defining A New Basic Scheduling Policy for more details.

## starpu_wake_worker_locked()

int starpu_wake_worker_locked | ( | int | workerid | ) |

Version of starpu_wake_worker_no_relax() which assumes that the sched mutex is locked See Defining A New Basic Scheduling Policy for more details.

## starpu_wake_worker_relax_light()

int starpu_wake_worker_relax_light | ( | int | workerid | ) |

Light version of starpu_wake_worker_relax() which, when possible, speculatively set keep_awake on the target worker without waiting for the worker to enter the relax state. See Defining A New Basic Scheduling Policy for more details.