Changeset 3328


Ignore:
Timestamp:
Sep 13, 2014 12:41:01 PM (6 years ago)
Author:
bradbell
Message:

Compute the cache indices.

Location:
branches/cache
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/cache/cppad/local/cache.hpp

    r3327 r3328  
    66$end
    77*/
     8# include <list>
    89
    910namespace CppAD { // BEGIN_CPPAD_NAMESPACE
     
    2223        CppAD::vector<size_t> last_use(num_var);
    2324        for(i = 0; i < num_var; i++)
    24                 last_use[i] = 0;
     25                last_use[i] = i;
    2526
    2627        // index of last result for current user atomic operation
     
    185186        index_sort(last_use, order);
    186187
     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
    187207        // temporary printing of result
    188         for(i = 0; i < num_var; i++)
    189         {       i_var = order[i];
    190                 std::cout << "last_use[" << i_var << "] = "
    191                 << last_use[i_var] << std::endl;
     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;
    192213        }
     214        std::cout << "num_cache = " << i_cache - num_var << std::endl;
    193215        return;
    194216}
  • branches/cache/plan.txt

    r3327 r3328  
    2727        4.1 Determine last_use[i_var]:
    2828    Use a forward analysis to determine last_use[i_var], the last result index
    29         that uses variable i_var as an operand. Sort this vector so that
     29        that uses variable i_var as an operand. In the special case where i_var
     30        is not used, last_use[i_var] = i_var. Sort this vector so that
    3031        last_use[ order[i] ] <= last_use[ order[j] ] whenever i < j.
    3132
     
    4142                mark the corresponding index as in use.
    4243
    43                 4.2.2 While last_use[ order[i_last] ] < i_var, mark
     44                4.2.2 While last_use[ order[i_last] ] <= i_var, mark
    4445                cache[ order[i_last] ] as aviable and increment i_last.
    4546
     
    6263
    63646. Example Cache Index determination:
     65        last_use[0] = 0 (dummy variable never used)
    6466        last_use[1] = 5
    6567        last_use[2] = 5
     
    6870        last_use[5] = 6
    6971        last_use[6] = 7
    70         last_use[7] = 0 (just dependent variable, never otherwise used)
     72        last_use[7] = 7 (just dependent variable, never otherwise used)
    7173
     74        cache[0]    = 8
    7275        cache[1]    = 8
    7376        cache[2]    = 9
Note: See TracChangeset for help on using the changeset viewer.