From 946250181a9561fb80a8bd36e9c16b69ba1667ef Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Tue, 14 May 2019 19:38:47 +0200 Subject: base: Make Bloom Filter counting by default Since a boolean bool filter is a saturating bloom filter with a single bit per entry, generalize them by using SatCounter instead of int for the filter entries. Change-Id: I7f54e28d54de5671e0770b02ed9161735e6bd339 Signed-off-by: Daniel R. Carvalho Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/18877 Tested-by: kokoro Reviewed-by: Nikos Nikoleris Maintainer: Nikos Nikoleris --- src/base/filters/BloomFilters.py | 12 +--- src/base/filters/SConscript | 1 - src/base/filters/base.hh | 10 +-- src/base/filters/block_bloom_filter.cc | 4 +- src/base/filters/lsb_counting_bloom_filter.cc | 98 -------------------------- src/base/filters/lsb_counting_bloom_filter.hh | 62 ---------------- src/base/filters/multi_bit_sel_bloom_filter.cc | 3 +- 7 files changed, 10 insertions(+), 180 deletions(-) delete mode 100644 src/base/filters/lsb_counting_bloom_filter.cc delete mode 100644 src/base/filters/lsb_counting_bloom_filter.hh diff --git a/src/base/filters/BloomFilters.py b/src/base/filters/BloomFilters.py index df0a894ab..b3460d747 100644 --- a/src/base/filters/BloomFilters.py +++ b/src/base/filters/BloomFilters.py @@ -42,6 +42,7 @@ class BloomFilterBase(SimObject): offset_bits = Param.Unsigned(6, "Number of bits in a cache line offset") # Most of the filters are booleans, and thus saturate on 1 + num_bits = Param.Int(1, "Number of bits in a filter entry") threshold = Param.Int(1, "Value at which an entry is considered as set") class BloomFilterBlock(BloomFilterBase): @@ -54,17 +55,6 @@ class BloomFilterBlock(BloomFilterBase): masks_sizes = VectorParam.Unsigned([Self.offset_bits, Self.offset_bits], "Size, in number of bits, of each mask") -class BloomFilterLSBCounting(BloomFilterBase): - type = 'BloomFilterLSBCounting' - cxx_class = 'BloomFilter::LSBCounting' - cxx_header = "base/filters/lsb_counting_bloom_filter.hh" - - # By default use 4-bit saturating counters - max_value = Param.Int(15, "Maximum value of the filter entries") - - # We assume that isSet will return true only when the counter saturates - threshold = Self.max_value - class BloomFilterMultiBitSel(BloomFilterBase): type = 'BloomFilterMultiBitSel' cxx_class = 'BloomFilter::MultiBitSel' diff --git a/src/base/filters/SConscript b/src/base/filters/SConscript index 4c02ff122..254531203 100644 --- a/src/base/filters/SConscript +++ b/src/base/filters/SConscript @@ -37,6 +37,5 @@ SimObject('BloomFilters.py') Source('block_bloom_filter.cc') Source('bulk_bloom_filter.cc') Source('h3_bloom_filter.cc') -Source('lsb_counting_bloom_filter.cc') Source('multi_bit_sel_bloom_filter.cc') Source('multi_bloom_filter.cc') diff --git a/src/base/filters/base.hh b/src/base/filters/base.hh index 1ce853979..fa618fe84 100644 --- a/src/base/filters/base.hh +++ b/src/base/filters/base.hh @@ -35,6 +35,7 @@ #include #include "base/intmath.hh" +#include "base/sat_counter.hh" #include "base/types.hh" #include "params/BloomFilterBase.hh" #include "sim/sim_object.hh" @@ -48,7 +49,7 @@ class Base : public SimObject const unsigned offsetBits; /** The filter itself. */ - std::vector filter; + std::vector filter; /** Number of bits needed to represent the size of the filter. */ const int sizeBits; @@ -61,7 +62,8 @@ class Base : public SimObject * Create and clear the filter. */ Base(const BloomFilterBaseParams* p) - : SimObject(p), offsetBits(p->offset_bits), filter(p->size), + : SimObject(p), offsetBits(p->offset_bits), + filter(p->size, SatCounter(p->num_bits)), sizeBits(floorLog2(p->size)), setThreshold(p->threshold) { clear(); @@ -74,7 +76,7 @@ class Base : public SimObject virtual void clear() { for (auto& entry : filter) { - entry = 0; + entry.reset(); } } @@ -89,7 +91,7 @@ class Base : public SimObject { assert(filter.size() == other->filter.size()); for (int i = 0; i < filter.size(); ++i){ - filter[i] |= other->filter[i]; + filter[i] += other->filter[i]; } } diff --git a/src/base/filters/block_bloom_filter.cc b/src/base/filters/block_bloom_filter.cc index 45e3b725e..890ada84a 100644 --- a/src/base/filters/block_bloom_filter.cc +++ b/src/base/filters/block_bloom_filter.cc @@ -63,13 +63,13 @@ Block::~Block() void Block::set(Addr addr) { - filter[hash(addr)] = 1; + filter[hash(addr)]++; } void Block::unset(Addr addr) { - filter[hash(addr)] = 0; + filter[hash(addr)]--; } int diff --git a/src/base/filters/lsb_counting_bloom_filter.cc b/src/base/filters/lsb_counting_bloom_filter.cc deleted file mode 100644 index 16f858f01..000000000 --- a/src/base/filters/lsb_counting_bloom_filter.cc +++ /dev/null @@ -1,98 +0,0 @@ -/* - * Copyright (c) 2019 Inria - * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer; - * redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution; - * neither the name of the copyright holders nor the names of its - * contributors may be used to endorse or promote products derived from - * this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * Authors: Daniel Carvalho - */ - -#include "base/filters/lsb_counting_bloom_filter.hh" - -#include "base/bitfield.hh" -#include "params/BloomFilterLSBCounting.hh" - -namespace BloomFilter { - -LSBCounting::LSBCounting( - const BloomFilterLSBCountingParams* p) - : Base(p), maxValue(p->max_value) -{ -} - -LSBCounting::~LSBCounting() -{ -} - -void -LSBCounting::merge(const Base* 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 -LSBCounting::set(Addr addr) -{ - const int i = hash(addr); - if (filter[i] < maxValue) - filter[i] += 1; -} - -void -LSBCounting::unset(Addr addr) -{ - const int i = hash(addr); - if (filter[i] > 0) - filter[i] -= 1; -} - -int -LSBCounting::getCount(Addr addr) const -{ - return filter[hash(addr)]; -} - -int -LSBCounting::hash(Addr addr) const -{ - return bits(addr, offsetBits + sizeBits - 1, offsetBits); -} - -} // namespace BloomFilter - -BloomFilter::LSBCounting* -BloomFilterLSBCountingParams::create() -{ - return new BloomFilter::LSBCounting(this); -} - diff --git a/src/base/filters/lsb_counting_bloom_filter.hh b/src/base/filters/lsb_counting_bloom_filter.hh deleted file mode 100644 index 6da6fd681..000000000 --- a/src/base/filters/lsb_counting_bloom_filter.hh +++ /dev/null @@ -1,62 +0,0 @@ -/* - * Copyright (c) 2019 Inria - * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer; - * redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution; - * neither the name of the copyright holders nor the names of its - * contributors may be used to endorse or promote products derived from - * this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * Authors: Daniel Carvalho - */ - -#ifndef __BASE_FILTERS_LSB_COUNTING_BLOOM_FILTER_HH__ -#define __BASE_FILTERS_LSB_COUNTING_BLOOM_FILTER_HH__ - -#include "base/filters/base.hh" - -struct BloomFilterLSBCountingParams; - -namespace BloomFilter { - -class LSBCounting : public Base -{ - public: - LSBCounting(const BloomFilterLSBCountingParams* p); - ~LSBCounting(); - - void merge(const Base* other) override; - void set(Addr addr) override; - void unset(Addr addr) override; - - int getCount(Addr addr) const override; - - private: - int hash(Addr addr) const; - - /** Maximum value of the filter entries. */ - const int maxValue; -}; - -} // namespace BloomFilter - -#endif //__BASE_FILTERS_LSB_COUNTING_BLOOM_FILTER_HH__ diff --git a/src/base/filters/multi_bit_sel_bloom_filter.cc b/src/base/filters/multi_bit_sel_bloom_filter.cc index efd20c315..6fa99fec6 100644 --- a/src/base/filters/multi_bit_sel_bloom_filter.cc +++ b/src/base/filters/multi_bit_sel_bloom_filter.cc @@ -58,8 +58,7 @@ void MultiBitSel::set(Addr addr) { for (int i = 0; i < numHashes; i++) { - int idx = hash(addr, i); - filter[idx] = 1; + filter[hash(addr, i)]++; } } -- cgit v1.2.3