1

(* 

2

* SchedMCore  A MultiCore Scheduling Framework

3

* Copyright (C) 20092011, 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 021111307

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 (n1)

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 nonredundant 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 spref1 do

92

aux pref i;

93

done;

94

for i=0 to spat1 do

95

aux pat i;

96

done;

97

(pref,pat)

98


99

(* Local Variables: *)

100

(* compilecommand:"make C .." *)

101

(* End: *)
