From 8d482dfeb69e77b55bd6548d495e19076be89243 Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Fri, 10 May 2019 09:13:10 +0200 Subject: [PATCH] mem-ruby: Finish implementing BloomFilter merge Not all Bloom Filters had their union functionality implemented. This change adds them. Change-Id: I86af18d3c5eabd0da8280b57a88789b3af803c04 Signed-off-by: Daniel R. Carvalho Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/18872 Tested-by: kokoro Reviewed-by: Nikos Nikoleris Maintainer: Nikos Nikoleris --- src/mem/ruby/filters/AbstractBloomFilter.hh | 16 ++++++++++++++-- src/mem/ruby/filters/H3BloomFilter.cc | 10 ---------- src/mem/ruby/filters/H3BloomFilter.hh | 1 - src/mem/ruby/filters/LSB_CountingBloomFilter.cc | 14 ++++++++++++++ src/mem/ruby/filters/LSB_CountingBloomFilter.hh | 1 + src/mem/ruby/filters/MultiBitSelBloomFilter.cc | 10 ---------- src/mem/ruby/filters/MultiBitSelBloomFilter.hh | 1 - 7 files changed, 29 insertions(+), 24 deletions(-) diff --git a/src/mem/ruby/filters/AbstractBloomFilter.hh b/src/mem/ruby/filters/AbstractBloomFilter.hh index 6a62d0ab1..a9826968a 100644 --- a/src/mem/ruby/filters/AbstractBloomFilter.hh +++ b/src/mem/ruby/filters/AbstractBloomFilter.hh @@ -76,8 +76,20 @@ class AbstractBloomFilter : public SimObject } } - /** Merges the contents of both filters into this'. */ - virtual void merge(const AbstractBloomFilter* other) {} + /** + * Merges the contents of both filters into this' (Bloom Filter union). + * Both must have the same number of entries. + * + * @param other The other bloom filter to merge with. + */ + virtual void + merge(const AbstractBloomFilter* other) + { + assert(filter.size() == other->filter.size()); + for (int i = 0; i < filter.size(); ++i){ + filter[i] |= other->filter[i]; + } + } /** * Perform the filter specific function to set the corresponding diff --git a/src/mem/ruby/filters/H3BloomFilter.cc b/src/mem/ruby/filters/H3BloomFilter.cc index 4e4f95d52..37af607e9 100644 --- a/src/mem/ruby/filters/H3BloomFilter.cc +++ b/src/mem/ruby/filters/H3BloomFilter.cc @@ -367,16 +367,6 @@ H3BloomFilter::~H3BloomFilter() { } -void -H3BloomFilter::merge(const AbstractBloomFilter *other) -{ - auto* cast_other = static_cast(other); - assert(filter.size() == cast_other->filter.size()); - for (int i = 0; i < filter.size(); ++i){ - filter[i] |= cast_other->filter[i]; - } -} - void H3BloomFilter::set(Addr addr) { diff --git a/src/mem/ruby/filters/H3BloomFilter.hh b/src/mem/ruby/filters/H3BloomFilter.hh index 62a8ec1a1..6a36692b0 100644 --- a/src/mem/ruby/filters/H3BloomFilter.hh +++ b/src/mem/ruby/filters/H3BloomFilter.hh @@ -43,7 +43,6 @@ class H3BloomFilter : public AbstractBloomFilter H3BloomFilter(const H3BloomFilterParams* p); ~H3BloomFilter(); - void merge(const AbstractBloomFilter* other) override; void set(Addr addr) override; int getCount(Addr addr) const override; diff --git a/src/mem/ruby/filters/LSB_CountingBloomFilter.cc b/src/mem/ruby/filters/LSB_CountingBloomFilter.cc index b999a2cb0..d45850d99 100644 --- a/src/mem/ruby/filters/LSB_CountingBloomFilter.cc +++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.cc @@ -41,6 +41,20 @@ LSB_CountingBloomFilter::~LSB_CountingBloomFilter() { } +void +LSB_CountingBloomFilter::merge(const AbstractBloomFilter* other) +{ + auto* cast_other = static_cast(other); + assert(filter.size() == cast_other->filter.size()); + for (int i = 0; i < filter.size(); ++i){ + if (filter[i] < maxValue - cast_other->filter[i]) { + filter[i] += cast_other->filter[i]; + } else { + filter[i] = maxValue; + } + } +} + void LSB_CountingBloomFilter::set(Addr addr) { diff --git a/src/mem/ruby/filters/LSB_CountingBloomFilter.hh b/src/mem/ruby/filters/LSB_CountingBloomFilter.hh index 4bc0441da..410f22d22 100644 --- a/src/mem/ruby/filters/LSB_CountingBloomFilter.hh +++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.hh @@ -39,6 +39,7 @@ class LSB_CountingBloomFilter : public AbstractBloomFilter LSB_CountingBloomFilter(const LSB_CountingBloomFilterParams* p); ~LSB_CountingBloomFilter(); + void merge(const AbstractBloomFilter* other) override; void set(Addr addr) override; void unset(Addr addr) override; diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc index 007de8e8b..65428e0b8 100644 --- a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc +++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc @@ -46,16 +46,6 @@ MultiBitSelBloomFilter::~MultiBitSelBloomFilter() { } -void -MultiBitSelBloomFilter::merge(const AbstractBloomFilter *other) -{ - auto cast_other = static_cast(other); - assert(filter.size() == cast_other->filter.size()); - for (int i = 0; i < filter.size(); ++i){ - filter[i] |= cast_other->filter[i]; - } -} - void MultiBitSelBloomFilter::set(Addr addr) { diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh index 501483dac..42ba94c4e 100644 --- a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh +++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh @@ -39,7 +39,6 @@ class MultiBitSelBloomFilter : public AbstractBloomFilter MultiBitSelBloomFilter(const MultiBitSelBloomFilterParams* p); ~MultiBitSelBloomFilter(); - void merge(const AbstractBloomFilter* other) override; void set(Addr addr) override; int getCount(Addr addr) const override; -- 2.30.2