summaryrefslogtreecommitdiff
path: root/src/mem/ruby/filters/BulkBloomFilter.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/mem/ruby/filters/BulkBloomFilter.cc')
-rw-r--r--src/mem/ruby/filters/BulkBloomFilter.cc313
1 files changed, 163 insertions, 150 deletions
diff --git a/src/mem/ruby/filters/BulkBloomFilter.cc b/src/mem/ruby/filters/BulkBloomFilter.cc
index 264b4201c..1788c0391 100644
--- a/src/mem/ruby/filters/BulkBloomFilter.cc
+++ b/src/mem/ruby/filters/BulkBloomFilter.cc
@@ -1,4 +1,3 @@
-
/*
* Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
* All rights reserved.
@@ -27,206 +26,220 @@
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-/*
- * BulkBloomFilter.cc
- *
- * Description:
- *
- *
- */
-
-#include "mem/ruby/filters/BulkBloomFilter.hh"
#include "mem/gems_common/Map.hh"
#include "mem/ruby/common/Address.hh"
+#include "mem/ruby/filters/BulkBloomFilter.hh"
BulkBloomFilter::BulkBloomFilter(string str)
{
- string tail(str);
- string head = string_split(tail, '_');
+ string tail(str);
+ string head = string_split(tail, '_');
- m_filter_size = atoi(head.c_str());
- m_filter_size_bits = log_int(m_filter_size);
- // split the filter bits in half, c0 and c1
- m_sector_bits = m_filter_size_bits - 1;
+ m_filter_size = atoi(head.c_str());
+ m_filter_size_bits = log_int(m_filter_size);
+ // split the filter bits in half, c0 and c1
+ m_sector_bits = m_filter_size_bits - 1;
- m_temp_filter.setSize(m_filter_size);
- m_filter.setSize(m_filter_size);
- clear();
-
- // clear temp filter
- for(int i=0; i < m_filter_size; ++i){
- m_temp_filter[i] = 0;
- }
-}
-
-BulkBloomFilter::~BulkBloomFilter(){
+ m_temp_filter.setSize(m_filter_size);
+ m_filter.setSize(m_filter_size);
+ clear();
+ // clear temp filter
+ for (int i = 0; i < m_filter_size; ++i) {
+ m_temp_filter[i] = 0;
+ }
}
-void BulkBloomFilter::clear()
+BulkBloomFilter::~BulkBloomFilter()
{
- for (int i = 0; i < m_filter_size; i++) {
- m_filter[i] = 0;
- }
}
-void BulkBloomFilter::increment(const Address& addr)
+void
+BulkBloomFilter::clear()
{
- // Not used
+ for (int i = 0; i < m_filter_size; i++) {
+ m_filter[i] = 0;
+ }
}
-
-void BulkBloomFilter::decrement(const Address& addr)
+void
+BulkBloomFilter::increment(const Address& addr)
{
- // Not used
+ // Not used
}
-void BulkBloomFilter::merge(AbstractBloomFilter * other_filter)
+void
+BulkBloomFilter::decrement(const Address& addr)
{
- // TODO
+ // Not used
}
-void BulkBloomFilter::set(const Address& addr)
+void
+BulkBloomFilter::merge(AbstractBloomFilter * other_filter)
{
- // c0 contains the cache index bits
- int set_bits = m_sector_bits;
- int block_bits = RubySystem::getBlockSizeBits();
- int c0 = addr.bitSelect( block_bits, block_bits + set_bits - 1);
- // c1 contains the lower m_sector_bits permuted bits
- //Address permuted_bits = permute(addr);
- //int c1 = permuted_bits.bitSelect(0, set_bits-1);
- int c1 = addr.bitSelect( block_bits+set_bits, (block_bits+2*set_bits) - 1);
- //ASSERT(c0 < (m_filter_size/2));
- //ASSERT(c0 + (m_filter_size/2) < m_filter_size);
- //ASSERT(c1 < (m_filter_size/2));
- // set v0 bit
- m_filter[c0 + (m_filter_size/2)] = 1;
- // set v1 bit
- m_filter[c1] = 1;
+ // TODO
}
-void BulkBloomFilter::unset(const Address& addr)
+void
+BulkBloomFilter::set(const Address& addr)
+{
+ // c0 contains the cache index bits
+ int set_bits = m_sector_bits;
+ int block_bits = RubySystem::getBlockSizeBits();
+ int c0 = addr.bitSelect( block_bits, block_bits + set_bits - 1);
+ // c1 contains the lower m_sector_bits permuted bits
+ //Address permuted_bits = permute(addr);
+ //int c1 = permuted_bits.bitSelect(0, set_bits-1);
+ int c1 = addr.bitSelect( block_bits+set_bits, (block_bits+2*set_bits) - 1);
+ //ASSERT(c0 < (m_filter_size/2));
+ //ASSERT(c0 + (m_filter_size/2) < m_filter_size);
+ //ASSERT(c1 < (m_filter_size/2));
+ // set v0 bit
+ m_filter[c0 + (m_filter_size/2)] = 1;
+ // set v1 bit
+ m_filter[c1] = 1;
+}
+
+void
+BulkBloomFilter::unset(const Address& addr)
{
- // not used
+ // not used
}
-bool BulkBloomFilter::isSet(const Address& addr)
+bool
+BulkBloomFilter::isSet(const Address& addr)
{
- // c0 contains the cache index bits
- int set_bits = m_sector_bits;
- int block_bits = RubySystem::getBlockSizeBits();
- int c0 = addr.bitSelect( block_bits, block_bits + set_bits - 1);
- // c1 contains the lower 10 permuted bits
- //Address permuted_bits = permute(addr);
- //int c1 = permuted_bits.bitSelect(0, set_bits-1);
- int c1 = addr.bitSelect( block_bits+set_bits, (block_bits+2*set_bits) - 1);
- //ASSERT(c0 < (m_filter_size/2));
- //ASSERT(c0 + (m_filter_size/2) < m_filter_size);
- //ASSERT(c1 < (m_filter_size/2));
- // set v0 bit
- m_temp_filter[c0 + (m_filter_size/2)] = 1;
- // set v1 bit
- m_temp_filter[c1] = 1;
+ // c0 contains the cache index bits
+ int set_bits = m_sector_bits;
+ int block_bits = RubySystem::getBlockSizeBits();
+ int c0 = addr.bitSelect( block_bits, block_bits + set_bits - 1);
+ // c1 contains the lower 10 permuted bits
+ //Address permuted_bits = permute(addr);
+ //int c1 = permuted_bits.bitSelect(0, set_bits-1);
+ int c1 = addr.bitSelect( block_bits+set_bits, (block_bits+2*set_bits) - 1);
+ //ASSERT(c0 < (m_filter_size/2));
+ //ASSERT(c0 + (m_filter_size/2) < m_filter_size);
+ //ASSERT(c1 < (m_filter_size/2));
+ // set v0 bit
+ m_temp_filter[c0 + (m_filter_size/2)] = 1;
+ // set v1 bit
+ m_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 < m_filter_size/2; ++i){
+ // get intersection of signatures
+ m_temp_filter[i] = m_temp_filter[i] && m_filter[i];
+ zero = zero || m_temp_filter[i];
+ }
+ zero = !zero;
+ if (zero) {
+ // one section is zero, no possiblility of address in signature
+ // reset bits we just set
+ m_temp_filter[c0 + (m_filter_size / 2)] = 0;
+ m_temp_filter[c1] = 0;
+ return false;
+ }
- // 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 < m_filter_size/2; ++i){
- // get intersection of signatures
- m_temp_filter[i] = m_temp_filter[i] && m_filter[i];
- zero = zero || m_temp_filter[i];
- }
- zero = !zero;
- if(zero){
- // one section is zero, no possiblility of address in signature
- // reset bits we just set
- m_temp_filter[c0 + (m_filter_size/2)] = 0;
- m_temp_filter[c1] = 0;
- return false;
- }
-
- // check second section
- zero = false;
- for(int i=m_filter_size/2; i < m_filter_size; ++i){
- // get intersection of signatures
- m_temp_filter[i] = m_temp_filter[i] && m_filter[i];
- zero = zero || m_temp_filter[i];
- }
- zero = !zero;
- if(zero){
- // one section is zero, no possiblility of address in signature
- m_temp_filter[c0 + (m_filter_size/2)] = 0;
+ // check second section
+ zero = false;
+ for(int i = m_filter_size / 2; i < m_filter_size; ++i) {
+ // get intersection of signatures
+ m_temp_filter[i] = m_temp_filter[i] && m_filter[i];
+ zero = zero || m_temp_filter[i];
+ }
+ zero = !zero;
+ if (zero) {
+ // one section is zero, no possiblility of address in signature
+ m_temp_filter[c0 + (m_filter_size / 2)] = 0;
+ m_temp_filter[c1] = 0;
+ return false;
+ }
+ // one section has at least one bit set
+ m_temp_filter[c0 + (m_filter_size / 2)] = 0;
m_temp_filter[c1] = 0;
- return false;
- }
- // one section has at least one bit set
- m_temp_filter[c0 + (m_filter_size/2)] = 0;
- m_temp_filter[c1] = 0;
- return true;
+ return true;
}
-
-int BulkBloomFilter::getCount(const Address& addr)
+int
+BulkBloomFilter::getCount(const Address& addr)
{
- // not used
- return 0;
+ // not used
+ return 0;
}
-int BulkBloomFilter::getTotalCount()
+int
+BulkBloomFilter::getTotalCount()
{
- int count = 0;
- for (int i = 0; i < m_filter_size; i++) {
- if (m_filter[i]) {
- count++;
+ int count = 0;
+ for (int i = 0; i < m_filter_size; i++) {
+ if (m_filter[i]) {
+ count++;
+ }
}
- }
- return count;
+ return count;
}
-int BulkBloomFilter::getIndex(const Address& addr)
+int
+BulkBloomFilter::getIndex(const Address& addr)
{
- return get_index(addr);
+ return get_index(addr);
}
-int BulkBloomFilter::readBit(const int index) {
- return 0;
- // TODO
+int
+BulkBloomFilter::readBit(const int index)
+{
+ return 0;
+ // TODO
}
-void BulkBloomFilter::writeBit(const int index, const int value) {
- // TODO
+void
+BulkBloomFilter::writeBit(const int index, const int value)
+{
+ // TODO
}
-void BulkBloomFilter::print(ostream& out) const
+void
+BulkBloomFilter::print(ostream& out) const
{
}
-int BulkBloomFilter::get_index(const Address& addr)
+int
+BulkBloomFilter::get_index(const Address& addr)
{
- return addr.bitSelect( RubySystem::getBlockSizeBits(), RubySystem::getBlockSizeBits() + m_filter_size_bits - 1);
+ return addr.bitSelect(RubySystem::getBlockSizeBits(),
+ RubySystem::getBlockSizeBits() +
+ m_filter_size_bits - 1);
}
-Address BulkBloomFilter::permute(const Address & addr){
- // permutes the original address bits according to Table 5
- int block_offset = RubySystem::getBlockSizeBits();
- physical_address_t part1 = addr.bitSelect( block_offset, block_offset + 6 );
- physical_address_t part2 = addr.bitSelect( block_offset + 9, block_offset + 9 );
- physical_address_t part3 = addr.bitSelect( block_offset + 11, block_offset + 11 );
- physical_address_t part4 = addr.bitSelect( block_offset + 17, block_offset + 17 );
- physical_address_t part5 = addr.bitSelect( block_offset + 7, block_offset + 8 );
- physical_address_t part6 = addr.bitSelect( block_offset + 10, block_offset + 10 );
- physical_address_t part7 = addr.bitSelect( block_offset + 12, block_offset + 12 );
- physical_address_t part8 = addr.bitSelect( block_offset + 13, block_offset + 13 );
- physical_address_t part9 = addr.bitSelect( block_offset + 15, block_offset + 16 );
- physical_address_t part10 = addr.bitSelect( block_offset + 18, block_offset + 20 );
- physical_address_t part11 = addr.bitSelect( block_offset + 14, block_offset + 14 );
-
- physical_address_t result = (part1 << 14 ) | (part2 << 13 ) | (part3 << 12 ) | (part4 << 11 ) | (part5 << 9) | (part6 << 8)
- | (part7 << 7) | (part8 << 6) | (part9 << 4) | (part10 << 1) | (part11);
- // assume 32 bit addresses (both virtual and physical)
- // select the remaining high-order 11 bits
- physical_address_t remaining_bits = (addr.bitSelect( block_offset + 21, 31 )) << 21;
- result = result | remaining_bits;
-
- return Address(result);
+Address
+BulkBloomFilter::permute(const Address & addr)
+{
+ // permutes the original address bits according to Table 5
+ int block_offset = RubySystem::getBlockSizeBits();
+ physical_address_t part1 = addr.bitSelect(block_offset, block_offset + 6),
+ part2 = addr.bitSelect(block_offset + 9, block_offset + 9),
+ part3 = addr.bitSelect(block_offset + 11, block_offset + 11),
+ part4 = addr.bitSelect(block_offset + 17, block_offset + 17),
+ part5 = addr.bitSelect(block_offset + 7, block_offset + 8),
+ part6 = addr.bitSelect(block_offset + 10, block_offset + 10),
+ part7 = addr.bitSelect(block_offset + 12, block_offset + 12),
+ part8 = addr.bitSelect(block_offset + 13, block_offset + 13),
+ part9 = addr.bitSelect(block_offset + 15, block_offset + 16),
+ part10 = addr.bitSelect(block_offset + 18, block_offset + 20),
+ part11 = addr.bitSelect(block_offset + 14, block_offset + 14);
+
+ physical_address_t result =
+ (part1 << 14) | (part2 << 13) | (part3 << 12) | (part4 << 11) |
+ (part5 << 9) | (part6 << 8) | (part7 << 7) | (part8 << 6) |
+ (part9 << 4) | (part10 << 1) | (part11);
+
+ // assume 32 bit addresses (both virtual and physical)
+ // select the remaining high-order 11 bits
+ physical_address_t remaining_bits =
+ addr.bitSelect(block_offset + 21, 31) << 21;
+ result = result | remaining_bits;
+
+ return Address(result);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-16 15:58:36 +0000