BloomFilters.py revision 14263
114262Sodanrc@yahoo.com.br# Copyright (c) 2019 Inria 214262Sodanrc@yahoo.com.br# All rights reserved. 314262Sodanrc@yahoo.com.br# 414262Sodanrc@yahoo.com.br# Redistribution and use in source and binary forms, with or without 514262Sodanrc@yahoo.com.br# modification, are permitted provided that the following conditions are 614262Sodanrc@yahoo.com.br# met: redistributions of source code must retain the above copyright 714262Sodanrc@yahoo.com.br# notice, this list of conditions and the following disclaimer; 814262Sodanrc@yahoo.com.br# redistributions in binary form must reproduce the above copyright 914262Sodanrc@yahoo.com.br# notice, this list of conditions and the following disclaimer in the 1014262Sodanrc@yahoo.com.br# documentation and/or other materials provided with the distribution; 1114262Sodanrc@yahoo.com.br# neither the name of the copyright holders nor the names of its 1214262Sodanrc@yahoo.com.br# contributors may be used to endorse or promote products derived from 1314262Sodanrc@yahoo.com.br# this software without specific prior written permission. 1414262Sodanrc@yahoo.com.br# 1514262Sodanrc@yahoo.com.br# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1614262Sodanrc@yahoo.com.br# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1714262Sodanrc@yahoo.com.br# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1814262Sodanrc@yahoo.com.br# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1914262Sodanrc@yahoo.com.br# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2014262Sodanrc@yahoo.com.br# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2114262Sodanrc@yahoo.com.br# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2214262Sodanrc@yahoo.com.br# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2314262Sodanrc@yahoo.com.br# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2414262Sodanrc@yahoo.com.br# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2514262Sodanrc@yahoo.com.br# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2614262Sodanrc@yahoo.com.br# 2714262Sodanrc@yahoo.com.br# Authors: Daniel Carvalho 2814262Sodanrc@yahoo.com.br 2914262Sodanrc@yahoo.com.brfrom m5.params import * 3014262Sodanrc@yahoo.com.brfrom m5.proxy import * 3114262Sodanrc@yahoo.com.brfrom m5.SimObject import SimObject 3214262Sodanrc@yahoo.com.br 3314262Sodanrc@yahoo.com.brclass BloomFilterBase(SimObject): 3414262Sodanrc@yahoo.com.br type = 'BloomFilterBase' 3514262Sodanrc@yahoo.com.br abstract = True 3614262Sodanrc@yahoo.com.br cxx_header = "base/filters/base.hh" 3714262Sodanrc@yahoo.com.br cxx_class = 'BloomFilter::Base' 3814262Sodanrc@yahoo.com.br 3914262Sodanrc@yahoo.com.br size = Param.Int(4096, "Number of entries in the filter") 4014262Sodanrc@yahoo.com.br 4114262Sodanrc@yahoo.com.br # By default assume that bloom filters are used for 64-byte cache lines 4214262Sodanrc@yahoo.com.br offset_bits = Param.Unsigned(6, "Number of bits in a cache line offset") 4314262Sodanrc@yahoo.com.br 4414262Sodanrc@yahoo.com.br # Most of the filters are booleans, and thus saturate on 1 4514262Sodanrc@yahoo.com.br threshold = Param.Int(1, "Value at which an entry is considered as set") 4614262Sodanrc@yahoo.com.br 4714262Sodanrc@yahoo.com.brclass BloomFilterBlock(BloomFilterBase): 4814262Sodanrc@yahoo.com.br type = 'BloomFilterBlock' 4914262Sodanrc@yahoo.com.br cxx_class = 'BloomFilter::Block' 5014262Sodanrc@yahoo.com.br cxx_header = "base/filters/block_bloom_filter.hh" 5114262Sodanrc@yahoo.com.br 5214262Sodanrc@yahoo.com.br masks_lsbs = VectorParam.Unsigned([Self.offset_bits, 5314262Sodanrc@yahoo.com.br 2 * Self.offset_bits], "Position of the LSB of each mask") 5414262Sodanrc@yahoo.com.br masks_sizes = VectorParam.Unsigned([Self.offset_bits, Self.offset_bits], 5514262Sodanrc@yahoo.com.br "Size, in number of bits, of each mask") 5614262Sodanrc@yahoo.com.br 5714262Sodanrc@yahoo.com.brclass BloomFilterLSBCounting(BloomFilterBase): 5814262Sodanrc@yahoo.com.br type = 'BloomFilterLSBCounting' 5914262Sodanrc@yahoo.com.br cxx_class = 'BloomFilter::LSBCounting' 6014262Sodanrc@yahoo.com.br cxx_header = "base/filters/lsb_counting_bloom_filter.hh" 6114262Sodanrc@yahoo.com.br 6214262Sodanrc@yahoo.com.br # By default use 4-bit saturating counters 6314262Sodanrc@yahoo.com.br max_value = Param.Int(15, "Maximum value of the filter entries") 6414262Sodanrc@yahoo.com.br 6514262Sodanrc@yahoo.com.br # We assume that isSet will return true only when the counter saturates 6614262Sodanrc@yahoo.com.br threshold = Self.max_value 6714262Sodanrc@yahoo.com.br 6814262Sodanrc@yahoo.com.brclass BloomFilterMultiBitSel(BloomFilterBase): 6914262Sodanrc@yahoo.com.br type = 'BloomFilterMultiBitSel' 7014262Sodanrc@yahoo.com.br cxx_class = 'BloomFilter::MultiBitSel' 7114262Sodanrc@yahoo.com.br cxx_header = "base/filters/multi_bit_sel_bloom_filter.hh" 7214262Sodanrc@yahoo.com.br 7314262Sodanrc@yahoo.com.br num_hashes = Param.Int(4, "Number of hashes") 7414262Sodanrc@yahoo.com.br threshold = Self.num_hashes 7514262Sodanrc@yahoo.com.br skip_bits = Param.Int(2, "Offset from block number") 7614262Sodanrc@yahoo.com.br is_parallel = Param.Bool(False, "Whether hashing is done in parallel") 7714262Sodanrc@yahoo.com.br 7814263Sodanrc@yahoo.com.brclass BloomFilterBulk(BloomFilterMultiBitSel): 7914263Sodanrc@yahoo.com.br type = 'BloomFilterBulk' 8014263Sodanrc@yahoo.com.br cxx_class = 'BloomFilter::Bulk' 8114263Sodanrc@yahoo.com.br cxx_header = "base/filters/bulk_bloom_filter.hh" 8214263Sodanrc@yahoo.com.br 8314262Sodanrc@yahoo.com.brclass BloomFilterH3(BloomFilterMultiBitSel): 8414262Sodanrc@yahoo.com.br type = 'BloomFilterH3' 8514262Sodanrc@yahoo.com.br cxx_class = 'BloomFilter::H3' 8614262Sodanrc@yahoo.com.br cxx_header = "base/filters/h3_bloom_filter.hh" 8714262Sodanrc@yahoo.com.br 8814262Sodanrc@yahoo.com.brclass BloomFilterMulti(BloomFilterBase): 8914262Sodanrc@yahoo.com.br type = 'BloomFilterMulti' 9014262Sodanrc@yahoo.com.br cxx_class = 'BloomFilter::Multi' 9114262Sodanrc@yahoo.com.br cxx_header = "base/filters/multi_bloom_filter.hh" 9214262Sodanrc@yahoo.com.br 9314262Sodanrc@yahoo.com.br # The base filter should not be used, since this filter is the combination 9414262Sodanrc@yahoo.com.br # of multiple sub-filters, so we use a dummy value 9514262Sodanrc@yahoo.com.br size = 1 9614262Sodanrc@yahoo.com.br 9714262Sodanrc@yahoo.com.br # By default there are two sub-filters that hash sequential bitfields 9814262Sodanrc@yahoo.com.br filters = VectorParam.BloomFilterBase([ 9914262Sodanrc@yahoo.com.br BloomFilterBlock(size = 4096, masks_lsbs = [6, 12]), 10014262Sodanrc@yahoo.com.br BloomFilterBlock(size = 1024, masks_lsbs = [18, 24])], 10114262Sodanrc@yahoo.com.br "Sub-filters to be combined") 10214262Sodanrc@yahoo.com.br 10314262Sodanrc@yahoo.com.br # By default match this with the number of sub-filters 10414262Sodanrc@yahoo.com.br threshold = 2 105