From f20624fd6c7984c6f0bfdf6cbfca8a7f0670f1a7 Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Sun, 12 May 2019 14:34:28 +0200 Subject: base: Make Bulk inherit from MultiBitSel Bloom Filter Cleanup bulk's code and make it inherit from MultiBitSel. Change-Id: I83154feb30bb3dac3d02743bcafbdcb57489c2fd Signed-off-by: Daniel R. Carvalho Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/18876 Tested-by: kokoro Reviewed-by: Nikos Nikoleris Maintainer: Nikos Nikoleris --- src/base/filters/BloomFilters.py | 10 ++-- src/base/filters/bulk_bloom_filter.cc | 98 +++++++---------------------------- src/base/filters/bulk_bloom_filter.hh | 20 ++++--- 3 files changed, 35 insertions(+), 93 deletions(-) diff --git a/src/base/filters/BloomFilters.py b/src/base/filters/BloomFilters.py index 208b8a97a..df0a894ab 100644 --- a/src/base/filters/BloomFilters.py +++ b/src/base/filters/BloomFilters.py @@ -54,11 +54,6 @@ class BloomFilterBlock(BloomFilterBase): masks_sizes = VectorParam.Unsigned([Self.offset_bits, Self.offset_bits], "Size, in number of bits, of each mask") -class BloomFilterBulk(BloomFilterBase): - type = 'BloomFilterBulk' - cxx_class = 'BloomFilter::Bulk' - cxx_header = "base/filters/bulk_bloom_filter.hh" - class BloomFilterLSBCounting(BloomFilterBase): type = 'BloomFilterLSBCounting' cxx_class = 'BloomFilter::LSBCounting' @@ -80,6 +75,11 @@ class BloomFilterMultiBitSel(BloomFilterBase): skip_bits = Param.Int(2, "Offset from block number") is_parallel = Param.Bool(False, "Whether hashing is done in parallel") +class BloomFilterBulk(BloomFilterMultiBitSel): + type = 'BloomFilterBulk' + cxx_class = 'BloomFilter::Bulk' + cxx_header = "base/filters/bulk_bloom_filter.hh" + class BloomFilterH3(BloomFilterMultiBitSel): type = 'BloomFilterH3' cxx_class = 'BloomFilter::H3' diff --git a/src/base/filters/bulk_bloom_filter.cc b/src/base/filters/bulk_bloom_filter.cc index 6488086c2..fb5778aa5 100644 --- a/src/base/filters/bulk_bloom_filter.cc +++ b/src/base/filters/bulk_bloom_filter.cc @@ -31,107 +31,45 @@ #include "base/filters/bulk_bloom_filter.hh" -#include - #include #include "base/bitfield.hh" +#include "base/logging.hh" #include "params/BloomFilterBulk.hh" namespace BloomFilter { Bulk::Bulk(const BloomFilterBulkParams* p) - : Base(p), sectorBits(sizeBits - 1) + : MultiBitSel(p), sectorBits(floorLog2(parFilterSize)) { + fatal_if((numHashes * sectorBits) > + (std::numeric_limits::digits - offsetBits), + "Sectors need more bits than available"); } Bulk::~Bulk() { } -void -Bulk::set(Addr addr) +int +Bulk::hash(Addr addr, int hash_number) const { - // c0 contains the cache index bits - int c0 = bits(addr, offsetBits + sectorBits - 1, offsetBits); - // c1 contains the lower sectorBits permuted bits - //Address permuted_bits = permute(addr); - int c1 = bits(addr, (offsetBits + 2 * sectorBits) - 1, - offsetBits + sectorBits); - //assert(c0 < (filter_size/2)); - //assert(c0 + (filter_size/2) < filter_size); - //assert(c1 < (filter_size/2)); - // set v0 bit - filter[c0 + (filter.size()/2)] = 1; - // set v1 bit - filter[c1] = 1; -} + addr = permute(addr); -bool -Bulk::isSet(Addr addr) const -{ - // c0 contains the cache index bits - const int filter_size = filter.size(); - int c0 = bits(addr, offsetBits + sectorBits - 1, offsetBits); - // c1 contains the lower 10 permuted bits - //Address permuted_bits = permute(addr); - int c1 = bits(addr, (offsetBits + 2 * sectorBits) - 1, - offsetBits + sectorBits); - //assert(c0 < (filter_size/2)); - //assert(c0 + (filter_size/2) < filter_size); - //assert(c1 < (filter_size/2)); - // set v0 bit - std::vector temp_filter(filter.size(), 0); - temp_filter[c0 + (filter_size/2)] = 1; - // set v1 bit - temp_filter[c1] = 1; - - // perform filter intersection. If any c part is 0, no possibility - // of address being in signature. get first c intersection part - bool zero = false; - for (int i = 0; i < filter_size/2; ++i){ - // get intersection of signatures - temp_filter[i] = temp_filter[i] && filter[i]; - zero = zero || temp_filter[i]; - } - zero = !zero; - if (zero) { - // one section is zero, no possiblility of address in signature - // reset bits we just set - temp_filter[c0 + (filter_size / 2)] = 0; - temp_filter[c1] = 0; - return false; - } - - // check second section - zero = false; - for (int i = filter_size / 2; i < filter_size; ++i) { - // get intersection of signatures - temp_filter[i] = temp_filter[i] && filter[i]; - zero = zero || temp_filter[i]; - } - zero = !zero; - if (zero) { - // one section is zero, no possiblility of address in signature - temp_filter[c0 + (filter_size / 2)] = 0; - temp_filter[c1] = 0; - return false; - } - // one section has at least one bit set - temp_filter[c0 + (filter_size / 2)] = 0; - temp_filter[c1] = 0; - return true; -} + // Get the sector-based c index + int c = bits(addr, (offsetBits + (hash_number + 1) * sectorBits) - 1, + offsetBits + hash_number * sectorBits); + assert(c < filter.size()/numHashes); -int -Bulk::getCount(Addr addr) const -{ - // TODO as in the multi-hashed filters - return 0; + // Transform the sector-based c index into a filder index (v) + c += (numHashes - 1 - hash_number) * (filter.size()/numHashes); + assert(c < filter.size()); + + return c; } Addr -Bulk::hash(Addr addr) const +Bulk::permute(Addr addr) const { // permutes the original address bits according to Table 5 Addr part1 = bits(addr, offsetBits + 6, offsetBits), diff --git a/src/base/filters/bulk_bloom_filter.hh b/src/base/filters/bulk_bloom_filter.hh index 7211aa2cd..e2fdaec74 100644 --- a/src/base/filters/bulk_bloom_filter.hh +++ b/src/base/filters/bulk_bloom_filter.hh @@ -32,7 +32,7 @@ #ifndef __BASE_FILTERS_BULK_BLOOM_FILTER_HH__ #define __BASE_FILTERS_BULK_BLOOM_FILTER_HH__ -#include "base/filters/base.hh" +#include "base/filters/multi_bit_sel_bloom_filter.hh" struct BloomFilterBulkParams; @@ -41,23 +41,27 @@ namespace BloomFilter { /** * Implementation of the bloom filter, as described in "Bulk Disambiguation of * Speculative Threads in Multiprocessors", by Ceze, Luis, et al. + * The number of hashes indicates the number of c bitfields. */ -class Bulk : public Base +class Bulk : public MultiBitSel { public: Bulk(const BloomFilterBulkParams* p); ~Bulk(); - void set(Addr addr) override; - - bool isSet(Addr addr) const override; - int getCount(Addr addr) const override; + protected: + int hash(Addr addr, int hash_number) const override; private: /** Permutes the address to generate its signature. */ - Addr hash(Addr addr) const; + Addr permute(Addr addr) const; - // split the filter bits in half, c0 and c1 + /** + * Number of bits used per sector. The filter is split into sectors, + * each of which with its own hash function. When an address is hashed + * all sectors are parsed to generate c indexes. These indexes are then + * used to find the respective v indexes in the main filter. + */ const int sectorBits; }; -- cgit v1.2.3