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

/*
 * This file is part of the StarPU Handbook.
 * Copyright (C) 2013 Simon Archipoff
 * See the file version.doxy for copying conditions.
 */

/*! \page ModularizedScheduler Modularized Scheduler


\section Introduction

Scheduler are a tree-like structure of homogeneous nodes that each
provides push and pop primitives. Each node may have one father by
context, specially worker nodes as they are shared between all contexts.

Tasks make a top bottom traversal of tree.

A push call on a node make either a recursive call on one of its
childs or make the task stored in the node and made available to a
pop, in this case that node should call starpu_sched_node_available to wake workers
up. Push must be called on a child, and only if this child can execute
the task.

A pop call on a node can either return a locally stored task or perform
a recursive call on its father in its current context. Only workers
should call pop.


\section Initialization
Scheduler node are created with the starpu_sched_node_foo_create() functions
and then must be assembled using them starpu_sched_node::add_child and
starpu_sched_node::remove_child functions.
A father can be set to allow him to be reachable by a starpu_sched_node::pop_task
call.

Underlyings workers are memoized in starpu_sched_node::workers. Hence the
function starpu_sched_tree_update_workers should be called when the scheduler is
finished, or modified.


\section Push
All scheduler node must define a starpu_sched_node::push_task
function. The caller ensure that the node can actually execute the task.

\section Pop
starpu_sched_node::push_task should either return a local task or
perform a recursive call on
starpu_sched_node::fathers[sched_ctx_id], or \c NULL if its a root
node.


\section WorkersAndCombinedWorkers Workers and Combined workers

Leafs are either a worker node that is bind to a starpu workers or a
combined worker node that is bind to several worker nodes.

Pushing a task on a combined worker node will in fact push a copy of
that task on each worker node of the combined worker.

A push call simply enqueue task in worker queue, no sort is performed
here.
If a worker call pop and get a parallel task, it will execute it with the
combined worker it belong to.

\section Example

Here we build a simple scheduler with a heft node on top and a work stealing node per memory node, and a best_impl node per worker,
which use random node to push uncalibrated tasks and tasks with no perf model, this is probably stupid.

\code{.c}

static void initialize_scheduler(unsigned sched_ctx_id)
{
	starpu_sched_ctx_create_worker_collection(sched_ctx_id, STARPU_WORKER_LIST);
	struct starpu_sched_tree * t = starpu_sched_tree_create(sched_ctx_id);
	
	struct starpu_sched_node * ws_nodes[STARPU_NMAXWORKERS] = {0};

	struct starpu_heft_data data =
		{
			.alpha = 1,
			.beta = 2,
			.gamma = 0,
			.idle_power = 0,
			.no_perf_model_node_create = starpu_sched_node_random_create,
			.arg_no_perf_model = NULL,
			.calibrating_node_create = starpu_sched_node_random_create,
			.arg_calibrating_node = NULL
		};

	struct starpu_sched_node * heft = starpu_sched_node_heft_create(&data);

	unsigned i;
	for(i = 0; i < starpu_worker_get_count() + starpu_combined_worker_get_count(); i++)
	{
		struct starpu_sched_node * worker_node = starpu_sched_node_worker_get(i);
		struct starpu_sched_node * best_impl = starpu_sched_node_best_implementation_create(NULL);
		best_impl->add_child(best_impl, worker_node);
		starpu_sched_node_set_father(worker_node, best_impl, sched_ctx_id);
		
		int memory_node = starpu_worker_get_memory_node(i);

		if(!ws_nodes[memory_node])
		{
			ws_nodes[memory_node] = starpu_sched_node_work_stealing_create(NULL);
			heft->add_child(heft, ws_nodes[memory_node]);
			starpu_sched_node_set_father(ws_nodes[memory_node], heft, sched_ctx_id);
		}

		struct starpu_sched_node * ws = ws_nodes[memory_node];
		ws->add_child(ws,best_impl);
		starpu_sched_node_set_father(best_impl, ws, sched_ctx_id);
	}

	t->root = heft;
	starpu_sched_tree_update_workers(t);
	starpu_sched_ctx_set_policy_data(sched_ctx_id, (void*)t);
}

static void deinitialize_scheduler(unsigned sched_ctx_id)
{
	struct starpu_sched_tree *t = (struct starpu_sched_tree*)starpu_sched_ctx_get_policy_data(sched_ctx_id);
	starpu_sched_tree_destroy(t);
	starpu_sched_ctx_delete_worker_collection(sched_ctx_id);
}


struct starpu_sched_policy scheduling_policy =
{
	.init_sched = initialize_scheduler,
	.deinit_sched = deinitialize_scheduler,
	.add_workers = starpu_sched_tree_add_workers,
	.remove_workers = starpu_sched_tree_remove_workers,
	.push_task = starpu_sched_tree_push_task,
	.pop_task = starpu_sched_tree_pop_task,
	.pre_exec_hook = starpu_sched_node_worker_pre_exec_hook,
	.post_exec_hook = starpu_sched_node_worker_post_exec_hook,
	.pop_every_task = NULL,
	.policy_name = "tree-heft",
	.policy_description = "heft tree policy"
};
\endcode


*/