lustrec / src / precedence_functions.ml @ 0cbf0839
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: *) |