source: branches/cache/cppad/local/cache.hpp @ 3328

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

Compute the cache indices.

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