diff options
Diffstat (limited to 'src/mem/ruby')
-rw-r--r-- | src/mem/ruby/filters/AbstractBloomFilter.hh | 18 | ||||
-rw-r--r-- | src/mem/ruby/filters/BlockBloomFilter.cc | 10 | ||||
-rw-r--r-- | src/mem/ruby/filters/BlockBloomFilter.hh | 4 | ||||
-rw-r--r-- | src/mem/ruby/filters/BulkBloomFilter.cc | 8 | ||||
-rw-r--r-- | src/mem/ruby/filters/BulkBloomFilter.hh | 4 | ||||
-rw-r--r-- | src/mem/ruby/filters/H3BloomFilter.cc | 24 | ||||
-rw-r--r-- | src/mem/ruby/filters/H3BloomFilter.hh | 3 | ||||
-rw-r--r-- | src/mem/ruby/filters/LSB_CountingBloomFilter.cc | 13 | ||||
-rw-r--r-- | src/mem/ruby/filters/LSB_CountingBloomFilter.hh | 3 | ||||
-rw-r--r-- | src/mem/ruby/filters/MultiBitSelBloomFilter.cc | 20 | ||||
-rw-r--r-- | src/mem/ruby/filters/MultiBitSelBloomFilter.hh | 3 | ||||
-rw-r--r-- | src/mem/ruby/filters/MultiGrainBloomFilter.cc | 16 | ||||
-rw-r--r-- | src/mem/ruby/filters/MultiGrainBloomFilter.hh | 3 | ||||
-rw-r--r-- | src/mem/ruby/filters/NonCountingBloomFilter.cc | 11 | ||||
-rw-r--r-- | src/mem/ruby/filters/NonCountingBloomFilter.hh | 3 |
15 files changed, 52 insertions, 91 deletions
diff --git a/src/mem/ruby/filters/AbstractBloomFilter.hh b/src/mem/ruby/filters/AbstractBloomFilter.hh index 851e5d9be..672236527 100644 --- a/src/mem/ruby/filters/AbstractBloomFilter.hh +++ b/src/mem/ruby/filters/AbstractBloomFilter.hh @@ -46,12 +46,18 @@ class AbstractBloomFilter /** 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(); } @@ -94,7 +100,11 @@ class AbstractBloomFilter * @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. @@ -102,7 +112,7 @@ class AbstractBloomFilter * @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 f9942fe71..f59a17547 100644 --- a/src/mem/ruby/filters/BlockBloomFilter.cc +++ b/src/mem/ruby/filters/BlockBloomFilter.cc @@ -32,7 +32,7 @@ #include "mem/ruby/system/RubySystem.hh" BlockBloomFilter::BlockBloomFilter(int size) - : AbstractBloomFilter(size) + : AbstractBloomFilter(size, 1) { } @@ -52,14 +52,8 @@ BlockBloomFilter::unset(Addr addr) 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 7c8ffc19c..fd75ba890 100644 --- a/src/mem/ruby/filters/BlockBloomFilter.hh +++ b/src/mem/ruby/filters/BlockBloomFilter.hh @@ -39,9 +39,7 @@ class BlockBloomFilter : public AbstractBloomFilter 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 a917a1491..251274bd6 100644 --- a/src/mem/ruby/filters/BulkBloomFilter.cc +++ b/src/mem/ruby/filters/BulkBloomFilter.cc @@ -32,7 +32,7 @@ #include "mem/ruby/system/RubySystem.hh" BulkBloomFilter::BulkBloomFilter(int size) - : AbstractBloomFilter(size), sectorBits(sizeBits - 1) + : AbstractBloomFilter(size, 1), sectorBits(sizeBits - 1) { } @@ -61,7 +61,7 @@ BulkBloomFilter::set(Addr addr) } bool -BulkBloomFilter::isSet(Addr addr) +BulkBloomFilter::isSet(Addr addr) const { // c0 contains the cache index bits const int filter_size = filter.size(); @@ -119,9 +119,9 @@ BulkBloomFilter::isSet(Addr addr) } 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 b6f52b960..7be00e673 100644 --- a/src/mem/ruby/filters/BulkBloomFilter.hh +++ b/src/mem/ruby/filters/BulkBloomFilter.hh @@ -45,8 +45,8 @@ class BulkBloomFilter : public AbstractBloomFilter 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 f6ee8a168..485cc3169 100644 --- a/src/mem/ruby/filters/H3BloomFilter.cc +++ b/src/mem/ruby/filters/H3BloomFilter.cc @@ -354,8 +354,8 @@ static int H3[64][16] = { }; 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 @@ H3BloomFilter::set(Addr addr) } } -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 6cfa29337..f92878b45 100644 --- a/src/mem/ruby/filters/H3BloomFilter.hh +++ b/src/mem/ruby/filters/H3BloomFilter.hh @@ -43,8 +43,7 @@ class H3BloomFilter : public AbstractBloomFilter 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 06e2d4f67..a718b4344 100644 --- a/src/mem/ruby/filters/LSB_CountingBloomFilter.cc +++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.cc @@ -33,7 +33,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) { } @@ -57,15 +59,8 @@ LSB_CountingBloomFilter::unset(Addr addr) 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 4fc635581..e9ffbcbd1 100644 --- a/src/mem/ruby/filters/LSB_CountingBloomFilter.hh +++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.hh @@ -40,8 +40,7 @@ class LSB_CountingBloomFilter : public AbstractBloomFilter 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 aa1438fd3..c453d10bf 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 @@ MultiBitSelBloomFilter::set(Addr addr) } } -bool -MultiBitSelBloomFilter::isSet(Addr addr) +int +MultiBitSelBloomFilter::getCount(Addr addr) const { - bool res = true; - + int count = 0; for (int i=0; i < numHashes; i++) { - int idx = hash(addr, i); - res = res && filter[idx]; + count += filter[hash(addr, i)]; } - return res; -} - -int -MultiBitSelBloomFilter::getCount(Addr addr) -{ - return isSet(addr)? 1: 0; + return count; } int diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh index 2d6954004..914875f85 100644 --- a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh +++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh @@ -40,8 +40,7 @@ class MultiBitSelBloomFilter : public AbstractBloomFilter 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 76016b2ff..7bf9dfe01 100644 --- a/src/mem/ruby/filters/MultiGrainBloomFilter.cc +++ b/src/mem/ruby/filters/MultiGrainBloomFilter.cc @@ -32,7 +32,7 @@ #include "mem/ruby/system/RubySystem.hh" MultiGrainBloomFilter::MultiGrainBloomFilter(int head, int tail) - : AbstractBloomFilter(head), + : AbstractBloomFilter(head, 2), pageFilter(tail), pageFilterSizeBits(floorLog2(tail)) { } @@ -61,21 +61,13 @@ MultiGrainBloomFilter::set(Addr addr) } -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 148f42df2..d45b58708 100644 --- a/src/mem/ruby/filters/MultiGrainBloomFilter.hh +++ b/src/mem/ruby/filters/MultiGrainBloomFilter.hh @@ -46,8 +46,7 @@ class MultiGrainBloomFilter : public AbstractBloomFilter 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 46e74d244..3196eb64f 100644 --- a/src/mem/ruby/filters/NonCountingBloomFilter.cc +++ b/src/mem/ruby/filters/NonCountingBloomFilter.cc @@ -32,7 +32,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) { } @@ -62,15 +62,8 @@ NonCountingBloomFilter::unset(Addr addr) 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 08c84ee7c..1553bec0b 100644 --- a/src/mem/ruby/filters/NonCountingBloomFilter.hh +++ b/src/mem/ruby/filters/NonCountingBloomFilter.hh @@ -41,8 +41,7 @@ class NonCountingBloomFilter : public AbstractBloomFilter 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; |