## 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: *) |