Ruby support for sparse memory.  Includes many 64-bit fixes.

diff -r 737662612eb7 src/mem/gems_common/util.cc
--- a/src/mem/gems_common/util.cc	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/gems_common/util.cc	Fri Sep 11 16:01:22 2009 -0700
@@ -96,9 +96,9 @@
   string lower(str);
   for (size_t i=0;i<str.length();i++)
     lower[i] = tolower(str[i]);
-  if (lower == "true")
+  if (lower == "true" || lower == "True")
     return true;
-  else if (lower == "false")
+  else if (lower == "false" || lower == "False")
     return false;
   else
     assert(0);
diff -r 737662612eb7 src/mem/protocol/MI_example-dir.sm
--- a/src/mem/protocol/MI_example-dir.sm	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/protocol/MI_example-dir.sm	Fri Sep 11 16:01:22 2009 -0700
@@ -108,15 +108,18 @@
 
     if (directory.isPresent(addr)) {
 
-      if (state == State:I)  {
-        assert(directory[addr].Owner.count() == 0);
-        assert(directory[addr].Sharers.count() == 0);
-      } else if (state == State:M) {
+      if (state == State:M) {
         assert(directory[addr].Owner.count() == 1);
         assert(directory[addr].Sharers.count() == 0);
       }
 
       directory[addr].DirectoryState := state;
+    
+      if (state == State:I)  {
+        assert(directory[addr].Owner.count() == 0);
+        assert(directory[addr].Sharers.count() == 0);
+        directory.invalidateBlock(addr);
+      }
     }
   }
 
@@ -277,10 +280,6 @@
       }
   }
 
-  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) {
       directory[address].Owner.clear();
@@ -527,7 +526,6 @@
   transition(M_DRDI, Memory_Ack, I) {
     l_sendWriteBackAck;
     w_deallocateTBE;   
-    d_deallocateDirectory;
     l_popMemQueue;
   }
 
@@ -550,7 +548,6 @@
     l_sendWriteBackAck;
     da_sendDMAAck;
     w_deallocateTBE;
-    d_deallocateDirectory;
     l_popMemQueue;
   }
 
@@ -572,7 +569,6 @@
     w_writeDataToMemoryFromTBE;
     l_sendWriteBackAck;
     w_deallocateTBE;
-    d_deallocateDirectory;
     l_popMemQueue;
   }
 
diff -r 737662612eb7 src/mem/ruby/common/Debug.cc
--- a/src/mem/ruby/common/Debug.cc	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/common/Debug.cc	Fri Sep 11 16:01:22 2009 -0700
@@ -95,19 +95,35 @@
 
 Debug::Debug( const string & name, const vector<string> & argv )
 {
+  // 
+  // must clear the filter before adding filter strings
+  //
+  clearFilter();
+
   for (size_t i=0;i<argv.size();i+=2){
-    if (argv[i] == "filter_string")
-      setFilterString( argv[i+1].c_str() );
-    else if (argv[i] == "verbosity_string")
+    if (argv[i] == "filter_string") {
+      if (setFilterString(argv[i+1].c_str()) != false) {
+        cerr << "Error: could not set filter string to %s " 
+             << argv[i+1].c_str() << endl;;
+        assert(0);
+      }
+    } 
+    else if (argv[i] == "verbosity_string") {
       setVerbosityString( argv[i+1].c_str() );
-    else if (argv[i] == "start_time")
+    } 
+    else if (argv[i] == "start_time") {
       m_starting_cycle = atoi( argv[i+1].c_str() );
-    else if (argv[i] == "output_filename")
+    } 
+    else if (argv[i] == "output_filename") {
       setDebugOutputFile( argv[i+1].c_str() );
-    else if (argv[i] == "protocol_trace")
+    } 
+    else if (argv[i] == "protocol_trace") {
       m_protocol_trace = string_to_bool(argv[i+1]);
-    else
+    } 
+    else {
+      cerr << "Error: invalid argument " << argv[i] << endl;
       assert(0);
+    }
   }
 }
 
