ruby: Ruby support for sparse memory

The patch includes direct support for the MI example protocol.

9 files changed, 646 insertions, 46 deletions

diff --git a/src/mem/protocol/MI_example-dir.sm b/src/mem/protocol/MI_example-dir.sm
index 3fc814315..cab90b9a7 100644
--- a/src/mem/protocol/MI_example-dir.sm
+++ b/src/mem/protocol/MI_example-dir.sm
@@ -98,15 +98,18 @@ machine(Directory, "Directory protocol")
 
     if (directory.isPresent(addr)) {
 
-      if (state == State:I)  {
-        assert(getDirectoryEntry(addr).Owner.count() == 0);
-        assert(getDirectoryEntry(addr).Sharers.count() == 0);
-      } else if (state == State:M) {
+      if (state == State:M) {
         assert(getDirectoryEntry(addr).Owner.count() == 1);
         assert(getDirectoryEntry(addr).Sharers.count() == 0);
       }
 
       getDirectoryEntry(addr).DirectoryState := state;
+    
+      if (state == State:I)  {
+        assert(getDirectoryEntry(addr).Owner.count() == 0);
+        assert(getDirectoryEntry(addr).Sharers.count() == 0);
+        directory.invalidateBlock(addr);
+      }
     }
   }
 
@@ -264,10 +267,6 @@ machine(Directory, "Directory protocol")
       }
   }
 
-  action(d_deallocateDirectory, "\d", desc="Deallocate Directory Entry") {
-      directory.invalidateBlock(address);
-  }
-
   action(e_ownerIsRequestor, "e", desc="The owner is now the requestor") {
     peek(requestQueue_in, RequestMsg) {
       getDirectoryEntry(address).Owner.clear();
@@ -527,7 +526,6 @@ machine(Directory, "Directory protocol")
   transition(M_DRDI, Memory_Ack, I) {
     l_sendWriteBackAck;
     w_deallocateTBE;   
-    d_deallocateDirectory;
     l_popMemQueue;
   }
 
@@ -550,7 +548,6 @@ machine(Directory, "Directory protocol")
     l_sendWriteBackAck;
     da_sendDMAAck;
     w_deallocateTBE;
-    d_deallocateDirectory;
     l_popMemQueue;
   }
 
@@ -572,7 +569,6 @@ machine(Directory, "Directory protocol")
     w_writeDataToMemoryFromTBE;
     l_sendWriteBackAck;
     w_deallocateTBE;
-    d_deallocateDirectory;
     l_popMemQueue;
   }
 
diff --git a/src/mem/ruby/system/DirectoryMemory.cc b/src/mem/ruby/system/DirectoryMemory.cc
index adf63d06f..78ca1e9e4 100644
--- a/src/mem/ruby/system/DirectoryMemory.cc
+++ b/src/mem/ruby/system/DirectoryMemory.cc
@@ -51,14 +51,24 @@ DirectoryMemory::DirectoryMemory(const Params *p)
     m_version = p->version;
     m_size_bytes = p->size;
     m_size_bits = log_int(m_size_bytes);
+    m_num_entries = 0;
+    m_use_map = p->use_map;
+    m_map_levels = p->map_levels;
 }
 
 void DirectoryMemory::init()
 {
   m_num_entries = m_size_bytes / RubySystem::getBlockSizeBytes();
-  m_entries = new Directory_Entry*[m_num_entries];
-  for (int i=0; i < m_num_entries; i++)
-    m_entries[i] = NULL;
+
+  if (m_use_map) {
+      int entry_bits = log_int(m_num_entries);
+      assert(entry_bits >= m_map_levels);
+      m_sparseMemory = new SparseMemory(entry_bits, m_map_levels);
+  } else {
+      m_entries = new Directory_Entry*[m_num_entries];
+      for (int i=0; i < m_num_entries; i++)
+          m_entries[i] = NULL;
+  }
 
   m_ram = g_system_ptr->getMemoryVector();
 
@@ -70,13 +80,15 @@ void DirectoryMemory::init()
 DirectoryMemory::~DirectoryMemory()
 {
   // free up all the directory entries
-  for (uint64 i=0;i<m_num_entries;i++) {
-    if (m_entries[i] != NULL) {
-      delete m_entries[i];
-    }
-  }
   if (m_entries != NULL) {
-    delete [] m_entries;
+      for (uint64 i = 0; i < m_num_entries; i++) {
+          if (m_entries[i] != NULL) {
+              delete m_entries[i];
+          }
+      }
+      delete [] m_entries;
+  } else if (m_use_map) {
+      delete m_sparseMemory;
   }
 }
 
@@ -102,14 +114,14 @@ void DirectoryMemory::printGlobalConfig(ostream & out)
         << "-" << RubySystem::getBlockSizeBits() << endl;
   }
   out << "  total memory size bytes: " << m_total_size_bytes << endl;
