source: branches/cache/plan.txt @ 3330

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

cache.hpp: better white space and comments.
plan.txt: changes missing from previous commit.

  • Property svn:keywords set to Id
File size: 5.2 KB
Line 
1Plan for implementing caching
2
30. Next Step:
4        Implement Step 4.1, sorting last_use.
5
61. In cppad/local/ad_fun.hpp add following to ADFun private data.
7                pod_vector<size_t> cache_;
8        where
9                taylor_[ cap_order_taylor_ * cache[i_var] + k ]
10        is the the cache copy of
11                taylor_[ cap_order_taylor_ * i_var + k ]
12        for k = 0 , ... , num_order_taylor_ - 1.
13
142. During forward mode, directly after
15                taylor_[ cap_order_taylor_ * i_var + p ]
16        is computed, copy
17                taylor_[ cap_order_taylor_ * i_var + k ]
18        to
19                taylor_[ cap_order_taylor_ * i_var + k ]
20        for k = 0 , ... , p-1.
21
223. For each opertion in the tape, and each argument arg that is an index in
23        taylor_, change arg to cache[arg].
24
254. Caching an Operation Sequence:
26
27        4.1 Determine last_use[i_var]:
28    Use a forward analysis to determine last_use[i_var], the last result index
29        that uses variable i_var as an operand. In the special case where i_var
30        is not used, last_use[i_var] = i_var. Sort this vector so that
31        last_use[ order[i] ] <= last_use[ order[j] ] whenever i < j.
32
33
34        4.2 Determine cache[i_var]:
35       
36                4.2.1 Use an forward analysis that starts with an empty cache vector
37                and no indices available. Initialize last_use index i_last = 0;
38
39                4.2.1 For each variable i_var, if there is a cache index available, set
40                i_cache to that index. If not, create another cache slot and set
41                i_cache to the corresponding index. Set cache[i_var] = i_cache, and
42                mark the corresponding index as in use.
43
44                4.2.2 While last_use[ order[i_last] ] <= i_var, mark
45                cache[ order[i_last] ] as aviable and increment i_last.
46
47        4.3 Change operand indices:
48                For each variable index i_var that is an operand, map i_var to
49                cache[i_var].
50 
51
525. Example Tape:
53        y[0] = 5 * (x[0] + x[1])
54        y[1] = y[0] + 5 * (x[0] - x[1]) = 10 * x[0];
55
56        o=1    v=1    Inv     | fz[0]=1
57        o=2    v=2    Inv     | fz[0]=2
58        o=3    v=3    Subvv    vl=1     vr=2    | fz[0]=-1
59        o=4    v=4    Mulpv    pl=5     vr=3    | fz[0]=-5
60        o=5    v=5    Addvv    vl=1     vr=2    | fz[0]=3
61        o=6    v=6    Mulpv    pl=5     vr=5    | fz[0]=15
62        o=7    v=7    Addvv    vl=4     vr=6    | fz[0]=10
63        o=8    v=     End     
64
65        partial_0 ( y[0] + 2 * y[1]) = 25
66        partial_1 ( y[0] + 2 * y[1]) = 5
67
686. Example Cache Index determination:
69        i_var   last_use    cache
70            0          0        8
71            1          5        8
72            2          5        9
73            3          4       10
74            4          7       11
75            5          6       10
76            6          7        8
77            7          7        9
78
797. Example Zero Order Forward Mode:
80        o=1 v=1 c=8  Inv                         | z[8] =z[1]           =1
81        o=2 v=2 c=9  Inv                         | z[9] =z[2]           =2
82        o=3 v=3 c=10 Addvv vl=1 cl=8  vr=2 cr=9  | z[10]=z[3]=z[8]+z[9] =3
83        o=4 v=4 c=11 Mulpv pl=5       vr=3 cr=10 | z[11]=z[4]=5*z[10]   =15
84        o=5 v=5 c=10 Subvv vl=1 cl=8  vr=2 cr=9  | z[10]=z[5]=z[8]-z[9] =-1
85        o=6 v=6 c=8  Mulpv pl=5       vr=5 cr=10 | z[8] =z[6]=5*z[10]   =-5
86        o=7 v=7 c=9  Addvv vl=4 cl=11 vr=6 cr=8  | z[9] =z[7]=z[11]+z[8]=10
87
888. Example First Order Reverse Mode:
89        z[*]=0, z[4]=1, z[7]=2
90
91        o=7 v=7 c=9  Addvv vl=4 cl=11 vr=6 cr=8  | z[9]+=z[7]      z[9]=2
92                                                 | z[8]+=z[9],     z[8]=2
93                                                 | z[11]+=z[9],    z[11]=2
94                                                 | z[9]=0
95
96        o=6 v=6 c=8  Mulpv pl=5       vr=5 cr=10 | z[8]+=z[6],     z[8]=2
97                                                 | z[10]+=5*z[8],  z[10]=10
98                                                 | z[8]=0
99
100        o=5 v=3 c=10 Subvv vl=1 cl=8  vr=2 cr=9  | z[10]+=z[5],    z[10]=10
101                                                 | z[8]+=z[10],    z[8]=10
102                                                 | z[9]-=z[10].    z[9]=-10
103                                                 | z[10]=0
104
105        o=4 v=4 c=11 Mulpv pl=5       vr=3 cr=10 | z[11]+=z[4],    z[11]=3
106                                                 | z[10]+=5*z[11], z[10]=15
107                                                 | z[11]=0
108
109        o=3 v=3 c=10 Addvv vl=1 cl=8  vr=2 cr=9  | z[10]+=z[3],    z[10]=15
110                                                 | z[8]+=z[10],    z[8]=25
111                                                 | z[9]+=z[10],    z[9]=5
112                                                 | z[10]=0
113
114        o=2 v=2 c=9  Inv                         | z[2]=z[9],      z[2]=5
115        o=1 v=1 c=8  Inv                         | z[1]=z[8],      z[1]=25
116
117
1189. Changes to data sructure:
119        ADFun::num_var_tape_:         no longer also the size of ADFun::taylor_
120        ADFun::num_cache_tape_:       number of cache entires in taylor_:
121        ADFun::cache_[num_var_tape_]: is the cache index for each variable
122
123
12410. Forward and Reverse:
125        10.1: If num_cache_tape_ is zero, cache will not be used.
126        otherwise, the special cache operatios will be done.
127
128        10.2: if NDEBUG is not defined, the varialbe
129        cache2variable[ADFun::num_cache_tape_] will map the cache index
130        to the corresonding current variable index. This will be used for tracing
131        and to check that the variables have the proper order for each operation;
132        i.e., the operations have lower variable index than the results.
133
13411. Operations:
135        The check that variables have proper order will be moved from each
136        individual operation into forward and reverse sweeps.
137
13812. Optmization:
139        compute the last_use and cache indices and change the
140        arguments to use cache indices instead of variable indices.
Note: See TracBrowser for help on using the repository browser.