Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /MLRISC/releases/release-110.84/library/probability.sml
ViewVC logotype

Annotation of /MLRISC/releases/release-110.84/library/probability.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1154 - (view) (download)
Original Path: sml/trunk/src/MLRISC/library/probability.sml

1 : jhr 1109 (* probability.sml
2 : monnier 411 *
3 : jhr 1109 * COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies.
4 :     *
5 :     * A representation of probabilities for branch prediction.
6 : monnier 411 *)
7 :    
8 : monnier 245 signature PROBABILITY =
9 : jhr 1109 sig
10 : monnier 245
11 : jhr 1109 type prob
12 : monnier 245
13 : jhr 1109 exception BadProb
14 :    
15 :     val never : prob (* 0% probability *)
16 : george 1136 val unlikely : prob (* very close to 0% *)
17 :     val likely : prob (* very close to 100% *)
18 : jhr 1109 val always : prob (* 100% probability *)
19 :    
20 : jhr 1110 val prob : (int * int) -> prob
21 : jhr 1109 val fromFreq : int list -> prob list
22 :    
23 :     val + : (prob * prob) -> prob
24 :     val - : (prob * prob) -> prob
25 :     val * : (prob * prob) -> prob
26 :     val / : (prob * int) -> prob
27 : jhr 1153 val not : prob -> prob (* not p == always - p *)
28 : jhr 1109
29 :     val percent : int -> prob
30 :    
31 : jhr 1144 (* combine a conditional branch probability (trueProb) with a
32 :     * prediction heuristic (takenProb) using Dempster-Shafer theory.
33 :     *)
34 :     val combineProb2 : {trueProb : prob, takenProb : prob} -> {t : prob, f : prob}
35 :    
36 : jhr 1109 val toReal : prob -> real
37 :     val toString : prob -> string
38 :    
39 :     end
40 :    
41 : monnier 245 structure Probability :> PROBABILITY =
42 : jhr 1109 struct
43 : monnier 245
44 : jhr 1154 open IntInf
45 :    
46 :     val zero = fromInt 0
47 :     val one = fromInt 1
48 :     val two = fromInt 2
49 :     val hundred = fromInt 100
50 :     fun eq (a, b) = (compare(a, b) = EQUAL)
51 :    
52 : jhr 1109 (* Probabilities are represented as positive rationals. Zero is
53 :     * represented as PROB(0w0, 0w0) and one is represented as
54 :     * PROB(0w1, 0w1). There are several invariants about PROB(n, d):
55 :     * 1) n <= d
56 :     * 2) if n = 0w0, then d = 0w0 (uniqueness of zero)
57 :     * 3) if d = 0w1, then n = 0w1 (uniqueness of one)
58 :     *)
59 : jhr 1154 datatype prob = PROB of (IntInf.int * IntInf.int)
60 : monnier 245
61 : jhr 1109 exception BadProb
62 : monnier 245
63 : jhr 1154 val never = PROB(zero, one)
64 :     val unlikely = PROB(one, fromInt 1000)
65 :     val likely = PROB(fromInt 999, fromInt 1000)
66 :     val always = PROB(one, one)
67 : monnier 245
68 : jhr 1154 fun gcd (m, n) = if eq(n, zero) then m else gcd(n, m mod n)
69 : monnier 245
70 : jhr 1154 fun normalize (n, d) =
71 :     if eq(n, zero) then never
72 :     else (case compare(n, d)
73 :     of LESS => let
74 :     val g = gcd(n, d)
75 :     in
76 :     if eq(g, one)
77 :     then PROB(n, d)
78 :     else PROB(n div g, d div g)
79 :     end
80 :     | EQUAL => always
81 :     | GREATER => raise BadProb
82 : jhr 1109 (* end case *))
83 :    
84 :     fun prob (n, d) =
85 : jhr 1154 if Int.>(n, d) orelse Int.<(n, 0) orelse Int.<=(d, 0)
86 : jhr 1109 then raise Domain
87 : jhr 1154 else normalize(fromInt n, fromInt d)
88 : monnier 245
89 : jhr 1109 fun add (PROB(n1, d1), PROB(n2, d2)) = normalize(d2*n1 + d1*n2, d1*d2)
90 : monnier 245
91 : jhr 1109 fun sub (PROB(n1, d1), PROB(n2, d2)) = let
92 :     val n1' = d2*n1
93 :     val n2' = d1*n2
94 :     in
95 :     if (n1' < n2') then raise BadProb else normalize(n1'-n2', d1*d2)
96 :     end
97 : monnier 245
98 : jhr 1109 fun mul (PROB(n1, d1), PROB(n2, d2)) = normalize (n1*n2, d1*d2)
99 : monnier 245
100 : jhr 1154 fun divide (PROB(n, d), m) = if Int.<=(m, 0)
101 : jhr 1109 then raise BadProb
102 : jhr 1154 else if eq(n, zero) then never
103 :     else normalize(n, d * fromInt m)
104 : monnier 245
105 : jhr 1109 fun percent n =
106 : jhr 1154 if Int.<(n, 0) then raise BadProb
107 :     else normalize(fromInt n, hundred)
108 : monnier 245
109 : jhr 1109 fun fromFreq l = let
110 :     fun sum ([], tot) = tot
111 : jhr 1154 | sum (w::r, tot) = if Int.<(w, 0)
112 : jhr 1109 then raise BadProb
113 : jhr 1154 else sum(r, fromInt w + tot)
114 :     val tot = sum (l, zero)
115 : jhr 1109 in
116 : jhr 1154 List.map (fn w => normalize(fromInt w, tot)) l
117 : jhr 1109 end
118 : monnier 245
119 : jhr 1154 fun toReal (PROB(n, d)) =
120 :     if eq(n, zero) then 0.0
121 :     else if eq(d, one) then 1.0
122 :     else let
123 :     val sz = log2 d
124 :     val (n, d) = if Int.>=(sz, 30)
125 :     then let
126 :     val scale = pow(two, Int.-(sz, 30))
127 :     val n = n div scale
128 :     in
129 :     (if n > zero then n else one, d div scale)
130 :     end
131 :     else (n, d)
132 :     fun toReal n = Real.fromLargeInt(toLarge n)
133 :     in
134 :     toReal n / toReal d
135 :     end
136 : jhr 1109
137 : jhr 1154 fun toString (PROB(n, d)) =
138 :     if eq(n, zero) then "0"
139 :     else if eq(d, one) then "1"
140 :     else concat [IntInf.toString n, "/", IntInf.toString d]
141 : jhr 1109
142 : jhr 1144 (* combine a conditional branch probability (trueProb) with a
143 :     * prediction heuristic (takenProb) using Dempster-Shafer theory.
144 :     * The basic equations (from Wu-Larus 1994) are:
145 :     * t = trueProb*takenProb / d
146 :     * f = ((1-trueProb)*(1-takenProb)) / d
147 :     * where
148 :     * d = trueProb*takenProb + ((1-trueProb)*(1-takenProb))
149 :     *)
150 :     fun combineProb2 {trueProb=PROB(n1, d1), takenProb=PROB(n2, d2)} = let
151 : jhr 1154 (* compute sn/sd, where
152 :     * sd/sn = (trueProb*takenProb) + (1-trueProb)*(1-takenProb)
153 : jhr 1144 *)
154 :     val d12 = d1*d2
155 :     val n12 = n1*n2
156 :     val (sn, sd) = let
157 : jhr 1154 val n = d12 + two*n12 - (d2*n1) - (d1*n2)
158 : jhr 1144 in
159 :     (d12, n)
160 :     end
161 :     (* compute the true probability *)
162 :     val t as PROB(tn, td) = normalize(n12*sn, d12*sd)
163 :     (* compute the false probability *)
164 :     val f = PROB(td-tn, td)
165 :     in
166 :     {t = t, f = f}
167 :     end
168 :    
169 : jhr 1154 fun not (PROB(n, d)) = PROB(d-n, d)
170 : jhr 1153
171 : jhr 1109 val op + = add
172 :     val op - = sub
173 :     val op * = mul
174 :     val op / = divide
175 :    
176 :     end
177 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0