Changeset 3325

Sep 12, 2014 8:51:00 AM (6 years ago)

Choose next step and add more details to it.

1 edited


  • branches/cache/plan.txt

    r3319 r3325  
    330. Next Step:
    4         if NDEBUG is not defined:
    5                 for k = 0 , ... , NumArg(op)
    6                         ArgIsVarTable[op][k]: true if k-th argument is a variable
    7         move the check that result has higher index than operands from
    8         operations into a general assert macro for all operations:
    9                 CPPAD_ASSERT_VARIABLE_ORDER(op)
     4        Implement Step 4, Caching.
    1161. In cppad/local/ad_fun.hpp add following to ADFun private data.
    2823        taylor_, change arg to cache[arg].
    30 4. To determine cache:
    31         4.1 Use a reverse analysis to determine last_use[i_var], for the
    32         last variable index that uses i_var.
     254. Caching an Operation Sequence:
    34         4.2 Use an forward analysis that starts with no cache indices free
    35         and an empty cache. For each variable, if there is a cache index
    36         available, use it for that variable. If not, push another cache index
    37         and use it for the variable. Then mark the variable index when this
    38         cache index can be freed. The free all the cache values that can be
    39         done so at this index (are operands to this variables operation).
     27        4.1 Determine last_use[i_var]:
     28    Use a reverse analysis to determine last_use[i_var], the last result index
     29        that uses variable i_var is used as an operand. Sort this vector so that
     30        last_use[i] <= last_use[j] whenever i < j.
     33        4.2 Determine cache[i_var]:
     35                4.2.1 Use an forward analysis that starts with an empty cache vector
     36                and no indices available. Initialize last_use index i_last = 0;
     38                4.2.1 For each variable i_var, if there is a cache index available, set
     39                i_cache to that index. If not, create another cache slot and set
     40                i_cache to the corresponding index. Set cache[i_var] = i_cache, and
     41                mark the corresponding index as in use.
     43                4.2.2 While last_use[i_last] < i_var, mark cache[i_last] as aviable
     44                and increment i_last.
     46        4.3 Change operand indices:
     47                For each variable index i_var that is an operand, map i_var to
     48                cache[i_var].
    41515. Example Tape:
    1061169. Changes to data sructure:
    107117        ADFun::num_var_tape_:         no longer also the size of ADFun::taylor_
    108         ADFun::num_cache_tape_:       number of chace entires in taylor_:
     118        ADFun::num_cache_tape_:       number of cache entires in taylor_:
    109119        ADFun::cache_[num_var_tape_]: is the cache index for each variable
    11212210. Forward and Reverse:
    113         10.1: If num_chace_tape_ is zero, cache will not be used.
     123        10.1: If num_cache_tape_ is zero, cache will not be used.
    114124        otherwise, the special cache operatios will be done.
Note: See TracChangeset for help on using the changeset viewer.