source: branches/cache/plan.txt @ 3350

Last change on this file since 3350 was 3350, checked in by bradbell, 6 years ago

plan.txt: Change to current status and example computation.

  • Property svn:keywords set to Id
File size: 5.4 KB
Line 
1/* $Id: plan.txt 3350 2014-09-22 10:27:27Z bradbell $ */
2/* --------------------------------------------------------------------------
3CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-14 Bradley M. Bell
4
5CppAD is distributed under multiple licenses. This distribution is under
6the terms of the
7                    Eclipse Public License Version 1.0.
8
9A copy of this license is included in the COPYING file of this distribution.
10Please visit http://www.coin-or.org/CppAD/ for information on other licenses.
11-------------------------------------------------------------------------- */
12
13I. Completed steps:
14
151. In cppad/local/player.hpp add following to ADFun private data.
16
17        num_cache_rec_:
18        size of he cache.  If num_cache_ is zero, cache will not be used.
19        otherwise, the special cache operatios will be done.
20
21        var2cache_rec_:
22        mapping from the variable indices to the correspnding cache indices.
23        where in ADFun:
24                taylor_[ cap_order_taylor_ * var2cache[i_var] + k ]
25        is the the cache copy of
26                taylor_[ cap_order_taylor_ * i_var + k ]
27        for k = 0 , ... , play.num_var_rec_ - 1.
28
29
30        cache2var:
31        During forward mode, and if NDEBUG is not defined, the variable
32        cache2var is used to map cache indices to the corresonding current
33        variable index.  This will be used for tracing
34        and to check that the variables have the proper order for each operation;
35        i.e., the operations have lower variable index than the results.
36
372. During forward mode, directly after
38                taylor_[ cap_order_taylor_ * i_var + p ]
39        is computed, copy
40                taylor_[ cap_order_taylor_ * i_var + k ]
41        to
42                taylor_[ cap_order_taylor_ * i_cache + k ]
43        for k = 0 , ... , p-1 where i_cache = var2cache[i_var].
44
453. For each opertion in the tape, and each argument arg[i] that is an variable,
46        change arg[i] to var2cache[arg[i]].
47
484. Caching an Operation Sequence:
49
50        4.1 Determine last_use[i_var]:
51    Use a forward analysis to determine last_use[i_var], the last result index
52        that uses variable i_var as an operand. In the special case where i_var
53        is not used, last_use[i_var] = i_var. Sort this vector so that
54        last_use[ order[i] ] <= last_use[ order[j] ] whenever i < j.
55
56
57        4.2 Determine var2cache[i_var]:
58       
59                4.2.1 Use an forward analysis that starts with an empty cache vector
60                and no indices available. Initialize last_use index i_last = 0;
61
62                4.2.1 For each variable i_var, if there is a cache index available, set
63                i_cache to that index. If not, create another cache slot and set
64                i_cache to the corresponding index. Set cache[i_var] = i_cache, and
65                mark the corresponding index as in use.
66
67                4.2.2 While last_use[ order[i_last] ] <= i_var, mark
68                var2cache[ order[i_last] ] as aviable and increment i_last.
69
70        4.3 Change operand indices:
71                For each variable index i_var that is an operand, map i_var to
72                var2cache[i_var].
73
745. Checking Variable Order.
75        The check that variables have proper order has been moved from each
76        individual operation into forward and reverse sweeps.
77
78II. Example
79
801. Case:
81        y[0] = 5 * (x[0] + x[1])
82        y[1] = y[0] + 5 * (x[0] - x[1]) = 10 * x[0];
83
84        o=1    v=1    Inv     | fz[0]=1
85        o=2    v=2    Inv     | fz[0]=2
86        o=3    v=3    Subvv    vl=1     vr=2    | fz[0]=-1
87        o=4    v=4    Mulpv    pl=5     vr=3    | fz[0]=-5
88        o=5    v=5    Addvv    vl=1     vr=2    | fz[0]=3
89        o=6    v=6    Mulpv    pl=5     vr=5    | fz[0]=15
90        o=7    v=7    Addvv    vl=4     vr=6    | fz[0]=10
91        o=8    v=     End     
92
93        partial_0 ( y[0] + 2 * y[1]) = 25
94        partial_1 ( y[0] + 2 * y[1]) = 5
95
962. Cache Index determination:
97        i_var   last_use    cache
98            0          0        8
99            1          5        8
100            2          5        9
101            3          4       10
102            4          7       11
103            5          6       10
104            6          7        8
105            7          7        9
106
1073. Zero Order Forward Mode:
108        o=1 v=1 c=8  Inv                         | z[8] =z[1]           =1
109        o=2 v=2 c=9  Inv                         | z[9] =z[2]           =2
110        o=3 v=3 c=10 Addvv vl=1 cl=8  vr=2 cr=9  | z[10]=z[3]=z[8]+z[9] =3
111        o=4 v=4 c=11 Mulpv pl=5       vr=3 cr=10 | z[11]=z[4]=5*z[10]   =15
112        o=5 v=5 c=10 Subvv vl=1 cl=8  vr=2 cr=9  | z[10]=z[5]=z[8]-z[9] =-1
113        o=6 v=6 c=8  Mulpv pl=5       vr=5 cr=10 | z[8] =z[6]=5*z[10]   =-5
114        o=7 v=7 c=9  Addvv vl=4 cl=11 vr=6 cr=8  | z[9] =z[7]=z[11]+z[8]=10
115
1164. First Order Reverse Mode:
117        z[*]=0, z[4]=1, z[7]=2
118
119        o=7 v=7 c=9  Addvv vl=4 cl=11 vr=6 cr=8  | z[9]+=z[7]      z[9]=2
120                                                 | z[8]+=z[9],     z[8]=2
121                                                 | z[11]+=z[9],    z[11]=2
122                                                 | z[9]=0
123
124        o=6 v=6 c=8  Mulpv pl=5       vr=5 cr=10 | z[8]+=z[6],     z[8]=2
125                                                 | z[10]+=5*z[8],  z[10]=10
126                                                 | z[8]=0
127
128        o=5 v=3 c=10 Subvv vl=1 cl=8  vr=2 cr=9  | z[10]+=z[5],    z[10]=10
129                                                 | z[8]+=z[10],    z[8]=10
130                                                 | z[9]-=z[10].    z[9]=-10
131                                                 | z[10]=0
132
133        o=4 v=4 c=11 Mulpv pl=5       vr=3 cr=10 | z[11]+=z[4],    z[11]=3
134                                                 | z[10]+=5*z[11], z[10]=15
135                                                 | z[11]=0
136
137        o=3 v=3 c=10 Addvv vl=1 cl=8  vr=2 cr=9  | z[10]+=z[3],    z[10]=15
138                                                 | z[8]+=z[10],    z[8]=25
139                                                 | z[9]+=z[10],    z[9]=5
140                                                 | z[10]=0
141
142        o=2 v=2 c=9  Inv                         | z[2]=z[9],      z[2]=5
143        o=1 v=1 c=8  Inv                         | z[1]=z[8],      z[1]=25
144
Note: See TracBrowser for help on using the repository browser.