From cbf8f7019c0d029c8d7c48c853a57816dc66220d Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Fri, 10 May 2019 09:34:55 +0200 Subject: [PATCH] mem-ruby: Make MultiGrainBloomFilter generic Allow combining any number of Bloom Filters in the MultiGrain. Change-Id: I73ae33063e1feed731af6f625d2f64245f21df18 Signed-off-by: Daniel R. Carvalho Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/18869 Reviewed-by: Nikos Nikoleris Maintainer: Nikos Nikoleris Tested-by: kokoro --- src/mem/ruby/filters/BloomFilters.py | 14 +++- src/mem/ruby/filters/MultiGrainBloomFilter.cc | 78 ++++++++++--------- src/mem/ruby/filters/MultiGrainBloomFilter.hh | 17 ++-- 3 files changed, 63 insertions(+), 46 deletions(-) diff --git a/src/mem/ruby/filters/BloomFilters.py b/src/mem/ruby/filters/BloomFilters.py index 89a4b9bdc..de5cd7d40 100644 --- a/src/mem/ruby/filters/BloomFilters.py +++ b/src/mem/ruby/filters/BloomFilters.py @@ -93,10 +93,18 @@ class MultiGrainBloomFilter(AbstractBloomFilter): 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 150e0a561..86e7d9b81 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,60 +44,67 @@ MultiGrainBloomFilter::~MultiGrainBloomFilter() void MultiGrainBloomFilter::clear() { - AbstractBloomFilter::clear(); - for (auto& entry : pageFilter){ - entry = 0; + for (auto& sub_filter : filters) { + sub_filter->clear(); } } void -MultiGrainBloomFilter::set(Addr addr) +MultiGrainBloomFilter::merge(const AbstractBloomFilter* other) { - const int index = hash(addr); - assert(index < filter.size()); - filter[index] = 1; - - const int page_index = pageHash(addr); - assert(page_index < pageFilter.size()); - pageFilter[page_index] = 1; + auto* cast_other = static_cast(other); + assert(filters.size() == cast_other->filters.size()); + for (int i = 0; i < filters.size(); ++i){ + filters[i]->merge(cast_other->filters[i]); + } } -int -MultiGrainBloomFilter::getCount(Addr addr) const +void +MultiGrainBloomFilter::set(Addr addr) { - 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]; + for (auto& sub_filter : filters) { + sub_filter->set(addr); + } } -int -MultiGrainBloomFilter::getTotalCount() const +void +MultiGrainBloomFilter::unset(Addr addr) { - int count = AbstractBloomFilter::getTotalCount(); - - for (const auto& entry : pageFilter) { - count += entry; + for (auto& sub_filter : filters) { + sub_filter->unset(addr); } +} - return count; +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::hash(Addr addr) const +MultiGrainBloomFilter::getCount(Addr addr) const { - // grap a chunk of bits after byte offset - return bits(addr, offsetBits + sizeBits - 1, offsetBits); + int count = 0; + for (const auto& sub_filter : filters) { + count += sub_filter->getCount(addr); + } + return count; } int -MultiGrainBloomFilter::pageHash(Addr addr) const +MultiGrainBloomFilter::getTotalCount() const { - int num_bits = offsetBits + sizeBits - 1; - - // grap a chunk of bits after first chunk - return bits(addr, num_bits + pageFilterSizeBits - 1, num_bits); + int count = 0; + for (const auto& sub_filter : filters) { + count += sub_filter->getTotalCount(); + } + return count; } MultiGrainBloomFilter* diff --git a/src/mem/ruby/filters/MultiGrainBloomFilter.hh b/src/mem/ruby/filters/MultiGrainBloomFilter.hh index e89578805..fffda367a 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 @@ class MultiGrainBloomFilter : public AbstractBloomFilter 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 pageFilter; - int pageFilterSizeBits; + /** Sub-filters used by this filter. */ + std::vector filters; }; #endif // __MEM_RUBY_FILTERS_MULTIGRAINBLOOMFILTER_HH__ -- 2.30.2