[Starpu-devel] Schedulers

[Nathalie Furmento <nathalie.furmento@labri.fr>]

All,

Following the discussion we had about the difference between dmda and heft, and  as i am preparing a tutorial, i looked at the list of schedulers StarPU is providing:

What the code says:

STARPU_SCHED can be either of
ws    -> work stealing
prio    -> eager (with priorities)
dm    -> performance model
dmda    -> data-aware performance model
heft    -> Heterogeneous Earliest Finish Task
dmdar    -> data-aware performance model (ready)
dmdas    -> data-aware performance model (sorted)
random    -> weighted random
eager    -> greedy policy
pheft    -> parallel HEFT
pgreedy    -> parallel greedy policy

What the documentation says:

The eager scheduler uses a central task queue, from which workers draw tasks to work on. This however does not permit to prefetch data since the scheduling decision is taken late. If a task has a non-0 priority, it is put at the front of the queue.

The prio scheduler also uses a central task queue, but sorts tasks by priority (between -5 and 5).

The random scheduler distributes tasks randomly according to assumed worker overall performance.

The ws (work stealing) scheduler schedules tasks on the local worker by default. When a worker becomes idle, it steals a task from the most loaded worker.

The dm (deque model) scheduler uses task execution performance models into account to perform an HEFT-similar scheduling strategy: it schedules tasks where their termination time will be minimal.

The dmda (deque model data aware) scheduler is similar to dm, it also takes into account data transfer time.

The dmdar (deque model data aware ready) scheduler is similar to dmda, it also sorts tasks on per-worker queues by number of already-available data buffers.

The dmdas (deque model data aware sorted) scheduler is similar to dmda, it also supports arbitrary priority values.

The heft (heterogeneous earliest finish time) scheduler is deprecated. It is now just an alias for dmda.

The pheft (parallel HEFT) scheduler is similar to heft, it also supports parallel tasks (still experimental).

The pgreedy (parallel greedy) scheduler is similar to greedy, it also supports parallel tasks (still experimental).

It would be good to have the same definitions in both place. I would also suggest to rename pgreedy to peager or eager to greedy. Saying pgreedy is similar to greedy, as greedy does not exist, is not consistent. We  could also rename the dm* schedulers to a name based on heft (as heft is known in the litterature).

Nathalie