@@ -119,7 +135,11 @@
   debug_cout_ptr = &cout;
 
   m_starting_cycle = filterStartTime;
-  setFilterString( filterString );
+  if (setFilterString(filterString) != false) {
+    cerr << "Error: could not set filter string to %s " 
+         << filterString << endl;;
+    assert(0);
+  }
   setVerbosityString( verboseString );
   setDebugOutputFile( filename );
 }
diff -r 737662612eb7 src/mem/ruby/config/MI_example-homogeneous.rb
--- a/src/mem/ruby/config/MI_example-homogeneous.rb	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/config/MI_example-homogeneous.rb	Fri Sep 11 16:01:22 2009 -0700
@@ -19,6 +19,7 @@
 num_memories = 2
 memory_size_mb = 1024
 num_dma = 1
+use_map = false
 protocol = "MI_example"
 
 # check for overrides
@@ -37,6 +38,9 @@
   elsif $*[i] == "-s"
     memory_size_mb = $*[i+1].to_i
     i = i + 1
+  elsif $*[i] == "-u"
+    use_map = $*[i+1]
+    i = i + 1
   end
 end
 
@@ -57,7 +61,7 @@
                                    sequencer)
 }
 num_memories.times { |n|
-  directory = DirectoryMemory.new("DirectoryMemory_"+n.to_s, memory_size_mb/num_memories)
+  directory = DirectoryMemory.new("DirectoryMemory_"+n.to_s, memory_size_mb/num_memories, use_map)
   memory_control = MemoryControl.new("MemoryControl_"+n.to_s)
   net_ports << MI_example_DirectoryController.new("DirectoryController_"+n.to_s,
                                        "Directory",
diff -r 737662612eb7 src/mem/ruby/config/cfg.rb
--- a/src/mem/ruby/config/cfg.rb	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/config/cfg.rb	Fri Sep 11 16:01:22 2009 -0700
@@ -275,7 +275,7 @@
 
   # override the default accessors (generated by default_param) for random_seed
   def self.random_seed=(seed)
-    assert (val.is_a?(Integer) or val == "rand"), "RubySystem.random_seed takes either an integer value or the string \"rand\""
+    #assert (val.is_a?(Integer) or val == "rand"), "RubySystem.random_seed takes either an integer value or the string \"rand\""
     @@params[:random_seed] = seed
   end
 
@@ -479,17 +479,20 @@
 
 class DirectoryMemory < LibRubyObject
   attr :size_mb
+  attr :map_levels
   attr_writer :controller
   @@total_size_mb = 0
 
-  def initialize(obj_name, size_mb)
+  def initialize(obj_name, size_mb, use_map)
     super(obj_name)
     @size_mb = size_mb
+    @map_levels = map_levels
     @@total_size_mb += size_mb
+    @use_map = use_map
   end
 
   def argv()
-    "version "+@controller.version.to_s+" size_mb "+@size_mb.to_s+" controller "+@controller.obj_name
+    "version "+@controller.version.to_s+" use_map "+@use_map.to_s+" map_levels "+@map_levels.to_s+" size_mb "+@size_mb.to_s+" controller "+@controller.obj_name
   end
 
   def cppClassName()
diff -r 737662612eb7 src/mem/ruby/config/defaults.rb
--- a/src/mem/ruby/config/defaults.rb	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/config/defaults.rb	Fri Sep 11 16:01:22 2009 -0700
@@ -94,7 +94,10 @@
   default_param :using_network_testing, Boolean, false
 end
 
-
+class DirectoryMemory < LibRubyObject
+  default_param :use_map, Boolean, false
+  default_param :map_levels, Integer, 4
+end
 
 #added by SS
 class Tracer < LibRubyObject
diff -r 737662612eb7 src/mem/ruby/libruby.cc
--- a/src/mem/ruby/libruby.cc	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/libruby.cc	Fri Sep 11 16:01:22 2009 -0700
@@ -66,6 +66,12 @@
   return out;
 }
 
+ostream& operator<<(std::ostream& out, const RubyRequest& obj)
+{
+  out << hex << "0x" << obj.paddr << flush;
+  return out;
+}
+
 vector<string> tokenizeString(string str, string delims)
 {
   vector<string> tokens;
diff -r 737662612eb7 src/mem/ruby/libruby.hh
--- a/src/mem/ruby/libruby.hh	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/libruby.hh	Fri Sep 11 16:01:22 2009 -0700
@@ -39,6 +39,8 @@
   {}
 };
 
+std::ostream& operator<<(std::ostream& out, const RubyRequest& obj);
+
 /**
  * Initialize the system.  cfg_file is a Ruby-lang configuration script
  */
diff -r 737662612eb7 src/mem/ruby/system/CacheMemory.hh
--- a/src/mem/ruby/system/CacheMemory.hh	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/system/CacheMemory.hh	Fri Sep 11 16:01:22 2009 -0700
@@ -197,7 +197,7 @@
 inline
 void CacheMemory::init(const vector<string> & argv)
 {
-  int cache_size = 0;
+  int cache_size = -1;
   string policy;
 
   m_controller = NULL;
@@ -217,7 +217,13 @@
     }
   }
 
