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 1144 - (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 :    
28 :     val percent : int -> prob
29 :    
30 : jhr 1144 (* combine a conditional branch probability (trueProb) with a
31 :     * prediction heuristic (takenProb) using Dempster-Shafer theory.
32 :     *)
33 :     val combineProb2 : {trueProb : prob, takenProb : prob} -> {t : prob, f : prob}
34 :    
35 : jhr 1109 val toReal : prob -> real
36 :     val toString : prob -> string
37 :    
38 :     end
39 :    
40 : monnier 245 structure Probability :> PROBABILITY =
41 : jhr 1109 struct
42 : monnier 245
43 : jhr 1109 (* Probabilities are represented as positive rationals. Zero is
44 :     * represented as PROB(0w0, 0w0) and one is represented as
45 :     * PROB(0w1, 0w1). There are several invariants about PROB(n, d):
46 :     * 1) n <= d
47 :     * 2) if n = 0w0, then d = 0w0 (uniqueness of zero)
48 :     * 3) if d = 0w1, then n = 0w1 (uniqueness of one)
49 :     *)
50 :     datatype prob = PROB of (word * word)
51 : monnier 245
52 : jhr 1109 exception BadProb
53 : monnier 245
54 : jhr 1109 val never = PROB(0w0, 0w0)
55 : george 1136 val unlikely = PROB(0w1, 0w1000)
56 :     val likely = PROB(0w999, 0w1000)
57 : jhr 1109 val always = PROB(0w1, 0w1)
58 : monnier 245
59 : jhr 1109 (* Fast GCD on words. This algorithm is based on the following
60 :     * observations:
61 :     * - If u and v are both even, then gcd(u, v) = 2*gcd(u/2, v/2)
62 :     * - If u is even and v is odd, then gcd(u, v) = gcd(u/2, v)
63 :     * - If both are odd, then gcd(u, v) = gcd(abs(u-v), v)
64 :     *)
65 :     fun gcd (u : word, v : word) = let
66 :     fun isEven x = (Word.andb(x, 0w1) = 0w0)
67 :     fun divBy2 x = Word.>>(x, 0w1)
68 :     fun lp1 (g, u, v) =
69 :     if isEven(Word.orb(u, v))
70 :     then lp1 (Word.<<(g, 0w1), divBy2 u, divBy2 v)
71 :     else lp2 (g, u, v)
72 :     and lp2 (g, 0w0, v) = g*v
73 :     | lp2 (g, u, v) =
74 :     if (isEven u) then lp2 (g, divBy2 u, v)
75 :     else if (isEven v) then lp2 (g, u, divBy2 v)
76 :     else if (u < v) then lp2 (g, u, divBy2(v-u))
77 :     else lp2 (g, divBy2(u-v), v)
78 :     in
79 :     lp1 (0w1, u, v)
80 :     end
81 : monnier 245
82 : jhr 1109 fun normalize (0w0, _) = never
83 :     | normalize (n, d) = (case Word.compare(n, d)
84 :     of LESS => (case gcd(n, d)
85 :     of 0w1 => PROB(n, d)
86 : george 1136 | g => PROB(Word.div(n, g), Word.div(d, g))
87 : jhr 1109 (* end case *))
88 :     | EQUAL => always
89 :     | GREATER => raise BadProb
90 :     (* end case *))
91 :    
92 :     fun prob (n, d) =
93 : jhr 1110 if (n > d) orelse (n < 0) orelse (d <= 0)
94 : jhr 1109 then raise Domain
95 : jhr 1110 else normalize(Word.fromInt n, Word.fromInt d)
96 : monnier 245
97 : jhr 1109 fun add (PROB(n1, d1), PROB(n2, d2)) = normalize(d2*n1 + d1*n2, d1*d2)
98 : monnier 245
99 : jhr 1109 fun sub (PROB(n1, d1), PROB(n2, d2)) = let
100 :     val n1' = d2*n1
101 :     val n2' = d1*n2
102 :     in
103 :     if (n1' < n2') then raise BadProb else normalize(n1'-n2', d1*d2)
104 :     end
105 : monnier 245
106 : jhr 1109 fun mul (PROB(n1, d1), PROB(n2, d2)) = normalize (n1*n2, d1*d2)
107 : monnier 245
108 : jhr 1109 fun divide (PROB(n, d), m) = if (m <= 0)
109 :     then raise BadProb
110 :     else if (n = 0w0) then never
111 : george 1136 else normalize(n, d * Word.fromInt m)
112 : monnier 245
113 : jhr 1109 fun percent n =
114 :     if (n < 0) then raise BadProb
115 :     else normalize(Word.fromInt n, 0w100)
116 : monnier 245
117 : jhr 1109 fun fromFreq l = let
118 :     fun sum ([], tot) = tot
119 :     | sum (w::r, tot) = if (w < 0)
120 :     then raise BadProb
121 :     else sum(r, Word.fromInt w + tot)
122 :     val tot = sum (l, 0w0)
123 :     in
124 :     List.map (fn w => normalize(Word.fromInt w, tot)) l
125 :     end
126 : monnier 245
127 : jhr 1109 fun toReal (PROB(0w0, _)) = 0.0
128 :     | toReal (PROB(_, 0w1)) = 1.0
129 :     | toReal (PROB(n, d)) = let
130 :     fun toReal n = Real.fromLargeInt(Word.toLargeIntX n)
131 :     in
132 :     toReal n / toReal d
133 :     end
134 :    
135 :     fun toString (PROB(0w0, _)) = "0"
136 :     | toString (PROB(_, 0w1)) = "1"
137 :     | toString (PROB(n, d)) = let
138 :     val toStr = Word.fmt StringCvt.DEC
139 :     in
140 :     concat [toStr n, "/", toStr d]
141 :     end
142 :    
143 : jhr 1144 (* combine a conditional branch probability (trueProb) with a
144 :     * prediction heuristic (takenProb) using Dempster-Shafer theory.
145 :     * The basic equations (from Wu-Larus 1994) are:
146 :     * t = trueProb*takenProb / d
147 :     * f = ((1-trueProb)*(1-takenProb)) / d
148 :     * where
149 :     * d = trueProb*takenProb + ((1-trueProb)*(1-takenProb))
150 :     *)
151 :     fun combineProb2 {trueProb=PROB(n1, d1), takenProb=PROB(n2, d2)} = let
152 :     (* compute sd/sn, where
153 :     * sn/sd = (trueProb*takenProb) + (1-trueProb)*(1-takenProb)
154 :     *)
155 :     val d12 = d1*d2
156 :     val n12 = n1*n2
157 :     val (sn, sd) = let
158 :     val n = d12 + 0w2*n12 - (d2*n1) - (d1*n2)
159 :     in
160 :     (d12, n)
161 :     end
162 :     (* compute the true probability *)
163 :     val t as PROB(tn, td) = normalize(n12*sn, d12*sd)
164 :     (* compute the false probability *)
165 :     val f = PROB(td-tn, td)
166 :     in
167 :     {t = t, f = f}
168 :     end
169 :    
170 : jhr 1109 val op + = add
171 :     val op - = sub
172 :     val op * = mul
173 :     val op / = divide
174 :    
175 :     end
176 :    

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