-  out << "  total memory size bits: " << log_int(m_total_size_bytes) << endl;
+  out << "  total memory bits: " << log_int(m_total_size_bytes) << endl;
 
 }
 
-int DirectoryMemory::mapAddressToDirectoryVersion(PhysAddress address)
+uint64 DirectoryMemory::mapAddressToDirectoryVersion(PhysAddress address)
 {
   if (m_num_directories_bits == 0) return 0;
-  int ret = address.bitSelect(RubySystem::getBlockSizeBits(),
+  uint64 ret = address.bitSelect(RubySystem::getBlockSizeBits(),
                               RubySystem::getBlockSizeBits()+m_num_directories_bits-1);
   return ret;
 }
@@ -121,9 +133,10 @@ bool DirectoryMemory::isPresent(PhysAddress address)
   return ret;
 }
 
-int DirectoryMemory::mapAddressToLocalIdx(PhysAddress address)
+uint64 DirectoryMemory::mapAddressToLocalIdx(PhysAddress address)
 {
-  int ret = address.getAddress() >> (RubySystem::getBlockSizeBits() + m_num_directories_bits);
+  uint64 ret = address.getAddress()
+      >> (RubySystem::getBlockSizeBits() + m_num_directories_bits);
   return ret;
 }
 
@@ -131,13 +144,32 @@ Directory_Entry& DirectoryMemory::lookup(PhysAddress address)
 {
   assert(isPresent(address));
   Directory_Entry* entry;
-  int idx = mapAddressToLocalIdx(address);
-  entry = m_entries[idx];
-  if (entry == NULL) {
-    entry = new Directory_Entry;
-    entry->getDataBlk().assign(m_ram->getBlockPtr(address));
-    m_entries[idx] = entry;
+  uint64 idx;
+  DEBUG_EXPR(CACHE_COMP, HighPrio, address);
+
+  if (m_use_map) {
+    if (m_sparseMemory->exist(address)) {
+      entry = m_sparseMemory->lookup(address);
+      assert(entry != NULL);
+    } else {
+      //
+      // Note: SparseMemory internally creates a new Directory Entry
+      //
+      m_sparseMemory->add(address);
+      entry = m_sparseMemory->lookup(address);
+    }
+  } else {
+    idx = mapAddressToLocalIdx(address);
+    assert(idx < m_num_entries);
+    entry = m_entries[idx];
+
+    if (entry == NULL) {
+      entry = new Directory_Entry();
+      entry->getDataBlk().assign(m_ram->getBlockPtr(address));
+      m_entries[idx] = entry;
+    }
   }
+
   return (*entry);
 }
 /*
@@ -169,20 +201,29 @@ Directory_Entry& DirectoryMemory::lookup(PhysAddress address)
 
 void DirectoryMemory::invalidateBlock(PhysAddress address)
 {
-  /*
-  assert(isPresent(address));
-
-  Index index = address.memoryModuleIndex();
-
-  if (index < 0 || index > m_size) {
-    ERROR_MSG("Directory Memory Assertion: accessing memory out of range.");
+  
+  if (m_use_map) {
+    assert(m_sparseMemory->exist(address));
+    m_sparseMemory->remove(address);
   }
+  /*
+  else {
+    assert(isPresent(address));
+    
+    Index index = address.memoryModuleIndex();
+    
+    if (index < 0 || index > m_size) {
+      ERROR_MSG("Directory Memory Assertion: accessing memory out of range.");
+    }
 
-  if(m_entries[index] != NULL){
-    delete m_entries[index];
-    m_entries[index] = NULL;
+    if(m_entries[index] != NULL){
+      delete m_entries[index];
+      m_entries[index] = NULL;
+    }
   }
   */
+
+
 }
 
 void DirectoryMemory::print(ostream& out) const
