Daniel Carvalho has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/18735
Change subject: mem-ruby: Generalize use of bloom filters' isSet
......................................................................
mem-ruby: Generalize use of bloom filters' isSet
In general the corresponding entries of an address are considered
to be set when the sum of all of them reach their maximum value
(i.e., they are all set), so generalize that into the base class.
Change-Id: If50b8c56065ad339b4ff2322ddc3c077a3bfc518
Signed-off-by: Daniel R. Carvalho <[email protected]>
---
M src/mem/ruby/filters/AbstractBloomFilter.hh
M src/mem/ruby/filters/BlockBloomFilter.cc
M src/mem/ruby/filters/BlockBloomFilter.hh
M src/mem/ruby/filters/BulkBloomFilter.cc
M src/mem/ruby/filters/BulkBloomFilter.hh
M src/mem/ruby/filters/H3BloomFilter.cc
M src/mem/ruby/filters/H3BloomFilter.hh
M src/mem/ruby/filters/LSB_CountingBloomFilter.cc
M src/mem/ruby/filters/LSB_CountingBloomFilter.hh
M src/mem/ruby/filters/MultiBitSelBloomFilter.cc
M src/mem/ruby/filters/MultiBitSelBloomFilter.hh
M src/mem/ruby/filters/MultiGrainBloomFilter.cc
M src/mem/ruby/filters/MultiGrainBloomFilter.hh
M src/mem/ruby/filters/NonCountingBloomFilter.cc
M src/mem/ruby/filters/NonCountingBloomFilter.hh
15 files changed, 53 insertions(+), 92 deletions(-)
diff --git a/src/mem/ruby/filters/AbstractBloomFilter.hh
b/src/mem/ruby/filters/AbstractBloomFilter.hh
index a89e29e..43633b0 100644
--- a/src/mem/ruby/filters/AbstractBloomFilter.hh
+++ b/src/mem/ruby/filters/AbstractBloomFilter.hh
@@ -57,12 +57,18 @@
/** Number of bits needed to represent the size of the filter. */
const int sizeBits;
+ /** Threshold at which a filter entry starts being considered as set.
*/
+ const int setThreshold;
+
public:
/**
* Create and clear the filter.
+ *
+ * @param size The number of filter entries.
+ * @param threshold The threshold that limits a set entry.
*/
- AbstractBloomFilter(std::size_t size)
- : filter(size), sizeBits(floorLog2(size))
+ AbstractBloomFilter(std::size_t size, int threshold)
+ : filter(size), sizeBits(floorLog2(size)), setThreshold(threshold)
{
clear();
}
@@ -105,7 +111,11 @@
* @param addr The address being parsed.
* @return Whether the respective filter entry is set.
*/
- virtual bool isSet(Addr addr) = 0;
+ virtual bool
+ isSet(Addr addr) const
+ {
+ return getCount(addr) >= setThreshold;
+ }
/**
* Get the value stored in the corresponding filter entry of an
address.
@@ -113,7 +123,7 @@
* @param addr The address being parsed.
* @param Get the value stored in the respective filter entry.
*/
- virtual int getCount(Addr addr) { return 0; }
+ virtual int getCount(Addr addr) const { return 0; }
/**
* Get the total value stored in the filter entries.
diff --git a/src/mem/ruby/filters/BlockBloomFilter.cc
b/src/mem/ruby/filters/BlockBloomFilter.cc
index 70093f9..8b95e65 100644
--- a/src/mem/ruby/filters/BlockBloomFilter.cc
+++ b/src/mem/ruby/filters/BlockBloomFilter.cc
@@ -31,7 +31,7 @@
#include "mem/ruby/system/RubySystem.hh"
BlockBloomFilter::BlockBloomFilter(int size)
- : AbstractBloomFilter(size)
+ : AbstractBloomFilter(size, 1)
{
}
@@ -51,14 +51,8 @@
filter[hash(addr)] = 0;
}
-bool
-BlockBloomFilter::isSet(Addr addr)
-{
- return filter[hash(addr)];
-}
-
int
-BlockBloomFilter::getCount(Addr addr)
+BlockBloomFilter::getCount(Addr addr) const
{
return filter[hash(addr)];
}
diff --git a/src/mem/ruby/filters/BlockBloomFilter.hh
b/src/mem/ruby/filters/BlockBloomFilter.hh
index 7c8ffc1..fd75ba8 100644
--- a/src/mem/ruby/filters/BlockBloomFilter.hh
+++ b/src/mem/ruby/filters/BlockBloomFilter.hh
@@ -39,9 +39,7 @@
void set(Addr addr) override;
void unset(Addr addr) override;
-
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ int getCount(Addr addr) const override;
private:
int hash(Addr addr) const;
diff --git a/src/mem/ruby/filters/BulkBloomFilter.cc
b/src/mem/ruby/filters/BulkBloomFilter.cc
index 454692d..2daf3bb 100644
--- a/src/mem/ruby/filters/BulkBloomFilter.cc
+++ b/src/mem/ruby/filters/BulkBloomFilter.cc
@@ -31,7 +31,7 @@
#include "mem/ruby/system/RubySystem.hh"
BulkBloomFilter::BulkBloomFilter(int size)
- : AbstractBloomFilter(size), sectorBits(sizeBits - 1)
+ : AbstractBloomFilter(size, 1), sectorBits(sizeBits - 1)
{
}
@@ -60,7 +60,7 @@
}
bool
-BulkBloomFilter::isSet(Addr addr)
+BulkBloomFilter::isSet(Addr addr) const
{
// c0 contains the cache index bits
const int filter_size = filter.size();
@@ -118,9 +118,9 @@
}
int
-BulkBloomFilter::getCount(Addr addr)
+BulkBloomFilter::getCount(Addr addr) const
{
- // not used
+ // TODO as in the multi-hashed filters
return 0;
}
diff --git a/src/mem/ruby/filters/BulkBloomFilter.hh
b/src/mem/ruby/filters/BulkBloomFilter.hh
index b6f52b9..7be00e6 100644
--- a/src/mem/ruby/filters/BulkBloomFilter.hh
+++ b/src/mem/ruby/filters/BulkBloomFilter.hh
@@ -45,8 +45,8 @@
void set(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ bool isSet(Addr addr) const override;
+ int getCount(Addr addr) const override;
private:
/** Permutes the address to generate its signature. */
diff --git a/src/mem/ruby/filters/H3BloomFilter.cc
b/src/mem/ruby/filters/H3BloomFilter.cc
index f6ee8a1..485cc31 100644
--- a/src/mem/ruby/filters/H3BloomFilter.cc
+++ b/src/mem/ruby/filters/H3BloomFilter.cc
@@ -354,8 +354,8 @@
};
H3BloomFilter::H3BloomFilter(int size, int num_hashes, bool parallel)
- : AbstractBloomFilter(size), numHashes(num_hashes),
isParallel(parallel),
- parFilterSize(filter.size() / numHashes)
+ : AbstractBloomFilter(size, num_hashes), numHashes(num_hashes),
+ isParallel(parallel), parFilterSize(filter.size() / numHashes)
{
fatal_if(numHashes > 16, "There are only 16 hash functions
implemented.");
}
@@ -382,22 +382,14 @@
}
}
-bool
-H3BloomFilter::isSet(Addr addr)
-{
- bool res = true;
-
- for (int i = 0; i < numHashes; i++) {
- int idx = hash(addr, i);
- res = res && filter[idx];
- }
- return res;
-}
-
int
-H3BloomFilter::getCount(Addr addr)
+H3BloomFilter::getCount(Addr addr) const
{
- return isSet(addr)? 1: 0;
+ int count = 0;
+ for (int i=0; i < numHashes; i++) {
+ count += filter[hash(addr, i)];
+ }
+ return count;
}
int
diff --git a/src/mem/ruby/filters/H3BloomFilter.hh
b/src/mem/ruby/filters/H3BloomFilter.hh
index 69a1ddd..f9c564a 100644
--- a/src/mem/ruby/filters/H3BloomFilter.hh
+++ b/src/mem/ruby/filters/H3BloomFilter.hh
@@ -43,8 +43,7 @@
void merge(const AbstractBloomFilter* other) override;
void set(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr) override;
+ int getCount(Addr addr) const override;
private:
/**
diff --git a/src/mem/ruby/filters/LSB_CountingBloomFilter.cc
b/src/mem/ruby/filters/LSB_CountingBloomFilter.cc
index 0230bb5..9e034b7 100644
--- a/src/mem/ruby/filters/LSB_CountingBloomFilter.cc
+++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.cc
@@ -32,7 +32,9 @@
LSB_CountingBloomFilter::LSB_CountingBloomFilter(std::size_t filter_size,
int max_value)
- : AbstractBloomFilter(filter_size), maxValue(max_value)
+ // Here we assume that isSet will return true only when the counter
+ // saturates
+ : AbstractBloomFilter(filter_size, max_value), maxValue(max_value)
{
}
@@ -56,15 +58,8 @@
filter[i] -= 1;
}
-bool
-LSB_CountingBloomFilter::isSet(Addr addr)
-{
- // TODO
- return false;
-}
-
int
-LSB_CountingBloomFilter::getCount(Addr addr)
+LSB_CountingBloomFilter::getCount(Addr addr) const
{
return filter[hash(addr)];
}
diff --git a/src/mem/ruby/filters/LSB_CountingBloomFilter.hh
b/src/mem/ruby/filters/LSB_CountingBloomFilter.hh
index 4fc6355..e9ffbcb 100644
--- a/src/mem/ruby/filters/LSB_CountingBloomFilter.hh
+++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.hh
@@ -40,8 +40,7 @@
void set(Addr addr) override;
void unset(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ int getCount(Addr addr) const override;
private:
int hash(Addr addr) const;
diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
index aa1438f..c453d10 100644
--- a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
+++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
@@ -32,7 +32,7 @@
MultiBitSelBloomFilter::MultiBitSelBloomFilter(std::size_t filter_size,
int num_hashes, int skip_bits, bool is_parallel)
- : AbstractBloomFilter(filter_size), numHashes(num_hashes),
+ : AbstractBloomFilter(filter_size, num_hashes), numHashes(num_hashes),
skipBits(skip_bits),
parFilterSize(filter_size / numHashes),
isParallel(is_parallel)
@@ -62,22 +62,14 @@
}
}
-bool
-MultiBitSelBloomFilter::isSet(Addr addr)
-{
- bool res = true;
-
- for (int i=0; i < numHashes; i++) {
- int idx = hash(addr, i);
- res = res && filter[idx];
- }
- return res;
-}
-
int
-MultiBitSelBloomFilter::getCount(Addr addr)
+MultiBitSelBloomFilter::getCount(Addr addr) const
{
- return isSet(addr)? 1: 0;
+ int count = 0;
+ for (int i=0; i < numHashes; i++) {
+ count += filter[hash(addr, i)];
+ }
+ return count;
}
int
diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh
b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh
index 2d69540..914875f 100644
--- a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh
+++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh
@@ -40,8 +40,7 @@
void merge(const AbstractBloomFilter* other) override;
void set(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ int getCount(Addr addr) const override;
private:
int hash(Addr addr, int hash_number) const;
diff --git a/src/mem/ruby/filters/MultiGrainBloomFilter.cc
b/src/mem/ruby/filters/MultiGrainBloomFilter.cc
index e7e5a7b..95be9c1 100644
--- a/src/mem/ruby/filters/MultiGrainBloomFilter.cc
+++ b/src/mem/ruby/filters/MultiGrainBloomFilter.cc
@@ -31,7 +31,7 @@
#include "mem/ruby/system/RubySystem.hh"
MultiGrainBloomFilter::MultiGrainBloomFilter(int head, int tail)
- : AbstractBloomFilter(head),
+ : AbstractBloomFilter(head, 2),
pageFilter(tail), pageFilterSizeBits(floorLog2(tail))
{
}
@@ -60,21 +60,13 @@
}
-bool
-MultiGrainBloomFilter::isSet(Addr addr)
+int
+MultiGrainBloomFilter::getCount(Addr addr) const
{
int i = hash(addr);
assert(i < filter.size());
assert(pageHash(addr) < pageFilter.size());
- // we have to have both indices set
- return (filter[i] && pageFilter[i]);
-}
-
-int
-MultiGrainBloomFilter::getCount(Addr addr)
-{
- // not used
- return 0;
+ return filter[i] + pageFilter[i];
}
int
diff --git a/src/mem/ruby/filters/MultiGrainBloomFilter.hh
b/src/mem/ruby/filters/MultiGrainBloomFilter.hh
index 148f42d..d45b587 100644
--- a/src/mem/ruby/filters/MultiGrainBloomFilter.hh
+++ b/src/mem/ruby/filters/MultiGrainBloomFilter.hh
@@ -46,8 +46,7 @@
void clear() override;
void set(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ int getCount(Addr addr) const override;
int getTotalCount() const override;
private:
diff --git a/src/mem/ruby/filters/NonCountingBloomFilter.cc
b/src/mem/ruby/filters/NonCountingBloomFilter.cc
index edfd03a..25841a3 100644
--- a/src/mem/ruby/filters/NonCountingBloomFilter.cc
+++ b/src/mem/ruby/filters/NonCountingBloomFilter.cc
@@ -31,7 +31,7 @@
#include "mem/ruby/system/RubySystem.hh"
NonCountingBloomFilter::NonCountingBloomFilter(std::size_t size, int
skip_bits)
- : AbstractBloomFilter(size), skipBits(skip_bits)
+ : AbstractBloomFilter(size, 1), skipBits(skip_bits)
{
}
@@ -61,15 +61,8 @@
filter[hash(addr)] = 0;
}
-bool
-NonCountingBloomFilter::isSet(Addr addr)
-{
- return filter[hash(addr)];
-}
-
-
int
-NonCountingBloomFilter::getCount(Addr addr)
+NonCountingBloomFilter::getCount(Addr addr) const
{
return filter[hash(addr)];
}
diff --git a/src/mem/ruby/filters/NonCountingBloomFilter.hh
b/src/mem/ruby/filters/NonCountingBloomFilter.hh
index 08c84ee..1553bec 100644
--- a/src/mem/ruby/filters/NonCountingBloomFilter.hh
+++ b/src/mem/ruby/filters/NonCountingBloomFilter.hh
@@ -41,8 +41,7 @@
void set(Addr addr) override;
void unset(Addr addr) override;
- bool isSet(Addr addr);
- int getCount(Addr addr);
+ int getCount(Addr addr) const override;
private:
int hash(Addr addr) const;
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/18735
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: If50b8c56065ad339b4ff2322ddc3c077a3bfc518
Gerrit-Change-Number: 18735
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
