From d4df04c4933142b66cf3020b37827b10c9c2045f Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Sat, 11 May 2019 18:10:04 +0200 Subject: [PATCH] mem-ruby: Make H3 inherit from MultiBitSelBloomFilter Make MultiBitSelBloomFilter a generic BloomFilter that maps multiple entries to an address, and therefore uses multiple hash functions. This allows the common functionality of both filters to be merged into one, since they only differ in the hash functions being used. Change-Id: I0984067b710a208715f5f2727b8c4312feb6529b Signed-off-by: Daniel R. Carvalho Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/18873 Reviewed-by: Nikos Nikoleris Maintainer: Nikos Nikoleris Tested-by: kokoro --- src/mem/ruby/filters/BloomFilters.py | 20 +++---- src/mem/ruby/filters/H3BloomFilter.cc | 52 +++++-------------- src/mem/ruby/filters/H3BloomFilter.hh | 34 ++---------- .../ruby/filters/MultiBitSelBloomFilter.cc | 41 +++++++-------- .../ruby/filters/MultiBitSelBloomFilter.hh | 30 +++++++---- 5 files changed, 63 insertions(+), 114 deletions(-) diff --git a/src/mem/ruby/filters/BloomFilters.py b/src/mem/ruby/filters/BloomFilters.py index 4103332e3..bed79cddd 100644 --- a/src/mem/ruby/filters/BloomFilters.py +++ b/src/mem/ruby/filters/BloomFilters.py @@ -58,15 +58,6 @@ class BulkBloomFilter(AbstractBloomFilter): cxx_class = 'BulkBloomFilter' cxx_header = "mem/ruby/filters/BulkBloomFilter.hh" -class H3BloomFilter(AbstractBloomFilter): - type = 'H3BloomFilter' - cxx_class = 'H3BloomFilter' - cxx_header = "mem/ruby/filters/H3BloomFilter.hh" - - num_hashes = Param.Int(3, "Number of hashes") - threshold = Self.num_hashes - is_parallel = Param.Bool(False, "Whether hashing is done in parallel") - class LSB_CountingBloomFilter(AbstractBloomFilter): type = 'LSB_CountingBloomFilter' cxx_class = 'LSB_CountingBloomFilter' @@ -83,19 +74,24 @@ class MultiBitSelBloomFilter(AbstractBloomFilter): cxx_class = 'MultiBitSelBloomFilter' cxx_header = "mem/ruby/filters/MultiBitSelBloomFilter.hh" - num_hashes = Param.Int(3, "Number of hashes") + num_hashes = Param.Int(4, "Number of hashes") threshold = Self.num_hashes skip_bits = Param.Int(2, "Offset from block number") is_parallel = Param.Bool(False, "Whether hashing is done in parallel") +class H3BloomFilter(MultiBitSelBloomFilter): + type = 'H3BloomFilter' + cxx_class = 'H3BloomFilter' + cxx_header = "mem/ruby/filters/H3BloomFilter.hh" + class MultiGrainBloomFilter(AbstractBloomFilter): type = 'MultiGrainBloomFilter' cxx_class = 'MultiGrainBloomFilter' cxx_header = "mem/ruby/filters/MultiGrainBloomFilter.hh" # The base filter should not be used, since this filter is the combination - # of multiple sub-filters - size = 0 + # of multiple sub-filters, so we use a dummy value + size = 1 # By default there are two sub-filters that hash sequential bitfields filters = VectorParam.AbstractBloomFilter([ diff --git a/src/mem/ruby/filters/H3BloomFilter.cc b/src/mem/ruby/filters/H3BloomFilter.cc index 37af607e9..92e309d0f 100644 --- a/src/mem/ruby/filters/H3BloomFilter.cc +++ b/src/mem/ruby/filters/H3BloomFilter.cc @@ -357,59 +357,33 @@ static int H3[64][16] = { }; H3BloomFilter::H3BloomFilter(const H3BloomFilterParams* p) - : AbstractBloomFilter(p), numHashes(p->num_hashes), - isParallel(p->is_parallel), parFilterSize(p->size / numHashes) + : MultiBitSelBloomFilter(p) { - fatal_if(numHashes > 16, "There are only 16 hash functions implemented."); + fatal_if(numHashes > 16, "There are only 16 H3 functions implemented."); } H3BloomFilter::~H3BloomFilter() { } -void -H3BloomFilter::set(Addr addr) -{ - for (int i = 0; i < numHashes; i++) { - filter[hash(addr, i)] = 1; - } -} - -int -H3BloomFilter::getCount(Addr addr) const -{ - int count = 0; - for (int i=0; i < numHashes; i++) { - count += filter[hash(addr, i)]; - } - return count; -} - int H3BloomFilter::hash(Addr addr, int hash_number) const { - uint64_t x = bits(addr, std::numeric_limits::digits - 1, offsetBits); - int y = hashH3(x, hash_number); + uint64_t val = + bits(addr, std::numeric_limits::digits - 1, offsetBits); + int result = 0; - if (isParallel) { - return (y % parFilterSize) + hash_number * parFilterSize; - } else { - return y % filter.size(); + for (int i = 0; (i < 64) && val; i++, val >>= 1) { + if (val & 1) { + result ^= H3[i][hash_number]; + } } -} -int -H3BloomFilter::hashH3(uint64_t value, int index) const -{ - uint64_t mask = 1; - uint64_t val = value; - int result = 0; - - for (int i = 0; i < 64; i++) { - if (val&mask) result ^= H3[i][index]; - val = val >> 1; + if (isParallel) { + return (result % parFilterSize) + hash_number * parFilterSize; + } else { + return result % filter.size(); } - return result; } H3BloomFilter* diff --git a/src/mem/ruby/filters/H3BloomFilter.hh b/src/mem/ruby/filters/H3BloomFilter.hh index 6a36692b0..5719d0077 100644 --- a/src/mem/ruby/filters/H3BloomFilter.hh +++ b/src/mem/ruby/filters/H3BloomFilter.hh @@ -29,7 +29,7 @@ #ifndef __MEM_RUBY_FILTERS_H3BLOOMFILTER_HH__ #define __MEM_RUBY_FILTERS_H3BLOOMFILTER_HH__ -#include "mem/ruby/filters/AbstractBloomFilter.hh" +#include "mem/ruby/filters/MultiBitSelBloomFilter.hh" struct H3BloomFilterParams; @@ -37,40 +37,14 @@ struct H3BloomFilterParams; * Implementation of the bloom filter as described in "Implementing Signatures * for Transactional Memory", by Sanchez, Daniel, et al. */ -class H3BloomFilter : public AbstractBloomFilter +class H3BloomFilter : public MultiBitSelBloomFilter { public: H3BloomFilter(const H3BloomFilterParams* p); ~H3BloomFilter(); - void set(Addr addr) override; - int getCount(Addr addr) const override; - - private: - /** - * 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; - - /** - * 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; - - /** 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; + protected: + int hash(Addr addr, int hash_number) const override; }; #endif // __MEM_RUBY_FILTERS_H3BLOOMFILTER_HH__ diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc index 65428e0b8..c61c0ddff 100644 --- a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc +++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc @@ -31,15 +31,19 @@ #include #include "base/bitfield.hh" +#include "base/logging.hh" #include "params/MultiBitSelBloomFilter.hh" MultiBitSelBloomFilter::MultiBitSelBloomFilter( const MultiBitSelBloomFilterParams* p) : AbstractBloomFilter(p), numHashes(p->num_hashes), - skipBits(p->skip_bits), parFilterSize(p->size / numHashes), - isParallel(p->is_parallel) + isParallel(p->is_parallel), skipBits(p->skip_bits) { + if (p->size % numHashes) { + fatal("Can't divide filter (%d) in %d equal portions", p->size, + numHashes); + } } MultiBitSelBloomFilter::~MultiBitSelBloomFilter() @@ -68,31 +72,24 @@ MultiBitSelBloomFilter::getCount(Addr addr) const int MultiBitSelBloomFilter::hash(Addr addr, int hash_number) const { - uint64_t x = bits(addr, std::numeric_limits::digits - 1, + uint64_t value = bits(addr, std::numeric_limits::digits - 1, offsetBits) >> skipBits; - int y = hashBitsel(x, hash_number, numHashes, 30, sizeBits); - //36-bit addresses, 6-bit cache lines - - if (isParallel) { - return (y % parFilterSize) + hash_number * parFilterSize; - } else { - return y % filter.size(); - } -} - -int -MultiBitSelBloomFilter::hashBitsel(uint64_t value, int index, int jump, - int maxBits, int numBits) const -{ - uint64_t mask = 1; + const int max_bits = std::numeric_limits::digits - offsetBits; int result = 0; int bit, i; - for (i = 0; i < numBits; i++) { - bit = (index + jump*i) % maxBits; - if (value & (mask << bit)) result += mask << i; + for (i = 0; i < sizeBits; i++) { + bit = (hash_number + numHashes * i) % max_bits; + if (value & (1 << bit)) { + result += 1 << i; + } + } + + if (isParallel) { + return (result % parFilterSize) + hash_number * parFilterSize; + } else { + return result % filter.size(); } - return result; } MultiBitSelBloomFilter* diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh index 42ba94c4e..34e38ca73 100644 --- a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh +++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh @@ -33,6 +33,10 @@ struct MultiBitSelBloomFilterParams; +/** + * The MultiBitSel Bloom Filter associates an address to multiple entries + * through the use of multiple hash functions. + */ class MultiBitSelBloomFilter : public AbstractBloomFilter { public: @@ -42,26 +46,30 @@ class MultiBitSelBloomFilter : public AbstractBloomFilter void set(Addr addr) override; int getCount(Addr addr) const override; - private: - int hash(Addr addr, int hash_number) const; - - int hashBitsel(uint64_t value, int index, int jump, int maxBits, - int numBits) const; + protected: + /** + * Apply the selected the hash functions to an address. + * + * @param addr The address to hash. + * @param hash_number Index of the hash function to be used. + */ + virtual int hash(Addr addr, int hash_number) const; /** Number of hashes. */ const int numHashes; - /** - * Bit offset from block number. Used to simulate bit selection hashing - * on larger than cache-line granularities, by skipping some bits. - */ - const int skipBits; - /** Size of the filter when doing parallel hashing. */ const int parFilterSize; /** Whether hashing should be performed in parallel. */ const bool isParallel; + + private: + /** + * Bit offset from block number. Used to simulate bit selection hashing + * on larger than cache-line granularities, by skipping some bits. + */ + const int skipBits; }; #endif // __MEM_RUBY_FILTERS_MULTIBITSELBLOOMFILTER_HH__ -- 2.30.2