Re: [Starpu-devel] [Starpu-commits] r8197 - in trunk: doc/chapters gcc-plugin/examples/cholesky src src/core src/sched_policies tests/sched_policies

[Cedric Augonnet <cedric.augonnet@inria.fr>]

Hi,

>From the top of my head, DM only modeled task duration, called DM as "deque" 
>modeling because it modeled the length the of work in the double-enque queue 
>structure (aka. deque in Cilk) that contained tasks). The name DM was 
>unfortunate, but it remained, and DMDA was the name given to the extention 
>that considered data transfers.

DM and DMDA were originally inspired by the work in new-madeleine, and it's 
only afterward that we realized there was an algorithm called HEFT in the 
scheduling literature that did about the same.

The difference between DMDA and HEFT (at least when I left the project) is 
that the HEFT algorithm consists of two steps: we first order a window of 
tasks, and then we schedule then to minimize some metric. DMDA does not 
perform this reordering phase as tasks are scheduled (as far as I know) as 
soon as they become ready. So if we must be precise, DMDA is a degenerated 
version of HEFT with a window of size 1. If some real HEFT was to be 
implemented, my plan was to implement it as a composition of DMDA with a 
window reordering algorithm, but scheduling composition never happened (as 
far as I know). Another hand, the "motivation" for maintaining this confusing 
"double" naming is that scheduling experts know about HEFT, while DMDA would 
not speak to anybody without a 5 minutes speech before-hand.

Hope that helps understanding how this messy naming happened.

Best,

Cedric

----- Mail original -----
> De: "Ludovic Courtès" <ludovic.courtes@inria.fr>
> À: "Samuel Thibault" <samuel.thibault@ens-lyon.org>
> Cc: starpu-devel@lists.gforge.inria.fr
> Envoyé: Mardi 4 Décembre 2012 13:52:57
> Objet: Re: [Starpu-devel] [Starpu-commits] r8197 - in trunk: doc/chapters   
>   gcc-plugin/examples/cholesky src src/core
> src/sched_policies    tests/sched_policies
> 
> Samuel Thibault <samuel.thibault@ens-lyon.org> skribis:
> 
> > DMDA ((task) modeling and data aware) is the name that Cédric
> > coined
> > in papers to get a name progression from eager to dm then dmda,
> > dmda
> > latter being equivalent to heft (which does both task modeling and
> > data
> > modeling).
> 
> Do you mean that “dmda” (the code) is more-or-less an implementation
> of
> HEFT (the algorithm)?
> 
> Ludo’.
> 
> _______________________________________________
> Starpu-devel mailing list
> Starpu-devel@lists.gforge.inria.fr
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/starpu-devel
>