Changeset 3316


Ignore:
Timestamp:
Sep 10, 2014 8:08:06 AM (6 years ago)
Author:
bradbell
Message:

plan.txt: Add example case.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/cache/plan.txt

    r3315 r3316  
    2424        4.1 Use a reverse analysis to determine last_use[i_var], for the
    2525        last variable index that uses i_var.
     26
    2627        4.2 Use an forward analysis that starts with no cache indices free
    2728        and an empty cache. For each variable, if there is a cache index
     
    3132        done so at this index (are operands to this variables operation).
    3233
     345. Example Tape:
     35        y[0] = 5 * (x[0] + x[1]) + 5 * (x[0] - x[1]);
     36
     37        o=1    v=1    Inv     | fz[0]=1
     38        o=2    v=2    Inv     | fz[0]=2
     39        o=3    v=3    Subvv    vl=1     vr=2    | fz[0]=-1
     40        o=4    v=4    Mulpv    pl=5     vr=3    | fz[0]=-5
     41        o=5    v=5    Addvv    vl=1     vr=2    | fz[0]=3
     42        o=6    v=6    Mulpv    pl=5     vr=5    | fz[0]=15
     43        o=7    v=7    Addvv    vl=6     vr=4    | fz[0]=10
     44        o=8    v=     End     
     45
     466. Example Cache Index determination:
     47        last_use[1] = 5
     48        last_use[2] = 5
     49        last_use[3] = 4
     50        last_use[4] = 7
     51        last_use[5] = 6
     52        last_use[6] = 7
     53        last_use[7] = 0 (just dependent variable, never otherwise used)
     54
     55        cache[1]    = 8
     56        cache[2]    = 9
     57        cache[3]    = 10
     58        cache[4]    = 11
     59        cache[5]    = cache[3] = 10
     60        cache[6]    = cache[1] = 8
     61        cache[7]    = cache[1] = 9
     62
     63        Cache size  = max(cache) - min(cache) + 1 = 11 - 8 + 1 = 4
     64
     657. Example Forward Mode:
     66        o=1 v=1 c=8  Inv                         | z[8] =z[1]           =1
     67        o=2 v=2 c=9  Inv                         | z[9] =z[2]           =2
     68        o=3 v=3 c=10 Subvv vl=1 cl=8  vr=2 cr=9  | z[10]=z[3]=z[8]-z[9] =-1
     69        o=4 v=4 c=11 Mulpv pl=5       vr=3 cr=10 | z[11]=z[4]=5*z[10]   =-5
     70        o=5 v=3 c=10 Addvv vl=1 cl=8  vr=2 cr=9  | z[10]=z[5]=z[8]+z[9] =3
     71        o=6 v=6 c=8  Mulpv pl=5       vr=5 cr=10 | z[8] =z[6]=5*z[10]   =15
     72        o=7 v=7 c=9  Addvv vl=6 cl=8  vr=4 cr=11 | z[9] =z[7]=z[8]+z[11]=10
     73
     74 
     75
     76
Note: See TracChangeset for help on using the changeset viewer.