Changeset 2978


Ignore:
Timestamp:
Oct 20, 2013 11:38:57 AM (6 years ago)
Author:
bradbell
Message:

Change conditional skip to skipping operations instead of skipping variables.

Location:
branches/opt_cond_exp
Files:
11 edited

Legend:

Unmodified
Added
Removed
  • branches/opt_cond_exp/cppad/local/ad_fun.hpp

    r2971 r2978  
    109109        pod_vector<Base> taylor_;
    110110
    111         /// which variables do not affect the results
    112         CppAD::vector<bool> cskip_var_;
     111        /// which operations can be conditionally skipped
     112        /// Set during forward pass of order zero
     113        CppAD::vector<bool> cskip_op_;
    113114
    114115        /// Packed results of the forward mode Jacobian sparsity calculations.
  • branches/opt_cond_exp/cppad/local/dependent.hpp

    r2971 r2978  
    271271
    272272        // conditional skip vector
    273         cskip_var_.clear();
    274         cskip_var_.resize(total_num_var_);
    275         for(i = 0; i < total_num_var_; i++)
    276                 cskip_var_[i] = false;
     273        cskip_op_.clear();
     274        cskip_op_.resize( tape->Rec_.num_rec_op() );
     275        for(i = 0; i < tape->Rec_.num_rec_op(); i++)
     276                cskip_op_[i] = false;
    277277
    278278        // now that each dependent variable has a place in the tape,
  • branches/opt_cond_exp/cppad/local/forward.hpp

    r2971 r2978  
    125125                compare_change_ = forward0sweep(s, true,
    126126                        n, total_num_var_, &play_, taylor_col_dim_, taylor_.data(),
    127                         cskip_var_
     127                        cskip_op_
    128128                );
    129129# else
    130130                compare_change_ = forward_sweep(s, true, q,
    131131                        p, n, total_num_var_, &play_, taylor_col_dim_, taylor_.data(),
    132                         cskip_var_
     132                        cskip_op_
    133133                );
    134134# endif
     
    137137        {       compare_change_ = forward_sweep(s, true, q,
    138138                        p, n, total_num_var_, &play_, taylor_col_dim_, taylor_.data(),
    139                         cskip_var_
     139                        cskip_op_
    140140                );
    141141        }
     
    143143        {       forward_sweep(s, true, q,
    144144                        p, n, total_num_var_, &play_, taylor_col_dim_, taylor_.data(),
    145                         cskip_var_
     145                        cskip_op_
    146146                );
    147147        }
  • branches/opt_cond_exp/cppad/local/forward0sweep.hpp

    r2970 r2978  
    111111index i on the tape.
    112112
    113 \param cskip_var
    114 Is a vector with size \c numvar,
     113\param cskip_op
     114Is a vector with size Rec->num_rec_op(),
    115115the input value of the elements does not matter.
    116 Upon return, if cskip_var[i] is true, the value of variable with index i
     116Upon return, if cskip_op[i] is true, the operator index i in the recording
    117117does not affect any of the dependent variable (given the value
    118118of the independent variables).
     
    135135        size_t                J,
    136136        Base                 *Taylor,
    137         CppAD::vector<bool>&  cskip_var
     137        CppAD::vector<bool>&  cskip_op
    138138)
    139139{       CPPAD_ASSERT_UNKNOWN( J >= 1 );
     
    169169
    170170        // zero order, so initialize conditional skip flags
    171         for(i = 0; i < numvar; i++)
    172                 cskip_var[i] = false;
     171        for(i = 0; i < Rec->num_rec_op(); i++)
     172                cskip_op[i] = false;
    173173
    174174        // work space used by UserOp.
     
    227227
    228228                // check if we are skipping this operation
    229                 CPPAD_ASSERT_UNKNOWN( NumRes(CSkipOp) == 0 );
    230                 CPPAD_ASSERT_UNKNOWN( NumRes(EndOp)  == 0 );
    231                 while( cskip_var[i_var] && NumRes(op) > 0 )
    232                 {       Rec->next_forward(op, arg, i_op, i_var);
    233                         if( op == CSumOp )
     229                while( cskip_op[i_op] )
     230                {       if( op == CSumOp )
    234231                        {       // CSumOp has a variable number of arguments and
    235232                                Rec->forward_csum(op, arg, i_op, i_var);
    236233                        }
     234                        Rec->next_forward(op, arg, i_op, i_var);
    237235                }
    238236
     
    312310                        Rec->forward_cskip(op, arg, i_op, i_var);
    313311                        forward_cskip_op_0(
    314                                 i_var, arg, num_par, parameter, J, Taylor, cskip_var
     312                                i_var, arg, num_par, parameter, J, Taylor, cskip_op
    315313                        );
    316314                        break;
  • branches/opt_cond_exp/cppad/local/forward_sweep.hpp

    r2970 r2978  
    120120index i on the tape.
    121121
    122 \param cskip_var
     122\param cskip_op
    123123Is a vector with size \c numvar,
    124124
     
    126126In this case,
    127127the input value of the elements does not matter.
    128 Upon return, if cskip_var[i] is true, the value of variable with index i
     128Upon return, if cskip_op[i] is true, the operator with index i
    129129does not affect any of the dependent variable (given the value
    130130of the independent variables).
     
    132132\li <tt>q > 0</tt>
    133133The vector is not modified and
    134 if cskip_var[i] is true, the value of variable with index i
     134if cskip_op[i] is true, the operator with index i
    135135does not affect any of the dependent variable (given the value
    136136of the independent variables).
     
    157157        const size_t          J,
    158158        Base                 *Taylor,
    159         CppAD::vector<bool>&  cskip_var
     159        CppAD::vector<bool>&  cskip_op
    160160)
    161161{       CPPAD_ASSERT_UNKNOWN( J >= p + 1 );
     
    198198                }
    199199                // includes zero order, so initialize conditional skip flags
    200                 for(i = 0; i < numvar; i++)
    201                         cskip_var[i] = false;
     200                for(i = 0; i < Rec->num_rec_op(); i++)
     201                        cskip_op[i] = false;
    202202        }
    203203
     
    259259                CPPAD_ASSERT_UNKNOWN( NumRes(CSkipOp) == 0 );
    260260                CPPAD_ASSERT_UNKNOWN( NumRes(EndOp)  == 0 );
    261                 while( cskip_var[i_var] && NumRes(op) > 0 )
    262                 {       Rec->next_forward(op, arg, i_op, i_var);
    263                         if( op == CSumOp )
     261                while( cskip_op[i_op] )
     262                {       if( op == CSumOp )
    264263                        {       // CSumOp has a variable number of arguments and
    265264                                Rec->forward_csum(op, arg, i_op, i_var);
    266265                        }
     266                        Rec->next_forward(op, arg, i_op, i_var);
    267267                }
    268268
     
    342342                                Rec->forward_cskip(op, arg, i_op, i_var);
    343343                                forward_cskip_op_0(
    344                                         i_var, arg, num_par, parameter, J, Taylor, cskip_var
     344                                        i_var, arg, num_par, parameter, J, Taylor, cskip_op
    345345                                );
    346346                        }
  • branches/opt_cond_exp/cppad/local/fun_construct.hpp

    r2970 r2978  
    327327
    328328        // allocate and copy the conditional skip information
    329         cskip_var_.clear();
    330         cskip_var_ = f.cskip_var_;
     329        cskip_op_.clear();
     330        cskip_op_ = f.cskip_op_;
    331331
    332332        // allocate and copy the forward sparsity information
     
    457457        compare_change_ = forward0sweep(std::cout, false,
    458458                n, total_num_var_, &play_, taylor_col_dim_, taylor_.data(),
    459                 cskip_var_
     459                cskip_op_
    460460        );
    461461# else
     
    463463        compare_change_ = forward_sweep(std::cout, false,
    464464                p, p, n, total_num_var_, &play_, taylor_col_dim_, taylor_.data(),
    465                 cskip_var_
     465                cskip_op_
    466466        );
    467467# endif
  • branches/opt_cond_exp/cppad/local/num_skip.hpp

    r2971 r2978  
    7171namespace CppAD {
    7272
     73// This routine is not const becasue it runs through the operations sequence
     74// 2DO: compute this value during zero order forward operations.
    7375template <typename Base>
    7476size_t ADFun<Base>::number_skip(void)
    75 {       // temporary indices
    76         size_t count = 0;
    77         for(size_t i = 0; i < total_num_var_; i++)
    78                 if( cskip_var_[i] )
    79                         count++;
    80         return count;
     77{       // must pass through operation sequence to map operations to variables
     78        OpCode op;
     79        size_t        i_op;
     80        size_t        i_var;
     81        const addr_t* arg;
    8182
     83        // number of variables skipped
     84        size_t n_skip = 0;
     85
     86        // start playback
     87        play_.start_forward(op, arg, i_op, i_var);
     88        CPPAD_ASSERT_UNKNOWN(op == BeginOp)
     89        while(op != EndOp)
     90        {       // next op
     91                play_.next_forward(op, arg, i_op, i_var);
     92                if( op == CSumOp)
     93                        play_.forward_csum(op, arg, i_op, i_var);
     94                else if (op == CSkipOp)
     95                        play_.forward_cskip(op, arg, i_op, i_var);
     96                //
     97                if( cskip_op_[i_op] & (NumRes(op) > 0) )
     98                        n_skip++;
     99        }
     100        return n_skip;
    82101}
    83102
  • branches/opt_cond_exp/cppad/local/op_code.hpp

    r2967 r2978  
    427427that correspond to this operation
    428428(ignored if NumRes(op) == 0).
     429
     430\par 2DO
     431print the operator index (in addition to the variables index).
    429432*/
    430433template <class Base, class Value>
  • branches/opt_cond_exp/cppad/local/optimize.hpp

    r2977 r2978  
    199199        size_t connect_index;
    200200
    201         /// Set during forward sweep to the index in the
    202         /// new operation sequence corresponding to this old varable.
     201        /// New operation sequence corresponding to this old varable.
     202        /// Set during forward sweep to the index in the new tape
    203203        addr_t new_var;
     204
     205        /// New operator index for this varable.
     206        /// Set during forward sweep to the index in the new tape
     207        size_t new_op;
     208};
     209
     210struct optimize_size_pair {
     211        size_t i_op;  // an operator index
     212        size_t i_var; // a variable index
    204213};
    205214
     
    681690
    682691\return
    683 the result value is the index corresponding to the current
     692the result is the operaiton and variable index corresponding to the current
    684693operation in the new operation sequence.
    685694*/
    686695template <class Base>
    687 size_t optimize_record_pv(
     696optimize_size_pair optimize_record_pv(
    688697        const CppAD::vector<struct optimize_old_variable>& tape           ,
    689698        size_t                                             current        ,
     
    713722        new_arg[1]   = tape[ arg[1] ].new_var;
    714723        rec->PutArg( new_arg[0], new_arg[1] );
    715         size_t i     = rec->PutOp(op);
    716         CPPAD_ASSERT_UNKNOWN( size_t(new_arg[0]) < i );
    717         return i;
     724
     725        optimize_size_pair ret;
     726        ret.i_op  = rec->num_rec_op();
     727        ret.i_var = rec->PutOp(op);
     728        CPPAD_ASSERT_UNKNOWN( size_t(new_arg[0]) < ret.i_var );
     729        return ret;
    718730}
    719731
     
    780792
    781793\return
    782 the result value is the index corresponding to the current
     794the result operation and variable index corresponding to the current
    783795operation in the new operation sequence.
    784796*/
    785797template <class Base>
    786 size_t optimize_record_vp(
     798optimize_size_pair optimize_record_vp(
    787799        const CppAD::vector<struct optimize_old_variable>& tape           ,
    788800        size_t                                             current        ,
     
    810822        new_arg[1]   = rec->PutPar( par[arg[1]] );
    811823        rec->PutArg( new_arg[0], new_arg[1] );
    812         size_t i     = rec->PutOp(op);
    813         CPPAD_ASSERT_UNKNOWN( size_t(new_arg[0]) < i );
    814         return i;
     824
     825        optimize_size_pair ret;
     826        ret.i_op  = rec->num_rec_op();
     827        ret.i_var = rec->PutOp(op);
     828        CPPAD_ASSERT_UNKNOWN( size_t(new_arg[0]) < ret.i_var );
     829        return ret;
    815830}
    816831
     
    876891
    877892\return
    878 the result value is the index corresponding to the current
     893the result is the operation and variable index corresponding to the current
    879894operation in the new operation sequence.
    880895*/
    881896template <class Base>
    882 size_t optimize_record_vv(
     897optimize_size_pair optimize_record_vv(
    883898        const CppAD::vector<struct optimize_old_variable>& tape           ,
    884899        size_t                                             current        ,
     
    908923        new_arg[1]   = tape[ arg[1] ].new_var;
    909924        rec->PutArg( new_arg[0], new_arg[1] );
    910         size_t i     = rec->PutOp(op);
    911         CPPAD_ASSERT_UNKNOWN( size_t(new_arg[0]) < i );
    912         return i;
     925
     926        optimize_size_pair ret;
     927        ret.i_op  = rec->num_rec_op();
     928        ret.i_var = rec->PutOp(op);
     929        CPPAD_ASSERT_UNKNOWN( size_t(new_arg[0]) < ret.i_var );
     930        CPPAD_ASSERT_UNKNOWN( size_t(new_arg[1]) < ret.i_var );
     931        return ret;
    913932}
    914933
     
    10021021
    10031022template <class Base>
    1004 size_t optimize_record_csum(
     1023optimize_size_pair optimize_record_csum(
    10051024        const CppAD::vector<struct optimize_old_variable>& tape           ,
    10061025        size_t                                             current        ,
     
    11351154        }
    11361155        rec->PutArg(n_add + n_sub);        // arg[3 + arg[0] + arg[1]]
    1137         i = rec->PutOp(CSumOp);
    1138         CPPAD_ASSERT_UNKNOWN(new_arg < tape.size());
    1139 
    1140         return i;
     1156
     1157
     1158        optimize_size_pair ret;
     1159        ret.i_op  = rec->num_rec_op();
     1160        ret.i_var = rec->PutOp(CSumOp);
     1161        CPPAD_ASSERT_UNKNOWN( new_arg < ret.i_var );
     1162        return ret;
    11411163}
    11421164// ==========================================================================
     
    17131735        // -------------------------------------------------------------
    17141736
    1715         // Erase all information in the recording
    1716         rec->free();
    1717 
    17181737        // Determine which variables can be conditionally skipped
    17191738        // 2DO: Perhaps we should change NumRes( UserOp ) = 1 , so it
     
    17471766        CPPAD_ASSERT_UNKNOWN( tape[0].op == BeginOp );
    17481767
    1749         // initialize mapping from old variable index to new variable index
     1768        // initialize mapping from old variable index to new
     1769        // operator and variable index
    17501770        for(i = 0; i < num_var; i++)
    1751                 tape[i].new_var = num_var; // invalid index
    1752        
     1771        {       tape[i].new_op  = rec->num_rec_op(); // invalid index
     1772                tape[i].new_var = num_var;           // invalid index
     1773        }
     1774
     1775        // Erase all information in the old recording
     1776        rec->free();
    17531777
    17541778        // initialize mapping from old VecAD index to new VecAD index
     
    17841808        CPPAD_ASSERT_UNKNOWN( op == BeginOp );
    17851809        CPPAD_ASSERT_NARG_NRES(BeginOp, 0, 1);
     1810        tape[i_var].new_op  = rec->num_rec_op();
    17861811        tape[i_var].new_var = rec->PutOp(BeginOp);
    17871812
     
    17921817        // (decalared here to avoid realloaction of memory)
    17931818        optimize_csum_stacks csum_work;
     1819
     1820        // tempory used to hold a size_pair
     1821        optimize_size_pair size_pair;
    17941822
    17951823        user_state = user_start;
     
    19051933                                new_arg[0]   = tape[ arg[0] ].new_var;
    19061934                                rec->PutArg( new_arg[0] );
    1907                                 i                   = rec->PutOp(op);
    1908                                 tape[i_var].new_var = i;
     1935                                tape[i_var].new_op  = rec->num_rec_op();
     1936                                tape[i_var].new_var = i = rec->PutOp(op);
    19091937                                CPPAD_ASSERT_UNKNOWN( size_t(new_arg[0]) < i );
    19101938                        }
     
    19171945                        {
    19181946                                // convert to a sequence of summation operators
    1919                                 tape[i_var].new_var = optimize_record_csum(
     1947                                size_pair = optimize_record_csum(
    19201948                                        tape                , // inputs
    19211949                                        i_var               ,
     
    19251953                                        csum_work
    19261954                                );
     1955                                tape[i_var].new_op  = size_pair.i_op;
     1956                                tape[i_var].new_var = size_pair.i_var;
    19271957                                // abort rest of this case
    19281958                                break;
     
    19411971                                tape[i_var].new_var = match_var;
    19421972                        else
    1943                         {       tape[i_var].new_var = optimize_record_vp(
     1973                        {       size_pair = optimize_record_vp(
    19441974                                        tape                , // inputs
    19451975                                        i_var               ,
     
    19501980                                        arg
    19511981                                );
     1982                                tape[i_var].new_op  = size_pair.i_op;
     1983                                tape[i_var].new_var = size_pair.i_var;
    19521984                                replace_hash = true;
    19531985                        }
     
    19611993                        {
    19621994                                // convert to a sequence of summation operators
    1963                                 tape[i_var].new_var = optimize_record_csum(
     1995                                size_pair = optimize_record_csum(
    19641996                                        tape                , // inputs
    19651997                                        i_var               ,
     
    19692001                                        csum_work
    19702002                                );
     2003                                tape[i_var].new_op  = size_pair.i_op;
     2004                                tape[i_var].new_var = size_pair.i_var;
    19712005                                // abort rest of this case
    19722006                                break;
     
    19862020                                tape[i_var].new_var = match_var;
    19872021                        else
    1988                         {       tape[i_var].new_var = optimize_record_pv(
     2022                        {       size_pair = optimize_record_pv(
    19892023                                        tape                , // inputs
    19902024                                        i_var               ,
     
    19952029                                        arg
    19962030                                );
     2031                                tape[i_var].new_op  = size_pair.i_op;
     2032                                tape[i_var].new_var = size_pair.i_var;
    19972033                                replace_hash = true;
    19982034                        }
     
    20082044                        {
    20092045                                // convert to a sequence of summation operators
    2010                                 tape[i_var].new_var = optimize_record_csum(
     2046                                size_pair = optimize_record_csum(
    20112047                                        tape                , // inputs
    20122048                                        i_var               ,
     
    20162052                                        csum_work
    20172053                                );
     2054                                tape[i_var].new_op  = size_pair.i_op;
     2055                                tape[i_var].new_var = size_pair.i_var;
    20182056                                // abort rest of this case
    20192057                                break;
     
    20332071                                tape[i_var].new_var = match_var;
    20342072                        else
    2035                         {       tape[i_var].new_var = optimize_record_vv(
     2073                        {       size_pair = optimize_record_vv(
    20362074                                        tape                , // inputs
    20372075                                        i_var               ,
     
    20422080                                        arg
    20432081                                );
     2082                                tape[i_var].new_op  = size_pair.i_op;
     2083                                tape[i_var].new_var = size_pair.i_var;
    20442084                                replace_hash = true;
    20452085                        }
     
    20722112                                new_arg[5]
    20732113                        );
     2114                        tape[i_var].new_op  = rec->num_rec_op();
    20742115                        tape[i_var].new_var = rec->PutOp(op);
    20752116                        break;
     
    20842125                        case InvOp:
    20852126                        CPPAD_ASSERT_NARG_NRES(op, 0, 1);
     2127                        tape[i_var].new_op  = rec->num_rec_op();
    20862128                        tape[i_var].new_var = rec->PutOp(op);
    20872129                        break;
     
    20932135
    20942136                        rec->PutArg( new_arg[0] );
     2137                        tape[i_var].new_op  = rec->num_rec_op();
    20952138                        tape[i_var].new_var = rec->PutOp(op);
    20962139                        break;
     
    21072150                                0
    21082151                        );
     2152                        tape[i_var].new_op  = rec->num_rec_op();
    21092153                        tape[i_var].new_var = rec->PutOp(op);
    21102154                        break;
     
    21222166                                0
    21232167                        );
     2168                        tape[i_var].new_var = rec->num_rec_op();
    21242169                        tape[i_var].new_var = rec->PutOp(op);
    21252170                        break;
     
    22372282                        case UsrrvOp:
    22382283                        CPPAD_ASSERT_NARG_NRES(op, 0, 1);
     2284                        tape[i_var].new_op  = rec->num_rec_op();
    22392285                        tape[i_var].new_var = rec->PutOp(UsrrvOp);
    22402286                        break;
     
    22752321                        for(j = 0; j < n_true; j++)
    22762322                        {       i_var = info.skip_on_true[j];
    2277                                 info.arg[6 + j] = tape[i_var].new_var;
     2323                                info.arg[6 + j] = tape[i_var].new_op;
    22782324                        }
    22792325                        for(j = 0; j < n_false; j++)
    22802326                        {       i_var = info.skip_on_false[j];
    2281                                 info.arg[6 + n_true + j] = tape[i_var].new_var;
     2327                                info.arg[6 + n_true + j] = tape[i_var].new_op;
    22822328                        }
    22832329                        info.arg[6 + n_true + n_false] =
  • branches/opt_cond_exp/cppad/local/recorder.hpp

    r2967 r2978  
    120120        {       return num_rec_var_; }
    121121
     122        /// Number of operators currently stored in the recording.
     123        size_t num_rec_op(void) const
     124        {       return  rec_op_.size(); }
     125
    122126        /// Approximate amount of memory used by the recording
    123127        size_t Memory(void) const
  • branches/opt_cond_exp/example/number_skip.cpp

    r2971 r2978  
    6262        x[0]    = 3.;
    6363        x[1]    = 4.;
    64         f.Forward(0, x);
     64        y   = f.Forward(0, x);
     65        ok &= (y[0] == x[0] + x[1]);
    6566
    6667        // before call to optimize
     
    7071        // now optimize the operation sequence
    7172        f.optimize();
    72         f.Forward(0, x);
    7373
    74         // after call to optimize and forward
     74        // after optimize, check forward mode result
     75        x[0]    = 4.;
     76        x[1]    = 3.;
     77        y   = f.Forward(0, x);
     78        ok &= (y[0] == x[0] - x[1]);
     79
     80        // after optimize, check amount of optimization
    7581        ok &= f.size_var() == n_var - 1;
    7682        ok &= f.number_skip() == 1;
Note: See TracChangeset for help on using the changeset viewer.