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 <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/18876
Tested-by: kokoro <noreply+kokoro@google.com>
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
diff --git a/src/base/filters/BloomFilters.py b/src/base/filters/BloomFilters.py
index 208b8a9..df0a894 100644
--- a/src/base/filters/BloomFilters.py
+++ b/src/base/filters/BloomFilters.py
@@ -54,11 +54,6 @@
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 @@
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 6488086..fb5778a 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 <vector>
-
#include <limits>
#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<Addr>::digits - offsetBits),
+ "Sectors need more bits than available");
}
Bulk::~Bulk()
{
}
-void
-Bulk::set(Addr addr)
-{
- // 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;
-}
-
-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<int> 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;
-}
-
int
-Bulk::getCount(Addr addr) const
+Bulk::hash(Addr addr, int hash_number) const
{
- // TODO as in the multi-hashed filters
- return 0;
+ addr = permute(addr);
+
+ // 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);
+
+ // 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 7211aa2..e2fdaec 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 @@
/**
* 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;
};
