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

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/library/probability.sml
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/library/probability.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1108, Fri Mar 1 04:46:54 2002 UTC revision 1109, Fri Mar 1 13:56:06 2002 UTC
# Line 1  Line 1 
1  (*  (* probability.sml
  * Probability datatype (what the hell is this?)  
2   *   *
3   * -- Allen   * COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies.
4     *
5     * A representation of probabilities for branch prediction.
6   *)   *)
7    
8  signature PROBABILITY =  signature PROBABILITY =
9  sig  sig
    eqtype prob  
10    
11     val prob     : int * int -> prob      type prob
12     val zero     : prob  
13     val one      : prob      exception BadProb
14     val <        : prob * prob -> bool  
15     val >        : prob * prob -> bool      val never : prob    (* 0% probability *)
16     val >=       : prob * prob -> bool      val always : prob   (* 100% probability *)
17     val <=       : prob * prob -> bool  
18     val !=       : prob * prob -> bool      val prob : (word * word) -> prob
19     val ==       : prob * prob -> bool      val fromFreq : int list -> prob list
20     val compare  : prob * prob -> order  
21     val avg      : (prob * int) list -> int      val + : (prob * prob) -> prob
22     val avg_prob : (prob * prob) list -> prob      val - : (prob * prob) -> prob
23     val +        : prob * prob -> prob      val * : (prob * prob) -> prob
24     val -        : prob * prob -> prob      val / : (prob * int) -> prob
25     val *        : prob * real -> prob  
26     val /        : prob * real -> prob      val percent : int -> prob
27     val toString : prob -> string  
28     val toReal   : prob -> real     val toReal   : prob -> real
29     val fromReal : real -> prob      val toString : prob -> string
30    
31  end  end
32    
33  structure Probability :> PROBABILITY =  structure Probability :> PROBABILITY =
34  struct  struct
35    
36     structure W = Word    (* Probabilities are represented as positive rationals.  Zero is
37       * represented as PROB(0w0, 0w0) and one is represented as
38       * PROB(0w1, 0w1).  There are several invariants about PROB(n, d):
39       *    1) n <= d
40       *    2) if n = 0w0, then d = 0w0 (uniqueness of zero)
41       *    3) if d = 0w1, then n = 0w1 (uniqueness of one)
42       *)
43        datatype prob = PROB of (word * word)
44    
45     type prob = W.word      exception BadProb
46    
47     val word = W.fromInt      val never = PROB(0w0, 0w0)
48        val always = PROB(0w1, 0w1)
49    
50      (* Fast GCD on words.  This algorithm is based on the following
51       * observations:
52       *    - If u and v are both even, then gcd(u, v) = 2*gcd(u/2, v/2)
53       *    - If u is even and v is odd, then gcd(u, v) = gcd(u/2, v)
54       *    - If both are odd, then gcd(u, v) = gcd(abs(u-v), v)
55       *)
56        fun gcd (u : word, v : word) = let
57              fun isEven x = (Word.andb(x, 0w1) = 0w0)
58              fun divBy2 x = Word.>>(x, 0w1)
59              fun lp1 (g, u, v) =
60                    if isEven(Word.orb(u, v))
61                      then lp1 (Word.<<(g, 0w1), divBy2 u, divBy2 v)
62                      else lp2 (g, u, v)
63              and lp2 (g, 0w0, v) = g*v
64                | lp2 (g, u, v) =
65                    if (isEven u) then lp2 (g, divBy2 u, v)
66                    else if (isEven v) then lp2 (g, u, divBy2 v)
67                    else if (u < v) then lp2 (g, u, divBy2(v-u))
68                    else lp2 (g, divBy2(u-v), v)
69              in
70                lp1 (0w1, u, v)
71              end
72    
73        fun normalize (0w0, _) = never
74          | normalize (n, d) = (case Word.compare(n, d)
75               of LESS => (case gcd(n, d)
76                     of 0w1 => PROB(n, d)
77                      | g => PROB(Word.div(n, g), g)
78                    (* end case *))
79                | EQUAL => always
80                | GREATER => raise BadProb
81              (* end case *))
82    
83        fun prob (n, d) =
84              if (n > d) orelse (d = 0w0)
85                then raise Domain
86                else normalize(n, d)
87    
88        fun add (PROB(n1, d1), PROB(n2, d2)) = normalize(d2*n1 + d1*n2, d1*d2)
89    
90        fun sub (PROB(n1, d1), PROB(n2, d2)) = let
91              val n1' = d2*n1
92              val n2' = d1*n2
93              in
94                if (n1' < n2') then raise BadProb else normalize(n1'-n2', d1*d2)
95              end
96    
97        fun mul (PROB(n1, d1), PROB(n2, d2)) = normalize (n1*n2, d1*d2)
98    
99        fun divide (PROB(n, d), m) = if (m <= 0)
100              then raise BadProb
101              else if (n = 0w0) then never
102              else normalize(d, n * Word.fromInt m)
103    
104        fun percent n =
105              if (n < 0) then raise BadProb
106              else normalize(Word.fromInt n, 0w100)
107    
108        fun fromFreq l = let
109              fun sum ([], tot) = tot
110                | sum (w::r, tot) = if (w < 0)
111                    then raise BadProb
112                    else sum(r, Word.fromInt w + tot)
113              val tot = sum (l, 0w0)
114              in
115                List.map (fn w => normalize(Word.fromInt w, tot)) l
116              end
117    
118        fun toReal (PROB(0w0, _)) = 0.0
119          | toReal (PROB(_, 0w1)) = 1.0
120          | toReal (PROB(n, d)) = let
121              fun toReal n = Real.fromLargeInt(Word.toLargeIntX n)
122              in
123                toReal n / toReal d
124              end
125    
126     val <<   = W.<<      fun toString (PROB(0w0, _)) = "0"
127     val >>   = W.>>        | toString (PROB(_, 0w1)) = "1"
128     val op + = W.+        | toString (PROB(n, d)) = let
129     val op - = W.-            val toStr = Word.fmt StringCvt.DEC
130              in
131     infix << >>              concat [toStr n, "/", toStr d]
   
    val shift   = 0w16  
    val shift2  = 0w8  
    val one     = 0w1 << shift  
    val half    = one >> 0w1  
    val half'   = (0w1 << shift2) >> 0w1  
    val realOne = Real.fromInt(Word.toInt one)  
    val zero    = 0w0  
    val op <    = W.<  
    val op >    = W.>  
    val op >=   = W.>=  
    val op <=   = W.<=  
    val !=      = fn (i:word,j:word) => i <> j  
    val ==      = fn (i:word,j:word) => i = j  
    val compare = W.compare  
   
    fun prob (x,y)   =  
        let val h = word y  
        in W.div((word x << shift) + (h >> 0w1),h) end  
    fun fromReal r   = Word.fromInt(Real.round(r * realOne))  
    fun toReal p     = Real.fromInt(Word.toInt p) / realOne  
    fun toString p   = Real.toString(Real.fromInt(  
                           Real.round(toReal p * 100.0))/100.0)  
   
    fun p * r = fromReal(Real.*(toReal p, r))  
    fun p / r = fromReal(Real./(toReal p, r))  
   
    fun avg [] = 0  
      | avg l  =  
    let fun f([],s,n)       = (s,n)  
          | f((p,i)::l,s,n) = f(l,W.*(p,word i) + s,n+0w1)  
        val (sum,n) = f(l,zero,0w0)  
    in  Word.toInt(W.div(sum,n))  
    end  
   
    fun avg_prob [] = zero  
      | avg_prob l =  
    let fun f([],s,n)       = (s,n)  
          | f((p,i)::l,s,n) = f(l,W.*((p+half')>>shift2,(i+half')>>shift2) + s,  
                                n+0w1)  
        val (sum,n) = f(l,zero,0w0)  
    in  W.div(sum,n)  
132     end     end
133    
134        val op + = add
135        val op - = sub
136        val op * = mul
137        val op / = divide
138    
139  end  end
140    

Legend:
Removed from v.1108  
changed lines
  Added in v.1109

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