specialize fully-associative caches

the dumb linear search of a set's tag array was far too slow

4 files changed, 114 insertions, 51 deletions

diff --git a/riscv/cachesim.cc b/riscv/cachesim.cc
index d029c29..cd33ca1 100644
--- a/riscv/cachesim.cc
+++ b/riscv/cachesim.cc
@@ -1,4 +1,5 @@
 #include "cachesim.h"
+#include "common.h"
 #include <cstdlib>
 #include <iostream>
 #include <iomanip>
@@ -18,19 +19,20 @@ static void help()
   exit(1);
 }
 
-cache_sim_t::cache_sim_t(const char* config, const char* _name)
- : name(_name)
+cache_sim_t* cache_sim_t::construct(const char* config, const char* name)
 {
   const char* wp = strchr(config, ':');
   if (!wp++) help();
   const char* bp = strchr(wp, ':');
   if (!bp++) help();
 
-  sets = atoi(std::string(config, wp).c_str());
-  ways = atoi(std::string(wp, bp).c_str());
-  linesz = atoi(bp);
+  size_t sets = atoi(std::string(config, wp).c_str());
+  size_t ways = atoi(std::string(wp, bp).c_str());
+  size_t linesz = atoi(bp);
 
-  init();
+  if (ways > 4 /* empirical */ && sets == 1)
+    return new fa_cache_sim_t(ways, linesz, name);
+  return new cache_sim_t(sets, ways, linesz, name);
 }
 
 void cache_sim_t::init()
@@ -96,34 +98,80 @@ void cache_sim_t::print_stats()
   std::cout << "Miss Rate:             " << mr << '%' << std::endl;
 }
 
+uint64_t* cache_sim_t::check_tag(uint64_t addr)
+{
+  size_t idx = (addr >> idx_shift) & (sets-1);
+  size_t tag = (addr >> idx_shift) | VALID;
+
+  for (size_t i = 0; i < ways; i++)
+    if (tag == (tags[idx*ways + i] & ~DIRTY))
+      return &tags[idx*ways + i];
+
+  return NULL;
+}
+
+uint64_t cache_sim_t::victimize(uint64_t addr)
+{
+  size_t idx = (addr >> idx_shift) & (sets-1);
+  size_t way = lfsr.next() % ways;
+  uint64_t victim = tags[idx*ways + way];
+  tags[idx*ways + way] = (addr >> idx_shift) | VALID;
+  return victim;
+}
+
 void cache_sim_t::access(uint64_t addr, size_t bytes, bool store)
 {
   store ? write_accesses++ : read_accesses++;
   (store ? bytes_written : bytes_read) += bytes;
 
-  size_t idx = (addr >> idx_shift) & (sets-1);
-  size_t tag = (addr >> idx_shift) | VALID;
-  size_t* set_tags = &tags[idx*ways];
-
-  for(size_t i = 0; i < ways; i++)
+  uint64_t* hit_way = check_tag(addr);
+  if (likely(hit_way != NULL))
   {
-    if(tag == (set_tags[i] & ~DIRTY)) // hit
-    {
-      if(store)
-        set_tags[i] |= DIRTY;
-      return;
-    }
+    if (store)
+      *hit_way |= DIRTY;
+    return;
   }
 
   store ? write_misses++ : read_misses++;
 
-  size_t way = lfsr.next() % ways;
-  if((set_tags[way] & (VALID | DIRTY)) == (VALID | DIRTY))
+  uint64_t victim = victimize(addr);
+
+  if ((victim & (VALID | DIRTY)) == (VALID | DIRTY))
   {
-    uint64_t dirty_addr = (set_tags[way] & ~(VALID | DIRTY)) << idx_shift;
-    if (miss_handler) miss_handler->access(dirty_addr, linesz, true);
+    uint64_t dirty_addr = (victim & ~(VALID | DIRTY)) << idx_shift;
+    if (miss_handler)
+      miss_handler->access(dirty_addr, linesz, true);
     writebacks++;
   }
-  if (miss_handler) miss_handler->access(addr & ~(linesz-1), linesz, false);
-  set_tags[way] = tag | (store ? DIRTY : 0);
+
+  if (miss_handler)
+    miss_handler->access(addr & ~(linesz-1), linesz, false);
+
+  if (store)
+    *check_tag(addr) |= DIRTY;
+}
+
+fa_cache_sim_t::fa_cache_sim_t(size_t ways, size_t linesz, const char* name)
+  : cache_sim_t(1, ways, linesz, name)
+{
+}
+
+uint64_t* fa_cache_sim_t::check_tag(uint64_t addr)
+{
+  auto it = tags.find(addr >> idx_shift);
+  return it == tags.end() ? NULL : &it->second;
+}
+
+uint64_t fa_cache_sim_t::victimize(uint64_t addr)
+{
+  uint64_t old_tag = 0;
+  if (tags.size() == ways)
+  {
+    auto it = tags.begin();
+    std::advance(it, lfsr.next() % ways);
+    old_tag = it->second;
+    tags.erase(it);
+  }
+  tags[addr >> idx_shift] = (addr >> idx_shift) | VALID;
+  return old_tag;
 }
diff --git a/riscv/cachesim.h b/riscv/cachesim.h
index d4f4fb4..d6f5946 100644
--- a/riscv/cachesim.h
+++ b/riscv/cachesim.h
@@ -4,6 +4,7 @@
 #include "memtracer.h"
 #include <cstring>
 #include <string>
+#include <map>
 #include <stdint.h>
 
 class lfsr_t