-  m_cache_num_sets = cache_size / m_cache_assoc;
+  assert(cache_size != -1);
+
+  if (cache_size == 0) {
+    m_cache_num_sets = 2;
+  } else {
+    m_cache_num_sets = cache_size / m_cache_assoc;
+  }
   m_cache_num_set_bits = log_int(m_cache_num_sets);
 
   if(policy == "PSEUDO_LRU")
diff -r 737662612eb7 src/mem/ruby/system/DirectoryMemory.cc
--- a/src/mem/ruby/system/DirectoryMemory.cc	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/system/DirectoryMemory.cc	Fri Sep 11 16:01:22 2009 -0700
@@ -44,24 +44,34 @@
 
 int DirectoryMemory::m_num_directories = 0;
 int DirectoryMemory::m_num_directories_bits = 0;
-int DirectoryMemory::m_total_size_bytes = 0;
+uint64 DirectoryMemory::m_total_size_bytes = 0;
 
 DirectoryMemory::DirectoryMemory(const string & name)
- : m_name(name)
+  : m_name(name), m_controller(NULL), m_entries(NULL), m_use_sparse_data_structure(false)
 {
 }
 
 void DirectoryMemory::init(const vector<string> & argv)
 {
+  int entry_bits = 0;
+  int map_levels = 0;
+
   m_controller = NULL;
-  for (vector<string>::const_iterator it = argv.begin(); it != argv.end(); it++) {
-    if ( (*it) == "version" )
+  for (vector<string>::const_iterator it = argv.begin(); 
+       it != argv.end(); 
+       it++) {
+    if ( (*it) == "version" ) {
       m_version = atoi( (*(++it)).c_str() );
-    else if ( (*it) == "size_mb" ) {
-      m_size_bytes = atoi((*(++it)).c_str()) * static_cast<uint64>(1<<20);
-      m_size_bits = log_int(m_size_bytes);
+    } else if ( (*it) == "size_mb" ) {
+      m_size_bytes = static_cast<uint64>(atoi((*(++it)).c_str()))
+        * static_cast<uint64>(1<<20);
+      m_bits = log_int(m_size_bytes);
+    } else if ( (*it) == "map_levels" ) {
+      map_levels = static_cast<uint64>(atoi((*(++it)).c_str()));
     } else if ( (*it) == "controller" ) {
       m_controller = RubySystem::getController((*(++it)));
+    } else if ( (*it) == "use_map" ) {
+      m_use_sparse_data_structure = string_to_bool(*(++it));
     } else {
       cerr << "DirectoryMemory: Unkown config parameter: " << (*it) << endl;
       assert(0);
@@ -69,26 +79,39 @@
   }
   assert(m_controller != NULL);
 
-  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;
-
-  m_ram = g_system_ptr->getMemoryVector();
+  m_num_entries = m_size_bytes / 
+    static_cast<uint64>(RubySystem::getBlockSizeBytes());
+  entry_bits = log_int(m_num_entries);
 
   m_num_directories++;
   m_num_directories_bits = log_int(m_num_directories);
   m_total_size_bytes += m_size_bytes;
+
+  if (m_use_sparse_data_structure == false) {
+    m_entries = new Directory_Entry*[m_num_entries];
+
+    for (uint64 i=0; i < m_num_entries; i++)
+      m_entries[i] = NULL;
+  } else {
+    assert(entry_bits >= map_levels);
+
+    m_sparseMemory = new SparseMemory(entry_bits, map_levels);
+  }
+
+  m_ram = g_system_ptr->getMemoryVector();
+
 }
 
 DirectoryMemory::~DirectoryMemory()
 {
-  // free up all the directory entries
-  for (int i=0;i<m_num_entries;i++)
-    if (m_entries[i] != NULL)
-      delete m_entries;
-  if (m_entries != NULL)
-    delete [] m_entries;
+  // if allocated, free up all the directory entries
+  if (m_entries != NULL) {
+    for (uint64 i=0;i<m_num_entries;i++)
+      if (m_entries[i] != NULL)
+        delete m_entries;
+    if (m_entries != NULL)
+      delete [] m_entries;
+  }
 }
 
 void DirectoryMemory::printConfig(ostream& out) const
@@ -96,7 +119,7 @@
   out << "DirectoryMemory module config: " << m_name << endl;
   out << "  controller: " << m_controller->getName() << endl;
   out << "  version: " << m_version << endl;
-  out << "  memory_bits: " << m_size_bits << endl;
+  out << "  memory_bits: " << m_bits << endl;
   out << "  memory_size_bytes: " << m_size_bytes << endl;
   out << "  memory_size_Kbytes: " << double(m_size_bytes) / (1<<10) << endl;
   out << "  memory_size_Mbytes: " << double(m_size_bytes) / (1<<20) << endl;
@@ -114,14 +137,14 @@
         << "-" << 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;
 }
@@ -133,9 +156,11 @@
   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()                         \
+               >> static_cast<uint64>(RubySystem::getBlockSizeBits()
+                                      + m_num_directories_bits);
   return ret;
 }
 
@@ -143,13 +168,35 @@
 {
   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_sparse_data_structure == false) {
+    idx = mapAddressToLocalIdx(address);
+    assert(idx < m_num_entries);
+    entry = m_entries[idx];
+
+    if (entry == NULL) {
+      DEBUG_MSG(CACHE_COMP, LowPrio, "Conventional Directory Entry Allocated");
+      entry = new Directory_Entry();
+      entry->getDataBlk().assign(m_ram->getBlockPtr(address));
+      m_entries[idx] = entry;
+    }
+
+  } else {
+    if (m_sparseMemory->exist(address)) {
+      entry = m_sparseMemory->lookup(address);
+      assert(entry != NULL);
+    } else {
+      DEBUG_MSG(CACHE_COMP, LowPrio, "Sparse Directory Entry Allocated");
+      //
+      // Note: SparseMemory internally creates a new Directory Entry
+      //
+      m_sparseMemory->add(address);
+      entry = m_sparseMemory->lookup(address);
+    }
   }
+
   return (*entry);
 }
 /*
@@ -181,20 +228,30 @@
 
 void DirectoryMemory::invalidateBlock(PhysAddress address)
 {
+  
+  if (m_use_sparse_data_structure != false) {
+    assert(m_sparseMemory->exist(address));
+    m_sparseMemory->remove(address);
+    DEBUG_MSG(CACHE_COMP, LowPrio, "Sparse Directory Entry Deleted");
+  }
   /*
-  assert(isPresent(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.");
+    }
 
-  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
diff -r 737662612eb7 src/mem/ruby/system/DirectoryMemory.hh
--- a/src/mem/ruby/system/DirectoryMemory.hh	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/system/DirectoryMemory.hh	Fri Sep 11 16:01:22 2009 -0700
@@ -42,10 +42,15 @@
 #include "mem/ruby/common/Global.hh"
 #include "mem/ruby/common/Address.hh"
 #include "mem/ruby/system/MemoryVector.hh"
+#include "mem/ruby/system/SparseMemory.hh"
 #include "mem/protocol/Directory_Entry.hh"
 
 class AbstractController;
 
+typedef struct DirectoryEntryStruct {
+  Directory_Entry* entry;
+} DirectoryEntryStruct_t;
+
 class DirectoryMemory {
 public:
   // Constructors
@@ -56,9 +61,10 @@
   // 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_sparse_data_structure; }
   uint64 getSize() { return m_size_bytes; }
 
   // Public Methods
@@ -83,15 +89,18 @@
   AbstractController* m_controller;
   // Data Members (m_ prefix)
   Directory_Entry **m_entries;
+  SparseMemory* m_sparseMemory;
+
   //  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_bits;
+  uint64 m_num_entries;
   int m_version;
+  bool m_use_sparse_data_structure;
 
   static int m_num_directories;
   static int m_num_directories_bits;
-  static int m_total_size_bytes;
+  static uint64 m_total_size_bytes;
 
   MemoryVector* m_ram;
 };
diff -r 737662612eb7 src/mem/ruby/system/SConscript
--- a/src/mem/ruby/system/SConscript	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/system/SConscript	Fri Sep 11 16:01:22 2009 -0700
@@ -35,6 +35,7 @@
 
 Source('DMASequencer.cc')
 Source('DirectoryMemory.cc')
+Source('SparseMemory.cc')
 Source('MemoryControl.cc')
 Source('MemoryNode.cc')
 Source('RubyPort.cc')
diff -r 737662612eb7 src/mem/ruby/system/Sequencer.cc
--- a/src/mem/ruby/system/Sequencer.cc	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/system/Sequencer.cc	Fri Sep 11 16:01:22 2009 -0700
@@ -44,6 +44,10 @@
 //Sequencer::Sequencer(int core_id, MessageBuffer* mandatory_q)
 
 #define LLSC_FAIL -2
+ostream& operator<<(std::ostream& out, const SequencerRequest& obj) {
+  out << obj.ruby_request << flush;
+  return out;
+}
 
 Sequencer::Sequencer(const string & name)
   :RubyPort(name)
@@ -106,7 +110,7 @@
     SequencerRequest* request = m_readRequestTable.lookup(keys[i]);
     if (current_time - request->issue_time >= m_deadlock_threshold) {
       WARN_MSG("Possible Deadlock detected");
-      WARN_EXPR(request);
+      WARN_EXPR(request->ruby_request);
       WARN_EXPR(m_version);
       WARN_EXPR(keys.size());
       WARN_EXPR(current_time);
@@ -121,7 +125,7 @@
     SequencerRequest* request = m_writeRequestTable.lookup(keys[i]);
     if (current_time - request->issue_time >= m_deadlock_threshold) {
       WARN_MSG("Possible Deadlock detected");
-      WARN_EXPR(request);
+      WARN_EXPR(request->ruby_request);
       WARN_EXPR(m_version);
       WARN_EXPR(current_time);
       WARN_EXPR(request->issue_time);
diff -r 737662612eb7 src/mem/ruby/system/Sequencer.hh
--- a/src/mem/ruby/system/Sequencer.hh	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/system/Sequencer.hh	Fri Sep 11 16:01:22 2009 -0700
@@ -63,6 +63,8 @@
   {}
 };
 
+std::ostream& operator<<(std::ostream& out, const SequencerRequest& obj);
+
 class Sequencer : public Consumer, public RubyPort {
 public:
   // Constructors
diff -r 737662612eb7 src/mem/ruby/system/SparseMemory.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/mem/ruby/system/SparseMemory.cc	Fri Sep 11 16:01:22 2009 -0700
@@ -0,0 +1,290 @@
+
+
+#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 Map<Address, SparseMemEntry_t>;
+
+}
+
+// PUBLIC METHODS
+
+// tests to see if an address is present in the memory
+bool SparseMemory::exist(const Address& address) const
+{
+  Map<Address, SparseMemEntry_t>* 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->exist(curAddress) != false) {
+      curTable = (Map<Address, SparseMemEntry_t>*)((curTable->lookup(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) == false);
+
+  Address curAddress;
+  Map<Address, SparseMemEntry_t>* 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->exist(curAddress) != false) {
+      curTable = (Map<Address, SparseMemEntry_t>*)((curTable->lookup(curAddress)).entry);
+    } else {
+
+      //
+      // 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 {
+        Map<Address, SparseMemEntry_t>* tempMap = new Map<Address, SparseMemEntry_t>;
+        newEntry = (void*)(tempMap);
+      }
+
+      //
+      // Create the pointer container SparseMemEntry_t and add it to the table.
+      //
+      entryStruct = new SparseMemEntry_t;
+      entryStruct->entry = newEntry;
+      curTable->add(curAddress, *entryStruct);
+
+      //
+      // Move to the next level of the heirarchy
+      //
+      curTable = (Map<Address, SparseMemEntry_t>*)newEntry;
+    }
+  }
+
+  assert(exist(address) != false);
+  return;
+}
+
+// recursively search table hierarchy for the lowest level table.
+// remove the lowest entry and any empty tables above it.
+void SparseMemory::recursivelyRemoveLevels(
+    const Address& address,
+    int level,
+    int highBit,
+    int lowBit,
+    Map<Address, SparseMemEntry_t>* curTable
+    )
+{
+  Address curAddress;
+
+  //
+  // 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(lowBit, highBit - 1));
+
+  DEBUG_EXPR(CACHE_COMP, HighPrio, address);
+  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);
+
+  assert(curTable->exist(curAddress) != false);
+
+  if (level < (m_number_of_levels - 1)) {
+    //
+    // recursively search the table hierarchy
+    //
+    recursivelyRemoveLevels(
+       address,
+       level + 1,
+       highBit - m_number_of_bits_per_level[level],
+       lowBit - m_number_of_bits_per_level[level + 1],
+       (Map<Address, SparseMemEntry_t>*)((curTable->lookup(curAddress)).entry)
+       );
+
+    //
+    // If this table is now empty, we should delete it
+    //
+    if (curTable->size() == 0) {
+      delete curTable;
+    }
+  } else {
+    //
+    // if this is the last level, we have reached the Directory Entry and thus
+    // we should delete.
+    //
+    curTable->erase(curAddress);
+  }
+  
+}
+
+// remove an entry from the table
+void SparseMemory::remove(const Address& address)
+{
+  assert(address == line_address(address));
+  assert(exist(address) != false);
+
+  //
+  // 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 = highBit - m_number_of_bits_per_level[0];;
+
+  // 
+  // recursively search the table hierarchy for empty tables starting from the
+  // level 0
+  //
+  recursivelyRemoveLevels(address,
+                          0,
+                          highBit,
+                          lowBit,
+                          m_map_head);
+
+  assert(exist(address) == false);
+  return;
+}
+
+// looks an address up in memory
+Directory_Entry* SparseMemory::lookup(const Address& address)
+{
+  assert(exist(address) != false);
+  assert(address == line_address(address));
+
+  Address curAddress;
+  Map<Address, SparseMemEntry_t>* 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));
+
+    //
+    // 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 = (Map<Address, SparseMemEntry_t>*)((curTable->lookup(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
+{
+}
+
diff -r 737662612eb7 src/mem/ruby/system/SparseMemory.hh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/mem/ruby/system/SparseMemory.hh	Fri Sep 11 16:01:22 2009 -0700
@@ -0,0 +1,74 @@
+
+#ifndef SPARSEMEMORY_H
+#define SPARSEMEMORY_H
+
+#include "mem/ruby/common/Global.hh"
+#include "mem/gems_common/Map.hh"
+#include "mem/ruby/common/Address.hh"
+#include "mem/protocol/Directory_Entry.hh"
+
+typedef struct SparseMemEntry {
+  void* entry;
+} SparseMemEntry_t;
+
+
+
+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;
+private:
+  // Private Methods
+
+  // Private copy constructor and assignment operator
+  SparseMemory(const SparseMemory& obj);
+  SparseMemory& operator=(const SparseMemory& obj);
+
+  // recursive search function
+  void recursivelyRemoveLevels(const Address& address,
+                               int level,
+                               int highBit,
+                               int lowBit,
+                               Map<Address, SparseMemEntry_t>* currentTable);
+
+  // Data Members (m_prefix)
+  Map<Address, SparseMemEntry_t>* m_map_head;
+
+  int m_total_number_of_bits;
+  int m_number_of_levels;
+  int* m_number_of_bits_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 -r 737662612eb7 src/mem/ruby/system/System.cc
--- a/src/mem/ruby/system/System.cc	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/ruby/system/System.cc	Fri Sep 11 16:01:22 2009 -0700
@@ -263,13 +263,27 @@
   DirectoryMemory* prev = NULL;
   for (map< string, DirectoryMemory*>::const_iterator it = m_directories.begin();
        it != m_directories.end(); it++) {
-    if (prev != NULL)
+
+    if (prev != NULL) {
       assert((*it).second->getSize() == prev->getSize()); // must be equal for proper address mapping
-    m_memory_size_bytes += (*it).second->getSize();
+    }
+
+    //
+    // if the DirectoryMemory is using a sparse memory implementation, then
+    // the system should not back-up the memory state with the Memory Vector
+    // and thus the memory size bytes should not be incremented
+    //
+    if ((*it).second->isSparseImplementation() == false) {
+      m_memory_size_bytes += (*it).second->getSize();
+    }
+
     prev = (*it).second;
   }
   m_mem_vec_ptr->setSize(m_memory_size_bytes);
-  m_memory_size_bits = log_int(m_memory_size_bytes);
+  if (m_memory_size_bytes > 0)
+    m_memory_size_bits = log_int(m_memory_size_bytes);
+  else
+    m_memory_size_bits = 0;
 
 //  m_tracer_ptr = new Tracer;
   DEBUG_MSG(SYSTEM_COMP, MedPrio,"finished initializing");
diff -r 737662612eb7 src/mem/rubymem.cc
--- a/src/mem/rubymem.cc	Fri Sep 11 11:07:22 2009 -0500
+++ b/src/mem/rubymem.cc	Fri Sep 11 16:01:22 2009 -0700
@@ -59,7 +59,7 @@
 
     vector<RubyObjConf> sys_conf;
     while (!config.eof()) {
-        char buffer[4096];
+        char buffer[65536];
         config.getline(buffer, sizeof(buffer));
         string line = buffer;
         if (line.empty())
diff -r 737662612eb7 tests/configs/ruby_config.py
--- a/tests/configs/ruby_config.py	Fri Sep 11 11:07:22 2009 -0500
+++ b/tests/configs/ruby_config.py	Fri Sep 11 16:01:22 2009 -0700
@@ -4,17 +4,25 @@
 from os.path import dirname, join as joinpath
 
 import m5
+from m5.params import *
 
-def generate(config_file, cores=1, memories=1, memory_size=1024):
+def generate(config_file, cores=1, memories=1, memory_size=1024, use_map=False):
     default = joinpath(dirname(__file__), '../../src/mem/ruby/config')
     ruby_config = os.environ.get('RUBY_CONFIG', default)
     args = [ "ruby", "-I", ruby_config, joinpath(ruby_config, "print_cfg.rb"),
              "-r", joinpath(ruby_config, config_file), "-p", str(cores),
-             "-m", str(memories), "-s", str(memory_size)]
+             "-m", str(memories), "-s", str(memory_size),
+             "-u", str(use_map)]
 
     temp_config = joinpath(m5.options.outdir, "ruby.config")
     ret = subprocess.call(args, stdout=file(temp_config, "w"))
     if ret != 0:
         raise RuntimeError, "subprocess failed!"
 
-    return m5.objects.RubyMemory(config_file=temp_config, num_cpus=cores)
+    if (use_map == False):
+        return m5.objects.RubyMemory(config_file=temp_config, num_cpus=cores)
+    else:
+        return m5.objects.RubyMemory(config_file=temp_config,
+                                     num_cpus=cores,
+                                     range=AddrRange(str(memory_size)+"MB"),
+                                     null='true')