diff options
Diffstat (limited to 'src/mem/ruby')
| -rw-r--r-- | src/mem/ruby/filters/AbstractBloomFilter.hh | 76 | ||||
| -rw-r--r-- | src/mem/ruby/filters/BlockBloomFilter.cc | 53 | ||||
| -rw-r--r-- | src/mem/ruby/filters/BlockBloomFilter.hh | 14 | ||||
| -rw-r--r-- | src/mem/ruby/filters/BulkBloomFilter.cc | 106 | ||||
| -rw-r--r-- | src/mem/ruby/filters/BulkBloomFilter.hh | 24 | ||||
| -rw-r--r-- | src/mem/ruby/filters/H3BloomFilter.cc | 92 | ||||
| -rw-r--r-- | src/mem/ruby/filters/H3BloomFilter.hh | 57 | ||||
| -rw-r--r-- | src/mem/ruby/filters/LSB_CountingBloomFilter.cc | 57 | ||||
| -rw-r--r-- | src/mem/ruby/filters/LSB_CountingBloomFilter.hh | 20 | ||||
| -rw-r--r-- | src/mem/ruby/filters/MultiBitSelBloomFilter.cc | 71 | ||||
| -rw-r--r-- | src/mem/ruby/filters/MultiBitSelBloomFilter.hh | 44 | ||||
| -rw-r--r-- | src/mem/ruby/filters/MultiGrainBloomFilter.cc | 69 | ||||
| -rw-r--r-- | src/mem/ruby/filters/MultiGrainBloomFilter.hh | 28 | ||||
| -rw-r--r-- | src/mem/ruby/filters/NonCountingBloomFilter.cc | 61 | ||||
| -rw-r--r-- | src/mem/ruby/filters/NonCountingBloomFilter.hh | 28 |
15 files changed, 289 insertions, 511 deletions
diff --git a/src/mem/ruby/filters/AbstractBloomFilter.hh b/src/mem/ruby/filters/AbstractBloomFilter.hh index 3e90cadd9..851e5d9be 100644 --- a/src/mem/ruby/filters/AbstractBloomFilter.hh +++ b/src/mem/ruby/filters/AbstractBloomFilter.hh @@ -1,4 +1,5 @@ /* + * Copyright (c) 2019 Inria * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood * All rights reserved. * @@ -24,19 +25,57 @@ * 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. + * + * Authors: Daniel Carvalho */ #ifndef __MEM_RUBY_FILTERS_ABSTRACTBLOOMFILTER_HH__ #define __MEM_RUBY_FILTERS_ABSTRACTBLOOMFILTER_HH__ -#include "mem/ruby/common/Address.hh" +#include <vector> + +#include "base/intmath.hh" +#include "base/types.hh" class AbstractBloomFilter { + protected: + /** The filter itself. */ + std::vector<int> filter; + + /** Number of bits needed to represent the size of the filter. */ + const int sizeBits; + public: + /** + * Create and clear the filter. + */ + AbstractBloomFilter(std::size_t size) + : filter(size), sizeBits(floorLog2(size)) + { + clear(); + } virtual ~AbstractBloomFilter() {}; - virtual void clear() = 0; - virtual void merge(AbstractBloomFilter * other_filter) = 0; + + /** + * Clear the filter by resetting all values. + */ + virtual void clear() + { + for (auto& entry : filter) { + entry = 0; + } + } + + /** Merges the contents of both filters into this'. */ + virtual void merge(const AbstractBloomFilter* other) {} + + /** + * Perform the filter specific function to set the corresponding + * entries (can be multiple) of an address. + * + * @param addr The address being parsed. + */ virtual void set(Addr addr) = 0; /** @@ -48,9 +87,36 @@ class AbstractBloomFilter */ virtual void unset(Addr addr) {}; + /** + * Check if the corresponding filter entries of an address should be + * considered as set. + * + * @param addr The address being parsed. + * @return Whether the respective filter entry is set. + */ virtual bool isSet(Addr addr) = 0; - virtual int getCount(Addr addr) = 0; - virtual int getTotalCount() = 0; + + /** + * Get the value stored in the corresponding filter entry of an address. + * + * @param addr The address being parsed. + * @param Get the value stored in the respective filter entry. + */ + virtual int getCount(Addr addr) { return 0; } + + /** + * Get the total value stored in the filter entries. + * + * @return The sum of all filter entries. + */ + virtual int getTotalCount() const + { + int count = 0; + for (const auto& entry : filter) { + count += entry; + } + return count; + } }; #endif // __MEM_RUBY_FILTERS_ABSTRACTBLOOMFILTER_HH__ diff --git a/src/mem/ruby/filters/BlockBloomFilter.cc b/src/mem/ruby/filters/BlockBloomFilter.cc index 351692885..f9942fe71 100644 --- a/src/mem/ruby/filters/BlockBloomFilter.cc +++ b/src/mem/ruby/filters/BlockBloomFilter.cc @@ -28,17 +28,12 @@ #include "mem/ruby/filters/BlockBloomFilter.hh" -#include "base/intmath.hh" +#include "mem/ruby/common/Address.hh" #include "mem/ruby/system/RubySystem.hh" BlockBloomFilter::BlockBloomFilter(int size) + : AbstractBloomFilter(size) { - m_filter_size = size; - m_filter_size_bits = floorLog2(m_filter_size); - - m_filter.resize(m_filter_size); - - clear(); } BlockBloomFilter::~BlockBloomFilter() @@ -46,61 +41,31 @@ BlockBloomFilter::~BlockBloomFilter() } void -BlockBloomFilter::clear() -{ - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } -} - -void -BlockBloomFilter::merge(AbstractBloomFilter * other_filter) -{ - // TODO -} - -void BlockBloomFilter::set(Addr addr) { - int i = get_index(addr); - m_filter[i] = 1; + filter[hash(addr)] = 1; } void BlockBloomFilter::unset(Addr addr) { - int i = get_index(addr); - m_filter[i] = 0; + filter[hash(addr)] = 0; } bool BlockBloomFilter::isSet(Addr addr) { - int i = get_index(addr); - return (m_filter[i]); + return filter[hash(addr)]; } int BlockBloomFilter::getCount(Addr addr) { - return m_filter[get_index(addr)]; -} - -int -BlockBloomFilter::getTotalCount() -{ - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - if (m_filter[i]) { - count++; - } - } - return count; + return filter[hash(addr)]; } int -BlockBloomFilter::get_index(Addr addr) +BlockBloomFilter::hash(Addr addr) const { // Pull out some bit field ==> B1 // Pull out additional bits, not the same as B1 ==> B2 @@ -111,9 +76,9 @@ BlockBloomFilter::get_index(Addr addr) Addr other_bits = bitSelect(addr, 2 * RubySystem::getBlockSizeBits() + offset, 2 * RubySystem::getBlockSizeBits() + offset + - m_filter_size_bits - 1); + sizeBits - 1); int index = block_bits ^ other_bits; - assert(index < m_filter_size); + assert(index < filter.size()); return index; } diff --git a/src/mem/ruby/filters/BlockBloomFilter.hh b/src/mem/ruby/filters/BlockBloomFilter.hh index 5eaf6ead3..7c8ffc19c 100644 --- a/src/mem/ruby/filters/BlockBloomFilter.hh +++ b/src/mem/ruby/filters/BlockBloomFilter.hh @@ -29,9 +29,6 @@ #ifndef __MEM_RUBY_FILTERS_BLOCKBLOOMFILTER_HH__ #define __MEM_RUBY_FILTERS_BLOCKBLOOMFILTER_HH__ -#include <vector> - -#include "mem/ruby/common/Address.hh" #include "mem/ruby/filters/AbstractBloomFilter.hh" class BlockBloomFilter : public AbstractBloomFilter @@ -40,21 +37,14 @@ class BlockBloomFilter : public AbstractBloomFilter BlockBloomFilter(int size); ~BlockBloomFilter(); - void clear(); - void merge(AbstractBloomFilter * other_filter); - void set(Addr addr); + void set(Addr addr) override; void unset(Addr addr) override; bool isSet(Addr addr); int getCount(Addr addr); - int getTotalCount(); private: - int get_index(Addr addr); - - std::vector<int> m_filter; - int m_filter_size; - int m_filter_size_bits; + int hash(Addr addr) const; }; #endif // __MEM_RUBY_FILTERS_BLOCKBLOOMFILTER_HH__ diff --git a/src/mem/ruby/filters/BulkBloomFilter.cc b/src/mem/ruby/filters/BulkBloomFilter.cc index da873f942..a917a1491 100644 --- a/src/mem/ruby/filters/BulkBloomFilter.cc +++ b/src/mem/ruby/filters/BulkBloomFilter.cc @@ -28,26 +28,12 @@ #include "mem/ruby/filters/BulkBloomFilter.hh" -#include <cassert> - -#include "base/intmath.hh" +#include "mem/ruby/common/Address.hh" #include "mem/ruby/system/RubySystem.hh" BulkBloomFilter::BulkBloomFilter(int size) + : AbstractBloomFilter(size), sectorBits(sizeBits - 1) { - m_filter_size = size; - m_filter_size_bits = floorLog2(m_filter_size); - // split the filter bits in half, c0 and c1 - m_sector_bits = m_filter_size_bits - 1; - - m_temp_filter.resize(m_filter_size); - m_filter.resize(m_filter_size); - clear(); - - // clear temp filter - for (int i = 0; i < m_filter_size; ++i) { - m_temp_filter[i] = 0; - } } BulkBloomFilter::~BulkBloomFilter() @@ -55,92 +41,80 @@ BulkBloomFilter::~BulkBloomFilter() } void -BulkBloomFilter::clear() -{ - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } -} - -void -BulkBloomFilter::merge(AbstractBloomFilter * other_filter) -{ - // TODO -} - -void BulkBloomFilter::set(Addr addr) { // c0 contains the cache index bits - int set_bits = m_sector_bits; + int set_bits = sectorBits; int block_bits = RubySystem::getBlockSizeBits(); int c0 = bitSelect(addr, block_bits, block_bits + set_bits - 1); - // c1 contains the lower m_sector_bits permuted bits + // c1 contains the lower sectorBits permuted bits //Address permuted_bits = permute(addr); //int c1 = permuted_bits.bitSelect(0, set_bits-1); int c1 = bitSelect(addr, block_bits+set_bits, (block_bits+2*set_bits) - 1); - //assert(c0 < (m_filter_size/2)); - //assert(c0 + (m_filter_size/2) < m_filter_size); - //assert(c1 < (m_filter_size/2)); + //assert(c0 < (filter_size/2)); + //assert(c0 + (filter_size/2) < filter_size); + //assert(c1 < (filter_size/2)); // set v0 bit - m_filter[c0 + (m_filter_size/2)] = 1; + filter[c0 + (filter.size()/2)] = 1; // set v1 bit - m_filter[c1] = 1; + filter[c1] = 1; } bool BulkBloomFilter::isSet(Addr addr) { // c0 contains the cache index bits - int set_bits = m_sector_bits; + const int filter_size = filter.size(); + int set_bits = sectorBits; int block_bits = RubySystem::getBlockSizeBits(); int c0 = bitSelect(addr, block_bits, block_bits + set_bits - 1); // c1 contains the lower 10 permuted bits //Address permuted_bits = permute(addr); //int c1 = permuted_bits.bitSelect(0, set_bits-1); int c1 = bitSelect(addr, block_bits+set_bits, (block_bits+2*set_bits) - 1); - //assert(c0 < (m_filter_size/2)); - //assert(c0 + (m_filter_size/2) < m_filter_size); - //assert(c1 < (m_filter_size/2)); + //assert(c0 < (filter_size/2)); + //assert(c0 + (filter_size/2) < filter_size); + //assert(c1 < (filter_size/2)); // set v0 bit - m_temp_filter[c0 + (m_filter_size/2)] = 1; + std::vector<int> temp_filter(filter.size(), 0); + temp_filter[c0 + (filter_size/2)] = 1; // set v1 bit - m_temp_filter[c1] = 1; + temp_filter[c1] = 1; // perform filter intersection. If any c part is 0, no possibility // of address being in signature. get first c intersection part bool zero = false; - for (int i = 0; i < m_filter_size/2; ++i){ + for (int i = 0; i < filter_size/2; ++i){ // get intersection of signatures - m_temp_filter[i] = m_temp_filter[i] && m_filter[i]; - zero = zero || m_temp_filter[i]; + temp_filter[i] = temp_filter[i] && filter[i]; + zero = zero || temp_filter[i]; } zero = !zero; if (zero) { // one section is zero, no possiblility of address in signature // reset bits we just set - m_temp_filter[c0 + (m_filter_size / 2)] = 0; - m_temp_filter[c1] = 0; + temp_filter[c0 + (filter_size / 2)] = 0; + temp_filter[c1] = 0; return false; } // check second section zero = false; - for (int i = m_filter_size / 2; i < m_filter_size; ++i) { + for (int i = filter_size / 2; i < filter_size; ++i) { // get intersection of signatures - m_temp_filter[i] = m_temp_filter[i] && m_filter[i]; - zero = zero || m_temp_filter[i]; + temp_filter[i] = temp_filter[i] && filter[i]; + zero = zero || temp_filter[i]; } zero = !zero; if (zero) { // one section is zero, no possiblility of address in signature - m_temp_filter[c0 + (m_filter_size / 2)] = 0; - m_temp_filter[c1] = 0; + temp_filter[c0 + (filter_size / 2)] = 0; + temp_filter[c1] = 0; return false; } // one section has at least one bit set - m_temp_filter[c0 + (m_filter_size / 2)] = 0; - m_temp_filter[c1] = 0; + temp_filter[c0 + (filter_size / 2)] = 0; + temp_filter[c1] = 0; return true; } @@ -151,28 +125,8 @@ BulkBloomFilter::getCount(Addr addr) return 0; } -int -BulkBloomFilter::getTotalCount() -{ - int count = 0; - for (int i = 0; i < m_filter_size; i++) { - if (m_filter[i]) { - count++; - } - } - return count; -} - -int -BulkBloomFilter::get_index(Addr addr) -{ - return bitSelect(addr, RubySystem::getBlockSizeBits(), - RubySystem::getBlockSizeBits() + - m_filter_size_bits - 1); -} - Addr -BulkBloomFilter::permute(Addr addr) +BulkBloomFilter::hash(Addr addr) const { // permutes the original address bits according to Table 5 int block_offset = RubySystem::getBlockSizeBits(); diff --git a/src/mem/ruby/filters/BulkBloomFilter.hh b/src/mem/ruby/filters/BulkBloomFilter.hh index 39cd80944..b6f52b960 100644 --- a/src/mem/ruby/filters/BulkBloomFilter.hh +++ b/src/mem/ruby/filters/BulkBloomFilter.hh @@ -31,35 +31,29 @@ #include <vector> -#include "mem/ruby/common/Address.hh" #include "mem/ruby/filters/AbstractBloomFilter.hh" +/** + * Implementation of the bloom filter, as described in "Bulk Disambiguation of + * Speculative Threads in Multiprocessors", by Ceze, Luis, et al. + */ class BulkBloomFilter : public AbstractBloomFilter { public: BulkBloomFilter(int size); ~BulkBloomFilter(); - void clear(); - void merge(AbstractBloomFilter * other_filter); - void set(Addr addr); + void set(Addr addr) override; bool isSet(Addr addr); int getCount(Addr addr); - int getTotalCount(); private: - int get_index(Addr addr); - Addr permute(Addr addr); - - std::vector<int> m_filter; - std::vector<int> m_temp_filter; - - int m_filter_size; - int m_filter_size_bits; - - int m_sector_bits; + /** Permutes the address to generate its signature. */ + Addr hash(Addr addr) const; + // split the filter bits in half, c0 and c1 + const int sectorBits; }; #endif // __MEM_RUBY_FILTERS_BULKBLOOMFILTER_HH__ diff --git a/src/mem/ruby/filters/H3BloomFilter.cc b/src/mem/ruby/filters/H3BloomFilter.cc index 7f44a2bd3..f6ee8a168 100644 --- a/src/mem/ruby/filters/H3BloomFilter.cc +++ b/src/mem/ruby/filters/H3BloomFilter.cc @@ -28,7 +28,8 @@ #include "mem/ruby/filters/H3BloomFilter.hh" -#include "base/intmath.hh" +#include "base/logging.hh" +#include "mem/ruby/common/Address.hh" static int H3[64][16] = { { 33268410, 395488709, 311024285, 456111753, @@ -352,41 +353,11 @@ static int H3[64][16] = { 394261773, 848616745, 15446017, 517723271, }, }; -H3BloomFilter::H3BloomFilter(int size, int hashes, bool parallel) +H3BloomFilter::H3BloomFilter(int size, int num_hashes, bool parallel) + : AbstractBloomFilter(size), numHashes(num_hashes), isParallel(parallel), + parFilterSize(filter.size() / numHashes) { - //TODO: change this ugly init code... - primes_list[0] = 9323; - primes_list[1] = 11279; - primes_list[2] = 10247; - primes_list[3] = 30637; - primes_list[4] = 25717; - primes_list[5] = 43711; - - mults_list[0] = 255; - mults_list[1] = 29; - mults_list[2] = 51; - mults_list[3] = 3; - mults_list[4] = 77; - mults_list[5] = 43; - - adds_list[0] = 841; - adds_list[1] = 627; - adds_list[2] = 1555; - adds_list[3] = 241; - adds_list[4] = 7777; - adds_list[5] = 65931; - - m_filter_size = size; - m_num_hashes = hashes; - isParallel = parallel; - - m_filter_size_bits = floorLog2(m_filter_size); - - m_par_filter_size = m_filter_size / m_num_hashes; - m_par_filter_size_bits = floorLog2(m_par_filter_size); - - m_filter.resize(m_filter_size); - clear(); + fatal_if(numHashes > 16, "There are only 16 hash functions implemented."); } H3BloomFilter::~H3BloomFilter() @@ -394,29 +365,20 @@ H3BloomFilter::~H3BloomFilter() } void -H3BloomFilter::clear() +H3BloomFilter::merge(const AbstractBloomFilter *other) { - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } -} - -void -H3BloomFilter::merge(AbstractBloomFilter *other_filter) -{ - // assumes both filters are the same size! - H3BloomFilter * temp = (H3BloomFilter*) other_filter; - for (int i = 0; i < m_filter_size; ++i){ - m_filter[i] |= (*temp)[i]; + auto* cast_other = static_cast<const H3BloomFilter*>(other); + assert(filter.size() == cast_other->filter.size()); + for (int i = 0; i < filter.size(); ++i){ + filter[i] |= cast_other->filter[i]; } } void H3BloomFilter::set(Addr addr) { - for (int i = 0; i < m_num_hashes; i++) { - int idx = get_index(addr, i); - m_filter[idx] = 1; + for (int i = 0; i < numHashes; i++) { + filter[hash(addr, i)] = 1; } } @@ -425,9 +387,9 @@ H3BloomFilter::isSet(Addr addr) { bool res = true; - for (int i = 0; i < m_num_hashes; i++) { - int idx = get_index(addr, i); - res = res && m_filter[idx]; + for (int i = 0; i < numHashes; i++) { + int idx = hash(addr, i); + res = res && filter[idx]; } return res; } @@ -439,32 +401,20 @@ H3BloomFilter::getCount(Addr addr) } int -H3BloomFilter::getTotalCount() -{ - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - count += m_filter[i]; - } - return count; -} - -int -H3BloomFilter::get_index(Addr addr, int i) +H3BloomFilter::hash(Addr addr, int hash_number) const { uint64_t x = makeLineAddress(addr); - // uint64_t y = (x*mults_list[i] + adds_list[i]) % primes_list[i]; - int y = hash_H3(x,i); + int y = hashH3(x, hash_number); if (isParallel) { - return (y % m_par_filter_size) + i*m_par_filter_size; + return (y % parFilterSize) + hash_number * parFilterSize; } else { - return y % m_filter_size; + return y % filter.size(); } } int -H3BloomFilter::hash_H3(uint64_t value, int index) +H3BloomFilter::hashH3(uint64_t value, int index) const { uint64_t mask = 1; uint64_t val = value; diff --git a/src/mem/ruby/filters/H3BloomFilter.hh b/src/mem/ruby/filters/H3BloomFilter.hh index 1df0d2a16..6cfa29337 100644 --- a/src/mem/ruby/filters/H3BloomFilter.hh +++ b/src/mem/ruby/filters/H3BloomFilter.hh @@ -29,49 +29,48 @@ #ifndef __MEM_RUBY_FILTERS_H3BLOOMFILTER_HH__ #define __MEM_RUBY_FILTERS_H3BLOOMFILTER_HH__ -#include <vector> - -#include "mem/ruby/common/Address.hh" #include "mem/ruby/filters/AbstractBloomFilter.hh" +/** + * Implementation of the bloom filter as described in "Implementing Signatures + * for Transactional Memory", by Sanchez, Daniel, et al. + */ class H3BloomFilter : public AbstractBloomFilter { public: - H3BloomFilter(int size, int hashes, bool parallel); + H3BloomFilter(int size, int num_hashes, bool parallel); ~H3BloomFilter(); - void clear(); - void merge(AbstractBloomFilter * other_filter); - void set(Addr addr); - + void merge(const AbstractBloomFilter* other) override; + void set(Addr addr) override; bool isSet(Addr addr); - int getCount(Addr addr); - int getTotalCount(); - - int - operator[](const int index) const - { - return this->m_filter[index]; - } + int getCount(Addr addr) override; private: - int get_index(Addr addr, int hashNumber); + /** + * Apply a hash functions to an address. + * + * @param addr The address to hash. + * @param hash_number Index of the H3 hash function to be used. + */ + int hash(Addr addr, int hash_number) const; - int hash_H3(uint64_t value, int index); + /** + * Apply one of the H3 hash functions to a value. + * + * @param value The value to hash. + * @param hash_number Index of the hash function to be used. + */ + int hashH3(uint64_t value, int hash_number) const; - std::vector<int> m_filter; - int m_filter_size; - int m_num_hashes; - int m_filter_size_bits; - - int m_par_filter_size; - int m_par_filter_size_bits; - - int primes_list[6];// = {9323,11279,10247,30637,25717,43711}; - int mults_list[6]; //= {255,29,51,3,77,43}; - int adds_list[6]; //= {841,627,1555,241,7777,65391}; + /** The number of hashes used in this filter. Can be at most 16. */ + const int numHashes; + /** Whether hashing should be performed in parallel. */ bool isParallel; + + /** Size of the filter when doing parallel hashing. */ + int parFilterSize; }; #endif // __MEM_RUBY_FILTERS_H3BLOOMFILTER_HH__ diff --git a/src/mem/ruby/filters/LSB_CountingBloomFilter.cc b/src/mem/ruby/filters/LSB_CountingBloomFilter.cc index 5d9475bed..06e2d4f67 100644 --- a/src/mem/ruby/filters/LSB_CountingBloomFilter.cc +++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.cc @@ -28,19 +28,13 @@ #include "mem/ruby/filters/LSB_CountingBloomFilter.hh" -#include "base/intmath.hh" +#include "mem/ruby/common/Address.hh" #include "mem/ruby/system/RubySystem.hh" -LSB_CountingBloomFilter::LSB_CountingBloomFilter(int head, int tail) +LSB_CountingBloomFilter::LSB_CountingBloomFilter(std::size_t filter_size, + int max_value) + : AbstractBloomFilter(filter_size), maxValue(max_value) { - m_filter_size = head; - m_filter_size_bits = floorLog2(m_filter_size); - - m_count = tail; - m_count_bits = floorLog2(m_count); - - m_filter.resize(m_filter_size); - clear(); } LSB_CountingBloomFilter::~LSB_CountingBloomFilter() @@ -48,33 +42,19 @@ LSB_CountingBloomFilter::~LSB_CountingBloomFilter() } void -LSB_CountingBloomFilter::clear() -{ - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } -} - -void -LSB_CountingBloomFilter::merge(AbstractBloomFilter * other_filter) -{ - // TODO -} - -void LSB_CountingBloomFilter::set(Addr addr) { - int i = get_index(addr); - if (m_filter[i] < m_count) - m_filter[i] += 1; + const int i = hash(addr); + if (filter[i] < maxValue) + filter[i] += 1; } void LSB_CountingBloomFilter::unset(Addr addr) { - int i = get_index(addr); - if (m_filter[i] > 0) - m_filter[i] -= 1; + const int i = hash(addr); + if (filter[i] > 0) + filter[i] -= 1; } bool @@ -87,26 +67,15 @@ LSB_CountingBloomFilter::isSet(Addr addr) int LSB_CountingBloomFilter::getCount(Addr addr) { - return m_filter[get_index(addr)]; -} - -int -LSB_CountingBloomFilter::getTotalCount() -{ - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - count += m_filter[i]; - } - return count; + return filter[hash(addr)]; } int -LSB_CountingBloomFilter::get_index(Addr addr) +LSB_CountingBloomFilter::hash(Addr addr) const { return bitSelect(addr, RubySystem::getBlockSizeBits(), RubySystem::getBlockSizeBits() + - m_filter_size_bits - 1); + sizeBits - 1); } diff --git a/src/mem/ruby/filters/LSB_CountingBloomFilter.hh b/src/mem/ruby/filters/LSB_CountingBloomFilter.hh index 7c02f7726..4fc635581 100644 --- a/src/mem/ruby/filters/LSB_CountingBloomFilter.hh +++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.hh @@ -29,35 +29,25 @@ #ifndef __MEM_RUBY_FILTERS_LSB_COUNTINGBLOOMFILTER_HH__ #define __MEM_RUBY_FILTERS_LSB_COUNTINGBLOOMFILTER_HH__ -#include <vector> - -#include "mem/ruby/common/Address.hh" #include "mem/ruby/filters/AbstractBloomFilter.hh" class LSB_CountingBloomFilter : public AbstractBloomFilter { public: - LSB_CountingBloomFilter(int head, int tail); + LSB_CountingBloomFilter(std::size_t filter_size, int max_value); ~LSB_CountingBloomFilter(); - void clear(); - void merge(AbstractBloomFilter * other_filter); - void set(Addr addr); + void set(Addr addr) override; void unset(Addr addr) override; bool isSet(Addr addr); int getCount(Addr addr); - int getTotalCount(); private: - int get_index(Addr addr); - - std::vector<int> m_filter; - int m_filter_size; - int m_filter_size_bits; + int hash(Addr addr) const; - int m_count_bits; - int m_count; + /** Maximum value of the filter entries. */ + const int maxValue; }; #endif //__MEM_RUBY_FILTERS_LSB_COUNTINGBLOOMFILTER_HH__ diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc index f64e14eab..aa1438fd3 100644 --- a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc +++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc @@ -28,20 +28,15 @@ #include "mem/ruby/filters/MultiBitSelBloomFilter.hh" -#include <vector> - -#include "base/intmath.hh" +#include "mem/ruby/common/Address.hh" MultiBitSelBloomFilter::MultiBitSelBloomFilter(std::size_t filter_size, int num_hashes, int skip_bits, bool is_parallel) - : m_filter_size(filter_size), m_num_hashes(num_hashes), - m_filter_size_bits(floorLog2(m_filter_size)), m_skip_bits(skip_bits), - m_par_filter_size(m_filter_size / m_num_hashes), - m_par_filter_size_bits(floorLog2(m_par_filter_size)), + : AbstractBloomFilter(filter_size), numHashes(num_hashes), + skipBits(skip_bits), + parFilterSize(filter_size / numHashes), isParallel(is_parallel) { - m_filter.resize(m_filter_size); - clear(); } MultiBitSelBloomFilter::~MultiBitSelBloomFilter() @@ -49,29 +44,21 @@ MultiBitSelBloomFilter::~MultiBitSelBloomFilter() } void -MultiBitSelBloomFilter::clear() -{ - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } -} - -void -MultiBitSelBloomFilter::merge(AbstractBloomFilter *other_filter) +MultiBitSelBloomFilter::merge(const AbstractBloomFilter *other) { - // assumes both filters are the same size! - MultiBitSelBloomFilter * temp = (MultiBitSelBloomFilter*) other_filter; - for (int i = 0; i < m_filter_size; ++i){ - m_filter[i] |= (*temp)[i]; + auto cast_other = static_cast<const MultiBitSelBloomFilter*>(other); + assert(filter.size() == cast_other->filter.size()); + for (int i = 0; i < filter.size(); ++i){ + filter[i] |= cast_other->filter[i]; } } void MultiBitSelBloomFilter::set(Addr addr) { - for (int i = 0; i < m_num_hashes; i++) { - int idx = get_index(addr, i); - m_filter[idx] = 1; + for (int i = 0; i < numHashes; i++) { + int idx = hash(addr, i); + filter[idx] = 1; } } @@ -80,9 +67,9 @@ MultiBitSelBloomFilter::isSet(Addr addr) { bool res = true; - for (int i=0; i < m_num_hashes; i++) { - int idx = get_index(addr, i); - res = res && m_filter[idx]; + for (int i=0; i < numHashes; i++) { + int idx = hash(addr, i); + res = res && filter[idx]; } return res; } @@ -94,36 +81,22 @@ MultiBitSelBloomFilter::getCount(Addr addr) } int -MultiBitSelBloomFilter::getTotalCount() -{ - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - count += m_filter[i]; - } - return count; -} - -int -MultiBitSelBloomFilter::get_index(Addr addr, int i) +MultiBitSelBloomFilter::hash(Addr addr, int hash_number) const { - // m_skip_bits is used to perform BitSelect after skipping some - // bits. Used to simulate BitSel hashing on larger than cache-line - // granularities - uint64_t x = (makeLineAddress(addr) >> m_skip_bits); - int y = hash_bitsel(x, i, m_num_hashes, 30, m_filter_size_bits); + uint64_t x = (makeLineAddress(addr) >> skipBits); + int y = hashBitsel(x, hash_number, numHashes, 30, sizeBits); //36-bit addresses, 6-bit cache lines if (isParallel) { - return (y % m_par_filter_size) + i*m_par_filter_size; + return (y % parFilterSize) + hash_number * parFilterSize; } else { - return y % m_filter_size; + return y % filter.size(); } } int -MultiBitSelBloomFilter::hash_bitsel(uint64_t value, int index, int jump, - int maxBits, int numBits) +MultiBitSelBloomFilter::hashBitsel(uint64_t value, int index, int jump, + int maxBits, int numBits) const { uint64_t mask = 1; int result = 0; diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh index 45952de93..2d6954004 100644 --- a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh +++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh @@ -29,10 +29,6 @@ #ifndef __MEM_RUBY_FILTERS_MULTIBITSELBLOOMFILTER_HH__ #define __MEM_RUBY_FILTERS_MULTIBITSELBLOOMFILTER_HH__ -#include <vector> - -#include "mem/ruby/common/Address.hh" -#include "mem/ruby/common/TypeDefines.hh" #include "mem/ruby/filters/AbstractBloomFilter.hh" class MultiBitSelBloomFilter : public AbstractBloomFilter @@ -42,37 +38,31 @@ class MultiBitSelBloomFilter : public AbstractBloomFilter int skip_bits, bool is_parallel); ~MultiBitSelBloomFilter(); - void clear(); - void merge(AbstractBloomFilter * other_filter); - void set(Addr addr); - + void merge(const AbstractBloomFilter* other) override; + void set(Addr addr) override; bool isSet(Addr addr); int getCount(Addr addr); - int getTotalCount(); - - int - operator[](const int index) const - { - return this->m_filter[index]; - } private: - int get_index(Addr addr, int hashNumber); + int hash(Addr addr, int hash_number) const; + + int hashBitsel(uint64_t value, int index, int jump, int maxBits, + int numBits) const; - int hash_bitsel(uint64_t value, int index, int jump, int maxBits, - int numBits); + /** Number of hashes. */ + const int numHashes; - std::vector<int> m_filter; - int m_filter_size; - int m_num_hashes; - int m_filter_size_bits; - // Bit offset from block number - int m_skip_bits; + /** + * Bit offset from block number. Used to simulate bit selection hashing + * on larger than cache-line granularities, by skipping some bits. + */ + const int skipBits; - int m_par_filter_size; - int m_par_filter_size_bits; + /** Size of the filter when doing parallel hashing. */ + const int parFilterSize; - bool isParallel; + /** Whether hashing should be performed in parallel. */ + const bool isParallel; }; #endif // __MEM_RUBY_FILTERS_MULTIBITSELBLOOMFILTER_HH__ diff --git a/src/mem/ruby/filters/MultiGrainBloomFilter.cc b/src/mem/ruby/filters/MultiGrainBloomFilter.cc index a1f8993c9..76016b2ff 100644 --- a/src/mem/ruby/filters/MultiGrainBloomFilter.cc +++ b/src/mem/ruby/filters/MultiGrainBloomFilter.cc @@ -28,22 +28,13 @@ #include "mem/ruby/filters/MultiGrainBloomFilter.hh" -#include "base/intmath.hh" +#include "mem/ruby/common/Address.hh" #include "mem/ruby/system/RubySystem.hh" MultiGrainBloomFilter::MultiGrainBloomFilter(int head, int tail) + : AbstractBloomFilter(head), + pageFilter(tail), pageFilterSizeBits(floorLog2(tail)) { - // head contains size of 1st bloom filter, tail contains size of - // 2nd bloom filter - m_filter_size = head; - m_filter_size_bits = floorLog2(m_filter_size); - - m_page_filter_size = tail; - m_page_filter_size_bits = floorLog2(m_page_filter_size); - - m_filter.resize(m_filter_size); - m_page_filter.resize(m_page_filter_size); - clear(); } MultiGrainBloomFilter::~MultiGrainBloomFilter() @@ -53,39 +44,31 @@ MultiGrainBloomFilter::~MultiGrainBloomFilter() void MultiGrainBloomFilter::clear() { - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } - for (int i=0; i < m_page_filter_size; ++i){ - m_page_filter[i] = 0; + AbstractBloomFilter::clear(); + for (auto& entry : pageFilter){ + entry = 0; } } void -MultiGrainBloomFilter::merge(AbstractBloomFilter *other_filter) -{ - // TODO -} - -void MultiGrainBloomFilter::set(Addr addr) { - int i = get_block_index(addr); - assert(i < m_filter_size); - assert(get_page_index(addr) < m_page_filter_size); - m_filter[i] = 1; - m_page_filter[i] = 1; + int i = hash(addr); + assert(i < filter.size()); + assert(pageHash(addr) < pageFilter.size()); + filter[i] = 1; + pageFilter[i] = 1; } bool MultiGrainBloomFilter::isSet(Addr addr) { - int i = get_block_index(addr); - assert(i < m_filter_size); - assert(get_page_index(addr) < m_page_filter_size); + int i = hash(addr); + assert(i < filter.size()); + assert(pageHash(addr) < pageFilter.size()); // we have to have both indices set - return (m_filter[i] && m_page_filter[i]); + return (filter[i] && pageFilter[i]); } int @@ -96,37 +79,33 @@ MultiGrainBloomFilter::getCount(Addr addr) } int -MultiGrainBloomFilter::getTotalCount() +MultiGrainBloomFilter::getTotalCount() const { - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - count += m_filter[i]; - } + int count = AbstractBloomFilter::getTotalCount(); - for (int i=0; i < m_page_filter_size; ++i) { - count += m_page_filter[i]; + for (const auto& entry : pageFilter) { + count += entry; } return count; } int -MultiGrainBloomFilter::get_block_index(Addr addr) +MultiGrainBloomFilter::hash(Addr addr) const { // grap a chunk of bits after byte offset return bitSelect(addr, RubySystem::getBlockSizeBits(), RubySystem::getBlockSizeBits() + - m_filter_size_bits - 1); + sizeBits - 1); } int -MultiGrainBloomFilter::get_page_index(Addr addr) +MultiGrainBloomFilter::pageHash(Addr addr) const { - int bits = RubySystem::getBlockSizeBits() + m_filter_size_bits - 1; + int bits = RubySystem::getBlockSizeBits() + sizeBits - 1; // grap a chunk of bits after first chunk - return bitSelect(addr, bits, bits + m_page_filter_size_bits - 1); + return bitSelect(addr, bits, bits + pageFilterSizeBits - 1); } diff --git a/src/mem/ruby/filters/MultiGrainBloomFilter.hh b/src/mem/ruby/filters/MultiGrainBloomFilter.hh index 6f9a58478..148f42df2 100644 --- a/src/mem/ruby/filters/MultiGrainBloomFilter.hh +++ b/src/mem/ruby/filters/MultiGrainBloomFilter.hh @@ -31,35 +31,33 @@ #include <vector> -#include "mem/ruby/common/Address.hh" #include "mem/ruby/filters/AbstractBloomFilter.hh" class MultiGrainBloomFilter : public AbstractBloomFilter { public: + /** + * @param head Size of 1st bloom filter. + * @param tail size of 2nd bloom filter. + */ MultiGrainBloomFilter(int head, int tail); ~MultiGrainBloomFilter(); - void clear(); - void merge(AbstractBloomFilter * other_filter); - void set(Addr addr); + void clear() override; + void set(Addr addr) override; bool isSet(Addr addr); int getCount(Addr addr); - int getTotalCount(); + int getTotalCount() const override; private: - int get_block_index(Addr addr); - int get_page_index(Addr addr); + int hash(Addr addr) const; + int pageHash(Addr addr) const; - // The block filter - std::vector<int> m_filter; - int m_filter_size; - int m_filter_size_bits; - // The page number filter - std::vector<int> m_page_filter; - int m_page_filter_size; - int m_page_filter_size_bits; + // The block filter uses the filter vector declared in the base class + /** The page number filter. */ + std::vector<int> pageFilter; + int pageFilterSizeBits; }; #endif // __MEM_RUBY_FILTERS_MULTIGRAINBLOOMFILTER_HH__ diff --git a/src/mem/ruby/filters/NonCountingBloomFilter.cc b/src/mem/ruby/filters/NonCountingBloomFilter.cc index 50432d7a8..46e74d244 100644 --- a/src/mem/ruby/filters/NonCountingBloomFilter.cc +++ b/src/mem/ruby/filters/NonCountingBloomFilter.cc @@ -28,19 +28,12 @@ #include "mem/ruby/filters/NonCountingBloomFilter.hh" -#include "base/intmath.hh" -#include "base/str.hh" +#include "mem/ruby/common/Address.hh" #include "mem/ruby/system/RubySystem.hh" -NonCountingBloomFilter::NonCountingBloomFilter(int head, int tail) +NonCountingBloomFilter::NonCountingBloomFilter(std::size_t size, int skip_bits) + : AbstractBloomFilter(size), skipBits(skip_bits) { - // head contains filter size, tail contains bit offset from block number - m_filter_size = head; - m_offset = tail; - m_filter_size_bits = floorLog2(m_filter_size); - - m_filter.resize(m_filter_size); - clear(); } NonCountingBloomFilter::~NonCountingBloomFilter() @@ -48,68 +41,46 @@ NonCountingBloomFilter::~NonCountingBloomFilter() } void -NonCountingBloomFilter::clear() -{ - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } -} - -void -NonCountingBloomFilter::merge(AbstractBloomFilter *other_filter) +NonCountingBloomFilter::merge(const AbstractBloomFilter *other) { - // assumes both filters are the same size! - NonCountingBloomFilter * temp = (NonCountingBloomFilter*) other_filter; - for (int i = 0; i < m_filter_size; ++i){ - m_filter[i] |= (*temp)[i]; + auto* cast_other = static_cast<const NonCountingBloomFilter*>(other); + assert(filter.size() == cast_other->filter.size()); + for (int i = 0; i < filter.size(); ++i){ + filter[i] |= cast_other->filter[i]; } } void NonCountingBloomFilter::set(Addr addr) { - int i = get_index(addr); - m_filter[i] = 1; + filter[hash(addr)] = 1; } void NonCountingBloomFilter::unset(Addr addr) { - int i = get_index(addr); - m_filter[i] = 0; + filter[hash(addr)] = 0; } bool NonCountingBloomFilter::isSet(Addr addr) { - int i = get_index(addr); - return (m_filter[i]); + return filter[hash(addr)]; } int NonCountingBloomFilter::getCount(Addr addr) { - return m_filter[get_index(addr)]; -} - -int -NonCountingBloomFilter::getTotalCount() -{ - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - count += m_filter[i]; - } - return count; + return filter[hash(addr)]; } int -NonCountingBloomFilter::get_index(Addr addr) +NonCountingBloomFilter::hash(Addr addr) const { - return bitSelect(addr, RubySystem::getBlockSizeBits() + m_offset, - RubySystem::getBlockSizeBits() + m_offset + - m_filter_size_bits - 1); + return bitSelect(addr, RubySystem::getBlockSizeBits() + skipBits, + RubySystem::getBlockSizeBits() + skipBits + + sizeBits - 1); } diff --git a/src/mem/ruby/filters/NonCountingBloomFilter.hh b/src/mem/ruby/filters/NonCountingBloomFilter.hh index 08610606e..08c84ee7c 100644 --- a/src/mem/ruby/filters/NonCountingBloomFilter.hh +++ b/src/mem/ruby/filters/NonCountingBloomFilter.hh @@ -29,39 +29,29 @@ #ifndef __MEM_RUBY_FILTERS_NONCOUNTINGBLOOMFILTER_HH__ #define __MEM_RUBY_FILTERS_NONCOUNTINGBLOOMFILTER_HH__ -#include <vector> - -#include "mem/ruby/common/Address.hh" #include "mem/ruby/filters/AbstractBloomFilter.hh" class NonCountingBloomFilter : public AbstractBloomFilter { public: - NonCountingBloomFilter(int head, int tail); + NonCountingBloomFilter(std::size_t filter_size, int skip_bits); ~NonCountingBloomFilter(); - void clear(); - void merge(AbstractBloomFilter * other_filter); - void set(Addr addr); + void merge(const AbstractBloomFilter* other) override; + void set(Addr addr) override; void unset(Addr addr) override; bool isSet(Addr addr); int getCount(Addr addr); - int getTotalCount(); - - int - operator[](const int index) const - { - return this->m_filter[index]; - } private: - int get_index(Addr addr); + int hash(Addr addr) const; - std::vector<int> m_filter; - int m_filter_size; - int m_offset; - int m_filter_size_bits; + /** + * Bit offset from block number. Used to simulate bit selection hashing + * on larger than cache-line granularities, by skipping some bits. + */ + int skipBits; }; #endif // __MEM_RUBY_FILTERS_NONCOUNTINGBLOOMFILTER_HH__ |