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 <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/18873
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
Tested-by: kokoro <noreply+kokoro@google.com>
diff --git a/src/mem/ruby/filters/BloomFilters.py b/src/mem/ruby/filters/BloomFilters.py
index 4103332..bed79cd 100644
--- a/src/mem/ruby/filters/BloomFilters.py
+++ b/src/mem/ruby/filters/BloomFilters.py
@@ -58,15 +58,6 @@
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 @@
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 37af607..92e309d 100644
--- a/src/mem/ruby/filters/H3BloomFilter.cc
+++ b/src/mem/ruby/filters/H3BloomFilter.cc
@@ -357,59 +357,33 @@
};
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);
-
- if (isParallel) {
- return (y % parFilterSize) + hash_number * parFilterSize;
- } else {
- return y % filter.size();
- }
-}
-
-int
-H3BloomFilter::hashH3(uint64_t value, int index) const
-{
- uint64_t mask = 1;
- uint64_t val = value;
+ uint64_t val =
+ bits(addr, std::numeric_limits<Addr>::digits - 1, offsetBits);
int result = 0;
- for (int i = 0; i < 64; i++) {
- if (val&mask) result ^= H3[i][index];
- val = val >> 1;
+ for (int i = 0; (i < 64) && val; i++, val >>= 1) {
+ if (val & 1) {
+ result ^= H3[i][hash_number];
+ }
}
- return result;
+
+ if (isParallel) {
+ return (result % parFilterSize) + hash_number * parFilterSize;
+ } else {
+ return result % filter.size();
+ }
}
H3BloomFilter*
diff --git a/src/mem/ruby/filters/H3BloomFilter.hh b/src/mem/ruby/filters/H3BloomFilter.hh
index 6a36692..5719d00 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 @@
* 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 65428e0..c61c0dd 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 @@
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;
+ }
}
- return result;
+
+ if (isParallel) {
+ return (result % parFilterSize) + hash_number * parFilterSize;
+ } else {
+ return result % filter.size();
+ }
}
MultiBitSelBloomFilter*
diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh
index 42ba94c..34e38ca 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 @@
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__
