Daniel Carvalho has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/18870
Change subject: mem-ruby: Parameterize xor bits in BlockBloomFilter
......................................................................
mem-ruby: Parameterize xor bits in BlockBloomFilter
Parameterize bitfield ranges in BlockBloomFilter such that the
hash is applied between two user defined bitfields of an address:
63 D C B A 0
| Addr | MSBBitfield | Offset2 | LSBBitfield | Offset1 |
Where A = offsetLSB
B = numLSBBits + A
C = offsetMSB + B
D = numMSBBits + C
And hash = MSBBitfield ^ LSBBitfield.
Change-Id: I008bd873458e9815e98530e308491adb65bb34cb
Signed-off-by: Daniel R. Carvalho <[email protected]>
---
M src/mem/ruby/filters/BlockBloomFilter.cc
M src/mem/ruby/filters/BlockBloomFilter.hh
M src/mem/ruby/filters/BloomFilters.py
3 files changed, 57 insertions(+), 9 deletions(-)
diff --git a/src/mem/ruby/filters/BlockBloomFilter.cc
b/src/mem/ruby/filters/BlockBloomFilter.cc
index bbc4527..c86d45c 100644
--- a/src/mem/ruby/filters/BlockBloomFilter.cc
+++ b/src/mem/ruby/filters/BlockBloomFilter.cc
@@ -29,11 +29,22 @@
#include "mem/ruby/filters/BlockBloomFilter.hh"
#include "base/bitfield.hh"
+#include "base/logging.hh"
#include "params/BlockBloomFilter.hh"
BlockBloomFilter::BlockBloomFilter(const BlockBloomFilterParams* p)
- : AbstractBloomFilter(p)
+ : AbstractBloomFilter(p),
+ offsetLSB(p->offset_lsb), numLSBBits(p->num_lsb_bits),
+ offsetMSB(p->offset_msb), numMSBBits(p->num_msb_bits)
{
+ fatal_if((numLSBBits > sizeBits) || (numLSBBits <= 0),
+ "The LSB bitfield must be indexable in the filter");
+ fatal_if((numMSBBits > sizeBits) || (numMSBBits <= 0),
+ "The bitfields must be indexable in the filter");
+ fatal_if(offsetLSB + numLSBBits + offsetMSB + numMSBBits >
+ (sizeof(Addr) * 8),
+ "The total size of the bitfields cannot be bigger than the " \
+ "number of bits in an address");
}
BlockBloomFilter::~BlockBloomFilter()
@@ -61,14 +72,12 @@
int
BlockBloomFilter::hash(Addr addr) const
{
- // Pull out some bit field ==> B1
- // Pull out additional bits, not the same as B1 ==> B2
- // XOR B1 and B2 to get hash index
- Addr block_bits = bits(addr, 2 * blkBits - 1, blkBits);
- int offset = 5;
- Addr other_bits =
- bits(addr, 2 * blkBits + offset + sizeBits - 1, 2 * blkBits +
offset);
- int index = block_bits ^ other_bits;
+ const Addr lsb_bitfield =
+ bits(addr, offsetLSB + numLSBBits - 1, offsetLSB);
+ const int lsb_msb_bitfield = offsetLSB + numLSBBits + offsetMSB;
+ const Addr msb_bitfield =
+ bits(addr, lsb_msb_bitfield + numMSBBits - 1, lsb_msb_bitfield);
+ const int index = lsb_bitfield ^ msb_bitfield;
assert(index < filter.size());
return index;
}
diff --git a/src/mem/ruby/filters/BlockBloomFilter.hh
b/src/mem/ruby/filters/BlockBloomFilter.hh
index c386624..34ebd7a 100644
--- a/src/mem/ruby/filters/BlockBloomFilter.hh
+++ b/src/mem/ruby/filters/BlockBloomFilter.hh
@@ -33,6 +33,11 @@
struct BlockBloomFilterParams;
+/**
+ * Simple deletable (with false negatives) bloom filter that extracts two
+ * bitfields of an address to use as indexes of the filter vector, ignoring
+ * the block offset bits.
+ */
class BlockBloomFilter : public AbstractBloomFilter
{
public:
@@ -44,7 +49,32 @@
int getCount(Addr addr) const override;
private:
+ /**
+ * XOR hash between two bitfields of an address. The address is divided
+ * into:
+ * 63 D C B A 0
+ * | Addr | MSBBitfield | Offset2 | LSBBitfield | Offset1 |
+ * Where A = offsetLSB
+ * B = numLSBBits + A
+ * C = offsetMSB + B
+ * D = numMSBBits + C
+ *
+ * @param addr The address to be hashed.
+ * @return The value of MSBBitfield ^ LSBBitfield.
+ */
int hash(Addr addr) const;
+
+ /** Number of bits between the LSB and the LSB bitfield. */
+ const unsigned offsetLSB;
+
+ /** Number of bits used in the XOR hash just after the block offset. */
+ const unsigned numLSBBits;
+
+ /** Number of bits between the LSB and MSB bitfields. */
+ const unsigned offsetMSB;
+
+ /** Number of bits used in the XOR hash just after the offset. */
+ const unsigned numMSBBits;
};
#endif // __MEM_RUBY_FILTERS_BLOCKBLOOMFILTER_HH__
diff --git a/src/mem/ruby/filters/BloomFilters.py
b/src/mem/ruby/filters/BloomFilters.py
index 2ec671d..f2b9f2b 100644
--- a/src/mem/ruby/filters/BloomFilters.py
+++ b/src/mem/ruby/filters/BloomFilters.py
@@ -48,6 +48,15 @@
cxx_class = 'BlockBloomFilter'
cxx_header = "mem/ruby/filters/BlockBloomFilter.hh"
+ offset_lsb = Param.Unsigned(Self.block_bits,
+ "Number of bits between the LSB and the LSB bitfied")
+ num_lsb_bits = Param.Unsigned(Self.block_bits,
+ "Number of LSB bits used in the XOR hash")
+ offset_msb = Param.Unsigned(5,
+ "Number of bits between the LSB and MSB bitfields")
+ num_msb_bits = Param.Unsigned(Self.block_bits,
+ "Number of MSB bits used in the XOR hash")
+
class BulkBloomFilter(AbstractBloomFilter):
type = 'BulkBloomFilter'
cxx_class = 'BulkBloomFilter'
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/18870
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-Change-Id: I008bd873458e9815e98530e308491adb65bb34cb
Gerrit-Change-Number: 18870
Gerrit-PatchSet: 1
Gerrit-Owner: Daniel Carvalho <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
