cpu/trace/opt_cpu.cc

   1 /*
   2  * Copyright (c) 2004-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
  29 /**
  30  * @file
  31  * Definition of a memory trace CPU object for optimal caches. Uses a memory
  32  * trace to access a fully associative cache with optimal replacement.
  33  */
  34
  35 #include <algorithm> // For heap functions.
  36
  37 #include "cpu/trace/opt_cpu.hh"
  38 #include "cpu/trace/reader/mem_trace_reader.hh"
  39
  40 #include "sim/builder.hh"
  41 #include "sim/sim_events.hh"
  42
  43 using namespace std;
  44
  45 OptCPU::OptCPU(const string &name,
  46                MemTraceReader *_trace,
  47                int block_size,
  48                int cache_size,
  49                int _assoc)
  50     : SimObject(name), tickEvent(this), trace(_trace),
  51       numBlks(cache_size/block_size), assoc(_assoc), numSets(numBlks/assoc),
  52       setMask(numSets - 1)
  53 {
  54     int log_block_size = 0;
  55     int tmp_block_size = block_size;
  56     while (tmp_block_size > 1) {
  57         ++log_block_size;
  58         tmp_block_size = tmp_block_size >> 1;
  59     }
  60     assert(1<<log_block_size == block_size);
  61     MemReqPtr req;
  62     trace->getNextReq(req);
  63     refInfo.resize(numSets);
  64     while (req) {
  65         RefInfo temp;
  66         temp.addr = req->paddr >> log_block_size;
  67         int set = temp.addr & setMask;
  68         refInfo[set].push_back(temp);
  69         trace->getNextReq(req);
  70     }
  71
  72     // Initialize top level of lookup table.
  73     lookupTable.resize(16);
  74
  75     // Annotate references with next ref time.
  76     for (int k = 0; k < numSets; ++k) {
  77         for (RefIndex i = refInfo[k].size() - 1; i >= 0; --i) {
  78             Addr addr = refInfo[k][i].addr;
  79             initTable(addr, InfiniteRef);
  80             refInfo[k][i].nextRefTime = lookupValue(addr);
  81             setValue(addr, i);
  82         }
  83     }
  84
  85     // Reset the lookup table
  86     for (int j = 0; j < 16; ++j) {
  87         if (lookupTable[j].size() == (1<<16)) {
  88             for (int k = 0; k < (1<<16); ++k) {
  89                 if (lookupTable[j][k].size() == (1<<16)) {
  90                     for (int l = 0; l < (1<<16); ++l) {
  91                         lookupTable[j][k][l] = -1;
  92                     }
  93                 }
  94             }
  95         }
  96     }
  97
  98     tickEvent.schedule(0);
  99
 100     hits = 0;
 101     misses = 0;
 102 }
 103
 104 void
 105 OptCPU::processSet(int set)
 106 {
 107     // Initialize cache
 108     int blks_in_cache = 0;
 109     RefIndex i = 0;
 110     cacheHeap.clear();
 111     cacheHeap.resize(assoc);
 112
 113     while (blks_in_cache < assoc) {
 114         RefIndex cache_index = lookupValue(refInfo[set][i].addr);
 115         if (cache_index == -1) {
 116             // First reference to this block
 117             misses++;
 118             cache_index = blks_in_cache++;
 119             setValue(refInfo[set][i].addr, cache_index);
 120         } else {
 121             hits++;
 122         }
 123         // update cache heap to most recent reference
 124         cacheHeap[cache_index] = i;
 125         if (++i >= refInfo[set].size()) {
 126             return;
 127         }
 128     }
 129     for (int start = assoc/2; start >= 0; --start) {
 130         heapify(set,start);
 131     }
 132     //verifyHeap(set,0);
 133
 134     for (; i < refInfo[set].size(); ++i) {
 135         RefIndex cache_index = lookupValue(refInfo[set][i].addr);
 136         if (cache_index == -1) {
 137             // miss
 138             misses++;
 139             // replace from cacheHeap[0]
 140             // mark replaced block as absent
 141             setValue(refInfo[set][cacheHeap[0]].addr, -1);
 142             setValue(refInfo[set][i].addr, 0);
 143             cacheHeap[0] = i;
 144             heapify(set, 0);
 145             // Make sure its in the cache
 146             assert(lookupValue(refInfo[set][i].addr) != -1);
 147         } else {
 148             // hit
 149             hits++;
 150             assert(refInfo[set][cacheHeap[cache_index]].addr ==
 151                    refInfo[set][i].addr);
 152             assert(refInfo[set][cacheHeap[cache_index]].nextRefTime == i);
 153             assert(heapLeft(cache_index) >= assoc);
 154
 155             cacheHeap[cache_index] = i;
 156             processRankIncrease(set, cache_index);
 157             assert(lookupValue(refInfo[set][i].addr) != -1);
 158         }
 159     }
 160 }
 161 void
 162 OptCPU::tick()
 163 {
 164     // Do opt simulation
 165
 166     int references = 0;
 167     for (int set = 0; set < numSets; ++set) {
 168         if (!refInfo[set].empty()) {
 169             processSet(set);
 170         }
 171         references += refInfo[set].size();
 172     }
 173     // exit;
 174     fprintf(stderr,"sys.cpu.misses %d #opt cache misses\n",misses);
 175     fprintf(stderr,"sys.cpu.hits %d #opt cache hits\n", hits);
 176     fprintf(stderr,"sys.cpu.accesses %d #opt cache acceses\n", references);
 177     new SimExitEvent("Finshed Memory Trace");
 178 }
 179
 180 void
 181 OptCPU::initTable(Addr addr, RefIndex index)
 182 {
 183     int l1_index = (addr >> 32) & 0x0f;
 184     int l2_index = (addr >> 16) & 0xffff;
 185     assert(l1_index == addr >> 32);
 186     if (lookupTable[l1_index].size() != (1<<16)) {
 187         lookupTable[l1_index].resize(1<<16);
 188     }
 189     if (lookupTable[l1_index][l2_index].size() != (1<<16)) {
 190         lookupTable[l1_index][l2_index].resize(1<<16, index);
 191     }
 192 }
 193
 194 OptCPU::TickEvent::TickEvent(OptCPU *c)
 195     : Event(&mainEventQueue, CPU_Tick_Pri), cpu(c)
 196 {
 197 }
 198
 199 void
 200 OptCPU::TickEvent::process()
 201 {
 202     cpu->tick();
 203 }
 204
 205 const char *
 206 OptCPU::TickEvent::description()
 207 {
 208     return "OptCPU tick event";
 209 }
 210
 211
 212 BEGIN_DECLARE_SIM_OBJECT_PARAMS(OptCPU)
 213
 214     SimObjectParam<MemTraceReader *> data_trace;
 215     Param<int> size;
 216     Param<int> block_size;
 217 Param<int> assoc;
 218
 219 END_DECLARE_SIM_OBJECT_PARAMS(OptCPU)
 220
 221 BEGIN_INIT_SIM_OBJECT_PARAMS(OptCPU)
 222
 223     INIT_PARAM_DFLT(data_trace, "memory trace", NULL),
 224     INIT_PARAM(size, "cache size"),
 225     INIT_PARAM(block_size, "block size"),
 226     INIT_PARAM(assoc,"associativity")
 227
 228 END_INIT_SIM_OBJECT_PARAMS(OptCPU)
 229
 230 CREATE_SIM_OBJECT(OptCPU)
 231 {
 232     return new OptCPU(getInstanceName(),
 233                       data_trace,
 234                       block_size,
 235                       size,
 236                       assoc);
 237 }
 238
 239 REGISTER_SIM_OBJECT("OptCPU", OptCPU)