src/mem/cache/tags/iic_repl/gen.hh

   1 /*
   2  * Copyright (c) 2002-2005 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Erik Hallnor
  29  */
  30
  31 /**
  32  * @file
  33  * Declarations of generational replacement policy
  34  */
  35
  36 #ifndef ___GEN_HH__
  37 #define __GEN_HH__
  38
  39 #include <list>
  40
  41 #include "base/statistics.hh"
  42 #include "mem/cache/tags/iic_repl/repl.hh"
  43 #include "params/GenRepl.hh"
  44
  45 /**
  46  * Generational Replacement entry.
  47  */
  48 class GenReplEntry
  49 {
  50   public:
  51     /** Valid flag, used to quickly invalidate bogus entries. */
  52     bool valid;
  53     /** The difference between this entry and the previous in the pool. */
  54     int delta;
  55     /** Pointer to the corresponding tag in the IIC. */
  56     unsigned long tag_ptr;
  57 };
  58
  59 /**
  60  * Generational replacement pool
  61  */
  62 class GenPool
  63 {
  64   public:
  65     /** The time the last entry was added. */
  66     Tick newest;
  67     /** The time the oldest entry was added. */
  68     Tick oldest;
  69     /** List of the replacement entries in this pool. */
  70     std::list<GenReplEntry*> entries;
  71
  72     /** The number of entries in this pool. */
  73     int size;
  74
  75     /**
  76      * Simple constructor.
  77      */
  78     GenPool() {
  79         newest = 0;
  80         oldest = 0;
  81         size = 0;
  82     }
  83
  84     /**
  85      * Add an entry to this pool.
  86      * @param re The entry to add.
  87      * @param now The current time.
  88      */
  89     void push(GenReplEntry *re, Tick now) {
  90         ++size;
  91         if (!entries.empty()) {
  92             re->delta = now - newest;
  93             newest = now;
  94         } else {
  95             re->delta = 0;
  96             newest = oldest = now;
  97         }
  98         entries.push_back(re);
  99     }
 100
 101     /**
 102      * Remove an entry from the pool.
 103      * @return The entry at the front of the list.
 104      */
 105     GenReplEntry* pop() {
 106         GenReplEntry *tmp = NULL;
 107         if (!entries.empty()) {
 108             --size;
 109             tmp = entries.front();
 110             entries.pop_front();
 111             oldest += tmp->delta;
 112         }
 113         return tmp;
 114     }
 115
 116     /**
 117      * Return the entry at the front of the list.
 118      * @return the entry at the front of the list.
 119      */
 120     GenReplEntry* top() {
 121         return entries.front();
 122     }
 123
 124     /**
 125      * Destructor.
 126      */
 127     ~GenPool() {
 128         while (!entries.empty()) {
 129             GenReplEntry *tmp = entries.front();
 130             entries.pop_front();
 131             delete tmp;
 132         }
 133     }
 134 };
 135
 136 /**
 137  * Generational replacement policy for use with the IIC.
 138  * @todo update to use STL and for efficiency
 139  */
 140 class GenRepl : public Repl
 141 {
 142   public:
 143     /** The number of pools. */
 144     int num_pools;
 145     /** The amount of time to stay in the fresh pool. */
 146     int fresh_res;
 147     /** The amount of time to stay in the normal pools. */
 148     int pool_res;
 149     /** The maximum number of entries */
 150     int num_entries;
 151     /** The number of entries currently in the pools. */
 152     int num_pool_entries;
 153     /** The number of misses. Used as the internal time. */
 154     Tick misses;
 155     /** The array of pools. */
 156     GenPool *pools;
 157
 158     // Statistics
 159
 160     /**
 161      * @addtogroup CacheStatistics
 162      * @{
 163      */
 164     /** The number of replacements from each pool. */
 165     Stats::Distribution repl_pool;
 166     /** The number of advances out of each pool. */
 167     Stats::Distribution advance_pool;
 168     /** The number of demotions from each pool. */
 169     Stats::Distribution demote_pool;
 170     /**
 171      * @}
 172      */
 173
 174     typedef GenReplParams Params;
 175     GenRepl(const Params *p);
 176
 177     /**
 178      * Destructor.
 179      */
 180     ~GenRepl();
 181
 182     /**
 183      * Returns the tag pointer of the cache block to replace.
 184      * @return The tag to replace.
 185      */
 186     virtual unsigned long getRepl();
 187
 188     /**
 189      * Return an array of N tag pointers to replace.
 190      * @param n The number of tag pointer to return.
 191      * @return An array of tag pointers to replace.
 192      */
 193     virtual unsigned long *getNRepl(int n);
 194
 195     /**
 196      * Update replacement data
 197      */
 198     virtual void doAdvance(std::list<unsigned long> &demoted);
 199
 200     /**
 201      * Add a tag to the replacement policy and return a pointer to the
 202      * replacement entry.
 203      * @param tag_index The tag to add.
 204      * @return The replacement entry.
 205      */
 206     virtual void* add(unsigned long tag_index);
 207
 208     /**
 209      * Register statistics.
 210      * @param name The name to prepend to statistic descriptions.
 211      */
 212     virtual void regStatsWithSuffix(const std::string name);
 213
 214     /**
 215      * Update the tag pointer to when the tag moves.
 216      * @param re The replacement entry of the tag.
 217      * @param old_index The old tag pointer.
 218      * @param new_index The new tag pointer.
 219      * @return 1 if successful, 0 otherwise.
 220      */
 221     virtual int fixTag(void *re, unsigned long old_index,
 222                        unsigned long new_index);
 223
 224     /**
 225      * Remove this entry from the replacement policy.
 226      * @param re The replacement entry to remove
 227      */
 228     virtual void removeEntry(void *re)
 229     {
 230         ((GenReplEntry*)re)->valid = false;
 231     }
 232
 233   protected:
 234     /**
 235      * Debug function to verify that there is only one repl entry per tag.
 236      * @param index The tag index to check.
 237      */
 238     bool findTagPtr(unsigned long index);
 239 };
 240
 241 #endif /* __GEN_HH__ */