package lustre-v6

  1. Overview
  2. Docs

Time-stamp: <modified the 21/11/2016 (at 17:07) by Erwan Jahier>

Some experiments on heuristics used in schedule Actions. Indeed, there are 2 dimensions:

  • at worst, there exists n! possible topological sorts (total orderings of actions) of a DAG (a partial ordering induced by dependencies). Some orderings are better than others because they makes it possible to factorize test opennings. Indeed, compare

"if c then e1; if c then e2;"


"if c then (e1;e2)"

  • Beside, some more tests can be saved by duplicating code. for ex

"if c then e1 ; e2 ; if c then e3;"

can be tranformed into

"if c then (e1 ; e2 ; e3) else e2;"

which saves 1 test. But of course the code size may blows up, and some trade-offs should be chosen.

Idées d'heuristiques :

  • Quand on choisit un successeur parmis dep(a), on pourrait prendre celui qui a le moins de dépendances.
val split_al : ActionsDeps.t -> Action.t list -> Action.t list * Action.t list
val compare_actions : (Lic.clock * 'a * 'b * 'c * 'd) -> (Lic.clock * 'a * 'b * 'c * 'd) -> int
val group : Action.t list -> ActionsDeps.t -> Action.t list list
val optimize_test_openning : Soc.gao list list -> Soc.gao list

Innovation. Community. Security.