source: branches/cache/cppad/local/cache.hpp @ 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 
1/*
2$begin cache$$
3
4$section Under Construction$$
5
6$end
7*/
8# include <list>
9
10namespace CppAD { // BEGIN_CPPAD_NAMESPACE
11
12template <class Base>
13void create_cache(
14        player<Base>&       play
15)
16{       size_t i;
17
18        // number of variables in operation sequence
19        size_t num_var = play.num_var_rec();
20
21        // initialize last use for each variable as the beginning of the
22        // operation sequence
23        CppAD::vector<size_t> last_use(num_var);
24        for(i = 0; i < num_var; i++)
25                last_use[i] = i;
26
27        // index of last result for current user atomic operation
28        size_t user_i_var;
29        bool   in_user_atomic = false;
30
31        // variables used to represent one operation
32        OpCode        op;     // operator
33        const addr_t* arg;    // arguments
34        size_t        i_var;  // index of last result for operation
35        size_t        i_op;   // index of operation
36
37        // Initilalize forward mode sweep through the operation sequence
38        play.forward_start(op, arg, i_op, i_var);
39        CPPAD_ASSERT_UNKNOWN( op == BeginOp );
40
41        while( op != EndOp )
42        {       // next op
43                play.forward_next(op, arg, i_op, i_var);
44                CPPAD_ASSERT_ARG_BEFORE_RESULT(op, arg, i_var);
45                switch(op)
46                {
47                        // --------------------------------------------------------------
48                        // no argument variables for this operation
49                        case BeginOp:
50                        case CSkipOp:
51                        case CSumOp:
52                        case EndOp:
53                        case InvOp:
54                        case LdpOp:
55                        case StppOp:
56                        break;
57       
58                        // --------------------------------------------------------------
59                        // first argument is only variable for this operation
60                        case AbsOp:
61                        case AcosOp:
62                        case AsinOp:
63                        case AtanOp:
64                        case CosOp:
65                        case CoshOp:
66                        case DivvpOp:
67                        case ExpOp:
68                        case LogOp:
69                        case ParOp:
70                        case PowvpOp:
71                        case SignOp:
72                        case SinOp:
73                        case SinhOp:
74                        case SqrtOp:
75                        case SubvpOp:
76                        case TanOp:
77                        case TanhOp:
78                        last_use[ arg[0] ] = i_var;
79                        break;
80       
81                        // --------------------------------------------------------------
82                        // second argument is only variable for this operation
83                        case AddpvOp:
84                        case DisOp:
85                        case DivpvOp:
86                        case LdvOp:
87                        case MulpvOp:
88                        case PowpvOp:
89                        case StvpOp:
90                        case SubpvOp:
91                        last_use[ arg[1] ] = i_var;
92                        break;
93       
94                        // --------------------------------------------------------------
95                        // first and second arguments are only variables for this operation
96                        case AddvvOp:
97                        case DivvvOp:
98                        case MulvvOp:
99                        case PowvvOp:
100                        case SubvvOp:
101                        last_use[ arg[0] ] = i_var;
102                        last_use[ arg[1] ] = i_var;
103                        break;
104       
105                        // --------------------------------------------------------------
106                        // third argument is only variables for this operation
107                        case StpvOp:
108                        last_use[ arg[2] ] = i_var;
109                        break;
110       
111                        // --------------------------------------------------------------
112                        // second and third arguments are only variables for this operation
113                        case StvvOp:
114                        last_use[ arg[1] ] = i_var;
115                        last_use[ arg[2] ] = i_var;
116                        break;
117       
118                        // --------------------------------------------------------------
119                        // Comparison operator
120                        case ComOp:
121                        if( arg[1] & 2 )
122                        {       last_use[ arg[2] ] = i_var;
123                        }
124                        if( arg[1] & 4 )
125                        {       last_use[ arg[3] ] = i_var;
126                        }
127                        break;
128       
129                        // --------------------------------------------------------------
130                        // Print operator
131                        case PriOp:
132                        if( arg[0] & 1 )
133                        {       last_use[ arg[1] ] = i_var;
134                        }
135                        if( arg[0] & 2 )
136                        {       last_use[ arg[3] ] = i_var;
137                        }
138                        break;
139       
140                        // --------------------------------------------------------------
141                        // Conditional expression
142                        case CExpOp:
143                        if( arg[1] & 1 )
144                        {       last_use[ arg[2] ] = i_var;
145                        }
146                        if( arg[1] & 2 )
147                        {       last_use[ arg[3] ] = i_var;
148                        }
149                        if( arg[1] & 4 )
150                        {       last_use[ arg[4] ] = i_var;
151                        }
152                        if( arg[1] & 8 )
153                        {       last_use[ arg[5] ] = i_var;
154                        }
155                        break;
156       
157                        // --------------------------------------------------------------
158                        // user atomic operations
159                        case UserOp:
160                        in_user_atomic = ! in_user_atomic;
161                        if( in_user_atomic )
162                                user_i_var     = i_var + size_t( arg[3] );
163                        break;
164       
165                        case UsrapOp:
166                        break;
167       
168                        case UsravOp:
169                        // all the results may depend on this argument value
170                        // (would be slightly better to use sparsity pattern as in optimize)
171                        CPPAD_ASSERT_UNKNOWN( in_user_atomic );
172                        last_use[ arg[0] ] = user_i_var;
173                        break;
174       
175                        case UsrrpOp:
176                        case UsrrvOp:
177                        break;
178       
179                        default:
180                        CPPAD_ASSERT_UNKNOWN(false);
181                        break;
182                }
183
184        }
185
186        // sort the order of the last_use elements
187        CppAD::vector<size_t> order(num_var);
188        index_sort(last_use, order);
189
190        // initialize the cache vector and available flags as empty
191        CppAD::vector<size_t> cache(num_var);
192        std::list<size_t> available;
193        std::list<size_t>::iterator itr;
194
195        // compute the cache index corresponding to each variable index
196        size_t i_cache = num_var;
197        size_t i_last  = 0;
198        for(i_var = 0; i_var < num_var; i_var++)
199        {       if( available.empty() )
200                        available.push_front(i_cache++);
201                cache[i_var] = available.front();
202                available.pop_front();
203
204                while( i_last < num_var && last_use[ order[i_last] ] <= i_var )
205                {       available.push_back( cache[ order[i_last++] ] );
206                }
207        }
208
209        // temporary printing of result
210        std::cout << "i_var, last_use, cache" << std::endl;
211        for(i_var = 0; i_var < num_var; i_var++)
212        {       std::cout << i_var << ", ";
213                std::cout << last_use[i_var] << ", ";
214                std::cout << cache[i_var] << std::endl;
215        }
216        std::cout << "num_cache = " << i_cache - num_var << std::endl;
217        return;
218}
219
220
221template <class Base>
222void ADFun<Base>::cache(void)
223{       create_cache(play_);
224}
225
226} // END_CPPAD_NAMESPACE
Note: See TracBrowser for help on using the repository browser.