diff options
Diffstat (limited to 'src/mem/ruby/filters/BulkBloomFilter.cc')
-rw-r--r-- | src/mem/ruby/filters/BulkBloomFilter.cc | 232 |
1 files changed, 232 insertions, 0 deletions
diff --git a/src/mem/ruby/filters/BulkBloomFilter.cc b/src/mem/ruby/filters/BulkBloomFilter.cc new file mode 100644 index 000000000..264b4201c --- /dev/null +++ b/src/mem/ruby/filters/BulkBloomFilter.cc @@ -0,0 +1,232 @@ + +/* + * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * 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" + +BulkBloomFilter::BulkBloomFilter(string str) +{ + 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_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(){ + +} + +void BulkBloomFilter::clear() +{ + for (int i = 0; i < m_filter_size; i++) { + m_filter[i] = 0; + } +} + +void BulkBloomFilter::increment(const Address& addr) +{ + // Not used +} + + +void BulkBloomFilter::decrement(const Address& addr) +{ + // Not used +} + +void BulkBloomFilter::merge(AbstractBloomFilter * other_filter) +{ + // TODO +} + +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 +} + +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; + + // 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; + 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; +} + + +int BulkBloomFilter::getCount(const Address& addr) +{ + // not used + return 0; +} + +int BulkBloomFilter::getTotalCount() +{ + int count = 0; + for (int i = 0; i < m_filter_size; i++) { + if (m_filter[i]) { + count++; + } + } + return count; +} + +int BulkBloomFilter::getIndex(const Address& addr) +{ + return get_index(addr); +} + +int BulkBloomFilter::readBit(const int index) { + return 0; + // TODO +} + +void BulkBloomFilter::writeBit(const int index, const int value) { + // TODO +} + +void BulkBloomFilter::print(ostream& out) const +{ +} + +int BulkBloomFilter::get_index(const Address& addr) +{ + 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); +} |