starpu-max/doc/doxygen/chapters/api/modularized_scheduler.doxy

/*
 * This file is part of the StarPU Handbook.
 * Copyright (C) 2013        Simon Archipoff
 * Copyright (C) 2009--2011  Universit@'e de Bordeaux
 * Copyright (C) 2014, 2015, 2016, 2017        CNRS
 * Copyright (C) 2013, 2014  INRIA
 * See the file version.doxy for copying conditions.
 */

/*! \defgroup API_Modularized_Scheduler Modularized Scheduler Interface

\enum starpu_sched_component_properties
\ingroup API_Modularized_Scheduler
flags for starpu_sched_component::properties
\var starpu_sched_component_properties::STARPU_SCHED_COMPONENT_HOMOGENEOUS
     indicate that all workers have the same starpu_worker_archtype
\var starpu_sched_component_properties::STARPU_SCHED_COMPONENT_SINGLE_MEMORY_NODE
     indicate that all workers have the same memory component

\def STARPU_SCHED_COMPONENT_IS_HOMOGENEOUS
\ingroup API_Modularized_Scheduler
indicate if component is homogeneous
\def STARPU_SCHED_COMPONENT_IS_SINGLE_MEMORY_NODE
\ingroup API_Modularized_Scheduler
indicate if all workers have the same memory component

\struct starpu_sched_component
\ingroup API_Modularized_Scheduler
This structure represent a scheduler module.  A scheduler is a
tree-like structure of them, some parts of scheduler can be shared by
several contexes to perform some local optimisations, so, for all
components, a list of parent is defined by \c sched_ctx_id. They
embed there specialised method in a pseudo object-style, so calls are
like <c>component->push_task(component,task)</c>

\var struct starpu_sched_tree *starpu_sched_component::tree
     The tree containing the component
\var struct starpu_bitmap *starpu_sched_component::workers
     this member contain the set of underlying workers
\var starpu_sched_component::workers_in_ctx
     this member contain the subset of starpu_sched_component::workers that is currently available in the context
     The push method should take this member into account.
     this member is set with :
     component->workers UNION tree->workers UNION
     component->child[i]->workers_in_ctx iff exist x such as component->children[i]->parents[x] == component
\var void *starpu_sched_component::data
     private data
\var int starpu_sched_component::nchildren
     the number of compoments's children
\var struct starpu_sched_component **starpu_sched_component::children
     the vector of component's children
\var int starpu_sched_component::nparents
     the numbers of component's parents
\var struct starpu_sched_component **starpu_sched_component::parents
     the vector of component's parents

\var void(*starpu_sched_component::add_child)(struct starpu_sched_component *component, struct starpu_sched_component *child)
     add a child to component
\var void(*starpu_sched_component::remove_child)(struct starpu_sched_component *component, struct starpu_sched_component *child)
     remove a child from component
\var void(*starpu_sched_component::add_parent)(struct starpu_sched_component *component, struct starpu_sched_component *parent)
     todo
\var void(*starpu_sched_component::remove_parent)(struct starpu_sched_component *component, struct starpu_sched_component *parent)
     todo

\var int (*starpu_sched_component::push_task)(struct starpu_sched_component *, struct starpu_task *)
     push a task in the scheduler module. this function is called to
     push a task on component subtree, this can either perform a
     recursive call on a child or store the task in the component,
     then it will be returned by a further pull_task call.
     the caller must ensure that component is able to execute task.
     This method must either return 0 if it the task was properly stored or
     passed over to a child component, or return a value different from 0 if the
     task could not be consumed (e.g. the queue is full).
\var struct starpu_task * (*starpu_sched_component::pull_task)(struct starpu_sched_component *)
     pop a task from the scheduler module. this function is called by workers to get a task from their
     parents. this function should first return a locally stored task
     or perform a recursive call on the parents.
     the task returned by this function is executable by the caller

\var int (*starpu_sched_component::can_push)(struct starpu_sched_component *component)
     This function is called by a component which implements a queue,
     allowing it to signify to its parents that an empty slot is
     available in its queue. The basic implementation of this function
     is a recursive call to its parents, the user has to specify a
     personally-made function to catch those calls.
\var void (*starpu_sched_component::can_pull)(struct starpu_sched_component *component)
     This function allow a component to wake up a worker. It is
     currently called by component which implements a queue, to
     signify to its children that a task have been pushed in its local
     queue, and is available to be popped by a worker, for example.
     The basic implementation of this function is a recursive call to
     its children, until at least one worker have been woken up.

\var double (*starpu_sched_component::estimated_load)(struct starpu_sched_component *component)
	is an heuristic to compute load of scheduler module. Basically the number of tasks divided by the sum
	of relatives speedup of workers available in context.
	estimated_load(component) = sum(estimated_load(component_children)) + nb_local_tasks / average(relative_speedup(underlying_worker))
\var starpu_sched_component::estimated_end
	return the time when a worker will enter in starvation. This function is relevant only if the task->predicted
	member has been set.

\var void (*starpu_sched_component::deinit_data)(struct starpu_sched_component *component)
	called by starpu_sched_component_destroy. Should free data allocated during creation
\var void (*starpu_sched_component::notify_change_workers)(struct starpu_sched_component *component)
	this function is called for each component when workers are added or removed from a context
\var int starpu_sched_component::properties
	todo
\var hwloc_obj_t starpu_sched_component::obj
	the hwloc object associated to scheduler module. points to the
	part of topology that is binded to this component, eg: a numa
	node for a ws component that would balance load between
	underlying sockets

\struct starpu_sched_tree
\ingroup API_Modularized_Scheduler
The actual scheduler
\var struct starpu_sched_component *starpu_sched_tree::root
	this is the entry module of the scheduler
\var struct starpu_bitmap *starpu_sched_tree::workers
	this is the set of workers available in this context, this value is used to mask workers in modules
\var unsigned starpu_sched_tree::sched_ctx_id
	the context id of the scheduler
\var starpu_pthread_mutex_t starpu_sched_tree::lock
	this lock is used to protect the scheduler, it is taken in
	read mode pushing a task and in write mode for adding or
	removing workers

@name Scheduling Tree API
\ingroup API_Modularized_Scheduler

\fn struct starpu_sched_tree *starpu_sched_tree_create(unsigned sched_ctx_id)
\ingroup API_Modularized_Scheduler
	 create a empty initialized starpu_sched_tree

\fn void starpu_sched_tree_destroy(struct starpu_sched_tree *tree)
\ingroup API_Modularized_Scheduler
	 destroy tree and free all non shared component in it.

\fn void starpu_sched_tree_update_workers(struct starpu_sched_tree *t)
\ingroup API_Modularized_Scheduler
	 recursively set all starpu_sched_component::workers, do not take into account shared parts (except workers).

\fn void starpu_sched_tree_update_workers_in_ctx(struct starpu_sched_tree *t)
\ingroup API_Modularized_Scheduler
	 recursively set all starpu_sched_component::workers_in_ctx, do not take into account shared parts (except workers)

\fn int starpu_sched_tree_push_task(struct starpu_task *task)
\ingroup API_Modularized_Scheduler
	 compatibility with starpu_sched_policy interface

\fn struct starpu_task *starpu_sched_tree_pop_task(unsigned sched_ctx)
\ingroup API_Modularized_Scheduler
	 compatibility with starpu_sched_policy interface

\fn void starpu_sched_tree_add_workers(unsigned sched_ctx_id, int *workerids, unsigned nworkers)
\ingroup API_Modularized_Scheduler
	 compatibility with starpu_sched_policy interface

\fn void starpu_sched_tree_remove_workers(unsigned sched_ctx_id, int *workerids, unsigned nworkers)
\ingroup API_Modularized_Scheduler
	 compatibility with starpu_sched_policy interface

\fn void starpu_sched_component_connect(struct starpu_sched_component *parent, struct starpu_sched_component *child)
\ingroup API_Modularized_Scheduler
	 Attaches component \p child to parent \p parent. Some component may accept only one child, others accept several (e.g. MCT)

@name Generic Scheduling Component API
\ingroup API_Modularized_Scheduler

\fn struct starpu_sched_component *starpu_sched_component_create(struct starpu_sched_tree *tree, const char *name)
\ingroup API_Modularized_Scheduler
	 allocate and initialize component field with defaults values :
	.pop_task make recursive call on father
	.estimated_load compute relative speedup and tasks in sub tree
	.estimated_end return the average of recursive call on children
	.add_child is starpu_sched_component_add_child
	.remove_child is starpu_sched_component_remove_child
	.notify_change_workers does nothing
	.deinit_data does nothing

\fn void starpu_sched_component_destroy(struct starpu_sched_component *component)
\ingroup API_Modularized_Scheduler
	 free data allocated by starpu_sched_component_create and call component->deinit_data(component)
	 set to <c>NULL</c> the member starpu_sched_component::fathers[sched_ctx_id] of all child if its equal to \p component

\fn void starpu_sched_component_destroy_rec(struct starpu_sched_component *component)
\ingroup API_Modularized_Scheduler
	 recursively destroy non shared parts of a \p component 's tree

\fn int starpu_sched_component_can_execute_task(struct starpu_sched_component *component, struct starpu_task *task)
\ingroup API_Modularized_Scheduler
	 return true iff \p component can execute \p task, this function take into account the workers available in the scheduling context

\fn int starpu_sched_component_execute_preds(struct starpu_sched_component *component, struct starpu_task *task, double *length)
\ingroup API_Modularized_Scheduler
	 return a non <c>NULL</c> value if \p component can execute \p task.
	 write the execution prediction length for the best implementation of the best worker available and write this at \p length address.
	 this result is more relevant if starpu_sched_component::is_homogeneous is non <c>NULL</c>.
	 if a worker need to be calibrated for an implementation, nan is set to \p length.

\fn double starpu_sched_component_transfer_length(struct starpu_sched_component *component, struct starpu_task *task)
\ingroup API_Modularized_Scheduler
	 return the average time to transfer \p task data to underlying \p component workers.

@name Worker Component API
\ingroup API_Modularized_Scheduler

\fn struct starpu_sched_component *starpu_sched_component_worker_get(unsigned sched_ctx, int workerid)
\ingroup API_Modularized_Scheduler
	 return the struct starpu_sched_component corresponding to \p workerid. Undefined if \p workerid is not a valid workerid

\fn int starpu_sched_component_worker_get_workerid(struct starpu_sched_component *worker_component)
\ingroup API_Modularized_Scheduler
	 return the workerid of \p worker_component, undefined if starpu_sched_component_is_worker(worker_component) == 0

\fn int starpu_sched_component_is_worker(struct starpu_sched_component *component)
\ingroup API_Modularized_Scheduler
	 return true iff \p component is a worker component

\fn int starpu_sched_component_is_simple_worker(struct starpu_sched_component *component)
\ingroup API_Modularized_Scheduler
	 return true iff \p component is a simple worker component

\fn int starpu_sched_component_is_combined_worker(struct starpu_sched_component *component)
\ingroup API_Modularized_Scheduler
	 return true iff \p component is a combined worker component

\fn void starpu_sched_component_worker_pre_exec_hook(struct starpu_task *task, unsigned sched_ctx_id)
\ingroup API_Modularized_Scheduler
	 compatibility with starpu_sched_policy interface
	 update predictions for workers

\fn void starpu_sched_component_worker_post_exec_hook(struct starpu_task *task, unsigned sched_ctx_id)
\ingroup API_Modularized_Scheduler
	 compatibility with starpu_sched_policy interface

@name Flow-control Fifo Component API
\ingroup API_Modularized_Scheduler

\fn double starpu_sched_component_estimated_load(struct starpu_sched_component * component);
\ingroup API_Modularized_Scheduler
default function for the estimated_load component method, just sums up the loads
of the children of the component.

\fn double starpu_sched_component_estimated_end_min(struct starpu_sched_component * component);
\ingroup API_Modularized_Scheduler
function that can be used for the estimated_end component method, which just computes the minimum completion time of the children.

\fn double starpu_sched_component_estimated_end_average(struct starpu_sched_component * component);
\ingroup API_Modularized_Scheduler
default function for the estimated_end component method, which just computes the average completion time of the children.


\struct starpu_sched_component_fifo_data
\ingroup API_Modularized_Scheduler
\var unsigned starpu_sched_component_fifo_data::ntasks_threshold
todo
\var double starpu_sched_component_fifo_data::exp_len_threshold
todo

\fn struct starpu_sched_component *starpu_sched_component_fifo_create(struct starpu_sched_tree *tree, struct starpu_sched_component_fifo_data *fifo_data)
\ingroup API_Modularized_Scheduler
	 Return a struct starpu_sched_component with a fifo. A stable sort is performed according to tasks priorities.
	 A push_task call on this component does not perform recursive calls, underlying components will have to call pop_task to get it.
	 starpu_sched_component::estimated_end function compute the estimated length by dividing the sequential length by the number of underlying workers. Do not take into account tasks that are currently executed.

\fn int starpu_sched_component_is_fifo(struct starpu_sched_component *component)
\ingroup API_Modularized_Scheduler
	 return true iff \p component is a fifo component

@name Flow-control Prio Component API
\ingroup API_Modularized_Scheduler

\struct starpu_sched_component_prio_data
\ingroup API_Modularized_Scheduler
\var unsigned starpu_sched_component_prio_data::ntasks_threshold
todo
\var double starpu_sched_component_prio_data::exp_len_threshold
todo

\fn struct starpu_sched_component *starpu_sched_component_prio_create(struct starpu_sched_tree *tree, struct starpu_sched_component_prio_data *prio_data)
\ingroup API_Modularized_Scheduler
todo

\fn int starpu_sched_component_is_prio(struct starpu_sched_component *component)
\ingroup API_Modularized_Scheduler
todo

@name Resource-mapping Work-Stealing Component API
\ingroup API_Modularized_Scheduler

\fn struct starpu_sched_component *starpu_sched_component_work_stealing_create(struct starpu_sched_tree *tree, void *arg)
\ingroup API_Modularized_Scheduler
	 return a component that perform a work stealing scheduling. Tasks are pushed in a round robin way. estimated_end return the average of expected length of fifos, starting at the average of the expected_end of his children. When a worker have to steal a task, it steal a task in a round robin way, and get the last pushed task of the higher priority.

\fn int starpu_sched_tree_work_stealing_push_task(struct starpu_task *task)
\ingroup API_Modularized_Scheduler
	 undefined if there is no work stealing component in the scheduler. If any, \p task is pushed in a default way if the caller is the application, and in the caller's fifo if its a worker.

\fn int starpu_sched_component_is_work_stealing(struct starpu_sched_component *component)
\ingroup API_Modularized_Scheduler
	 return true iff \p component is a work stealing component

@name Resource-mapping Random Component API
\ingroup API_Modularized_Scheduler

\fn struct starpu_sched_component *starpu_sched_component_random_create(struct starpu_sched_tree *tree, void *arg)
\ingroup API_Modularized_Scheduler
	 create a component that perform a random scheduling

\fn int starpu_sched_component_is_random(struct starpu_sched_component *)
\ingroup API_Modularized_Scheduler
	 return true iff \p component is a random component

@name Resource-mapping Eager Component API
\ingroup API_Modularized_Scheduler

\fn struct starpu_sched_component *starpu_sched_component_eager_create(struct starpu_sched_tree *tree, void *arg)
\ingroup API_Modularized_Scheduler
todo

\fn int starpu_sched_component_is_eager(struct starpu_sched_component *)
\ingroup API_Modularized_Scheduler
todo

@name Resource-mapping Eager-Calibration Component API
\ingroup API_Modularized_Scheduler

\fn struct starpu_sched_component *starpu_sched_component_eager_calibration_create(struct starpu_sched_tree *tree, void *arg)
\ingroup API_Modularized_Scheduler
todo

\fn int starpu_sched_component_is_eager_calibration(struct starpu_sched_component *)
\ingroup API_Modularized_Scheduler
todo

@name Resource-mapping MCT Component API
\ingroup API_Modularized_Scheduler

\struct starpu_sched_component_mct_data
\ingroup API_Modularized_Scheduler
\var double starpu_sched_component_mct_data::alpha
todo
\var double starpu_sched_component_mct_data::beta
todo
\var double starpu_sched_component_mct_data::_gamma
todo
\var double starpu_sched_component_mct_data::idle_power
todo

\fn struct starpu_sched_component *starpu_sched_component_mct_create(struct starpu_sched_tree *tree, struct starpu_sched_component_mct_data *mct_data)
\ingroup API_Modularized_Scheduler
create a component with mct_data paremeters. the mct component doesnt
do anything but pushing tasks on no_perf_model_component and
calibrating_component

\fn int starpu_sched_component_is_mct(struct starpu_sched_component *component);
\ingroup API_Modularized_Scheduler
todo

@name Resource-mapping Heft Component API
\ingroup API_Modularized_Scheduler

\fn struct starpu_sched_component *starpu_sched_component_heft_create(struct starpu_sched_tree *tree, struct starpu_sched_component_mct_data *mct_data)
\ingroup API_Modularized_Scheduler
	 this component perform a heft scheduling

\fn int starpu_sched_component_is_heft(struct starpu_sched_component *component)
\ingroup API_Modularized_Scheduler
	 return true iff \p component is a heft component

@name Special-purpose Best_Implementation Component API
\ingroup API_Modularized_Scheduler

\fn struct starpu_sched_component *starpu_sched_component_best_implementation_create(struct starpu_sched_tree *tree, void *arg)
\ingroup API_Modularized_Scheduler
	 Select the implementation that offer the shortest computation length for the first worker that can execute the task.
	 Or an implementation that need to be calibrated.
	 Also set starpu_task::predicted and starpu_task::predicted_transfer for memory component of the first suitable workerid.
	 If starpu_sched_component::push method is called and starpu_sched_component::nchild > 1 the result is undefined.

@name Special-purpose Perfmodel_Select Component API
\ingroup API_Modularized_Scheduler

\struct starpu_sched_component_perfmodel_select_data
\ingroup API_Modularized_Scheduler
\var struct starpu_sched_component *starpu_sched_component_perfmodel_select_data::calibrator_component
todo
\var struct starpu_sched_component *starpu_sched_component_perfmodel_select_data::no_perfmodel_component
todo
\var struct starpu_sched_component *starpu_sched_component_perfmodel_select_data::perfmodel_component
todo

\fn struct starpu_sched_component *starpu_sched_component_perfmodel_select_create(struct starpu_sched_tree *tree, struct starpu_sched_component_perfmodel_select_data *perfmodel_select_data)
\ingroup API_Modularized_Scheduler
todo

\fn int starpu_sched_component_is_perfmodel_select(struct starpu_sched_component *component)
\ingroup API_Modularized_Scheduler
todo

@name Recipe Component API
\ingroup API_Modularized_Scheduler

\struct starpu_sched_component_composed_recipe
\ingroup API_Modularized_Scheduler
	parameters for starpu_sched_component_composed_component_create

\fn struct starpu_sched_component_composed_recipe *starpu_sched_component_composed_recipe_create(void)
\ingroup API_Modularized_Scheduler
	 return an empty recipe for a composed component, it should not be used without modification

\fn struct starpu_sched_component_composed_recipe *starpu_sched_component_composed_recipe_create_singleton(struct starpu_sched_component *(*create_component)(struct starpu_sched_tree *tree, void *arg), void *arg)
\ingroup API_Modularized_Scheduler
	 return a recipe to build a composed component with a \p create_component

\fn void starpu_sched_component_composed_recipe_add(struct starpu_sched_component_composed_recipe *recipe, struct starpu_sched_component *(*create_component)(struct starpu_sched_tree *tree, void *arg), void *arg)
\ingroup API_Modularized_Scheduler
	 add \p create_component under all previous components in recipe

\fn void starpu_sched_component_composed_recipe_destroy(struct starpu_sched_component_composed_recipe *)
\ingroup API_Modularized_Scheduler
	 destroy composed_sched_component, this should be done after starpu_sched_component_composed_component_create was called

\fn struct starpu_sched_component *starpu_sched_component_composed_component_create(struct starpu_sched_tree *tree, struct starpu_sched_component_composed_recipe *recipe)
\ingroup API_Modularized_Scheduler
	 create a component that behave as all component of recipe where linked. Except that you cant use starpu_sched_component_is_foo function
	 if recipe contain a single create_foo arg_foo pair, create_foo(arg_foo) is returned instead of a composed component

\struct starpu_sched_component_specs
\ingroup API_Modularized_Scheduler
	 Define how build a scheduler according to topology. Each level (except for hwloc_machine_composed_sched_component) can be <c>NULL</c>, then
	 the level is just skipped. Bugs everywhere, do not rely on.
\var struct starpu_sched_component_composed_recipe *starpu_sched_specs::hwloc_machine_composed_sched_component
     the composed component to put on the top of the scheduler
     this member must not be <c>NULL</c> as it is the root of the topology
\var struct starpu_sched_component_composed_recipe *starpu_sched_specs::hwloc_component_composed_sched_component
     the composed component to put for each memory component
\var struct starpu_sched_component_composed_recipe *starpu_sched_specs::hwloc_socket_composed_sched_component
     the composed component to put for each socket
\var struct starpu_sched_component_composed_recipe *starpu_sched_specs::hwloc_cache_composed_sched_component
     the composed component to put for each cache
\var struct starpu_sched_component_composed_recipe *(*starpu_sched_specs::worker_composed_sched_component)(enum starpu_worker_archtype archtype)
     a function that return a starpu_sched_component_composed_recipe to put on top of a worker of type \p archtype.
     <c>NULL</c> is a valid return value, then no component will be added on top
\var starpu_sched_specs::mix_heterogeneous_workers
     this flag is a dirty hack because of the poor expressivity of this interface. As example, if you want to build
     a heft component with a fifo component per numa component, and you also have GPUs, if this flag is set, GPUs will share those fifos.
     If this flag is not set, a new fifo will be built for each of them (if they have the same starpu_perf_arch and the same
     numa component it will be shared. it indicates if heterogenous workers should be brothers or cousins, as example, if a gpu and a cpu should share or not there numa node

\fn struct starpu_sched_tree *starpu_sched_component_make_scheduler(unsigned sched_ctx_id, struct starpu_sched_component_specs s)
\ingroup API_Modularized_Scheduler
	 this function build a scheduler for \p sched_ctx_id according to \p s and the hwloc topology of the machine.

\fn int starpu_sched_component_push_task(struct starpu_sched_component *from, struct starpu_sched_component *to, struct starpu_task *task)
\ingroup API_Modularized_Scheduler
Push a task to a component. This is a helper for <c>component->push_task(component, task)</c> plus tracing.

\fn struct starpu_task *starpu_sched_component_pull_task(struct starpu_sched_component *from, struct starpu_sched_component *to)
\ingroup API_Modularized_Scheduler
Pull a task from a component. This is a helper for <c>component->pull_task(component)</c> plus tracing.

*/