mem-ruby: Make MultiGrainBloomFilter generic
Allow combining any number of Bloom Filters in the MultiGrain.
Change-Id: I73ae33063e1feed731af6f625d2f64245f21df18
Signed-off-by: Daniel R. Carvalho <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/18869
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 89a4b9b..de5cd7d 100644
--- a/src/mem/ruby/filters/BloomFilters.py
+++ b/src/mem/ruby/filters/BloomFilters.py
@@ -93,10 +93,18 @@
cxx_class = 'MultiGrainBloomFilter'
cxx_header = "mem/ruby/filters/MultiGrainBloomFilter.hh"
- # This is the maximum value achievable of the sum of the hashed respective
- # entry of the two filters
+ # The base filter should not be used, since this filter is the combination
+ # of multiple sub-filters
+ size = 0
+
+ # By default there are two sub-filters that hash sequential bitfields
+ filters = VectorParam.AbstractBloomFilter([
+ BlockBloomFilter(size = 4096, masks_lsbs = [6, 12]),
+ BlockBloomFilter(size = 1024, masks_lsbs = [18, 24])],
+ "Sub-filters to be combined")
+
+ # By default match this with the number of sub-filters
threshold = 2
- page_filter_size = Param.Int(1024, "Number of entries in the page filter")
class NonCountingBloomFilter(AbstractBloomFilter):
type = 'NonCountingBloomFilter'
diff --git a/src/mem/ruby/filters/MultiGrainBloomFilter.cc b/src/mem/ruby/filters/MultiGrainBloomFilter.cc
index 150e0a5..86e7d9b 100644
--- a/src/mem/ruby/filters/MultiGrainBloomFilter.cc
+++ b/src/mem/ruby/filters/MultiGrainBloomFilter.cc
@@ -28,13 +28,12 @@
#include "mem/ruby/filters/MultiGrainBloomFilter.hh"
-#include "base/bitfield.hh"
+#include "base/logging.hh"
#include "params/MultiGrainBloomFilter.hh"
MultiGrainBloomFilter::MultiGrainBloomFilter(
const MultiGrainBloomFilterParams* p)
- : AbstractBloomFilter(p), pageFilter(p->page_filter_size),
- pageFilterSizeBits(floorLog2(p->page_filter_size))
+ : AbstractBloomFilter(p), filters(p->filters)
{
}
@@ -45,62 +44,69 @@
void
MultiGrainBloomFilter::clear()
{
- AbstractBloomFilter::clear();
- for (auto& entry : pageFilter){
- entry = 0;
+ for (auto& sub_filter : filters) {
+ sub_filter->clear();
+ }
+}
+
+void
+MultiGrainBloomFilter::merge(const AbstractBloomFilter* other)
+{
+ auto* cast_other = static_cast<const MultiGrainBloomFilter*>(other);
+ assert(filters.size() == cast_other->filters.size());
+ for (int i = 0; i < filters.size(); ++i){
+ filters[i]->merge(cast_other->filters[i]);
}
}
void
MultiGrainBloomFilter::set(Addr addr)
{
- const int index = hash(addr);
- assert(index < filter.size());
- filter[index] = 1;
+ for (auto& sub_filter : filters) {
+ sub_filter->set(addr);
+ }
+}
- const int page_index = pageHash(addr);
- assert(page_index < pageFilter.size());
- pageFilter[page_index] = 1;
+void
+MultiGrainBloomFilter::unset(Addr addr)
+{
+ for (auto& sub_filter : filters) {
+ sub_filter->unset(addr);
+ }
+}
+
+bool
+MultiGrainBloomFilter::isSet(Addr addr) const
+{
+ int count = 0;
+ for (const auto& sub_filter : filters) {
+ if (sub_filter->isSet(addr)) {
+ count++;
+ }
+ }
+ return count >= setThreshold;
}
int
MultiGrainBloomFilter::getCount(Addr addr) const
{
- const int index = hash(addr);
- const int page_index = pageHash(addr);
- assert(index < filter.size());
- assert(page_index < pageFilter.size());
- return filter[index] + pageFilter[page_index];
+ int count = 0;
+ for (const auto& sub_filter : filters) {
+ count += sub_filter->getCount(addr);
+ }
+ return count;
}
int
MultiGrainBloomFilter::getTotalCount() const
{
- int count = AbstractBloomFilter::getTotalCount();
-
- for (const auto& entry : pageFilter) {
- count += entry;
+ int count = 0;
+ for (const auto& sub_filter : filters) {
+ count += sub_filter->getTotalCount();
}
-
return count;
}
-int
-MultiGrainBloomFilter::hash(Addr addr) const
-{
- // grap a chunk of bits after byte offset
- return bits(addr, offsetBits + sizeBits - 1, offsetBits);
-}
-
-int
-MultiGrainBloomFilter::pageHash(Addr addr) const
-{
- int num_bits = offsetBits + sizeBits - 1;
-
- // grap a chunk of bits after first chunk
- return bits(addr, num_bits + pageFilterSizeBits - 1, num_bits);
-}
-
MultiGrainBloomFilter*
MultiGrainBloomFilterParams::create()
{
diff --git a/src/mem/ruby/filters/MultiGrainBloomFilter.hh b/src/mem/ruby/filters/MultiGrainBloomFilter.hh
index e895788..fffda36 100644
--- a/src/mem/ruby/filters/MultiGrainBloomFilter.hh
+++ b/src/mem/ruby/filters/MultiGrainBloomFilter.hh
@@ -35,6 +35,11 @@
struct MultiGrainBloomFilterParams;
+/**
+ * This BloomFilter has multiple sub-filters, each with its own hashing
+ * functionality. The results of the operations are the results of applying
+ * them to each sub-filter.
+ */
class MultiGrainBloomFilter : public AbstractBloomFilter
{
public:
@@ -43,18 +48,16 @@
void clear() override;
void set(Addr addr) override;
+ void unset(Addr addr) override;
+ void merge(const AbstractBloomFilter* other) override;
+ bool isSet(Addr addr) const override;
int getCount(Addr addr) const override;
int getTotalCount() const override;
private:
- int hash(Addr addr) const;
- int pageHash(Addr addr) const;
-
- // The block filter uses the filter vector declared in the base class
- /** The page number filter. */
- std::vector<int> pageFilter;
- int pageFilterSizeBits;
+ /** Sub-filters used by this filter. */
+ std::vector<AbstractBloomFilter*> filters;
};
#endif // __MEM_RUBY_FILTERS_MULTIGRAINBLOOMFILTER_HH__
