Daniel Carvalho has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/18873
Change subject: mem-ruby: Make H3 inherit from MultiBitSelBloomFilter
......................................................................
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 <[email protected]>
---
M src/mem/ruby/filters/BloomFilters.py
M src/mem/ruby/filters/H3BloomFilter.cc
M src/mem/ruby/filters/H3BloomFilter.hh
M src/mem/ruby/filters/MultiBitSelBloomFilter.cc
M src/mem/ruby/filters/MultiBitSelBloomFilter.hh
5 files changed, 62 insertions(+), 120 deletions(-)
diff --git a/src/mem/ruby/filters/BloomFilters.py
b/src/mem/ruby/filters/BloomFilters.py
index f8c9155..1dfcf4c 100644
--- a/src/mem/ruby/filters/BloomFilters.py
+++ b/src/mem/ruby/filters/BloomFilters.py
@@ -62,15 +62,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'
@@ -87,19 +78,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
# These should be set together. By default there are two sub-filters
that
# hash sequential bitfields
diff --git a/src/mem/ruby/filters/H3BloomFilter.cc
b/src/mem/ruby/filters/H3BloomFilter.cc
index 68a377a..dc54992 100644
--- a/src/mem/ruby/filters/H3BloomFilter.cc
+++ b/src/mem/ruby/filters/H3BloomFilter.cc
@@ -355,59 +355,32 @@
};
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, 63, blkBits);
- 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, 63, blkBits);
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 53e7752..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,45 +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;
-
- static constexpr int primesList[6] =
- {9323, 11279, 10247, 30637, 25717, 43711};
- static constexpr int multsList[6] = {255, 29, 51, 3, 77, 43};
- static constexpr int addsList[6] = {841, 627, 1555, 241, 7777, 65931};
+ 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 e777945..b822548 100644
--- a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
+++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
@@ -34,10 +34,13 @@
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()
@@ -66,30 +69,23 @@
int
MultiBitSelBloomFilter::hash(Addr addr, int hash_number) const
{
- uint64_t x = bits(addr, 63, blkBits) >> 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;
+ uint64_t value = bits(addr, sizeof(Addr) * 8 - 1, blkBits) >> skipBits;
+ const int max_bits = sizeof(Addr) * 8 - blkBits;
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__
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/18873
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-Change-Id: I0984067b710a208715f5f2727b8c4312feb6529b
Gerrit-Change-Number: 18873
Gerrit-PatchSet: 1
Gerrit-Owner: Daniel Carvalho <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
