Changeset 3350


Ignore:
Timestamp:
Sep 22, 2014 6:27:27 AM (6 years ago)
Author:
bradbell
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/cache/plan.txt

    r3338 r3350  
    1111-------------------------------------------------------------------------- */
    1212
    13 Plan for implementing caching
     13I. Completed steps:
    1414
    15 0. Next Step:
    16         Implement Step 4.1, sorting last_use.
     151. In cppad/local/player.hpp add following to ADFun private data.
    1716
    18 1. In cppad/local/ad_fun.hpp add following to ADFun private data.
    19                 pod_vector<size_t> cache_;
    20         where
    21                 taylor_[ cap_order_taylor_ * cache[i_var] + k ]
     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 ]
    2225        is the the cache copy of
    2326                taylor_[ cap_order_taylor_ * i_var + k ]
    24         for k = 0 , ... , num_order_taylor_ - 1.
     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.
    2536
    26372. During forward mode, directly after
     
    2940                taylor_[ cap_order_taylor_ * i_var + k ]
    3041        to
    31                 taylor_[ cap_order_taylor_ * i_var + k ]
    32         for k = 0 , ... , p-1.
     42                taylor_[ cap_order_taylor_ * i_cache + k ]
     43        for k = 0 , ... , p-1 where i_cache = var2cache[i_var].
    3344
    34 3. For each opertion in the tape, and each argument arg that is an index in
    35         taylor_, change arg to cache[arg].
     453. For each opertion in the tape, and each argument arg[i] that is an variable,
     46        change arg[i] to var2cache[arg[i]].
    3647
    37484. Caching an Operation Sequence:
     
    4455
    4556
    46         4.2 Determine cache[i_var]:
     57        4.2 Determine var2cache[i_var]:
    4758       
    4859                4.2.1 Use an forward analysis that starts with an empty cache vector
     
    5566
    5667                4.2.2 While last_use[ order[i_last] ] <= i_var, mark
    57                 cache[ order[i_last] ] as aviable and increment i_last.
     68                var2cache[ order[i_last] ] as aviable and increment i_last.
    5869
    5970        4.3 Change operand indices:
    6071                For each variable index i_var that is an operand, map i_var to
    61                 cache[i_var].
    62  
     72                var2cache[i_var].
    6373
    64 5. Example Tape:
     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:
    6581        y[0] = 5 * (x[0] + x[1])
    6682        y[1] = y[0] + 5 * (x[0] - x[1]) = 10 * x[0];
     
    7894        partial_1 ( y[0] + 2 * y[1]) = 5
    7995
    80 6. Example Cache Index determination:
     962. Cache Index determination:
    8197        i_var   last_use    cache
    8298            0          0        8
     
    89105            7          7        9
    90106
    91 7. Example Zero Order Forward Mode:
     1073. Zero Order Forward Mode:
    92108        o=1 v=1 c=8  Inv                         | z[8] =z[1]           =1
    93109        o=2 v=2 c=9  Inv                         | z[9] =z[2]           =2
     
    98114        o=7 v=7 c=9  Addvv vl=4 cl=11 vr=6 cr=8  | z[9] =z[7]=z[11]+z[8]=10
    99115
    100 8. Example First Order Reverse Mode:
     1164. First Order Reverse Mode:
    101117        z[*]=0, z[4]=1, z[7]=2
    102118
     
    127143        o=1 v=1 c=8  Inv                         | z[1]=z[8],      z[1]=25
    128144
    129 
    130 9. Changes to data sructure:
    131         ADFun::num_var_tape_:         no longer also the size of ADFun::taylor_
    132         ADFun::num_cache_tape_:       number of cache entires in taylor_:
    133         ADFun::cache_[num_var_tape_]: is the cache index for each variable
    134 
    135 
    136 10. Forward and Reverse:
    137         10.1: If num_cache_tape_ is zero, cache will not be used.
    138         otherwise, the special cache operatios will be done.
    139 
    140         10.2: if NDEBUG is not defined, the varialbe
    141         cache2variable[ADFun::num_cache_tape_] will map the cache index
    142         to the corresonding current variable index. This will be used for tracing
    143         and to check that the variables have the proper order for each operation;
    144         i.e., the operations have lower variable index than the results.
    145 
    146 11. Operations:
    147         The check that variables have proper order will be moved from each
    148         individual operation into forward and reverse sweeps.
    149 
    150 12. Optmization:
    151         compute the last_use and cache indices and change the
    152         arguments to use cache indices instead of variable indices.
Note: See TracChangeset for help on using the changeset viewer.