@@ -19,7 +20,6 @@ class lfsr_t
 class cache_sim_t
 {
  public:
-  cache_sim_t(const char* config, const char* name);
   cache_sim_t(size_t sets, size_t ways, size_t linesz, const char* name);
   cache_sim_t(const cache_sim_t& rhs);
   ~cache_sim_t();
@@ -28,7 +28,15 @@ class cache_sim_t
   void print_stats();
   void set_miss_handler(cache_sim_t* mh) { miss_handler = mh; }
 
- private:
+  static cache_sim_t* construct(const char* config, const char* name);
+
+ protected:
+  static const uint64_t VALID = 1ULL << 63;
+  static const uint64_t DIRTY = 1ULL << 62;
+
+  virtual uint64_t* check_tag(uint64_t addr);
+  virtual uint64_t victimize(uint64_t addr);
+
   lfsr_t lfsr;
   cache_sim_t* miss_handler;
 
@@ -49,53 +57,65 @@ class cache_sim_t
 
   std::string name;
 
-  static const uint64_t VALID = 1ULL << 63;
-  static const uint64_t DIRTY = 1ULL << 62;
-
   void init();
 };
 
-class unified_cache_sim_t : public memtracer_t
+class fa_cache_sim_t : public cache_sim_t
 {
  public:
-  unified_cache_sim_t(const char* config) : cache(config, "U$") {}
-  bool interested_in_range(size_t begin, size_t end, bool store, bool fetch)
+  fa_cache_sim_t(size_t ways, size_t linesz, const char* name);
+  uint64_t* check_tag(uint64_t addr);
+  uint64_t victimize(uint64_t addr);
+ private:
+  static bool cmp(uint64_t a, uint64_t b);
+  std::map<uint64_t, uint64_t> tags;
+};
+
+class cache_memtracer_t : public memtracer_t
+{
+ public:
+  cache_memtracer_t(const char* config, const char* name)
   {
-    return true;
+    cache = cache_sim_t::construct(config, name);
   }
-  void trace(uint64_t addr, size_t bytes, bool store, bool fetch)
+  ~cache_memtracer_t()
   {
-    cache.access(addr, bytes, store);
+    delete cache;
   }
- private:
-  cache_sim_t cache;
+  void set_miss_handler(cache_sim_t* mh)
+  {
+    cache->set_miss_handler(mh);
+  }
+
+ protected:
+  cache_sim_t* cache;
 };
 
-class icache_sim_t : public memtracer_t, public cache_sim_t
+class icache_sim_t : public cache_memtracer_t
 {
  public:
-  icache_sim_t(const char* config) : cache_sim_t(config, "I$") {}
-  bool interested_in_range(size_t begin, size_t end, bool store, bool fetch)
+  icache_sim_t(const char* config) : cache_memtracer_t(config, "I$") {}
+  bool interested_in_range(uint64_t begin, uint64_t end, bool store, bool fetch)
   {
     return fetch;
   }
   void trace(uint64_t addr, size_t bytes, bool store, bool fetch)
   {
-    if (fetch) access(addr, bytes, false);
+    if (fetch) cache->access(addr, bytes, false);
   }
 };
 
-class dcache_sim_t : public memtracer_t, public cache_sim_t
+class dcache_sim_t : public cache_memtracer_t
 {
  public:
-  dcache_sim_t(const char* config) : cache_sim_t(config, "D$") {}
-  bool interested_in_range(size_t begin, size_t end, bool store, bool fetch)
+  dcache_sim_t(const char* config) : cache_memtracer_t(config, "D$") {}
+  bool interested_in_range(uint64_t begin, uint64_t end, bool store, bool fetch)
   {
     return !fetch;
   }
   void trace(uint64_t addr, size_t bytes, bool store, bool fetch)
   {
-    if (!fetch) access(addr, bytes, store);
+    if (!fetch) cache->access(addr, bytes, false);
   }
 };
 
diff --git a/riscv/memtracer.h b/riscv/memtracer.h
index ed62be5..82c02b6 100644
--- a/riscv/memtracer.h
+++ b/riscv/memtracer.h
@@ -8,16 +8,11 @@
 class memtracer_t
 {
  public:
-  memtracer_t() : link(NULL) {}
+  memtracer_t() {}
   virtual ~memtracer_t() {}
 
   virtual bool interested_in_range(uint64_t begin, uint64_t end, bool store, bool fetch) = 0;
   virtual void trace(uint64_t addr, size_t bytes, bool store, bool fetch) = 0;
-
- protected:
-
- private:
-  memtracer_t* link;
 };
 
 class memtracer_list_t : public memtracer_t
diff --git a/riscv/riscv-isa-run.cc b/riscv/riscv-isa-run.cc
index 7b79945..852556c 100644
--- a/riscv/riscv-isa-run.cc
+++ b/riscv/riscv-isa-run.cc
@@ -40,7 +40,7 @@ int main(int argc, char** argv)
   parser.option('m', 0, 1, [&](const char* s){mem_mb = atoi(s);});
   parser.option(0, "ic", 1, [&](const char* s){ic.reset(new icache_sim_t(s));});
   parser.option(0, "dc", 1, [&](const char* s){dc.reset(new dcache_sim_t(s));});
-  parser.option(0, "l2", 1, [&](const char* s){l2.reset(new cache_sim_t(s, "L2$"));});
+  parser.option(0, "l2", 1, [&](const char* s){l2.reset(cache_sim_t::construct(s, "L2$"));});
 
   auto argv1 = parser.parse(argv);
   if (!*argv1)