src/mem/ruby/system/MultiBitSelBloomFilter.cc

   1
   2 /*
   3  * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are
   8  * met: redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer;
  10  * redistributions in binary form must reproduce the above copyright
  11  * notice, this list of conditions and the following disclaimer in the
  12  * documentation and/or other materials provided with the distribution;
  13  * neither the name of the copyright holders nor the names of its
  14  * contributors may be used to endorse or promote products derived from
  15  * this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 /*
  31  * NonCountingBloomFilter.C
  32  *
  33  * Description:
  34  *
  35  *
  36  */
  37
  38 #include "MultiBitSelBloomFilter.hh"
  39 #include "Map.hh"
  40 #include "Address.hh"
  41
  42 MultiBitSelBloomFilter::MultiBitSelBloomFilter(string str)
  43 {
  44
  45   string tail(str);
  46   string head = string_split(tail, '_');
  47
  48   // head contains filter size, tail contains bit offset from block number
  49   m_filter_size = atoi(head.c_str());
  50
  51   head = string_split(tail, '_');
  52   m_num_hashes = atoi(head.c_str());
  53
  54   head = string_split(tail, '_');
  55   m_skip_bits = atoi(head.c_str());
  56
  57   if(tail == "Regular") {
  58     isParallel = false;
  59   } else if (tail == "Parallel") {
  60     isParallel = true;
  61   } else {
  62     cout << "ERROR: Incorrect config string for MultiBitSel Bloom! :" << str << endl;
  63     assert(0);
  64   }
  65
  66   m_filter_size_bits = log_int(m_filter_size);
  67
  68   m_par_filter_size = m_filter_size/m_num_hashes;
  69   m_par_filter_size_bits = log_int(m_par_filter_size);
  70
  71   m_filter.setSize(m_filter_size);
  72   clear();
  73 }
  74
  75 MultiBitSelBloomFilter::~MultiBitSelBloomFilter(){
  76 }
  77
  78 void MultiBitSelBloomFilter::clear()
  79 {
  80   for (int i = 0; i < m_filter_size; i++) {
  81     m_filter[i] = 0;
  82   }
  83 }
  84
  85 void MultiBitSelBloomFilter::increment(const Address& addr)
  86 {
  87   // Not used
  88 }
  89
  90
  91 void MultiBitSelBloomFilter::decrement(const Address& addr)
  92 {
  93   // Not used
  94 }
  95
  96 void MultiBitSelBloomFilter::merge(AbstractBloomFilter * other_filter){
  97   // assumes both filters are the same size!
  98   MultiBitSelBloomFilter * temp = (MultiBitSelBloomFilter*) other_filter;
  99   for(int i=0; i < m_filter_size; ++i){
 100     m_filter[i] |= (*temp)[i];
 101   }
 102
 103 }
 104
 105 void MultiBitSelBloomFilter::set(const Address& addr)
 106 {
 107   for (int i = 0; i < m_num_hashes; i++) {
 108     int idx = get_index(addr, i);
 109     m_filter[idx] = 1;
 110
 111     //Profile hash value distribution
 112     //g_system_ptr->getProfiler()->getXactProfiler()->profileHashValue(i, idx); //gem5:Arka for decomissioning of log_tm
 113   }
 114 }
 115
 116 void MultiBitSelBloomFilter::unset(const Address& addr)
 117 {
 118   cout << "ERROR: Unset should never be called in a Bloom filter";
 119   assert(0);
 120 }
 121
 122 bool MultiBitSelBloomFilter::isSet(const Address& addr)
 123 {
 124   bool res = true;
 125
 126   for (int i=0; i < m_num_hashes; i++) {
 127     int idx = get_index(addr, i);
 128     res = res && m_filter[idx];
 129   }
 130   return res;
 131 }
 132
 133
 134 int MultiBitSelBloomFilter::getCount(const Address& addr)
 135 {
 136   return isSet(addr)? 1: 0;
 137 }
 138
 139 int MultiBitSelBloomFilter::getIndex(const Address& addr)
 140 {
 141   return 0;
 142 }
 143
 144 int MultiBitSelBloomFilter::readBit(const int index) {
 145   return 0;
 146 }
 147
 148 void MultiBitSelBloomFilter::writeBit(const int index, const int value) {
 149
 150 }
 151
 152 int MultiBitSelBloomFilter::getTotalCount()
 153 {
 154   int count = 0;
 155
 156   for (int i = 0; i < m_filter_size; i++) {
 157     count += m_filter[i];
 158   }
 159   return count;
 160 }
 161
 162 void MultiBitSelBloomFilter::print(ostream& out) const
 163 {
 164 }
 165
 166 int MultiBitSelBloomFilter::get_index(const Address& addr, int i)
 167 {
 168   // m_skip_bits is used to perform BitSelect after skipping some bits. Used to simulate BitSel hashing on larger than cache-line granularities
 169   uint64 x = (addr.getLineAddress()) >> m_skip_bits;
 170   int y = hash_bitsel(x, i, m_num_hashes, 30, m_filter_size_bits);
 171   //36-bit addresses, 6-bit cache lines
 172
 173   if(isParallel) {
 174     return (y % m_par_filter_size) + i*m_par_filter_size;
 175   } else {
 176     return y % m_filter_size;
 177   }
 178 }
 179
 180
 181 int MultiBitSelBloomFilter::hash_bitsel(uint64 value, int index, int jump, int maxBits, int numBits) {
 182   uint64 mask = 1;
 183   int result = 0;
 184   int bit, i;
 185
 186   for(i = 0; i < numBits; i++) {
 187     bit = (index + jump*i) % maxBits;
 188     if (value & (mask << bit)) result += mask << i;
 189   }
 190   return result;
 191 }