starpu-max/doc/doxygen_dev/chapters/010_core.doxy

/* StarPU --- Runtime system for heterogeneous multicore architectures.
 *
 * Copyright (C) 2018                                     Inria
 *
 * StarPU is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or (at
 * your option) any later version.
 *
 * StarPU is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 * See the GNU Lesser General Public License in COPYING.LGPL for more details.
 */

/*! \page StarPUCore StarPU Core

\section CoreEntities StarPU Core Entities

TODO

\subsection CoreEntitiesOverview Overview

Execution entities:
- worker: A worker (see \ref CoreEntitiesWorkers, \ref
  CoreEntitiesWorkersAndContexts) entity is a thread created by StarPU to manage
  one computing unit. The computing unit can be a local CPU core, an accelerator
  or GPU device, or --- on the master side when running in master-slave
  distributed mode --- a remote slave computing node. It is responsible for
  querying scheduling policies for tasks to execute.

- sched_context: A scheduling context (see \ref CoreEntitiesContexts, \ref
  CoreEntitiesWorkersAndContexts) is a logical set of workers governed by an
  instance of a scheduling policy. It defines the computing units to which the
  scheduling policy instance may assign work entities.

- driver: A driver is the set of hardware-dependent routines used by a
  worker to initialize its associated computing unit, execute work entities on
  it, and finalize the computing unit usage at the end of the session.

Work entities:
- task: TODO
- job: TODO

Data entities:
- data handle
- data replicate: TODO

\subsection CoreEntitiesWorkers Workers

TODO

\subsubsection CoreEntitiesWorkersStates States

Scheduling operations related state

While a worker is conducting a scheduling operations, e.g. the worker is in the
process of selecting a new task to execute, flag state_sched_op_pending is set
to !0, otherwise it is set to 0.

While state_sched_op_pending is !0, the following exhaustive list of operations on that
workers are restricted in the stated way:

- adding the worker to a context is not allowed;
- removing the worker from a context is not allowed;
- adding the worker to a parallel task team is not allowed;
- removing the worker from a parallel task team is not allowed;
- querying state information about the worker is only allowed while
  state_relax_refcnt > 0;
  - in particular, querying whether the worker is blocked on a parallel team entry is only
  allowed while state_relax_refcnt > 0.

Entering and leaving the state_sched_op_pending state is done through calls to
_starpu_worker_enter_sched_op() and _starpu_worker_leave_sched_op()
respectively (see these functions in use in functions _starpu_get_worker_task() and
_starpu_get_multi_worker_task()). These calls ensure that any pending
conflicting operation deferred while the worker was in the
state_sched_op_pending state is performed in an orderly manner.


Scheduling contexts related states

Flag state_changing_ctx_notice is set to !0 when a thread is about to
add to a scheduling context or remove it from a scheduling context, and is
currently waiting for a safe window to do, until the targeted worker is not in a
scheduling operation or parallel task operation anymore. This flag set to !0 will also
prevent the targeted worker to attempt a fresh scheduling operation or parallel
task operation to avoid starving conditions. However, a scheduling operation
that was already in process before the notice is allowed to complete.

Flag state_changing_ctx_waiting is set to !0 when a scheduling context worker
addition or removal involving the targeted worker is about to occur and the
worker is currently performing a scheduling operation to tell the targeted
worker that the initiator thread is waiting for the scheduling operation to
complete and should be woken up upon completion.

Relaxed synchronization related states

Any StarPU worker may participate to scheduling operations, and in this process,
may be forced to observe state information from other workers. 
A StarPU worker thread may therefore be observed by any thread, even
other StarPU workers. Since workers may observe each other in any order, it is
not possible to rely exclusively on the sched_mutex of each worker to protect the
observation of worker state flags by other workers, because
worker A observing worker B would involve locking workers in (A B) sequence,
while worker B observing worker A would involve locking workers in (B A)
sequence, leading to lock inversion deadlocks.

In consequence, no thread must hold more than one worker's sched_mutex at any time.
Instead, workers implement a relaxed locking scheme based on the state_relax_refcnt
counter, itself protected by the worker's sched_mutex. When state_relax_refcnt
> 0, the targeted worker state flags may be observed, otherwise the thread attempting
>the observation must repeatedly wait on the targeted worker's sched_cond
>condition until state_relax_refcnt > 0.

The relaxed mode, while on, can actually be seen as a transactional consistency
model, where concurrent accesses are authorized and potential conflicts are
resolved after the fact. When the relaxed mode is off, the consistency model
becomes a mutual exclusion model, where the sched_mutex of the worker must be
held in order to access or change the worker state.

Parallel tasks related states

When a worker is scheduled to participate to the execution of a parallel task,
it must wait for the whole team of workers participating to the execution of
this task to be ready. While the worker waits for its teammates, it is not
available to run other tasks or perform other operations. Such a waiting
operation can therefore not start while conflicting operations such as
scheduling operations and scheduling context resizing involving the worker are
on-going. Conversely these operations and other may query weather the worker is
blocked on a parallel task entry with starpu_worker_is_blocked_in_parallel().

The starpu_worker_is_blocked_in_parallel() function is allowed to proceed while
and only while state_relax_refcnt > 0. Due to the relaxed worker locking scheme,
the state_blocked_in_parallel flag of the targeted worker may change after it
has been observed by an observer thread. In consequence, flag
state_blocked_in_parallel_observed of the targeted worker is set to 1 by the
observer immediately after the observation to "taint" the targeted worker. The
targeted worker will clear the state_blocked_in_parallel_observed flag tainting
and defer the processing of parallel task related requests until a full
scheduling operation shot completes without the
state_blocked_in_parallel_observed flag being tainted again. The purpose of this
tainting flag is to prevent parallel task operations to be started immediately
after the observation of a transient scheduling state.

Worker's management of parallel tasks is
governed by the following set of state flags and counters:

- state_blocked_in_parallel: set to !0 while the worker is currently blocked on a parallel
  task;
- state_blocked_in_parallel_observed: set to !0 to taint the worker when a
  thread has observed the state_blocked_in_parallel flag of this worker while
  its state_relax_refcnt state counter was >0. Any pending request to add or
  remove the worker from a parallel task team will be deferred until a whole
  scheduling operation shot completes without being tainted again.

- state_block_in_parallel_req: set to !0 when a thread is waiting on a request
  for the worker to be added to a parallel task team. Must be protected by the
  worker's sched_mutex.

- state_block_in_parallel_ack: set to !0 by the worker when acknowledging a
  request for being added to a parallel task team. Must be protected by the
  worker's sched_mutex.


- state_unblock_in_parallel_req: set to !0 when a thread is waiting on a request
  for the worker to be removed from a parallel task team. Must be protected by the
  worker's sched_mutex.


- state_unblock_in_parallel_ack: set to !0 by the worker when acknowledging a
  request for being removed from a parallel task team. Must be protected by the
  worker's sched_mutex.


- block_in_parallel_ref_count: counts the number of consecutive pending requests
  to enter parallel task teams. Only the first of a train of requests for
  entering parallel task teams triggers the transition of the
  state_block_in_parallel_req flag from 0 to 1. Only the last of a train of
  requests to leave a parallel task team triggers the transition of flag
  state_unblock_in_parallel_req from 0 to 1. Must be protected by the
  worker's sched_mutex.



\subsection CoreEntitiesContexts Scheduling Contexts

TODO

\subsection CoreEntitiesWorkersAndContexts Workers and Scheduling Contexts

TODO

*/