## lustrec / src / precedence_functions.ml @ 22fe1c93

History | View | Annotate | Download (2.92 KB)

1 | 22fe1c93 | ploc | (* ---------------------------------------------------------------------------- |
---|---|---|---|

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