  The tremendous increase in the size and heterogeneity of supercomputers makes
it very difficult to predict the performance of a scheduling algorithm.
Therefore, dynamic solutions, where scheduling decisions are made at runtime
have overpassed static allocation strategies. The simplicity and efficiency of
dynamic schedulers such as Hadoop are a key of the success of the MapReduce
framework. Dynamic schedulers such as StarPU, PaRSEC or StarSs are also
developed for more constrained computations, e.g. task graphs coming from
linear algebra. To make their decisions, these runtime systems make use of some
static information, such as the distance of tasks to the critical path or the
affinity between tasks and computing resources (CPU, GPU,...) and of dynamic
information, such as where input data are actually located. In this paper, we
concentrate on two elementary linear algebra kernels, namely the outer product
and the matrix multiplication. For each problem, we propose several dynamic
strategies that can be used at runtime and we provide an analytic study of
their theoretical performance. We prove that the theoretical analysis provides
very good estimate of the amount of communications induced by a dynamic
strategy and can be used in order to efficiently determine thresholds used in
dynamic scheduler, thus enabling to choose among them for a given problem and
architecture.