@@ -190,6 +231,13 @@ void DirectoryMemory::print(ostream& out) const
 
 }
 
+void DirectoryMemory::printStats(ostream& out) const
+{
+    if (m_use_map) {
+        m_sparseMemory->printStats(out);
+    }
+}
+
 DirectoryMemory *
 RubyDirectoryMemoryParams::create()
 {
diff --git a/src/mem/ruby/system/DirectoryMemory.hh b/src/mem/ruby/system/DirectoryMemory.hh
index 0f4368b2c..455329cd0 100644
--- a/src/mem/ruby/system/DirectoryMemory.hh
+++ b/src/mem/ruby/system/DirectoryMemory.hh
@@ -45,6 +45,7 @@
 #include "mem/protocol/Directory_Entry.hh"
 #include "sim/sim_object.hh"
 #include "params/RubyDirectoryMemory.hh"
+#include "mem/ruby/system/SparseMemory.hh"
 
 class DirectoryMemory : public SimObject {
 public:
@@ -57,9 +58,10 @@ public:
   // Destructor
   ~DirectoryMemory();
 
-  int mapAddressToLocalIdx(PhysAddress address);
-  static int mapAddressToDirectoryVersion(PhysAddress address);
+  uint64 mapAddressToLocalIdx(PhysAddress address);
+  static uint64 mapAddressToDirectoryVersion(PhysAddress address);
 
+  bool isSparseImplementation() { return m_use_map; }
   uint64 getSize() { return m_size_bytes; }
 
   // Public Methods
@@ -71,6 +73,7 @@ public:
   void invalidateBlock(PhysAddress address);
 
   void print(ostream& out) const;
+  void printStats(ostream& out) const;
 
 private:
   // Private Methods
@@ -86,7 +89,7 @@ private:
   //  int m_size;  // # of memory module blocks this directory is responsible for
   uint64 m_size_bytes;
   uint64 m_size_bits;
-  int m_num_entries;
+  uint64 m_num_entries;
   int m_version;
 
   static int m_num_directories;
@@ -94,6 +97,9 @@ private:
   static uint64_t m_total_size_bytes;
 
   MemoryVector* m_ram;
+  SparseMemory* m_sparseMemory;
+  bool m_use_map;
+  int m_map_levels;
 };
 
 // Output operator declaration
diff --git a/src/mem/ruby/system/DirectoryMemory.py b/src/mem/ruby/system/DirectoryMemory.py
index 3744ce577..9892f3135 100644
--- a/src/mem/ruby/system/DirectoryMemory.py
+++ b/src/mem/ruby/system/DirectoryMemory.py
@@ -36,3 +36,5 @@ class RubyDirectoryMemory(SimObject):
     cxx_class = 'DirectoryMemory'
     version = Param.Int(0, "")
     size = Param.MemorySize("1GB", "capacity in bytes")
+    use_map = Param.Bool(False, "enable sparse memory")
+    map_levels = Param.Int(4, "sparse memory map levels")
diff --git a/src/mem/ruby/system/SConscript b/src/mem/ruby/system/SConscript
index 715c9fb86..2d14229d7 100644
--- a/src/mem/ruby/system/SConscript
+++ b/src/mem/ruby/system/SConscript
@@ -41,6 +41,7 @@ SimObject('RubySystem.py')
 
 Source('DMASequencer.cc')
 Source('DirectoryMemory.cc')
+Source('SparseMemory.cc')
 Source('CacheMemory.cc')
 Source('MemoryControl.cc')
 Source('MemoryNode.cc')
diff --git a/src/mem/ruby/system/SparseMemory.cc b/src/mem/ruby/system/SparseMemory.cc
new file mode 100644
index 000000000..c351f9e60
--- /dev/null
+++ b/src/mem/ruby/system/SparseMemory.cc
@@ -0,0 +1,425 @@
+
+/*
+ * Copyright (c) 2009 Advanced Micro Devices, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "mem/ruby/system/SparseMemory.hh"
+
+
+// ****************************************************************
+
+
+SparseMemory::SparseMemory(int number_of_bits, int number_of_levels)
+{
+    int even_level_bits;
+    int extra;
+    m_total_number_of_bits = number_of_bits;
+    m_number_of_levels = number_of_levels;
+    
+    //
+    // Create the array that describes the bits per level
+    //
+    m_number_of_bits_per_level = new int[m_number_of_levels];
+    even_level_bits = m_total_number_of_bits / m_number_of_levels;
+    extra = m_total_number_of_bits % m_number_of_levels;
+    for (int level = 0; level < m_number_of_levels; level++) {
+        if (level < extra)
+            m_number_of_bits_per_level[level] = even_level_bits + 1;
+        else
+            m_number_of_bits_per_level[level] = even_level_bits;
+    }
+    m_map_head = new SparseMapType;
+    
+    m_total_adds = 0;
+    m_total_removes = 0;
+    m_adds_per_level = new uint64_t[m_number_of_levels];
+    m_removes_per_level = new uint64_t[m_number_of_levels];
+    for (int level = 0; level < m_number_of_levels; level++) {
+        m_adds_per_level[level] = 0;
+        m_removes_per_level[level] = 0;
+    }
+}
+
+SparseMemory::~SparseMemory()
+{
+    recursivelyRemoveTables(m_map_head, 0);
+    delete m_map_head;
+    delete [] m_number_of_bits_per_level;
+    delete [] m_adds_per_level;
+    delete [] m_removes_per_level;
+}
+
+// Recursively search table hierarchy for the lowest level table.
+// Delete the lowest table first, the tables above
+void 
+SparseMemory::recursivelyRemoveTables(SparseMapType* curTable, int curLevel)
+{
+    SparseMapType::iterator iter;
+
+    for (iter = curTable->begin(); iter != curTable->end(); iter++) {
+        SparseMemEntry_t* entryStruct = &((*iter).second);
+        
+        if (curLevel != (m_number_of_levels - 1)) {
+            //
+            // If the not at the last level, analyze those lower level tables first,
+            // then delete those next tables
+            //
+            SparseMapType* nextTable;
+            nextTable = (SparseMapType*)(entryStruct->entry);
+            recursivelyRemoveTables(nextTable, (curLevel + 1));
+            delete nextTable;
+            
+        } else {
+            //
+            // If at the last level, delete the directory entry
+            //
+            Directory_Entry* dirEntry;
+            dirEntry = (Directory_Entry*)(entryStruct->entry);
+            delete dirEntry;
+        }
+        entryStruct->entry = NULL;
+    }  
+    
+    //
+    // Once all entries have been deleted, erase the entries
+    //
+    curTable->erase(curTable->begin(), curTable->end());
+}
+
+
+// PUBLIC METHODS
+
+// tests to see if an address is present in the memory
+bool 
+SparseMemory::exist(const Address& address) const
+{
+    SparseMapType* curTable = m_map_head;
+    Address curAddress;
+    
+    //
+    // Initiallize the high bit to be the total number of bits plus the block
+    // offset.  However the highest bit index is one less than this value.
+    //
+    int highBit = m_total_number_of_bits + RubySystem::getBlockSizeBits();
+    int lowBit;
+    assert(address == line_address(address));
+    DEBUG_EXPR(CACHE_COMP, HighPrio, address);
+    
+    for (int level = 0; level < m_number_of_levels; level++) {
+        //
+        // Create the appropriate sub address for this level
+        // Note: that set Address is inclusive of the specified range, thus the
+        // high bit is one less than the total number of bits used to create the
+        // address.
+        //
+        lowBit = highBit - m_number_of_bits_per_level[level];
+        curAddress.setAddress(address.bitSelect(lowBit, highBit - 1));
+        
+        DEBUG_EXPR(CACHE_COMP, HighPrio, level);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, lowBit);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, highBit - 1);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, curAddress);
+        
+        //
+        // Adjust the highBit value for the next level
+        //
+        highBit -= m_number_of_bits_per_level[level];
+        
+        //
+        // If the address is found, move on to the next level.  Otherwise,
+        // return not found
+        //
+        if (curTable->count(curAddress) != 0) {
+            curTable = (SparseMapType*)(((*curTable)[curAddress]).entry);
+        } else {
+            DEBUG_MSG(CACHE_COMP, HighPrio, "Not found");
+            return false;
+        }
+    }
+    
+    DEBUG_MSG(CACHE_COMP, HighPrio, "Entry found");
+    return true;
+}
+
+// add an address to memory
+void 
+SparseMemory::add(const Address& address)
+{
+    assert(address == line_address(address));
+    assert(!exist(address));
+    
+    m_total_adds++;
+    
+    Address curAddress;
+    SparseMapType* curTable = m_map_head;
+    SparseMemEntry_t* entryStruct = NULL;
+    
+    //
+    // Initiallize the high bit to be the total number of bits plus the block
+    // offset.  However the highest bit index is one less than this value.
+    //
+    int highBit = m_total_number_of_bits + RubySystem::getBlockSizeBits();
+    int lowBit;
+    void* newEntry = NULL;
+    
+    for (int level = 0; level < m_number_of_levels; level++) {
+        //
+        // create the appropriate address for this level
+        // Note: that set Address is inclusive of the specified range, thus the 
+        // high bit is one less than the total number of bits used to create the
+        // address.
+        //
+        lowBit = highBit - m_number_of_bits_per_level[level];
+        curAddress.setAddress(address.bitSelect(lowBit, highBit - 1));
+        
+        //
+        // Adjust the highBit value for the next level
+        //
+        highBit -= m_number_of_bits_per_level[level];
+        
+        //
+        // if the address exists in the cur table, move on.  Otherwise
+        // create a new table.
+        //
+        if (curTable->count(curAddress) != 0) {
+            curTable = (SparseMapType*)(((*curTable)[curAddress]).entry);
+        } else {
+            
+            m_adds_per_level[level]++;
+            //
+            // if the last level, add a directory entry.  Otherwise add a map.
+            //
+            if (level == (m_number_of_levels - 1)) {
+                Directory_Entry* tempDirEntry = new Directory_Entry();
+                tempDirEntry->getDataBlk().clear();
+                newEntry = (void*)tempDirEntry;
+            } else {
+                SparseMapType* tempMap = new SparseMapType;
+                newEntry = (void*)(tempMap);
+            }
+
+            //
+            // Create the pointer container SparseMemEntry_t and add it to the 
+            // table.
+            //
+            entryStruct = new SparseMemEntry_t;
+            entryStruct->entry = newEntry;
+            (*curTable)[curAddress] = *entryStruct;
+            
+            //
+            // Move to the next level of the heirarchy
+            //
+            curTable = (SparseMapType*)newEntry;
+        }
+    }
+    
+    assert(exist(address));
+    return;
+}
+
+// recursively search table hierarchy for the lowest level table.
+// remove the lowest entry and any empty tables above it.
+int 
+SparseMemory::recursivelyRemoveLevels(
+    const Address& address,
+    curNextInfo& curInfo)
+{
+    Address curAddress;
+    curNextInfo nextInfo;
+    SparseMemEntry_t* entryStruct;
+    
+    //
+    // create the appropriate address for this level
+    // Note: that set Address is inclusive of the specified range, thus the 
+    // high bit is one less than the total number of bits used to create the
+    // address.
+    //
+    curAddress.setAddress(address.bitSelect(curInfo.lowBit, 
+                                            curInfo.highBit - 1));
+    
+    DEBUG_EXPR(CACHE_COMP, HighPrio, address);
+    DEBUG_EXPR(CACHE_COMP, HighPrio, curInfo.level);
+    DEBUG_EXPR(CACHE_COMP, HighPrio, curInfo.lowBit);
+    DEBUG_EXPR(CACHE_COMP, HighPrio, curInfo.highBit - 1);
+    DEBUG_EXPR(CACHE_COMP, HighPrio, curAddress);
+    
+    assert(curInfo.curTable->count(curAddress) != 0);
+    
+    entryStruct = &((*(curInfo.curTable))[curAddress]);
+    
+    if (curInfo.level < (m_number_of_levels - 1)) {
+        //
+        // set up next level's info
+        //
+        nextInfo.curTable = (SparseMapType*)(entryStruct->entry);
+        nextInfo.level = curInfo.level + 1;
+
+        nextInfo.highBit = curInfo.highBit - 
+            m_number_of_bits_per_level[curInfo.level];
+
+        nextInfo.lowBit = curInfo.lowBit - 
+            m_number_of_bits_per_level[curInfo.level + 1];
+        
+        //
+        // recursively search the table hierarchy
+        //
+        int tableSize = recursivelyRemoveLevels(address, nextInfo);
+        
+        //
+        // If this table below is now empty, we must delete it and erase it from 
+        // our table.
+        //
+        if (tableSize == 0) {
+            m_removes_per_level[curInfo.level]++;
+            delete nextInfo.curTable;
+            entryStruct->entry = NULL;
+            curInfo.curTable->erase(curAddress);
+        }
+    } else {
+        //
+        // if this is the last level, we have reached the Directory Entry and thus
+        // we should delete it including the SparseMemEntry container struct.
+        //
+        Directory_Entry* dirEntry;
+        dirEntry = (Directory_Entry*)(entryStruct->entry);
+        entryStruct->entry = NULL;
+        delete dirEntry;
+        curInfo.curTable->erase(curAddress);
+        m_removes_per_level[curInfo.level]++;
+    }
+    return curInfo.curTable->size();
+}
+
+// remove an entry from the table
+void 
+SparseMemory::remove(const Address& address)
+{
+    assert(address == line_address(address));
+    assert(exist(address));
+    
+    m_total_removes++;
+    
+    curNextInfo nextInfo;
+    
+    //
+    // Initialize table pointer and level value
+    //
+    nextInfo.curTable = m_map_head;
+    nextInfo.level = 0;
+    
+    //
+    // Initiallize the high bit to be the total number of bits plus the block
+    // offset.  However the highest bit index is one less than this value.
+    //
+    nextInfo.highBit = m_total_number_of_bits + RubySystem::getBlockSizeBits();
+    nextInfo.lowBit = nextInfo.highBit - m_number_of_bits_per_level[0];;
+    
+    // 
+    // recursively search the table hierarchy for empty tables starting from the
+    // level 0.  Note we do not check the return value because the head table is
+    // never deleted;
+    //
+    recursivelyRemoveLevels(address, nextInfo);
+    
+    assert(!exist(address));
+    return;
+}
+
+// looks an address up in memory
+Directory_Entry* 
+SparseMemory::lookup(const Address& address)
+{
+    assert(exist(address));
+    assert(address == line_address(address));
+
+    DEBUG_EXPR(CACHE_COMP, HighPrio, address);
+    
+    Address curAddress;
+    SparseMapType* curTable = m_map_head;
+    Directory_Entry* entry = NULL;
+    
+    //
+    // Initiallize the high bit to be the total number of bits plus the block
+    // offset.  However the highest bit index is one less than this value.
+    //
+    int highBit = m_total_number_of_bits + RubySystem::getBlockSizeBits();
+    int lowBit;
+    
+    for (int level = 0; level < m_number_of_levels; level++) {
+        //
+        // create the appropriate address for this level
+        // Note: that set Address is inclusive of the specified range, thus the 
+        // high bit is one less than the total number of bits used to create the 
+        // address.
+        //
+        lowBit = highBit - m_number_of_bits_per_level[level];
+        curAddress.setAddress(address.bitSelect(lowBit, highBit - 1));
+        
+        DEBUG_EXPR(CACHE_COMP, HighPrio, level);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, lowBit);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, highBit - 1);
+        DEBUG_EXPR(CACHE_COMP, HighPrio, curAddress);
+        
+        //
+        // Adjust the highBit value for the next level
+        //
+        highBit -= m_number_of_bits_per_level[level];
+        
+        //
+        // The entry should be in the table and valid
+        //
+        curTable = (SparseMapType*)(((*curTable)[curAddress]).entry);
+        assert(curTable != NULL);
+    }
+    
+    //
+    // The last entry actually points to the Directory entry not a table
+    //
+    entry = (Directory_Entry*)curTable;
+
+    return entry;
+}
+
+void 
+SparseMemory::print(ostream& out) const
+{
+}
+
+void 
+SparseMemory::printStats(ostream& out) const
+{
+    out << "total_adds: " << m_total_adds << " [";
+    for (int level = 0; level < m_number_of_levels; level++) {
+        out << m_adds_per_level[level] << " ";
+    }
+    out << "]" << endl;
+    out << "total_removes: " << m_total_removes << " [";
+    for (int level = 0; level < m_number_of_levels; level++) {
+        out << m_removes_per_level[level] << " ";
+    }
+    out << "]" << endl;
+}
diff --git a/src/mem/ruby/system/SparseMemory.hh b/src/mem/ruby/system/SparseMemory.hh
new file mode 100644
index 000000000..4a7ac98c2
--- /dev/null
+++ b/src/mem/ruby/system/SparseMemory.hh
@@ -0,0 +1,114 @@
+
+/*
+ * Copyright (c) 2009 Advanced Micro Devices, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+
+#ifndef SPARSEMEMORY_H
+#define SPARSEMEMORY_H
+
+#include "mem/ruby/common/Global.hh"
+#include "base/hashmap.hh"
+#include "mem/ruby/common/Address.hh"
+#include "mem/protocol/Directory_Entry.hh"
+
+typedef struct SparseMemEntry {
+    void* entry;
+} SparseMemEntry_t;
+
+typedef m5::hash_map<Address, SparseMemEntry_t> SparseMapType;
+
+typedef struct curNextInfo {
+    SparseMapType* curTable;
+    int level;
+    int highBit;
+    int lowBit;
+};
+
+class SparseMemory {
+  public:
+
+    // Constructors
+    SparseMemory(int number_of_bits, int number_of_levels);
+    
+    // Destructor
+    ~SparseMemory();
+    
+    // Public Methods
+    
+    void printConfig(ostream& out) { }
+    
+    bool exist(const Address& address) const;
+    void add(const Address& address);
+    void remove(const Address& address);
+    
+    Directory_Entry* lookup(const Address& address);
+    
+    // Print cache contents
+    void print(ostream& out) const;
+    void printStats(ostream& out) const;
+
+  private:
+    // Private Methods
+    
+    // Private copy constructor and assignment operator
+    SparseMemory(const SparseMemory& obj);
+    SparseMemory& operator=(const SparseMemory& obj);
+    
+    // Used by destructor to recursively remove all tables
+    void recursivelyRemoveTables(SparseMapType* currentTable, int level);
+    
+    // recursive search for address and remove associated entries
+    int recursivelyRemoveLevels(const Address& address, curNextInfo& curInfo);
+    
+    // Data Members (m_prefix)
+    SparseMapType* m_map_head;
+    
+    int m_total_number_of_bits;
+    int m_number_of_levels;
+    int* m_number_of_bits_per_level;
+    
+    uint64_t m_total_adds;
+    uint64_t m_total_removes;
+    uint64_t* m_adds_per_level;
+    uint64_t* m_removes_per_level;
+};
+
+// Output operator declaration
+ostream& operator<<(ostream& out, const SparseMemEntry& obj);
+
+// Output operator definition
+extern inline
+ostream& operator<<(ostream& out, const SparseMemEntry& obj)
+{
+    out << "SparseMemEntry";
+    out << flush;
+    return out;
+}
+
+
+#endif //SPARSEMEMORY_H
diff --git a/src/mem/ruby/system/System.cc b/src/mem/ruby/system/System.cc
index 9f5ec9f09..105f6fb36 100644
--- a/src/mem/ruby/system/System.cc
+++ b/src/mem/ruby/system/System.cc
@@ -76,7 +76,11 @@ RubySystem::RubySystem(const Params *p)
     m_block_size_bits = log_int(m_block_size_bytes);
 
     m_memory_size_bytes = p->mem_size;
-    m_memory_size_bits = log_int(m_memory_size_bytes);
+    if (m_memory_size_bytes == 0) {
+        m_memory_size_bits = 0;
+    } else {
+        m_memory_size_bits = log_int(m_memory_size_bytes);
+    }
 
     m_network_ptr = p->network;
     g_debug_ptr = p->debug;
@@ -104,7 +108,10 @@ void RubySystem::init()
 
 RubySystem::~RubySystem()
 {
-
+  delete m_network_ptr;
+  delete m_profiler_ptr;
+  delete m_tracer_ptr;
+  delete m_mem_vec_ptr;
 }
 
 void RubySystem::printSystemConfig(ostream & out)
diff --git a/src/mem/slicc/symbols/StateMachine.py b/src/mem/slicc/symbols/StateMachine.py
index 6614c7bd0..0c66ddab4 100644
--- a/src/mem/slicc/symbols/StateMachine.py
+++ b/src/mem/slicc/symbols/StateMachine.py
@@ -651,6 +651,7 @@ $c_ident::printStats(ostream& out) const
         #
         for param in self.config_parameters:
             if param.type_ast.type.ident == "CacheMemory" or \
+               param.type_ast.type.ident == "DirectoryMemory" or \
                    param.type_ast.type.ident == "MemoryControl":
                 assert(param.pointer)
                 code('    m_${{param.ident}}_ptr->printStats(out);')