diff options
| -rw-r--r-- | src/mem/ruby/filters/BloomFilters.py | 20 | ||||
| -rw-r--r-- | src/mem/ruby/filters/H3BloomFilter.cc | 52 | ||||
| -rw-r--r-- | src/mem/ruby/filters/H3BloomFilter.hh | 34 | ||||
| -rw-r--r-- | src/mem/ruby/filters/MultiBitSelBloomFilter.cc | 41 | ||||
| -rw-r--r-- | src/mem/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<Addr>::digits - 1, offsetBits); - int y = hashH3(x, hash_number); + uint64_t val = + bits(addr, std::numeric_limits<Addr>::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 <limits> #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<Addr>::digits - 1, + uint64_t value = bits(addr, std::numeric_limits<Addr>::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<Addr>::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__ |