Project

General

Profile

Statistics
| Branch: | Tag: | Revision:

lustrec / src / precedence_functions.ml @ 22fe1c93

History | View | Annotate | Download (2.92 KB)

1
(* ----------------------------------------------------------------------------
2
 * SchedMCore - A MultiCore Scheduling Framework
3
 * Copyright (C) 2009-2011, ONERA, Toulouse, FRANCE - LIFL, Lille, FRANCE
4
 *
5
 * This file is part of Prelude
6
 *
7
 * Prelude is free software; you can redistribute it and/or
8
 * modify it under the terms of the GNU Lesser General Public License
9
 * as published by the Free Software Foundation ; either version 2 of
10
 * the License, or (at your option) any later version.
11
 *
12
 * Prelude is distributed in the hope that it will be useful, but
13
 * WITHOUT ANY WARRANTY ; without even the implied warranty of
14
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15
 * Lesser General Public License for more details.
16
 *
17
 * You should have received a copy of the GNU Lesser General Public
18
 * License along with this program ; if not, write to the Free Software
19
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
20
 * USA
21
 *---------------------------------------------------------------------------- *)
22

    
23
open Task_graph
24

    
25
(* Precedences as defined by g_ops(n) (see thesis manuscript) *)
26

    
27
(* g_ops(n) *)
28
let rec gops ops n =
29
  match ops with
30
  | [] -> n
31
  | (Gfby _)::rest ->
32
      gops rest (n+1)
33
  | (Guclock k)::rest ->
34
      gops rest (k*n)
35
  | (Gdclock k)::rest ->
36
      gops rest (int_of_float (ceil ((float_of_int n)/. (float_of_int k))))
37
  | (Gphclock _)::rest ->
38
      gops rest n
39
  | Gtail::rest ->
40
      if n = 0 then gops rest 0 else
41
      gops rest (n-1)
42
  | (Gconcat _)::rest ->
43
      gops rest (n+1)
44

    
45
(* pref(ops) *)
46
let pref_size ops =
47
  let rec aux ops =
48
    match ops with
49
    | [] -> 0
50
    | (Guclock k)::rest ->
51
        let props = aux rest in
52
        int_of_float (ceil ((float_of_int props) /. (float_of_int k)))
53
    | (Gdclock k)::rest ->
54
        let props = aux rest in
55
        (props -1)*k+1
56
    | Gtail::rest ->
57
        (aux rest)+1
58
    | (Gfby _)::rest | (Gconcat _)::rest ->
59
        let props = aux rest in
60
        max (props -1) 0
61
    | (Gphclock _)::rest ->
62
        aux rest
63
  in
64
  max (aux ops) 0
65

    
66
(* P(ops) *)
67
let rec periodicity ops =
68
  match ops with
69
  | [] -> 1
70
  | (Guclock k)::rest ->
71
      let pops = periodicity rest in
72
      pops/(Utils.gcd k pops)
73
  | (Gdclock k)::rest ->
74
      k*(periodicity rest)
75
  | (Gfby _)::rest ->
76
      periodicity rest
77
  | (Gphclock _)::rest | Gtail::rest | (Gconcat _)::rest ->
78
      periodicity rest
79

    
80
(* Returns the non-redundant precedence relation as defined in RTAS, ie
81
   the set of pairs (n,n') such that ti.n->tj.n' (in the first HP) *)
82
let prec_relation ops =
83
  let spref = pref_size ops in
84
  let spat = periodicity ops in
85
  let pref = Hashtbl.create spref in
86
  let pat = Hashtbl.create spat in
87
  let aux tbl n =
88
    if gops ops n <> gops ops (n+1) then
89
      Hashtbl.add tbl n (gops ops n)
90
  in
91
  for i=0 to spref-1 do
92
    aux pref i;
93
  done;
94
  for i=0 to spat-1 do
95
    aux pat i;
96
  done;
97
  (pref,pat)
98

    
99
(* Local Variables: *)
100
(* compile-command:"make -C .." *)
101
(* End: *)