mem-ruby: Generalize use of bloom filters' isSet
In general the corresponding entries of an address are considered
to be set when the sum of all of them reach their maximum value
(i.e., they are all set), so generalize that into the base class.
Change-Id: If50b8c56065ad339b4ff2322ddc3c077a3bfc518
Signed-off-by: Daniel R. Carvalho <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/18735
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
Tested-by: kokoro <noreply+kokoro@google.com>
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
diff --git a/src/mem/ruby/filters/AbstractBloomFilter.hh b/src/mem/ruby/filters/AbstractBloomFilter.hh
index 851e5d9..6722365 100644
--- a/src/mem/ruby/filters/AbstractBloomFilter.hh
+++ b/src/mem/ruby/filters/AbstractBloomFilter.hh
@@ -46,12 +46,18 @@
/** Number of bits needed to represent the size of the filter. */
const int sizeBits;
+ /** Threshold at which a filter entry starts being considered as set. */
+ const int setThreshold;
+
public:
/**
* Create and clear the filter.
+ *
+ * @param size The number of filter entries.
+ * @param threshold The threshold that limits a set entry.
*/
- AbstractBloomFilter(std::size_t size)
- : filter(size), sizeBits(floorLog2(size))
+ AbstractBloomFilter(std::size_t size, int threshold)
+ : filter(size), sizeBits(floorLog2(size)), setThreshold(threshold)
{
clear();
}
@@ -94,7 +100,11 @@
* @param addr The address being parsed.
* @return Whether the respective filter entry is set.
*/
- virtual bool isSet(Addr addr) = 0;
+ virtual bool
+ isSet(Addr addr) const
+ {
+ return getCount(addr) >= setThreshold;
+ }
/**
* Get the value stored in the corresponding filter entry of an address.
@@ -102,7 +112,7 @@
* @param addr The address being parsed.
* @param Get the value stored in the respective filter entry.
*/
- virtual int getCount(Addr addr) { return 0; }
+ virtual int getCount(Addr addr) const { return 0; }
/**
* Get the total value stored in the filter entries.
diff --git a/src/mem/ruby/filters/BlockBloomFilter.cc b/src/mem/ruby/filters/BlockBloomFilter.cc
index f9942fe..f59a175 100644
--- a/src/mem/ruby/filters/BlockBloomFilter.cc
+++ b/src/mem/ruby/filters/BlockBloomFilter.cc
@@ -32,7 +32,7 @@
#include "mem/ruby/system/RubySystem.hh"
BlockBloomFilter::BlockBloomFilter(int size)
- : AbstractBloomFilter(size)
+ : AbstractBloomFilter(size, 1)
{
}
@@ -52,14 +52,8 @@
filter[hash(addr)] = 0;
}
-bool
-BlockBloomFilter::isSet(Addr addr)
-{
- return filter[hash(addr)];
-}
-
int
-BlockBloomFilter::getCount(Addr addr)
+BlockBloomFilter::getCount(Addr addr) const
{
return filter[hash(addr)];
}
diff --git a/src/mem/ruby/filters/BlockBloomFilter.hh b/src/mem/ruby/filters/BlockBloomFilter.hh
index 7c8ffc1..fd75ba8 100644
--- a/src/mem/ruby/filters/BlockBloomFilter.hh
+++ b/src/mem/ruby/filters/BlockBloomFilter.hh
@@ -39,9 +39,7 @@
void set(Addr addr) override;
void unset(Addr addr) override;
-
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ int getCount(Addr addr) const override;
private:
int hash(Addr addr) const;
diff --git a/src/mem/ruby/filters/BulkBloomFilter.cc b/src/mem/ruby/filters/BulkBloomFilter.cc
index a917a14..251274b 100644
--- a/src/mem/ruby/filters/BulkBloomFilter.cc
+++ b/src/mem/ruby/filters/BulkBloomFilter.cc
@@ -32,7 +32,7 @@
#include "mem/ruby/system/RubySystem.hh"
BulkBloomFilter::BulkBloomFilter(int size)
- : AbstractBloomFilter(size), sectorBits(sizeBits - 1)
+ : AbstractBloomFilter(size, 1), sectorBits(sizeBits - 1)
{
}
@@ -61,7 +61,7 @@
}
bool
-BulkBloomFilter::isSet(Addr addr)
+BulkBloomFilter::isSet(Addr addr) const
{
// c0 contains the cache index bits
const int filter_size = filter.size();
@@ -119,9 +119,9 @@
}
int
-BulkBloomFilter::getCount(Addr addr)
+BulkBloomFilter::getCount(Addr addr) const
{
- // not used
+ // TODO as in the multi-hashed filters
return 0;
}
diff --git a/src/mem/ruby/filters/BulkBloomFilter.hh b/src/mem/ruby/filters/BulkBloomFilter.hh
index b6f52b9..7be00e6 100644
--- a/src/mem/ruby/filters/BulkBloomFilter.hh
+++ b/src/mem/ruby/filters/BulkBloomFilter.hh
@@ -45,8 +45,8 @@
void set(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ bool isSet(Addr addr) const override;
+ int getCount(Addr addr) const override;
private:
/** Permutes the address to generate its signature. */
diff --git a/src/mem/ruby/filters/H3BloomFilter.cc b/src/mem/ruby/filters/H3BloomFilter.cc
index f6ee8a1..485cc31 100644
--- a/src/mem/ruby/filters/H3BloomFilter.cc
+++ b/src/mem/ruby/filters/H3BloomFilter.cc
@@ -354,8 +354,8 @@
};
H3BloomFilter::H3BloomFilter(int size, int num_hashes, bool parallel)
- : AbstractBloomFilter(size), numHashes(num_hashes), isParallel(parallel),
- parFilterSize(filter.size() / numHashes)
+ : AbstractBloomFilter(size, num_hashes), numHashes(num_hashes),
+ isParallel(parallel), parFilterSize(filter.size() / numHashes)
{
fatal_if(numHashes > 16, "There are only 16 hash functions implemented.");
}
@@ -382,22 +382,14 @@
}
}
-bool
-H3BloomFilter::isSet(Addr addr)
-{
- bool res = true;
-
- for (int i = 0; i < numHashes; i++) {
- int idx = hash(addr, i);
- res = res && filter[idx];
- }
- return res;
-}
-
int
-H3BloomFilter::getCount(Addr addr)
+H3BloomFilter::getCount(Addr addr) const
{
- return isSet(addr)? 1: 0;
+ int count = 0;
+ for (int i=0; i < numHashes; i++) {
+ count += filter[hash(addr, i)];
+ }
+ return count;
}
int
diff --git a/src/mem/ruby/filters/H3BloomFilter.hh b/src/mem/ruby/filters/H3BloomFilter.hh
index 6cfa293..f92878b 100644
--- a/src/mem/ruby/filters/H3BloomFilter.hh
+++ b/src/mem/ruby/filters/H3BloomFilter.hh
@@ -43,8 +43,7 @@
void merge(const AbstractBloomFilter* other) override;
void set(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr) override;
+ int getCount(Addr addr) const override;
private:
/**
diff --git a/src/mem/ruby/filters/LSB_CountingBloomFilter.cc b/src/mem/ruby/filters/LSB_CountingBloomFilter.cc
index 06e2d4f..a718b43 100644
--- a/src/mem/ruby/filters/LSB_CountingBloomFilter.cc
+++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.cc
@@ -33,7 +33,9 @@
LSB_CountingBloomFilter::LSB_CountingBloomFilter(std::size_t filter_size,
int max_value)
- : AbstractBloomFilter(filter_size), maxValue(max_value)
+ // Here we assume that isSet will return true only when the counter
+ // saturates
+ : AbstractBloomFilter(filter_size, max_value), maxValue(max_value)
{
}
@@ -57,15 +59,8 @@
filter[i] -= 1;
}
-bool
-LSB_CountingBloomFilter::isSet(Addr addr)
-{
- // TODO
- return false;
-}
-
int
-LSB_CountingBloomFilter::getCount(Addr addr)
+LSB_CountingBloomFilter::getCount(Addr addr) const
{
return filter[hash(addr)];
}
diff --git a/src/mem/ruby/filters/LSB_CountingBloomFilter.hh b/src/mem/ruby/filters/LSB_CountingBloomFilter.hh
index 4fc6355..e9ffbcb 100644
--- a/src/mem/ruby/filters/LSB_CountingBloomFilter.hh
+++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.hh
@@ -40,8 +40,7 @@
void set(Addr addr) override;
void unset(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ int getCount(Addr addr) const override;
private:
int hash(Addr addr) const;
diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
index aa1438f..c453d10 100644
--- a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
+++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
@@ -32,7 +32,7 @@
MultiBitSelBloomFilter::MultiBitSelBloomFilter(std::size_t filter_size,
int num_hashes, int skip_bits, bool is_parallel)
- : AbstractBloomFilter(filter_size), numHashes(num_hashes),
+ : AbstractBloomFilter(filter_size, num_hashes), numHashes(num_hashes),
skipBits(skip_bits),
parFilterSize(filter_size / numHashes),
isParallel(is_parallel)
@@ -62,22 +62,14 @@
}
}
-bool
-MultiBitSelBloomFilter::isSet(Addr addr)
-{
- bool res = true;
-
- for (int i=0; i < numHashes; i++) {
- int idx = hash(addr, i);
- res = res && filter[idx];
- }
- return res;
-}
-
int
-MultiBitSelBloomFilter::getCount(Addr addr)
+MultiBitSelBloomFilter::getCount(Addr addr) const
{
- return isSet(addr)? 1: 0;
+ int count = 0;
+ for (int i=0; i < numHashes; i++) {
+ count += filter[hash(addr, i)];
+ }
+ return count;
}
int
diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh
index 2d69540..914875f 100644
--- a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh
+++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh
@@ -40,8 +40,7 @@
void merge(const AbstractBloomFilter* other) override;
void set(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ int getCount(Addr addr) const override;
private:
int hash(Addr addr, int hash_number) const;
diff --git a/src/mem/ruby/filters/MultiGrainBloomFilter.cc b/src/mem/ruby/filters/MultiGrainBloomFilter.cc
index 76016b2..7bf9dfe 100644
--- a/src/mem/ruby/filters/MultiGrainBloomFilter.cc
+++ b/src/mem/ruby/filters/MultiGrainBloomFilter.cc
@@ -32,7 +32,7 @@
#include "mem/ruby/system/RubySystem.hh"
MultiGrainBloomFilter::MultiGrainBloomFilter(int head, int tail)
- : AbstractBloomFilter(head),
+ : AbstractBloomFilter(head, 2),
pageFilter(tail), pageFilterSizeBits(floorLog2(tail))
{
}
@@ -61,21 +61,13 @@
}
-bool
-MultiGrainBloomFilter::isSet(Addr addr)
+int
+MultiGrainBloomFilter::getCount(Addr addr) const
{
int i = hash(addr);
assert(i < filter.size());
assert(pageHash(addr) < pageFilter.size());
- // we have to have both indices set
- return (filter[i] && pageFilter[i]);
-}
-
-int
-MultiGrainBloomFilter::getCount(Addr addr)
-{
- // not used
- return 0;
+ return filter[i] + pageFilter[i];
}
int
diff --git a/src/mem/ruby/filters/MultiGrainBloomFilter.hh b/src/mem/ruby/filters/MultiGrainBloomFilter.hh
index 148f42d..d45b587 100644
--- a/src/mem/ruby/filters/MultiGrainBloomFilter.hh
+++ b/src/mem/ruby/filters/MultiGrainBloomFilter.hh
@@ -46,8 +46,7 @@
void clear() override;
void set(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ int getCount(Addr addr) const override;
int getTotalCount() const override;
private:
diff --git a/src/mem/ruby/filters/NonCountingBloomFilter.cc b/src/mem/ruby/filters/NonCountingBloomFilter.cc
index 46e74d2..3196eb6 100644
--- a/src/mem/ruby/filters/NonCountingBloomFilter.cc
+++ b/src/mem/ruby/filters/NonCountingBloomFilter.cc
@@ -32,7 +32,7 @@
#include "mem/ruby/system/RubySystem.hh"
NonCountingBloomFilter::NonCountingBloomFilter(std::size_t size, int skip_bits)
- : AbstractBloomFilter(size), skipBits(skip_bits)
+ : AbstractBloomFilter(size, 1), skipBits(skip_bits)
{
}
@@ -62,15 +62,8 @@
filter[hash(addr)] = 0;
}
-bool
-NonCountingBloomFilter::isSet(Addr addr)
-{
- return filter[hash(addr)];
-}
-
-
int
-NonCountingBloomFilter::getCount(Addr addr)
+NonCountingBloomFilter::getCount(Addr addr) const
{
return filter[hash(addr)];
}
diff --git a/src/mem/ruby/filters/NonCountingBloomFilter.hh b/src/mem/ruby/filters/NonCountingBloomFilter.hh
index 08c84ee..1553bec 100644
--- a/src/mem/ruby/filters/NonCountingBloomFilter.hh
+++ b/src/mem/ruby/filters/NonCountingBloomFilter.hh
@@ -41,8 +41,7 @@
void set(Addr addr) override;
void unset(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ int getCount(Addr addr) const override;
private:
int hash(Addr addr) const;
