From 65abb0c468b704eb5159e94ffd6a3264b147a49a Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Sun, 5 May 2019 17:22:56 +0200 Subject: [PATCH] mem-ruby: Cleanup filters Renamed member variables to comply with general naming conventional outside of the ruby folder so that the filters can be moved out. Moved code to base to reduce code duplication. Renamed the private get_index functions to hash, to make their functionality explicit. Change-Id: Ic6519cfc5e09ea95bc502a29b27f750f04eda754 Signed-off-by: Daniel R. Carvalho Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/18734 Maintainer: Nikos Nikoleris Tested-by: kokoro Reviewed-by: Nikos Nikoleris --- src/mem/ruby/filters/AbstractBloomFilter.hh | 76 ++++++++++++- src/mem/ruby/filters/BlockBloomFilter.cc | 53 ++------- src/mem/ruby/filters/BlockBloomFilter.hh | 14 +-- src/mem/ruby/filters/BulkBloomFilter.cc | 106 +++++------------- src/mem/ruby/filters/BulkBloomFilter.hh | 24 ++-- src/mem/ruby/filters/H3BloomFilter.cc | 92 ++++----------- src/mem/ruby/filters/H3BloomFilter.hh | 57 +++++----- .../ruby/filters/LSB_CountingBloomFilter.cc | 57 +++------- .../ruby/filters/LSB_CountingBloomFilter.hh | 20 +--- .../ruby/filters/MultiBitSelBloomFilter.cc | 71 ++++-------- .../ruby/filters/MultiBitSelBloomFilter.hh | 44 +++----- src/mem/ruby/filters/MultiGrainBloomFilter.cc | 69 ++++-------- src/mem/ruby/filters/MultiGrainBloomFilter.hh | 28 +++-- .../ruby/filters/NonCountingBloomFilter.cc | 61 +++------- .../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 + +#include "base/intmath.hh" +#include "base/types.hh" class AbstractBloomFilter { + protected: + /** The filter itself. */ + std::vector 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,79 +28,44 @@ #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() { } -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 - -#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 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,119 +28,93 @@ #include "mem/ruby/filters/BulkBloomFilter.hh" -#include - -#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() { } -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 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 -#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 m_filter; - std::vector 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(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 - -#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 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,53 +28,33 @@ #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() { } -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 - -#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 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 - -#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(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 - -#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 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 -#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 m_filter; - int m_filter_size; - int m_filter_size_bits; - // The page number filter - std::vector 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 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(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 - -#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 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__ -- 2.30.2