diff options
26 files changed, 532 insertions, 4657 deletions
diff --git a/src/mem/protocol/RubySlicc_Types.sm b/src/mem/protocol/RubySlicc_Types.sm index a948322dd..3f038031d 100644 --- a/src/mem/protocol/RubySlicc_Types.sm +++ b/src/mem/protocol/RubySlicc_Types.sm @@ -153,16 +153,4 @@ external_type(TimerTable, inport="yes") { bool isSet(Address); } -external_type(GenericBloomFilter) { - - void clear(int); - void increment(Address, int); - void decrement(Address, int); - void set(Address, int); - void unset(Address, int); - - bool isSet(Address, int); - int getCount(Address, int); -} - diff --git a/src/mem/ruby/SConscript b/src/mem/ruby/SConscript index 6ac7dad6a..5ad6bd08f 100644 --- a/src/mem/ruby/SConscript +++ b/src/mem/ruby/SConscript @@ -103,7 +103,6 @@ MakeInclude('slicc_interface/Message.hh') MakeInclude('slicc_interface/NetworkMessage.hh') MakeInclude('system/CacheMemory.hh') MakeInclude('system/DirectoryMemory.hh') -MakeInclude('system/GenericBloomFilter.hh') MakeInclude('system/MachineID.hh') MakeInclude('system/MemoryControl.hh') MakeInclude('system/NodeID.hh') diff --git a/src/mem/ruby/common/BigSet.cc b/src/mem/ruby/common/BigSet.cc deleted file mode 100644 index f55d7b79c..000000000 --- a/src/mem/ruby/common/BigSet.cc +++ /dev/null @@ -1,249 +0,0 @@ - -/* - * 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. - */ - -#include "mem/ruby/common/Set.hh" -#include "mem/ruby/config/RubyConfig.hh" - -Set::Set() -{ - setSize(RubyConfig::numberOfProcessors()); -} - -Set::Set(int size) -{ - setSize(size); -} - -void Set::add(NodeID index) -{ - m_bits[index] = Present; -} - -void Set::addSet(const Set& set) -{ - assert(m_bits.size() == set.getSize()); - for (int i=0; i<m_bits.size(); i++) { - if(set.isElement(i)){ - add(i); - } - } -} - -void Set::addRandom() -{ - int rand = random(); - for (int i=0; i<m_bits.size(); i++) { - if(rand & 0x1 == 0) { // Look at the low order bit - add(i); - } - rand = (rand >> 1); // Shift the random number to look at the next bit - } -} - -void Set::remove(NodeID index) -{ - m_bits[index] = NotPresent; -} - -void Set::removeSet(const Set& set) -{ - assert(m_bits.size() == set.getSize()); - for (int i=0; i<m_bits.size(); i++) { - if(set.isElement(i)){ - remove(i); - } - } -} - -void Set::clear() -{ - for (int i=0; i<m_bits.size(); i++) { - m_bits[i] = NotPresent; - } -} - -void Set::broadcast() -{ - for (int i=0; i<m_bits.size(); i++) { - m_bits[i] = Present; - } -} - -int Set::count() const -{ - int counter = 0; - for (int i=0; i<m_bits.size(); i++) { - if (m_bits[i] == Present) { - counter++; - } - } - return counter; -} - -bool Set::isEqual(const Set& set) const -{ - assert(m_bits.size() == set.getSize()); - for (int i=0; i<m_bits.size(); i++) { - if (m_bits[i] != set.isElement(i)) { - return false; - } - } - return true; -} - -NodeID Set::smallestElement() const -{ - assert(count() > 0); - for (int i=0; i<m_bits.size(); i++) { - if (isElement(i)) { - return i; - } - } - ERROR_MSG("No smallest element of an empty set."); -} - -// Returns true iff all bits are set -bool Set::isBroadcast() const -{ - for (int i=0; i<m_bits.size(); i++) { - if (m_bits[i] == NotPresent) { - return false; - } - } - return true; -} - -// Returns true iff no bits are set -bool Set::isEmpty() const -{ - for (int i=0; i<m_bits.size(); i++) { - if (m_bits[i] == Present) { - return false; - } - } - return true; -} - -// returns the logical OR of "this" set and orSet -Set Set::OR(const Set& orSet) const -{ - Set result; - assert(m_bits.size() == orSet.getSize()); - result.setSize(m_bits.size()); - for (int i=0; i<m_bits.size(); i++) { - if(m_bits[i] == Present || orSet.isElement(i)){ - result.add(i); - }else{ - result.remove(i); - } - } - - return result; - -} - -// returns the logical AND of "this" set and andSet -Set Set::AND(const Set& andSet) const -{ - Set result; - assert(m_bits.size() == andSet.getSize()); - result.setSize(m_bits.size()); - for (int i=0; i<m_bits.size(); i++) { - if(m_bits[i] == Present && andSet.isElement(i)){ - result.add(i); - }else{ - result.remove(i); - } - } - return result; -} - -// Returns true if the intersection of the two sets is non-empty -bool Set::intersectionIsNotEmpty(const Set& other_set) const -{ - assert(m_bits.size() == other_set.getSize()); - for(int index=0; index < m_bits.size(); index++){ - if(other_set.isElement(index) && isElement(index)) { - return true; - } - } - return false; -} - -// Returns true if the intersection of the two sets is non-empty -bool Set::intersectionIsEmpty(const Set& other_set) const -{ - assert(m_bits.size() == other_set.getSize()); - for(int index=0; index < m_bits.size(); index++){ - if(other_set.isElement(index) && isElement(index)) { - return false; - } - } - return true; -} - -bool Set::isSuperset(const Set& test) const -{ - assert(m_bits.size() == test.getSize()); - for(int index=0; index < m_bits.size(); index++){ - if(test.isElement(index) && !isElement(index)) { - return false; - } - } - return true; -} - -bool Set::isElement(NodeID element) const -{ - return (m_bits[element] == Present); -} - -NodeID Set::elementAt(int index) const -{ - if (m_bits[index] == Present) { - return m_bits[index] == Present; - } else { - return 0; - } -} - -void Set::setSize(int size) -{ - m_bits.setSize(size); - clear(); -} - -void Set::print(ostream& out) const -{ - out << "[Set "; - for (int i=0; i<m_bits.size(); i++) { - out << (bool)m_bits[i] << " "; - } - out << "]"; -} diff --git a/src/mem/ruby/common/BigSet.hh b/src/mem/ruby/common/BigSet.hh deleted file mode 100644 index 06ee6a66d..000000000 --- a/src/mem/ruby/common/BigSet.hh +++ /dev/null @@ -1,125 +0,0 @@ - -/* - * 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. - */ - -// NOTE: Never include this file directly, this should only be -// included from Set.h - -#ifndef SET_H -#define SET_H - -#include "mem/ruby/common/Global.hh" -#include "mem/gems_common/Vector.hh" -#include "mem/ruby/system/NodeID.hh" -#include "mem/ruby/config/RubyConfig.hh" - -enum PresenceBit {NotPresent, Present}; - -class Set { -public: - // Constructors - // creates and empty set - Set(); - Set (int size); - - // used during the replay mechanism - // Set(const char *str); - - // Set(const Set& obj); - // Set& operator=(const Set& obj); - - // Destructor - // ~Set(); - - // Public Methods - - void add(NodeID newElement); - void addSet(const Set& set); - void addRandom(); - void remove(NodeID newElement); - void removeSet(const Set& set); - void clear(); - void broadcast(); - int count() const; - bool isEqual(const Set& set) const; - - Set OR(const Set& orSet) const; // return the logical OR of this set and orSet - Set AND(const Set& andSet) const; // return the logical AND of this set and andSet - - // Returns true if the intersection of the two sets is non-empty - bool intersectionIsNotEmpty(const Set& other_set) const; - - // Returns true if the intersection of the two sets is empty - bool intersectionIsEmpty(const Set& other_set) const; - - bool isSuperset(const Set& test) const; - bool isSubset(const Set& test) const { return test.isSuperset(*this); } - bool isElement(NodeID element) const; - bool isBroadcast() const; - bool isEmpty() const; - - NodeID smallestElement() const; - - // int size() const; - void setSize (int size); - - // get element for a index - NodeID elementAt(int index) const; - int getSize() const { return m_bits.size(); } - - // DEPRECATED METHODS - void addToSet(NodeID newElement) { add(newElement); } // Deprecated - void removeFromSet(NodeID newElement) { remove(newElement); } // Deprecated - void clearSet() { clear(); } // Deprecated - void setBroadcast() { broadcast(); } // Deprecated - bool presentInSet(NodeID element) const { return isElement(element); } // Deprecated - - void print(ostream& out) const; -private: - // Private Methods - - // Data Members (m_ prefix) - Vector<uint8> m_bits; // This is an vector of uint8 to reduce the size of the set -}; - -// Output operator declaration -ostream& operator<<(ostream& out, const Set& obj); - -// ******************* Definitions ******************* - -// Output operator definition -extern inline -ostream& operator<<(ostream& out, const Set& obj) -{ - obj.print(out); - out << flush; - return out; -} - -#endif //SET_H - diff --git a/src/mem/ruby/common/OptBigSet.cc b/src/mem/ruby/common/OptBigSet.cc deleted file mode 100644 index b4c4e4789..000000000 --- a/src/mem/ruby/common/OptBigSet.cc +++ /dev/null @@ -1,576 +0,0 @@ - -/* - * 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. - */ - -/* - * Set.C - * - * Description: See Set.h - * - * $Id: BigSet.C 1.9 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $ - * - */ - -// modified (rewritten) 05/20/05 by Dan Gibson to accomimdate FASTER >32 bit -// set sizes - -#include "mem/ruby/common/Set.hh" -#include "mem/ruby/config/RubyConfig.hh" - -#if __amd64__ || __LP64__ -#define __64BITS__ -#else -#define __32BITS__ -#endif - -Set::Set() -{ - m_p_nArray = NULL; - setSize(RubyConfig::numberOfProcessors()); -} - -// copy constructor -Set::Set(const Set& obj) { - m_p_nArray = NULL; - setSize(obj.m_nSize); - - // copy from the host to this array - for(int i=0; i<m_nArrayLen; i++) { - m_p_nArray[i] = obj.m_p_nArray[i]; - } - -} - -Set::Set(int size) -{ - m_p_nArray = NULL; - assert(size>0); - setSize(size); -} - -Set::~Set() { - if( (m_p_nArray != (&m_p_nArray_Static[0])) && (m_p_nArray != NULL)) - delete [] m_p_nArray; - m_p_nArray = NULL; -} - - -// /* -// * This function should set the bit corresponding to index -// * to 1. -// */ - -// void Set::add(NodeID index) -// { -// assert(index<m_nSize && index >= 0); - -// #ifdef __32BITS__ -// m_p_nArray[index>>5] |= (1 << (index & 0x01F)); -// #else -// m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F)); -// #endif // __32BITS__ - -// } - -/* - * This function should set all the bits in the current set - * that are already set in the parameter set - */ -void Set::addSet(const Set& set) -{ - assert(getSize()==set.getSize()); - for(int i=0; i<m_nArrayLen; i++) { - m_p_nArray[i] |= set.m_p_nArray[i]; - } - -} - -/* - * This function should randomly assign 1 to the bits in the set-- - * it should not clear the bits bits first, though? - */ -void Set::addRandom() -{ - - for(int i=0; i<m_nArrayLen; i++) { - m_p_nArray[i] |= random() ^ (random() << 4); // this ensures that all 32 bits are subject to random effects, - // as RAND_MAX typically = 0x7FFFFFFF - } - - // now just ensure that no bits over the maximum size were set -#ifdef __32BITS__ - long mask = 0x7FFFFFFF; - - // the number of populated spaces in the higest-order array slot is: - // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be - // cleared - - if((m_nSize % 32) != 0) { - for(int j=0; j<32-(m_nSize&0x01F); j++) { - m_p_nArray[m_nArrayLen-1] &= mask; - mask = mask >> 1; - } - } -#else - long mask = 0x7FFFFFFFFFFFFFFF; - - // the number of populated spaces in the higest-order array slot is: - // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be - // cleared - - if((m_nSize % 64) != 0) { - for(int j=0; j<64-(m_nSize&0x03F); j++) { - m_p_nArray[m_nArrayLen-1] &= mask; - mask = mask >> 1; - } - } -#endif // __32BITS__ - -} - -// /* -// * This function unsets the bit associated with index -// */ -// void Set::remove(NodeID index) -// { -// assert(index<m_nSize && index>=0); - -// #ifdef __32BITS__ -// m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F)); -// #else -// m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F)); -// #endif // __32BITS__ - -// } - - -/* - * This function clears bits that are =1 in the parameter set - */ -void Set::removeSet(const Set& set) -{ - - assert(m_nSize==set.m_nSize); - for(int i=0; i<m_nArrayLen; i++) { - m_p_nArray[i] &= ~(set.m_p_nArray[i]); - } - -} - -// /* -// * This function clears all bits in the set -// */ -// void Set::clear() -// { -// for(int i=0; i<m_nArrayLen; i++) { -// m_p_nArray[i] = 0; -// } -// } - -/* - * this function sets all bits in the set - */ -void Set::broadcast() -{ - - for(int i=0; i<m_nArrayLen; i++) { - m_p_nArray[i] = -1; // note that -1 corresponds to all 1's in 2's comp. - } - - // now just ensure that no bits over the maximum size were set -#ifdef __32BITS__ - long mask = 0x7FFFFFFF; - - // the number of populated spaces in the higest-order array slot is: - // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be - // cleared - - if((m_nSize % 32) != 0) { - for(int j=0; j<32-(m_nSize&0x01F); j++) { - m_p_nArray[m_nArrayLen-1] &= mask; - mask = mask >> 1; - } - } -#else - long mask = 0x7FFFFFFFFFFFFFFF; - - // the number of populated spaces in the higest-order array slot is: - // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be - // cleared - - if((m_nSize % 64) != 0) { - for(int j=0; j<64-(m_nSize&0x03F); j++) { - m_p_nArray[m_nArrayLen-1] &= mask; - mask = mask >> 1; - } - } -#endif // __32BITS__ - -} - -/* - * This function returns the population count of 1's in the set - */ -int Set::count() const -{ - int counter = 0; - long mask; - for( int i=0; i<m_nArrayLen; i++) { - mask = (long) 0x01; - -#ifdef __32BITS__ - for( int j=0; j<32; j++) { - if(m_p_nArray[i] & mask) counter++; - mask = mask << 1; - } - -#else - - for( int j=0; j<64; j++) { // FIXME - significant performance loss when array population << 64 - if((m_p_nArray[i] & mask) != 0) { - counter++; - } - mask = mask << 1; - } - -#endif // __32BITS__ - - } - - return counter; -} - -/* - * This function checks for set equality - */ - -bool Set::isEqual(const Set& set) const -{ - assert(m_nSize==set.m_nSize); - - for(int i=0;i<m_nArrayLen;i++) { - if(m_p_nArray[i] != set.m_p_nArray[i]) { - return false; - } - } - - return true; -} - -/* - * This function returns the NodeID (int) of the - * least set bit - */ -NodeID Set::smallestElement() const -{ - assert(count() > 0); - long x; - for( int i=0; i<m_nArrayLen; i++) { - if(m_p_nArray[i]!=0) { - // the least-set bit must be in here - x = m_p_nArray[i]; - -#ifdef __32BITS__ - for( int j=0; j<32; j++) { - if(x & 0x00000001) { - return 32*i+j; - } - - x = x >> 1; - } -#else - for( int j=0; j<64; j++) { - if(x & 0x0000000000000001) { - return 64*i+j; - } - - x = x >> 1; - } -#endif // __32BITS__ - - ERROR_MSG("No smallest element of an empty set."); - } - } - - ERROR_MSG("No smallest element of an empty set."); - - return 0; -} - -/* - * this function returns true iff all bits are set - */ -bool Set::isBroadcast() const -{ - // check the fully-loaded words by equal to 0xffffffff - // only the last word may not be fully loaded, it is not - // fully loaded iff m_nSize % 32 or 64 !=0 => fully loaded iff - // m_nSize % 32 or 64 == 0 - -#ifdef __32BITS__ - for(int i=0; i< (((m_nSize % 32)==0) ? m_nArrayLen : m_nArrayLen-1); i++) { - if(m_p_nArray[i]!=-1) { - return false; - } - } - - // now check the last word, which may not be fully loaded - long mask = 1; - for(int j=0; j< (m_nSize % 32); j++) { - if((mask & m_p_nArray[m_nArrayLen-1])==0) { - return false; - } - mask = mask << 1; - } -#else - for(int i=0; i< (((m_nSize % 64)==0) ? m_nArrayLen : m_nArrayLen-1); i++) { - if(m_p_nArray[i]!=-1) { - return false; - } - } - - // now check the last word, which may not be fully loaded - long mask = 1; - for(int j=0; j< (m_nSize % 64); j++) { - if((mask & m_p_nArray[m_nArrayLen-1])==0) { - return false; - } - mask = mask << 1; - } - -#endif // __32BITS__ - - return true; -} - -/* - * this function returns true iff no bits are set - */ -bool Set::isEmpty() const -{ - - // here we can simply check if all = 0, since we ensure - // that "extra slots" are all zero - for(int i=0; i< m_nArrayLen ; i++) { - if(m_p_nArray[i]!=0) { - return false; - } - } - - return true; -} - -// returns the logical OR of "this" set and orSet -Set Set::OR(const Set& orSet) const -{ - Set result(m_nSize); - assert(m_nSize == orSet.m_nSize); - for(int i=0; i< m_nArrayLen; i++) { - result.m_p_nArray[i] = m_p_nArray[i] | orSet.m_p_nArray[i]; - } - - return result; - -} - -// returns the logical AND of "this" set and andSet -Set Set::AND(const Set& andSet) const -{ - Set result(m_nSize); - assert(m_nSize == andSet.m_nSize); - - for(int i=0; i< m_nArrayLen; i++) { - result.m_p_nArray[i] = m_p_nArray[i] & andSet.m_p_nArray[i]; - } - - return result; -} - -// // Returns true if the intersection of the two sets is non-empty -// bool Set::intersectionIsNotEmpty(const Set& other_set) const -// { -// assert(m_nSize == other_set.m_nSize); -// for(int i=0; i< m_nArrayLen; i++) { -// if(m_p_nArray[i] & other_set.m_p_nArray[i]) { -// return true; -// } -// } - -// return false; - -// } - -// // Returns true if the intersection of the two sets is empty -// bool Set::intersectionIsEmpty(const Set& other_set) const -// { -// assert(m_nSize == other_set.m_nSize); -// for(int i=0; i< m_nArrayLen; i++) { -// if(m_p_nArray[i] & other_set.m_p_nArray[i]) { -// return false; -// } -// } - -// return true; - -// } - -/* - * Returns false if a bit is set in the parameter set that is - * NOT set in this set - */ -bool Set::isSuperset(const Set& test) const -{ - assert(m_nSize == test.m_nSize); - - for(int i=0;i<m_nArrayLen;i++) { - if(((test.m_p_nArray[i] & m_p_nArray[i]) | ~test.m_p_nArray[i]) != -1) { - return false; - } - } - - return true; -} - -// /* -// * Returns true iff this bit is set -// */ -// bool Set::isElement(NodeID element) const -// { -// bool result; - -// #ifdef __32BITS__ -// result = ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0); -// #else -// result = ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0); -// #endif // __32BITS__ - -// return result; -// } - -/* - * "Supposed" to return the node id of the (n+1)th set - * bit, IE n=0 => returns nodeid of first set bit, BUT - * since BigSet.C behaves strangely, this implementation - * will behave strangely just for reverse compatability. - * - * Was originally implemented for the flight data recorder - * FDR - */ - -// NodeID Set::elementAt(int n) const -// { -// if(isElement(n)) return (NodeID) true; -// else return 0; - -// /* -// int match = -1; -// for(int i=0;i<m_nSize;i++) { -// if(isElement(i)) match++; -// if(match==n) { -// return i; -// } -// } - -// return -1; -// */ -// } - -void Set::setSize(int size) -{ - m_nSize = size; - -#ifdef __32BITS__ - m_nArrayLen = m_nSize/32 + ((m_nSize%32==0) ? 0 : 1 ); -#else - m_nArrayLen = m_nSize/64 + ((m_nSize%64==0) ? 0 : 1 ); -#endif // __32BITS__ - - // decide whether to use dynamic or static alloction - if(m_nArrayLen<=NUMBER_WORDS_PER_SET) { // constant defined in RubyConfig.h - // its OK to use the static allocation, and it will - // probably be faster (as m_nArrayLen is already in the - // cache and they will probably share the same cache line) - - // if switching from dyanamic to static allocation (which - // is probably rare, but why not be complete?), must delete - // the dynamically allocated space - if((m_p_nArray != NULL) && (m_p_nArray != &m_p_nArray_Static[0])) - delete [] m_p_nArray; - - m_p_nArray = & m_p_nArray_Static[0]; - } else { - - // can't use static allocation...simply not enough room - // so dynamically allocate some space - if((m_p_nArray != NULL) && (m_p_nArray != &m_p_nArray_Static[0])) - delete [] m_p_nArray; - - m_p_nArray = new long[m_nArrayLen]; - } - - clear(); -} - -Set& Set::operator=(const Set& obj) { - if(this == &obj) { - // do nothing - } else { - - // resize this item - setSize(obj.getSize()); - - // copy the elements from obj to this - for(int i=0; i<m_nArrayLen; i++) { - m_p_nArray[i] = obj.m_p_nArray[i]; - } - } - - return *this; -} - -void Set::print(ostream& out) const -{ - if(m_p_nArray==NULL) { - out << "[Set {Empty}]"; - return; - } - char buff[24]; - out << "[Set 0x "; - for (int i=m_nArrayLen-1; i>=0; i--) { -#ifdef __32BITS__ - sprintf(buff,"%08X ",m_p_nArray[i]); -#else - sprintf(buff,"0x %016llX ",m_p_nArray[i]); -#endif // __32BITS__ - out << buff; - } - out << " ]"; - -} - - diff --git a/src/mem/ruby/common/OptBigSet.hh b/src/mem/ruby/common/OptBigSet.hh deleted file mode 100644 index 45f06e6aa..000000000 --- a/src/mem/ruby/common/OptBigSet.hh +++ /dev/null @@ -1,202 +0,0 @@ - -/* - * 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. - */ - -/* - * Set.h - * - * Description: - * - * $Id: BigSet.h 1.6 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $ - * - */ - -// modified by Dan Gibson on 05/20/05 to accomidate FASTER -// >32 set lengths, using an array of ints w/ 32 bits/int - -// NOTE: Never include this file directly, this should only be -// included from Set.h - -#ifndef SET_H -#define SET_H - -#include "mem/ruby/common/Global.hh" -#include "mem/gems_common/Vector.hh" -#include "mem/ruby/system/NodeID.hh" -#include "mem/ruby/config/RubyConfig.hh" - -// gibson 05/20/05 -// enum PresenceBit {NotPresent, Present}; - -class Set { -public: - // Constructors - // creates and empty set - Set(); - Set (int size); - - // used during the replay mechanism - // Set(const char *str); - - Set(const Set& obj); - Set& operator=(const Set& obj); - - // Destructor - ~Set(); - - // Public Methods - - inline void add(NodeID index) - { -#ifdef __32BITS__ - m_p_nArray[index>>5] |= (1 << (index & 0x01F)); -#else - m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F)); -#endif // __32BITS__ - } - - void addSet(const Set& set); - void addRandom(); - - inline void remove(NodeID index) - { -#ifdef __32BITS__ - m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F)); -#else - m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F)); -#endif // __32BITS__ - } - - - void removeSet(const Set& set); - - inline void clear() { for(int i=0; i<m_nArrayLen; i++) m_p_nArray[i] = 0; } - - void broadcast(); - int count() const; - bool isEqual(const Set& set) const; - - Set OR(const Set& orSet) const; // return the logical OR of this set and orSet - Set AND(const Set& andSet) const; // return the logical AND of this set and andSet - - // Returns true if the intersection of the two sets is non-empty - inline bool intersectionIsNotEmpty(const Set& other_set) const - { - for(int i=0; i< m_nArrayLen; i++) { - if(m_p_nArray[i] & other_set.m_p_nArray[i]) { - return true; - } - } - return false; - } - - // Returns true if the intersection of the two sets is empty - inline bool intersectionIsEmpty(const Set& other_set) const - { - for(int i=0; i< m_nArrayLen; i++) { - if(m_p_nArray[i] & other_set.m_p_nArray[i]) { - return false; - } - } - return true; - } - - bool isSuperset(const Set& test) const; - bool isSubset(const Set& test) const { return test.isSuperset(*this); } - - inline bool isElement(NodeID element) const - { -#ifdef __32BITS__ - return ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0); -#else - return ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0); -#endif // __32BITS__ - - } - - bool isBroadcast() const; - bool isEmpty() const; - - NodeID smallestElement() const; - - // int size() const; - void setSize (int size); - - // get element for a index - inline NodeID elementAt(int index) const - { - if(isElement(index)) return (NodeID) true; - else return 0; - } - - // gibson 05/20/05 - int getSize() const { return m_nSize; } - - // DEPRECATED METHODS - void addToSet(NodeID newElement) { add(newElement); } // Deprecated - void removeFromSet(NodeID newElement) { remove(newElement); } // Deprecated - void clearSet() { clear(); } // Deprecated - void setBroadcast() { broadcast(); } // Deprecated - bool presentInSet(NodeID element) const { return isElement(element); } // Deprecated - - void print(ostream& out) const; -private: - // Private Methods - - // Data Members (m_ prefix) - // gibson 05/20/05 - // Vector<uint8> m_bits; // This is an vector of uint8 to reduce the size of the set - - int m_nSize; // the number of bits in this set - int m_nArrayLen; // the number of 32-bit words that are held in the array - - // Changed 5/24/05 for static allocation of array - // note that "long" corresponds to 32 bits on a 32-bit machine, - // 64 bits if the -m64 parameter is passed to g++, which it is - // for an AMD opteron under our configuration - - long * m_p_nArray; // an word array to hold the bits in the set - long m_p_nArray_Static[NUMBER_WORDS_PER_SET]; -}; - -// Output operator declaration -ostream& operator<<(ostream& out, const Set& obj); - -// ******************* Definitions ******************* - -// Output operator definition -extern inline -ostream& operator<<(ostream& out, const Set& obj) -{ - obj.print(out); - out << flush; - return out; -} - -#endif //SET_H - diff --git a/src/mem/ruby/common/Set.cc b/src/mem/ruby/common/Set.cc index ce4b4af04..b4c4e4789 100644 --- a/src/mem/ruby/common/Set.cc +++ b/src/mem/ruby/common/Set.cc @@ -32,200 +32,545 @@ * * Description: See Set.h * - * $Id$ + * $Id: BigSet.C 1.9 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $ * */ +// modified (rewritten) 05/20/05 by Dan Gibson to accomimdate FASTER >32 bit +// set sizes + #include "mem/ruby/common/Set.hh" #include "mem/ruby/config/RubyConfig.hh" -#ifdef OPTBIGSET -#include "OptBigSet.cc" -#else - -#ifdef BIGSET -#include "BigSet.cc" // code to supports sets larger than 32 +#if __amd64__ || __LP64__ +#define __64BITS__ #else +#define __32BITS__ +#endif Set::Set() { - setSize(RubyConfig::numberOfChips()); + m_p_nArray = NULL; + setSize(RubyConfig::numberOfProcessors()); +} + +// copy constructor +Set::Set(const Set& obj) { + m_p_nArray = NULL; + setSize(obj.m_nSize); + + // copy from the host to this array + for(int i=0; i<m_nArrayLen; i++) { + m_p_nArray[i] = obj.m_p_nArray[i]; + } + } Set::Set(int size) { + m_p_nArray = NULL; + assert(size>0); setSize(size); } -bool Set::isEqual(const Set& set) -{ - return (m_bits == set.m_bits); +Set::~Set() { + if( (m_p_nArray != (&m_p_nArray_Static[0])) && (m_p_nArray != NULL)) + delete [] m_p_nArray; + m_p_nArray = NULL; } -void Set::add(NodeID index) -{ - assert((m_bits & m_mask) == m_bits); // check for any bits outside the range - assert(index < m_size); - m_bits |= (1 << index); - assert((m_bits & m_mask) == m_bits); // check for any bits outside the range -} +// /* +// * This function should set the bit corresponding to index +// * to 1. +// */ + +// void Set::add(NodeID index) +// { +// assert(index<m_nSize && index >= 0); + +// #ifdef __32BITS__ +// m_p_nArray[index>>5] |= (1 << (index & 0x01F)); +// #else +// m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F)); +// #endif // __32BITS__ + +// } + +/* + * This function should set all the bits in the current set + * that are already set in the parameter set + */ void Set::addSet(const Set& set) { - assert(m_size == set.m_size); - m_bits |= set.m_bits; - assert((m_bits & m_mask) == m_bits); // check for any bits outside the range + assert(getSize()==set.getSize()); + for(int i=0; i<m_nArrayLen; i++) { + m_p_nArray[i] |= set.m_p_nArray[i]; + } + } +/* + * This function should randomly assign 1 to the bits in the set-- + * it should not clear the bits bits first, though? + */ void Set::addRandom() { - m_bits |= random(); - m_bits &= m_mask; - assert((m_bits & m_mask) == m_bits); // check for any bits outside the range -} -void Set::remove(NodeID index) -{ - assert(index < m_size); - m_bits &= ~(1 << index); - assert((m_bits & m_mask) == m_bits); // check for any bits outside the range + for(int i=0; i<m_nArrayLen; i++) { + m_p_nArray[i] |= random() ^ (random() << 4); // this ensures that all 32 bits are subject to random effects, + // as RAND_MAX typically = 0x7FFFFFFF + } + + // now just ensure that no bits over the maximum size were set +#ifdef __32BITS__ + long mask = 0x7FFFFFFF; + + // the number of populated spaces in the higest-order array slot is: + // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be + // cleared + + if((m_nSize % 32) != 0) { + for(int j=0; j<32-(m_nSize&0x01F); j++) { + m_p_nArray[m_nArrayLen-1] &= mask; + mask = mask >> 1; + } + } +#else + long mask = 0x7FFFFFFFFFFFFFFF; + + // the number of populated spaces in the higest-order array slot is: + // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be + // cleared + + if((m_nSize % 64) != 0) { + for(int j=0; j<64-(m_nSize&0x03F); j++) { + m_p_nArray[m_nArrayLen-1] &= mask; + mask = mask >> 1; + } + } +#endif // __32BITS__ + } +// /* +// * This function unsets the bit associated with index +// */ +// void Set::remove(NodeID index) +// { +// assert(index<m_nSize && index>=0); + +// #ifdef __32BITS__ +// m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F)); +// #else +// m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F)); +// #endif // __32BITS__ + +// } + + +/* + * This function clears bits that are =1 in the parameter set + */ void Set::removeSet(const Set& set) { - assert(m_size == set.m_size); - m_bits &= ~(set.m_bits); - assert((m_bits & m_mask) == m_bits); // check for any bits outside the range -} -void Set::clear() -{ - m_bits = 0; + assert(m_nSize==set.m_nSize); + for(int i=0; i<m_nArrayLen; i++) { + m_p_nArray[i] &= ~(set.m_p_nArray[i]); + } + } +// /* +// * This function clears all bits in the set +// */ +// void Set::clear() +// { +// for(int i=0; i<m_nArrayLen; i++) { +// m_p_nArray[i] = 0; +// } +// } + +/* + * this function sets all bits in the set + */ void Set::broadcast() { - m_bits = m_mask; + + for(int i=0; i<m_nArrayLen; i++) { + m_p_nArray[i] = -1; // note that -1 corresponds to all 1's in 2's comp. + } + + // now just ensure that no bits over the maximum size were set +#ifdef __32BITS__ + long mask = 0x7FFFFFFF; + + // the number of populated spaces in the higest-order array slot is: + // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be + // cleared + + if((m_nSize % 32) != 0) { + for(int j=0; j<32-(m_nSize&0x01F); j++) { + m_p_nArray[m_nArrayLen-1] &= mask; + mask = mask >> 1; + } + } +#else + long mask = 0x7FFFFFFFFFFFFFFF; + + // the number of populated spaces in the higest-order array slot is: + // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be + // cleared + + if((m_nSize % 64) != 0) { + for(int j=0; j<64-(m_nSize&0x03F); j++) { + m_p_nArray[m_nArrayLen-1] &= mask; + mask = mask >> 1; + } + } +#endif // __32BITS__ + } +/* + * This function returns the population count of 1's in the set + */ int Set::count() const { int counter = 0; - for (int i=0; i<m_size; i++) { - if ((m_bits & (1 << i)) != 0) { - counter++; + long mask; + for( int i=0; i<m_nArrayLen; i++) { + mask = (long) 0x01; + +#ifdef __32BITS__ + for( int j=0; j<32; j++) { + if(m_p_nArray[i] & mask) counter++; + mask = mask << 1; } + +#else + + for( int j=0; j<64; j++) { // FIXME - significant performance loss when array population << 64 + if((m_p_nArray[i] & mask) != 0) { + counter++; + } + mask = mask << 1; + } + +#endif // __32BITS__ + } + return counter; } -NodeID Set::elementAt(int index) { - // count from right to left, index starts from 0 - for (int i=0; i<m_size; i++) { - if ((m_bits & (1 << i)) != 0) { - if (index == 0) return i; - index --; +/* + * This function checks for set equality + */ + +bool Set::isEqual(const Set& set) const +{ + assert(m_nSize==set.m_nSize); + + for(int i=0;i<m_nArrayLen;i++) { + if(m_p_nArray[i] != set.m_p_nArray[i]) { + return false; } } - assert(0); // index out of range - return 0; + + return true; } +/* + * This function returns the NodeID (int) of the + * least set bit + */ NodeID Set::smallestElement() const { assert(count() > 0); - int counter = 0; - for (int i=0; i<m_size; i++) { - if (isElement(i)) { - return i; + long x; + for( int i=0; i<m_nArrayLen; i++) { + if(m_p_nArray[i]!=0) { + // the least-set bit must be in here + x = m_p_nArray[i]; + +#ifdef __32BITS__ + for( int j=0; j<32; j++) { + if(x & 0x00000001) { + return 32*i+j; + } + + x = x >> 1; + } +#else + for( int j=0; j<64; j++) { + if(x & 0x0000000000000001) { + return 64*i+j; + } + + x = x >> 1; + } +#endif // __32BITS__ + + ERROR_MSG("No smallest element of an empty set."); } } + ERROR_MSG("No smallest element of an empty set."); + + return 0; } -// Returns true iff all bits are set +/* + * this function returns true iff all bits are set + */ bool Set::isBroadcast() const { - assert((m_bits & m_mask) == m_bits); // check for any bits outside the range - return (m_mask == m_bits); + // check the fully-loaded words by equal to 0xffffffff + // only the last word may not be fully loaded, it is not + // fully loaded iff m_nSize % 32 or 64 !=0 => fully loaded iff + // m_nSize % 32 or 64 == 0 + +#ifdef __32BITS__ + for(int i=0; i< (((m_nSize % 32)==0) ? m_nArrayLen : m_nArrayLen-1); i++) { + if(m_p_nArray[i]!=-1) { + return false; + } + } + + // now check the last word, which may not be fully loaded + long mask = 1; + for(int j=0; j< (m_nSize % 32); j++) { + if((mask & m_p_nArray[m_nArrayLen-1])==0) { + return false; + } + mask = mask << 1; + } +#else + for(int i=0; i< (((m_nSize % 64)==0) ? m_nArrayLen : m_nArrayLen-1); i++) { + if(m_p_nArray[i]!=-1) { + return false; + } + } + + // now check the last word, which may not be fully loaded + long mask = 1; + for(int j=0; j< (m_nSize % 64); j++) { + if((mask & m_p_nArray[m_nArrayLen-1])==0) { + return false; + } + mask = mask << 1; + } + +#endif // __32BITS__ + + return true; } -// Returns true iff no bits are set +/* + * this function returns true iff no bits are set + */ bool Set::isEmpty() const { - assert((m_bits & m_mask) == m_bits); // check for any bits outside the range - return (m_bits == 0); + + // here we can simply check if all = 0, since we ensure + // that "extra slots" are all zero + for(int i=0; i< m_nArrayLen ; i++) { + if(m_p_nArray[i]!=0) { + return false; + } + } + + return true; } // returns the logical OR of "this" set and orSet Set Set::OR(const Set& orSet) const { - assert(m_size == orSet.m_size); - Set result(m_size); - result.m_bits = (m_bits | orSet.m_bits); - assert((result.m_bits & result.m_mask) == result.m_bits); // check for any bits outside the range + Set result(m_nSize); + assert(m_nSize == orSet.m_nSize); + for(int i=0; i< m_nArrayLen; i++) { + result.m_p_nArray[i] = m_p_nArray[i] | orSet.m_p_nArray[i]; + } + return result; + } // returns the logical AND of "this" set and andSet Set Set::AND(const Set& andSet) const { - assert(m_size == andSet.m_size); - Set result(m_size); - result.m_bits = (m_bits & andSet.m_bits); - assert((result.m_bits & result.m_mask) == result.m_bits); // check for any bits outside the range + Set result(m_nSize); + assert(m_nSize == andSet.m_nSize); + + for(int i=0; i< m_nArrayLen; i++) { + result.m_p_nArray[i] = m_p_nArray[i] & andSet.m_p_nArray[i]; + } + return result; } -// Returns true if the intersection of the two sets is non-empty -bool Set::intersectionIsNotEmpty(const Set& other_set) const -{ - assert(m_size == other_set.m_size); - return ((m_bits & other_set.m_bits) != 0); -} +// // Returns true if the intersection of the two sets is non-empty +// bool Set::intersectionIsNotEmpty(const Set& other_set) const +// { +// assert(m_nSize == other_set.m_nSize); +// for(int i=0; i< m_nArrayLen; i++) { +// if(m_p_nArray[i] & other_set.m_p_nArray[i]) { +// return true; +// } +// } -// Returns true if the intersection of the two sets is empty -bool Set::intersectionIsEmpty(const Set& other_set) const -{ - assert(m_size == other_set.m_size); - return ((m_bits & other_set.m_bits) == 0); -} +// return false; + +// } + +// // Returns true if the intersection of the two sets is empty +// bool Set::intersectionIsEmpty(const Set& other_set) const +// { +// assert(m_nSize == other_set.m_nSize); +// for(int i=0; i< m_nArrayLen; i++) { +// if(m_p_nArray[i] & other_set.m_p_nArray[i]) { +// return false; +// } +// } + +// return true; + +// } +/* + * Returns false if a bit is set in the parameter set that is + * NOT set in this set + */ bool Set::isSuperset(const Set& test) const { - assert(m_size == test.m_size); - uint32 temp = (test.m_bits & (~m_bits)); - return (temp == 0); -} + assert(m_nSize == test.m_nSize); -bool Set::isElement(NodeID element) const -{ - return ((m_bits & (1 << element)) != 0); + for(int i=0;i<m_nArrayLen;i++) { + if(((test.m_p_nArray[i] & m_p_nArray[i]) | ~test.m_p_nArray[i]) != -1) { + return false; + } + } + + return true; } +// /* +// * Returns true iff this bit is set +// */ +// bool Set::isElement(NodeID element) const +// { +// bool result; + +// #ifdef __32BITS__ +// result = ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0); +// #else +// result = ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0); +// #endif // __32BITS__ + +// return result; +// } + +/* + * "Supposed" to return the node id of the (n+1)th set + * bit, IE n=0 => returns nodeid of first set bit, BUT + * since BigSet.C behaves strangely, this implementation + * will behave strangely just for reverse compatability. + * + * Was originally implemented for the flight data recorder + * FDR + */ + +// NodeID Set::elementAt(int n) const +// { +// if(isElement(n)) return (NodeID) true; +// else return 0; + +// /* +// int match = -1; +// for(int i=0;i<m_nSize;i++) { +// if(isElement(i)) match++; +// if(match==n) { +// return i; +// } +// } + +// return -1; +// */ +// } + void Set::setSize(int size) { - // We're using 32 bit ints, and the 32nd bit acts strangely due to - // signed/unsigned, so restrict the set size to 31 bits. - assert(size < 32); - m_size = size; - m_bits = 0; - m_mask = ~((~0) << m_size); - assert(m_mask != 0); - assert((m_bits & m_mask) == m_bits); // check for any bits outside the range + m_nSize = size; + +#ifdef __32BITS__ + m_nArrayLen = m_nSize/32 + ((m_nSize%32==0) ? 0 : 1 ); +#else + m_nArrayLen = m_nSize/64 + ((m_nSize%64==0) ? 0 : 1 ); +#endif // __32BITS__ + + // decide whether to use dynamic or static alloction + if(m_nArrayLen<=NUMBER_WORDS_PER_SET) { // constant defined in RubyConfig.h + // its OK to use the static allocation, and it will + // probably be faster (as m_nArrayLen is already in the + // cache and they will probably share the same cache line) + + // if switching from dyanamic to static allocation (which + // is probably rare, but why not be complete?), must delete + // the dynamically allocated space + if((m_p_nArray != NULL) && (m_p_nArray != &m_p_nArray_Static[0])) + delete [] m_p_nArray; + + m_p_nArray = & m_p_nArray_Static[0]; + } else { + + // can't use static allocation...simply not enough room + // so dynamically allocate some space + if((m_p_nArray != NULL) && (m_p_nArray != &m_p_nArray_Static[0])) + delete [] m_p_nArray; + + m_p_nArray = new long[m_nArrayLen]; + } + + clear(); } -void Set::print(ostream& out) const -{ - out << "[Set (" << m_size << ") "; +Set& Set::operator=(const Set& obj) { + if(this == &obj) { + // do nothing + } else { + + // resize this item + setSize(obj.getSize()); - for (int i=0; i<m_size; i++) { - out << (bool) isElement(i) << " "; + // copy the elements from obj to this + for(int i=0; i<m_nArrayLen; i++) { + m_p_nArray[i] = obj.m_p_nArray[i]; + } } - out << "]"; + + return *this; } -#endif // BIGSET +void Set::print(ostream& out) const +{ + if(m_p_nArray==NULL) { + out << "[Set {Empty}]"; + return; + } + char buff[24]; + out << "[Set 0x "; + for (int i=m_nArrayLen-1; i>=0; i--) { +#ifdef __32BITS__ + sprintf(buff,"%08X ",m_p_nArray[i]); +#else + sprintf(buff,"0x %016llX ",m_p_nArray[i]); +#endif // __32BITS__ + out << buff; + } + out << " ]"; + +} -#endif // OPTBIGSET diff --git a/src/mem/ruby/common/Set.hh b/src/mem/ruby/common/Set.hh index ea16c66a5..45f06e6aa 100644 --- a/src/mem/ruby/common/Set.hh +++ b/src/mem/ruby/common/Set.hh @@ -32,24 +32,15 @@ * * Description: * - * $Id$ + * $Id: BigSet.h 1.6 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $ * */ -// Define this to use the BigSet class which is slower, but supports -// sets of size larger than 32. +// modified by Dan Gibson on 05/20/05 to accomidate FASTER +// >32 set lengths, using an array of ints w/ 32 bits/int -// #define BIGSET - -#define OPTBIGSET - -#ifdef OPTBIGSET -#include "mem/ruby/common/OptBigSet.hh" -#else - -#ifdef BIGSET -#include "mem/ruby/common/BigSet.hh" // code to supports sets larger than 32 -#else +// NOTE: Never include this file directly, this should only be +// included from Set.h #ifndef SET_H #define SET_H @@ -59,46 +50,95 @@ #include "mem/ruby/system/NodeID.hh" #include "mem/ruby/config/RubyConfig.hh" +// gibson 05/20/05 +// enum PresenceBit {NotPresent, Present}; + class Set { public: // Constructors // creates and empty set Set(); - Set(int size); + Set (int size); // used during the replay mechanism // Set(const char *str); - // Set(const Set& obj); - // Set& operator=(const Set& obj); + Set(const Set& obj); + Set& operator=(const Set& obj); // Destructor - // ~Set(); + ~Set(); // Public Methods - void add(NodeID newElement); + inline void add(NodeID index) + { +#ifdef __32BITS__ + m_p_nArray[index>>5] |= (1 << (index & 0x01F)); +#else + m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F)); +#endif // __32BITS__ + } + void addSet(const Set& set); void addRandom(); - void remove(NodeID newElement); + + inline void remove(NodeID index) + { +#ifdef __32BITS__ + m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F)); +#else + m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F)); +#endif // __32BITS__ + } + + void removeSet(const Set& set); - void clear(); + + inline void clear() { for(int i=0; i<m_nArrayLen; i++) m_p_nArray[i] = 0; } + void broadcast(); int count() const; - bool isEqual(const Set& set); + bool isEqual(const Set& set) const; Set OR(const Set& orSet) const; // return the logical OR of this set and orSet Set AND(const Set& andSet) const; // return the logical AND of this set and andSet // Returns true if the intersection of the two sets is non-empty - bool intersectionIsNotEmpty(const Set& other_set) const; + inline bool intersectionIsNotEmpty(const Set& other_set) const + { + for(int i=0; i< m_nArrayLen; i++) { + if(m_p_nArray[i] & other_set.m_p_nArray[i]) { + return true; + } + } + return false; + } // Returns true if the intersection of the two sets is empty - bool intersectionIsEmpty(const Set& other_set) const; + inline bool intersectionIsEmpty(const Set& other_set) const + { + for(int i=0; i< m_nArrayLen; i++) { + if(m_p_nArray[i] & other_set.m_p_nArray[i]) { + return false; + } + } + return true; + } bool isSuperset(const Set& test) const; bool isSubset(const Set& test) const { return test.isSuperset(*this); } - bool isElement(NodeID element) const; + + inline bool isElement(NodeID element) const + { +#ifdef __32BITS__ + return ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0); +#else + return ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0); +#endif // __32BITS__ + + } + bool isBroadcast() const; bool isEmpty() const; @@ -108,8 +148,14 @@ public: void setSize (int size); // get element for a index - NodeID elementAt(int index); - int getSize() const { return m_size; } + inline NodeID elementAt(int index) const + { + if(isElement(index)) return (NodeID) true; + else return 0; + } + + // gibson 05/20/05 + int getSize() const { return m_nSize; } // DEPRECATED METHODS void addToSet(NodeID newElement) { add(newElement); } // Deprecated @@ -123,10 +169,19 @@ private: // Private Methods // Data Members (m_ prefix) - int m_size; - uint32 m_bits; // Set as a bit vector - uint32 m_mask; // a 000001111 mask where the number of 1s is equal to m_size + // gibson 05/20/05 + // Vector<uint8> m_bits; // This is an vector of uint8 to reduce the size of the set + + int m_nSize; // the number of bits in this set + int m_nArrayLen; // the number of 32-bit words that are held in the array + + // Changed 5/24/05 for static allocation of array + // note that "long" corresponds to 32 bits on a 32-bit machine, + // 64 bits if the -m64 parameter is passed to g++, which it is + // for an AMD opteron under our configuration + long * m_p_nArray; // an word array to hold the bits in the set + long m_p_nArray_Static[NUMBER_WORDS_PER_SET]; }; // Output operator declaration @@ -144,6 +199,4 @@ ostream& operator<<(ostream& out, const Set& obj) } #endif //SET_H -#endif //BIGSET -#endif //OPTBIGSET diff --git a/src/mem/ruby/system/AbstractBloomFilter.hh b/src/mem/ruby/system/AbstractBloomFilter.hh deleted file mode 100644 index f5fe209c0..000000000 --- a/src/mem/ruby/system/AbstractBloomFilter.hh +++ /dev/null @@ -1,72 +0,0 @@ - -/* - * 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. - */ - -/* - * AbstractBloomFilter.h - * - * Description: - * - * - */ - -#ifndef ABSTRACT_BLOOM_FILTER_H -#define ABSTRACT_BLOOM_FILTER_H - -#include "mem/ruby/common/Global.hh" -#include "mem/ruby/slicc_interface/AbstractChip.hh" -#include "mem/ruby/config/RubyConfig.hh" -#include "mem/ruby/common/Address.hh" - -class AbstractBloomFilter { -public: - - virtual ~AbstractBloomFilter() {}; - virtual void clear() = 0; - virtual void increment(const Address& addr) = 0; - virtual void decrement(const Address& addr) = 0; - virtual void merge(AbstractBloomFilter * other_filter) = 0; - virtual void set(const Address& addr) = 0; - virtual void unset(const Address& addr) = 0; - - virtual bool isSet(const Address& addr) = 0; - virtual int getCount(const Address& addr) = 0; - virtual int getTotalCount() = 0; - - virtual void print(ostream& out) const = 0; - - virtual int getIndex(const Address& addr) = 0; - virtual int readBit(const int index) = 0; - virtual void writeBit(const int index, const int value) = 0; - -private: - -}; - - -#endif diff --git a/src/mem/ruby/system/BlockBloomFilter.cc b/src/mem/ruby/system/BlockBloomFilter.cc deleted file mode 100644 index d81f34ab1..000000000 --- a/src/mem/ruby/system/BlockBloomFilter.cc +++ /dev/null @@ -1,147 +0,0 @@ - -/* - * 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. - */ - -/* - * BlockBloomFilter.C - * - * Description: - * - * - */ - -#include "mem/ruby/system/BlockBloomFilter.hh" -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Address.hh" - -BlockBloomFilter::BlockBloomFilter(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); - - m_filter.setSize(m_filter_size); - - clear(); -} - -BlockBloomFilter::~BlockBloomFilter(){ -} - -void BlockBloomFilter::clear() -{ - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } -} - -void BlockBloomFilter::increment(const Address& addr) -{ - // Not used -} - - -void BlockBloomFilter::decrement(const Address& addr) -{ - // Not used -} - -void BlockBloomFilter::merge(AbstractBloomFilter * other_filter) -{ - // TODO -} - -void BlockBloomFilter::set(const Address& addr) -{ - int i = get_index(addr); - m_filter[i] = 1; -} - -void BlockBloomFilter::unset(const Address& addr) -{ - int i = get_index(addr); - m_filter[i] = 0; -} - -bool BlockBloomFilter::isSet(const Address& addr) -{ - int i = get_index(addr); - return (m_filter[i]); -} - - -int BlockBloomFilter::getCount(const Address& addr) -{ - return m_filter[get_index(addr)]; -} - -int BlockBloomFilter::getTotalCount() -{ - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - if (m_filter[i]) { - count++; - } - } - return count; -} - -int BlockBloomFilter::getIndex(const Address& addr) -{ - return get_index(addr); -} - -void BlockBloomFilter::print(ostream& out) const -{ -} - -int BlockBloomFilter::readBit(const int index) { - return m_filter[index]; -} - -void BlockBloomFilter::writeBit(const int index, const int value) { - m_filter[index] = value; -} - -int BlockBloomFilter::get_index(const Address& addr) -{ - // Pull out some bit field ==> B1 - // Pull out additional bits, not the same as B1 ==> B2 - // XOR B1 and B2 to get hash index - physical_address_t block_bits = addr.bitSelect( RubyConfig::dataBlockBits(), 2*RubyConfig::dataBlockBits() - 1); - int offset = 5; - physical_address_t other_bits = addr.bitSelect( 2*RubyConfig::dataBlockBits() + offset, 2*RubyConfig::dataBlockBits() + offset + m_filter_size_bits - 1); - int index = block_bits ^ other_bits; - assert(index < m_filter_size); - return index; -} - - diff --git a/src/mem/ruby/system/BlockBloomFilter.hh b/src/mem/ruby/system/BlockBloomFilter.hh deleted file mode 100644 index ea7c0807a..000000000 --- a/src/mem/ruby/system/BlockBloomFilter.hh +++ /dev/null @@ -1,83 +0,0 @@ - -/* - * 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. - */ - -/* - * BlockBloomFilter.h - * - * Description: - * - * - */ - -#ifndef BLOCK_BLOOM_FILTER_H -#define BLOCK_BLOOM_FILTER_H - -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Global.hh" -#include "mem/ruby/slicc_interface/AbstractChip.hh" -#include "mem/ruby/config/RubyConfig.hh" -#include "mem/ruby/common/Address.hh" -#include "mem/ruby/system/AbstractBloomFilter.hh" - -class BlockBloomFilter : public AbstractBloomFilter { -public: - - ~BlockBloomFilter(); - BlockBloomFilter(string config); - - void clear(); - void increment(const Address& addr); - void decrement(const Address& addr); - void merge(AbstractBloomFilter * other_filter); - void set(const Address& addr); - void unset(const Address& addr); - - bool isSet(const Address& addr); - int getCount(const Address& addr); - int getTotalCount(); - int getIndex(const Address& addr); - int readBit(const int index); - void writeBit(const int index, const int value); - - void print(ostream& out) const; - -private: - - int get_index(const Address& addr); - - Vector<int> m_filter; - int m_filter_size; - int m_filter_size_bits; - - int m_count_bits; - int m_count; -}; - - -#endif diff --git a/src/mem/ruby/system/BulkBloomFilter.cc b/src/mem/ruby/system/BulkBloomFilter.cc deleted file mode 100644 index 6d5c3f240..000000000 --- a/src/mem/ruby/system/BulkBloomFilter.cc +++ /dev/null @@ -1,233 +0,0 @@ - -/* - * 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.C - * - * Description: - * - * - */ - -#include "mem/ruby/system/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, '_'); - - int smt_threads = RubyConfig::numberofSMTThreads(); - 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 = RubyConfig::dataBlockBits(); - 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 = RubyConfig::dataBlockBits(); - 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( RubyConfig::dataBlockBits(), RubyConfig::dataBlockBits() + m_filter_size_bits - 1); -} - -Address BulkBloomFilter::permute(const Address & addr){ - // permutes the original address bits according to Table 5 - int block_offset = RubyConfig::dataBlockBits(); - 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); -} diff --git a/src/mem/ruby/system/BulkBloomFilter.hh b/src/mem/ruby/system/BulkBloomFilter.hh deleted file mode 100644 index 8c5276517..000000000 --- a/src/mem/ruby/system/BulkBloomFilter.hh +++ /dev/null @@ -1,88 +0,0 @@ - -/* - * 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.h - * - * Description: - * - * - */ - -#ifndef BULK_BLOOM_FILTER_H -#define BULK_BLOOM_FILTER_H - -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Global.hh" -#include "mem/ruby/slicc_interface/AbstractChip.hh" -#include "mem/ruby/config/RubyConfig.hh" -#include "mem/ruby/common/Address.hh" -#include "mem/ruby/system/AbstractBloomFilter.hh" - -class BulkBloomFilter : public AbstractBloomFilter { -public: - - ~BulkBloomFilter(); - BulkBloomFilter(string config); - - void clear(); - void increment(const Address& addr); - void decrement(const Address& addr); - void merge(AbstractBloomFilter * other_filter); - void set(const Address& addr); - void unset(const Address& addr); - - bool isSet(const Address& addr); - int getCount(const Address& addr); - int getTotalCount(); - int getIndex(const Address& addr); - int readBit(const int index); - void writeBit(const int index, const int value); - - void print(ostream& out) const; - -private: - - int get_index(const Address& addr); - Address permute(const Address & addr); - - Vector<int> m_filter; - Vector<int> m_temp_filter; - - int m_filter_size; - int m_filter_size_bits; - - int m_sector_bits; - - int m_count_bits; - int m_count; -}; - - -#endif diff --git a/src/mem/ruby/system/GenericBloomFilter.cc b/src/mem/ruby/system/GenericBloomFilter.cc deleted file mode 100644 index da8ec4262..000000000 --- a/src/mem/ruby/system/GenericBloomFilter.cc +++ /dev/null @@ -1,154 +0,0 @@ - -/* - * 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. - */ - -/* - * GenericBloomFilter.h - * - * Description: - * - * - */ - -#include "mem/ruby/common/Global.hh" -#include "mem/ruby/slicc_interface/AbstractChip.hh" -#include "mem/ruby/config/RubyConfig.hh" -#include "mem/ruby/common/Address.hh" - -#include "mem/ruby/system/GenericBloomFilter.hh" -#include "mem/ruby/system/LSB_CountingBloomFilter.hh" -#include "mem/ruby/system/NonCountingBloomFilter.hh" -#include "mem/ruby/system/BulkBloomFilter.hh" -#include "mem/ruby/system/BlockBloomFilter.hh" -#include "mem/ruby/system/MultiGrainBloomFilter.hh" -#include "mem/ruby/system/MultiBitSelBloomFilter.hh" -#include "mem/ruby/system/H3BloomFilter.hh" - -GenericBloomFilter::GenericBloomFilter(AbstractChip* chip_ptr, string config) -{ - m_chip_ptr = chip_ptr; - - - string tail(config); - string head = string_split(tail,'_'); - - if (head == "LSB_Counting" ) { - m_filter = new LSB_CountingBloomFilter(tail); - } - else if(head == "NonCounting" ) { - m_filter = new NonCountingBloomFilter(tail); - } - else if(head == "Bulk" ) { - m_filter = new BulkBloomFilter(tail); - } - else if(head == "Block") { - m_filter = new BlockBloomFilter(tail); - } - else if(head == "Multigrain"){ - m_filter = new MultiGrainBloomFilter(tail); - } - else if(head == "MultiBitSel"){ - m_filter = new MultiBitSelBloomFilter(tail); - } - else if(head == "H3"){ - m_filter = new H3BloomFilter(tail); - } - else { - assert(0); - } -} - -GenericBloomFilter::~GenericBloomFilter() -{ - delete m_filter; -} - -void GenericBloomFilter::clear() -{ - m_filter->clear(); -} - -void GenericBloomFilter::increment(const Address& addr) -{ - m_filter->increment(addr); -} - -void GenericBloomFilter::decrement(const Address& addr) -{ - m_filter->decrement(addr); -} - -void GenericBloomFilter::merge(GenericBloomFilter * other_filter) -{ - m_filter->merge(other_filter->getFilter()); -} - -void GenericBloomFilter::set(const Address& addr) -{ - m_filter->set(addr); -} - -void GenericBloomFilter::unset(const Address& addr) -{ - m_filter->unset(addr); -} - -bool GenericBloomFilter::isSet(const Address& addr) -{ - return m_filter->isSet(addr); -} - -int GenericBloomFilter::getCount(const Address& addr) -{ - return m_filter->getCount(addr); -} - -int GenericBloomFilter::getTotalCount() -{ - return m_filter->getTotalCount(); -} - -int GenericBloomFilter::getIndex(const Address& addr) -{ - return m_filter->getIndex(addr); -} - -int GenericBloomFilter::readBit(const int index) { - return m_filter->readBit(index); -} - -void GenericBloomFilter::writeBit(const int index, const int value) { - m_filter->writeBit(index, value); -} - -void GenericBloomFilter::print(ostream& out) const -{ - return m_filter->print(out); -} - - diff --git a/src/mem/ruby/system/GenericBloomFilter.hh b/src/mem/ruby/system/GenericBloomFilter.hh deleted file mode 100644 index 11603b06f..000000000 --- a/src/mem/ruby/system/GenericBloomFilter.hh +++ /dev/null @@ -1,96 +0,0 @@ - -/* - * 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. - */ - -/* - * GenericBloomFilter.h - * - * Description: - * - * - */ - -#ifndef GENERIC_BLOOM_FILTER_H -#define GENERIC_BLOOM_FILTER_H - -#include "mem/ruby/common/Global.hh" -#include "mem/ruby/slicc_interface/AbstractChip.hh" -#include "mem/ruby/config/RubyConfig.hh" -#include "mem/ruby/common/Address.hh" -#include "mem/ruby/system/AbstractBloomFilter.hh" - -class GenericBloomFilter { -public: - - // Constructors - GenericBloomFilter(AbstractChip* chip_ptr, string config); - - void clear(); - void increment(const Address& addr); - void decrement(const Address& addr); - void merge(GenericBloomFilter * other_filter); - void set(const Address& addr); - void unset(const Address& addr); - AbstractBloomFilter * getFilter(){ - return m_filter; - } - - bool isSet(const Address& addr); - - int getCount(const Address& addr); - - int getTotalCount(); - - int getIndex(const Address& addr); - int readBit(const int index); - void writeBit(const int index, const int value); - - void print(ostream& out) const; - void printConfig(ostream& out) { out << "GenericBloomFilter" << endl; } - - // Destructor - ~GenericBloomFilter(); - - -private: - - AbstractChip* m_chip_ptr; - AbstractBloomFilter* m_filter; -}; - -// Output operator definition -extern inline -ostream& operator<<(ostream& out, const GenericBloomFilter& obj) -{ - obj.print(out); - out << flush; - return out; -} - - -#endif diff --git a/src/mem/ruby/system/H3BloomFilter.cc b/src/mem/ruby/system/H3BloomFilter.cc deleted file mode 100644 index 8fed32814..000000000 --- a/src/mem/ruby/system/H3BloomFilter.cc +++ /dev/null @@ -1,210 +0,0 @@ - -/* - * 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. - */ - -/* - * NonCountingBloomFilter.C - * - * Description: - * - * - */ - -#include "mem/ruby/system/H3BloomFilter.hh" -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Address.hh" - -H3BloomFilter::H3BloomFilter(string str) -{ - //TODO: change this ugly init code... - primes_list[0] = 9323; - primes_list[1] = 11279; - primes_list[2] = 10247; - primes_list[3] = 30637; - primes_list[4] = 25717; - primes_list[5] = 43711; - - mults_list[0] = 255; - mults_list[1] = 29; - mults_list[2] = 51; - mults_list[3] = 3; - mults_list[4] = 77; - mults_list[5] = 43; - - adds_list[0] = 841; - adds_list[1] = 627; - adds_list[2] = 1555; - adds_list[3] = 241; - adds_list[4] = 7777; - adds_list[5] = 65931; - - - - string tail(str); - string head = string_split(tail, '_'); - - // head contains filter size, tail contains bit offset from block number - m_filter_size = atoi(head.c_str()); - - head = string_split(tail, '_'); - m_num_hashes = atoi(head.c_str()); - - if(tail == "Regular") { - isParallel = false; - } else if (tail == "Parallel") { - isParallel = true; - } else { - cout << "ERROR: Incorrect config string for MultiHash Bloom! :" << str << endl; - assert(0); - } - - m_filter_size_bits = log_int(m_filter_size); - - m_par_filter_size = m_filter_size/m_num_hashes; - m_par_filter_size_bits = log_int(m_par_filter_size); - - m_filter.setSize(m_filter_size); - clear(); -} - -H3BloomFilter::~H3BloomFilter(){ -} - -void H3BloomFilter::clear() -{ - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } -} - -void H3BloomFilter::increment(const Address& addr) -{ - // Not used -} - - -void H3BloomFilter::decrement(const Address& addr) -{ - // Not used -} - -void H3BloomFilter::merge(AbstractBloomFilter * other_filter){ - // assumes both filters are the same size! - H3BloomFilter * temp = (H3BloomFilter*) other_filter; - for(int i=0; i < m_filter_size; ++i){ - m_filter[i] |= (*temp)[i]; - } - -} - -void H3BloomFilter::set(const Address& addr) -{ - for (int i = 0; i < m_num_hashes; i++) { - int idx = get_index(addr, i); - m_filter[idx] = 1; - - //Profile hash value distribution - //g_system_ptr->getProfiler()->getXactProfiler()->profileHashValue(i, idx); // gem5:Arka decomissiong of log_tm - } -} - -void H3BloomFilter::unset(const Address& addr) -{ - cout << "ERROR: Unset should never be called in a Bloom filter"; - assert(0); -} - -bool H3BloomFilter::isSet(const Address& addr) -{ - bool res = true; - - for (int i=0; i < m_num_hashes; i++) { - int idx = get_index(addr, i); - res = res && m_filter[idx]; - } - return res; -} - - -int H3BloomFilter::getCount(const Address& addr) -{ - return isSet(addr)? 1: 0; -} - -int H3BloomFilter::getIndex(const Address& addr) -{ - return 0; -} - -int H3BloomFilter::readBit(const int index) { - return 0; -} - -void H3BloomFilter::writeBit(const int index, const int value) { - -} - -int H3BloomFilter::getTotalCount() -{ - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - count += m_filter[i]; - } - return count; -} - -void H3BloomFilter::print(ostream& out) const -{ -} - -int H3BloomFilter::get_index(const Address& addr, int i) -{ - uint64 x = addr.getLineAddress(); - //uint64 y = (x*mults_list[i] + adds_list[i]) % primes_list[i]; - int y = hash_H3(x,i); - - if(isParallel) { - return (y % m_par_filter_size) + i*m_par_filter_size; - } else { - return y % m_filter_size; - } -} - -int H3BloomFilter::hash_H3(uint64 value, int index) { - uint64 mask = 1; - uint64 val = value; - int result = 0; - - for(int i = 0; i < 64; i++) { - if(val&mask) result ^= H3[i][index]; - val = val >> 1; - } - return result; - } - diff --git a/src/mem/ruby/system/H3BloomFilter.hh b/src/mem/ruby/system/H3BloomFilter.hh deleted file mode 100644 index 0797b0c08..000000000 --- a/src/mem/ruby/system/H3BloomFilter.hh +++ /dev/null @@ -1,1259 +0,0 @@ - -/* - * 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. - */ - -/* - * H3BloomFilter.h - * - * Description: - * - * - */ - -#ifndef H3_BLOOM_FILTER_H -#define H3_BLOOM_FILTER_H - -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Global.hh" -#include "mem/ruby/slicc_interface/AbstractChip.hh" -#include "mem/ruby/system/System.hh" -#include "mem/ruby/profiler/Profiler.hh" -#include "mem/ruby/config/RubyConfig.hh" -#include "mem/ruby/common/Address.hh" -#include "mem/ruby/system/AbstractBloomFilter.hh" - -static int H3[64][16] = { -{ -33268410, -395488709, -311024285, -456111753, -181495008, -119997521, -220697869, -433891432, -755927921, -515226970, -719448198, -349842774, -269183649, -463275672, -429800228, -521598937 -}, -{ -628677802, -820947732, -809435975, -1024657192, -887631270, -412050215, -391365090, -324227279, -318338329, -1038393087, -489807930, -387366128, -518096428, -324184340, -429376066, -447109279 -}, -{ -599747653, -404960623, -103933604, -946416030, -656460913, -925957005, -1047665689, -163552053, -88359290, -841315415, -899833584, -1067336680, -348549994, -464045876, -270252128, -829897652 -}, -{ -215495230, -966696438, -82589012, -750102795, -909780866, -920285789, -769759214, -331966823, -939936006, -439950703, -883794828, -1009277508, -61634610, -741444350, -98689608, -524144422 -}, -{ -93868534, -196958667, -774076619, -327921978, -122538783, -879785030, -690748527, -3498564, -83163077, -1027963025, -582088444, -466152216, -312424878, -550064499, -646612667, -561099434 -}, -{ -1002047931, -395477707, -821317480, -890482112, -697094476, -263813044, -840275189, -469664185, -795625845, -211504898, -99204277, -1004491153, -725930417, -1064479221, -893834767, -839719181 -}, -{ -278507126, -985111995, -706462983, -1042178726, -123281719, -963778122, -500881056, -726291104, -134293026, -568379664, -317050609, -533470307, -1022365922, -197645211, -315125721, -634827678 -}, -{ -219227366, -553960647, -870169525, -322232839, -508322497, -648672696, -249405795, -883596102, -476433133, -541372919, -646647793, -1042679515, -43242483, -600187508, -499866821, -135713210 -}, -{ -52837162, -96966684, -401840460, -1071661176, -733560065, -150035417, -341319946, -811582750, -636173904, -519054065, -196321433, -1028294565, -882204070, -522965093, -48884074, -117810166 -}, -{ -650860353, -789534698, -328813544, -473250022, -143128306, -173196006, -846958825, -174632187, -683273509, -405459497, -787235556, -773873501, -240110267, -426797736, -92043842, -711789240 -}, -{ -586637493, -5059646, -398035664, -6686087, -498300175, -948278148, -681227731, -592751744, -572019677, -558044722, -589368271, -695745538, -1073416749, -529192035, -550984939, -1070620580 -}, -{ -102904663, -647598516, -758863940, -313426443, -76504114, -1050747783, -708436441, -563815069, -224107668, -875925186, -167675944, -926209739, -279737287, -1040288182, -768184312, -371708956 -}, -{ -683968868, -1027427757, -180781926, -742898864, -624078545, -645659833, -577225838, -987150210, -723410002, -224013421, -993286634, -33188488, -247264323, -888018697, -38048664, -189037096 -}, -{ -475612146, -426739285, -873726278, -529192871, -607715202, -388486246, -987001312, -474493980, -259747270, -417465536, -217062395, -392858482, -563810075, -137852805, -1051814153, -72895217 -}, -{ -71277086, -785496675, -500608842, -89633426, -274085706, -248467935, -838061983, -48106147, -773662506, -49545328, -9071573, -100739031, -602018002, -904371654, -534132064, -332211304 -}, -{ -401893602, -735125342, -775548339, -210224843, -256081130, -482894412, -350801633, -1035713633, -429458128, -327281409, -739927752, -359327650, -886942880, -847691759, -752417993, -359445596 -}, -{ -267472014, -1050659620, -1068232362, -1049684368, -17130239, -690524969, -793224378, -14455158, -423092885, -873853424, -430535778, -7867877, -309731959, -370260786, -862353083, -403906850 -}, -{ -993077283, -218812656, -389234651, -393202875, -413116501, -263300295, -470013158, -592730725, -441847172, -732392823, -407574059, -875664777, -271347307, -792954404, -554774761, -1022424300 -}, -{ -675919719, -637054073, -784720745, -149714381, -813144874, -502525801, -635436670, -1003196587, -160786091, -947509775, -969788637, -26854073, -257964369, -63898568, -539767732, -772364518 -}, -{ -943076868, -1021732472, -697575075, -15843624, -617573396, -534113303, -122953324, -964873912, -942995378, -87830944, -1012914818, -455484661, -592160054, -599844284, -810394353, -836812568 -}, -{ -688992674, -279465370, -731582262, -687883235, -438178468, -80493001, -342701501, -663561405, -23360106, -531315007, -508931618, -36294623, -231216223, -840438413, -255665680, -663205938 -}, -{ -857265418, -552630887, -8173237, -792122963, -210140052, -823124938, -667709953, -751538219, -991957789, -462064153, -19070176, -726604748, -714567823, -151147895, -1012619677, -697114353 -}, -{ -467105652, -683256174, -702387467, -28730434, -549942998, -48712701, -960519696, -1008345587, -679267717, -370932249, -880419471, -352141567, -331640403, -598772468, -95160685, -812053015 -}, -{ -1053491323, -430526562, -1014938507, -109685515, -765949103, -177288303, -1034642653, -485421658, -71850281, -981034542, -61620389, -601367920, -504420930, -220599168, -583051998, -158735752 -}, -{ -103033901, -522494916, -658494760, -959206022, -931348143, -834510661, -21542994, -189699884, -679327018, -171983002, -96774168, -456133168, -543103352, -923945936, -970074188, -643658485 -}, -{ -566379913, -805798263, -840662512, -820206124, -796507494, -223712542, -118811519, -662246595, -809326534, -416471323, -748027186, -161169753, -739149488, -276330378, -924837051, -964873733 -}, -{ -585882743, -135502711, -3386031, -625631285, -1068193307, -270342640, -432739484, -556606453, -826419155, -1038540977, -158000202, -69109538, -207087256, -298111218, -678046259, -184611498 -}, -{ -305310710, -46237988, -855726974, -735975153, -930663798, -425764232, -104362407, -391371443, -867622101, -71645091, -61824734, -661902640, -293738633, -309416189, -281710675, -879317360 -}, -{ -398146324, -398293087, -689145387, -1038451703, -521637478, -516134620, -314658937, -830334981, -583400300, -340083705, -68029852, -675389876, -994635780, -788959180, -406967042, -74403607 -}, -{ -69463153, -744427484, -191639960, -590927798, -969916795, -546846769, -728756758, -889355646, -520855076, -136068426, -776132410, -189663815, -252051082, -533662856, -362198652, -1026161384 -}, -{ -584984279, -1004834381, -568439705, -834508761, -21812513, -670870173, -1052043300, -341868768, -473755574, -124339439, -36193947, -437997647, -137419489, -58705193, -337793711, -340738909 -}, -{ -898051466, -512792906, -234874060, -655358775, -683745319, -671676404, -428888546, -639928192, -672697722, -176477579, -747020991, -758211282, -443045009, -205395173, -1016944273, -5584717 -}, -{ -156038300, -138620174, -588466825, -1061494056, -1013672100, -1064257198, -881417791, -839470738, -83519030, -100875683, -237486447, -461483733, -681527127, -777996147, -574635362, -815974538 -}, -{ -184168473, -519509808, -62531892, -51821173, -43787358, -385711644, -141325169, -36069511, -584183031, -571372909, -671503175, -226486781, -194932686, -1045460970, -753718579, -331442433 -}, -{ -73065106, -1015327221, -630916840, -1058053470, -306737587, -296343219, -907194989, -920172546, -224516225, -818625553, -551143849, -634570650, -432966225, -756438259, -939564853, -767999933 -}, -{ -884775648, -394862257, -446787794, -219833788, -727195727, -728122304, -249888353, -732947974, -289908868, -448282580, -618161877, -898939716, -739554163, -860631799, -1058977530, -86916736 -}, -{ -143850006, -352708694, -200194048, -979764914, -629404175, -546279766, -72106714, -860980514, -313190585, -897143111, -308425797, -953791785, -349924906, -221457005, -950588925, -908254505 -}, -{ -950032043, -829868728, -68623614, -714624605, -69760597, -297275854, -355894016, -985369737, -882852618, -864071289, -958512902, -950910111, -991368991, -829645051, -434698210, -771350575 -}, -{ -552695074, -319195551, -80297396, -496413831, -944046531, -621525571, -617653363, -416729825, -441842808, -9847464, -99420657, -1033914550, -812966458, -937053011, -673390195, -934577365 -}, -{ -1034695843, -190969665, -332900185, -51897434, -523888639, -883512843, -146908572, -506785674, -565814307, -692255649, -314052926, -826386588, -430691325, -866927620, -413880214, -936474339 -}, -{ -129380164, -741739952, -1013703462, -494392795, -957214600, -1010879043, -931790677, -94551922, -988065869, -120637871, -882506912, -395075379, -210570485, -812422692, -910383687, -817722285 -}, -{ -51850866, -283408630, -1053047202, -858940389, -818507731, -477082181, -353546901, -993324368, -407093779, -231608253, -1067319867, -73159811, -429792535, -971320614, -565699344, -718823399 -}, -{ -408185106, -491493570, -596050720, -310776444, -703628192, -454438809, -523988035, -728512200, -686012353, -976339656, -72816924, -116926720, -165866591, -452043792, -866943072, -968545481 -}, -{ -443231195, -905907843, -1061421320, -746360489, -1043120338, -1069659155, -463359031, -688303227, -186550710, -155347339, -1044842421, -1005904570, -69332909, -706951903, -422513657, -882038450 -}, -{ -430990623, -946501980, -742556791, -278398643, -183759217, -659404315, -279754382, -1069347846, -843746517, -222777670, -990835599, -548741637, -129220580, -1392170, -1032654091, -894058935 -}, -{ -452042227, -751640705, -259481376, -765824585, -145991469, -1013683228, -1055491225, -536379588, -392593350, -913368594, -1029429776, -226857786, -31505342, -1054416381, -32341741, -687106649 -}, -{ -404750944, -811417027, -869530820, -773491060, -810901282, -979340397, -1036910290, -461764404, -834235095, -765695033, -604692390, -452158120, -928988098, -442719218, -1024059719, -167723114 -}, -{ -974245177, -1046377300, -1003424287, -787349855, -336314155, -875074696, -1018462718, -890313003, -367376809, -86355556, -1020618772, -890710345, -444741481, -373230261, -767064947, -840920177 -}, -{ -719581124, -431808156, -138301690, -668222575, -497413494, -740492013, -485033226, -125301442, -831265111, -879071459, -341690480, -152975256, -850330086, -717444507, -694225877, -785340566 -}, -{ -1032766252, -140959364, -737474726, -1062767538, -364464647, -331414723, -356152634, -642832379, -158733632, -374691640, -285504811, -345349905, -876599880, -476392727, -479589210, -606376325 -}, -{ -174997730, -778177086, -319164313, -163614456, -10331364, -599358958, -8331663, -237538058, -159173957, -174533880, -65588684, -878222844, -424467599, -901803515, -187504218, -776690353 -}, -{ -803856182, -965850321, -694948067, -218315960, -358416571, -683713254, -178069303, -428076035, -686176454, -579553217, -357306738, -315018080, -886852373, -568563910, -896839725, -257416821 -}, -{ -401650013, -183289141, -497957228, -879734476, -265024455, -825794561, -889237440, -323359863, -100258491, -991414783, -313986632, -85847250, -362520248, -276103512, -1041630342, -525981595 -}, -{ -487732740, -46201705, -990837834, -62744493, -1067364756, -58015363, -690846283, -680262648, -997278956, -469357861, -432164624, -996763915, -211907847, -167824295, -144928194, -454839915 -}, -{ -41404232, -514493300, -259546924, -578217256, -972345130, -123299213, -346040332, -1014668104, -520910639, -579955198, -36627803, -179072921, -547684341, -598950511, -269497394, -854352266 -}, -{ -603906768, -100863318, -708837659, -204175569, -375560904, -908375384, -28314106, -6303733, -175283124, -749851198, -308667367, -415293931, -225365403, -1032188331, -977112710, -819705229 -}, -{ -399767123, -697985692, -356790426, -643687584, -298624218, -185095167, -381653926, -876816342, -296720023, -2205879, -235816616, -521850105, -622753786, -1021421218, -726349744, -256504902 -}, -{ -851245024, -1022500222, -511909628, -313809625, -99776025, -39710175, -798739932, -741832408, -140631966, -898295927, -607660421, -870669312, -1051422478, -789055529, -669113756, -681943450 -}, -{ -853872755, -491465269, -503341472, -98019440, -258267420, -335602837, -320687824, -1053324395, -24932389, -955011453, -934255131, -435625663, -501568768, -238967025, -549987406, -248619780 -}, -{ -411151284, -576471205, -757985419, -544137226, -968135693, -877548443, -194586894, -74882373, -248353663, -21207540, -273789651, -853653916, -861267970, -533253322, -3739570, -661358586 -}, -{ -271430986, -71390029, -257643671, -949329860, -348156406, -251939238, -445808698, -48269799, -907589462, -105677619, -635451508, -20805932, -464874661, -7542147, -243619464, -288304568 -}, -{ -368215982, -530288964, -770090421, -660961164, -614935537, -630760399, -931299233, -794519275, -779918979, -401746493, -561237006, -1027202224, -258968003, -339508073, -1050610516, -1064307013 -}, -{ -1039172162, -448331205, -928997884, -49813151, -198712120, -992335354, -671024050, -879525220, -745915336, -1038822580, -138669665, -917958819, -681422342, -792868818, -924762727, -816386174 -}, -{ -515190336, -313808618, -441296783, -1022120897, -792325033, -354387581, -59273006, -280075434, -411357221, -665274694, -4054464, -1059046246, -394261773, -848616745, -15446017, -517723271 -}}; - - -class H3BloomFilter : public AbstractBloomFilter { -public: - - ~H3BloomFilter(); - H3BloomFilter(string config); - - void clear(); - void increment(const Address& addr); - void decrement(const Address& addr); - void merge(AbstractBloomFilter * other_filter); - void set(const Address& addr); - void unset(const Address& addr); - - bool isSet(const Address& addr); - int getCount(const Address& addr); - int getTotalCount(); - void print(ostream& out) const; - - int getIndex(const Address& addr); - int readBit(const int index); - void writeBit(const int index, const int value); - - int operator[](const int index) const{ - return this->m_filter[index]; - } - -private: - - int get_index(const Address& addr, int hashNumber); - - int hash_H3(uint64 value, int index); - - Vector<int> m_filter; - int m_filter_size; - int m_num_hashes; - int m_filter_size_bits; - - int m_par_filter_size; - int m_par_filter_size_bits; - - int m_count_bits; - int m_count; - - - - int primes_list[6];// = {9323,11279,10247,30637,25717,43711}; - int mults_list[6]; //= {255,29,51,3,77,43}; - int adds_list[6]; //= {841,627,1555,241,7777,65391}; - - bool isParallel; - -}; - - -#endif diff --git a/src/mem/ruby/system/LSB_CountingBloomFilter.cc b/src/mem/ruby/system/LSB_CountingBloomFilter.cc deleted file mode 100644 index f3b533b90..000000000 --- a/src/mem/ruby/system/LSB_CountingBloomFilter.cc +++ /dev/null @@ -1,141 +0,0 @@ - -/* - * 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. - */ - -/* - * LSB_CountingBloomFilter.C - * - * Description: - * - * - */ - -#include "mem/ruby/system/LSB_CountingBloomFilter.hh" -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Address.hh" - -LSB_CountingBloomFilter::LSB_CountingBloomFilter(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); - - m_count = atoi(tail.c_str()); - m_count_bits = log_int(m_count); - - m_filter.setSize(m_filter_size); - clear(); -} - -LSB_CountingBloomFilter::~LSB_CountingBloomFilter(){ -} - -void LSB_CountingBloomFilter::clear() -{ - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } -} - -void LSB_CountingBloomFilter::increment(const Address& addr) -{ - int i = get_index(addr); - if (m_filter[i] < m_count); - m_filter[i] += 1; -} - - -void LSB_CountingBloomFilter::decrement(const Address& addr) -{ - int i = get_index(addr); - if (m_filter[i] > 0) - m_filter[i] -= 1; -} - -void LSB_CountingBloomFilter::merge(AbstractBloomFilter * other_filter) -{ - // TODO -} - -void LSB_CountingBloomFilter::set(const Address& addr) -{ - // TODO -} - -void LSB_CountingBloomFilter::unset(const Address& addr) -{ - // TODO -} - -bool LSB_CountingBloomFilter::isSet(const Address& addr) -{ - // TODO -} - - -int LSB_CountingBloomFilter::getCount(const Address& addr) -{ - return m_filter[get_index(addr)]; -} - -int LSB_CountingBloomFilter::getTotalCount() -{ - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - count += m_filter[i]; - } - return count; -} - -int LSB_CountingBloomFilter::getIndex(const Address& addr) -{ - return get_index(addr); -} - -void LSB_CountingBloomFilter::print(ostream& out) const -{ -} - -int LSB_CountingBloomFilter::readBit(const int index) { - return 0; - // TODO -} - -void LSB_CountingBloomFilter::writeBit(const int index, const int value) { - // TODO -} - -int LSB_CountingBloomFilter::get_index(const Address& addr) -{ - return addr.bitSelect( RubyConfig::dataBlockBits(), RubyConfig::dataBlockBits() + m_filter_size_bits - 1); -} - - diff --git a/src/mem/ruby/system/LSB_CountingBloomFilter.hh b/src/mem/ruby/system/LSB_CountingBloomFilter.hh deleted file mode 100644 index fb039cea7..000000000 --- a/src/mem/ruby/system/LSB_CountingBloomFilter.hh +++ /dev/null @@ -1,83 +0,0 @@ - -/* - * 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. - */ - -/* - * LSB_CountingBloomFilter.h - * - * Description: - * - * - */ - -#ifndef LSB_COUNTING_BLOOM_FILTER_H -#define LSB_COUNTING_BLOOM_FILTER_H - -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Global.hh" -#include "mem/ruby/slicc_interface/AbstractChip.hh" -#include "mem/ruby/config/RubyConfig.hh" -#include "mem/ruby/common/Address.hh" -#include "mem/ruby/system/AbstractBloomFilter.hh" - -class LSB_CountingBloomFilter : public AbstractBloomFilter { -public: - - ~LSB_CountingBloomFilter(); - LSB_CountingBloomFilter(string config); - - void clear(); - void increment(const Address& addr); - void decrement(const Address& addr); - void merge(AbstractBloomFilter * other_filter); - void set(const Address& addr); - void unset(const Address& addr); - - bool isSet(const Address& addr); - int getCount(const Address& addr); - int getTotalCount(); - int getIndex(const Address& addr); - int readBit(const int index); - void writeBit(const int index, const int value); - - void print(ostream& out) const; - -private: - - int get_index(const Address& addr); - - Vector<int> m_filter; - int m_filter_size; - int m_filter_size_bits; - - int m_count_bits; - int m_count; -}; - - -#endif diff --git a/src/mem/ruby/system/MultiBitSelBloomFilter.cc b/src/mem/ruby/system/MultiBitSelBloomFilter.cc deleted file mode 100644 index 8083506db..000000000 --- a/src/mem/ruby/system/MultiBitSelBloomFilter.cc +++ /dev/null @@ -1,191 +0,0 @@ - -/* - * 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. - */ - -/* - * NonCountingBloomFilter.C - * - * Description: - * - * - */ - -#include "mem/ruby/system/MultiBitSelBloomFilter.hh" -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Address.hh" - -MultiBitSelBloomFilter::MultiBitSelBloomFilter(string str) -{ - - string tail(str); - string head = string_split(tail, '_'); - - // head contains filter size, tail contains bit offset from block number - m_filter_size = atoi(head.c_str()); - - head = string_split(tail, '_'); - m_num_hashes = atoi(head.c_str()); - - head = string_split(tail, '_'); - m_skip_bits = atoi(head.c_str()); - - if(tail == "Regular") { - isParallel = false; - } else if (tail == "Parallel") { - isParallel = true; - } else { - cout << "ERROR: Incorrect config string for MultiBitSel Bloom! :" << str << endl; - assert(0); - } - - m_filter_size_bits = log_int(m_filter_size); - - m_par_filter_size = m_filter_size/m_num_hashes; - m_par_filter_size_bits = log_int(m_par_filter_size); - - m_filter.setSize(m_filter_size); - clear(); -} - -MultiBitSelBloomFilter::~MultiBitSelBloomFilter(){ -} - -void MultiBitSelBloomFilter::clear() -{ - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } -} - -void MultiBitSelBloomFilter::increment(const Address& addr) -{ - // Not used -} - - -void MultiBitSelBloomFilter::decrement(const Address& addr) -{ - // Not used -} - -void MultiBitSelBloomFilter::merge(AbstractBloomFilter * other_filter){ - // assumes both filters are the same size! - MultiBitSelBloomFilter * temp = (MultiBitSelBloomFilter*) other_filter; - for(int i=0; i < m_filter_size; ++i){ - m_filter[i] |= (*temp)[i]; - } - -} - -void MultiBitSelBloomFilter::set(const Address& addr) -{ - for (int i = 0; i < m_num_hashes; i++) { - int idx = get_index(addr, i); - m_filter[idx] = 1; - - //Profile hash value distribution - //g_system_ptr->getProfiler()->getXactProfiler()->profileHashValue(i, idx); //gem5:Arka for decomissioning of log_tm - } -} - -void MultiBitSelBloomFilter::unset(const Address& addr) -{ - cout << "ERROR: Unset should never be called in a Bloom filter"; - assert(0); -} - -bool MultiBitSelBloomFilter::isSet(const Address& addr) -{ - bool res = true; - - for (int i=0; i < m_num_hashes; i++) { - int idx = get_index(addr, i); - res = res && m_filter[idx]; - } - return res; -} - - -int MultiBitSelBloomFilter::getCount(const Address& addr) -{ - return isSet(addr)? 1: 0; -} - -int MultiBitSelBloomFilter::getIndex(const Address& addr) -{ - return 0; -} - -int MultiBitSelBloomFilter::readBit(const int index) { - return 0; -} - -void MultiBitSelBloomFilter::writeBit(const int index, const int value) { - -} - -int MultiBitSelBloomFilter::getTotalCount() -{ - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - count += m_filter[i]; - } - return count; -} - -void MultiBitSelBloomFilter::print(ostream& out) const -{ -} - -int MultiBitSelBloomFilter::get_index(const Address& addr, int i) -{ - // m_skip_bits is used to perform BitSelect after skipping some bits. Used to simulate BitSel hashing on larger than cache-line granularities - uint64 x = (addr.getLineAddress()) >> m_skip_bits; - int y = hash_bitsel(x, i, m_num_hashes, 30, m_filter_size_bits); - //36-bit addresses, 6-bit cache lines - - if(isParallel) { - return (y % m_par_filter_size) + i*m_par_filter_size; - } else { - return y % m_filter_size; - } -} - - -int MultiBitSelBloomFilter::hash_bitsel(uint64 value, int index, int jump, int maxBits, int numBits) { - uint64 mask = 1; - int result = 0; - int bit, i; - - for(i = 0; i < numBits; i++) { - bit = (index + jump*i) % maxBits; - if (value & (mask << bit)) result += mask << i; - } - return result; -} diff --git a/src/mem/ruby/system/MultiBitSelBloomFilter.hh b/src/mem/ruby/system/MultiBitSelBloomFilter.hh deleted file mode 100644 index 1fa7e7e63..000000000 --- a/src/mem/ruby/system/MultiBitSelBloomFilter.hh +++ /dev/null @@ -1,98 +0,0 @@ - -/* - * 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. - */ - -/* - * MultiBitSelBloomFilter.h - * - * Description: - * - * - */ - -#ifndef MULTIBITSEL_BLOOM_FILTER_H -#define MULTIBITSEL_BLOOM_FILTER_H - -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Global.hh" -#include "mem/ruby/slicc_interface/AbstractChip.hh" -#include "mem/ruby/system/System.hh" -#include "mem/ruby/profiler/Profiler.hh" -#include "mem/ruby/config/RubyConfig.hh" -#include "mem/ruby/common/Address.hh" -#include "mem/ruby/system/AbstractBloomFilter.hh" - -class MultiBitSelBloomFilter : public AbstractBloomFilter { -public: - - ~MultiBitSelBloomFilter(); - MultiBitSelBloomFilter(string config); - - void clear(); - void increment(const Address& addr); - void decrement(const Address& addr); - void merge(AbstractBloomFilter * other_filter); - void set(const Address& addr); - void unset(const Address& addr); - - bool isSet(const Address& addr); - int getCount(const Address& addr); - int getTotalCount(); - void print(ostream& out) const; - - int getIndex(const Address& addr); - int readBit(const int index); - void writeBit(const int index, const int value); - - int operator[](const int index) const{ - return this->m_filter[index]; - } - -private: - - int get_index(const Address& addr, int hashNumber); - - int hash_bitsel(uint64 value, int index, int jump, int maxBits, int numBits); - - Vector<int> m_filter; - int m_filter_size; - int m_num_hashes; - int m_filter_size_bits; - int m_skip_bits; - - int m_par_filter_size; - int m_par_filter_size_bits; - - int m_count_bits; - int m_count; - - bool isParallel; - -}; - -#endif diff --git a/src/mem/ruby/system/MultiGrainBloomFilter.cc b/src/mem/ruby/system/MultiGrainBloomFilter.cc deleted file mode 100644 index 2af95514f..000000000 --- a/src/mem/ruby/system/MultiGrainBloomFilter.cc +++ /dev/null @@ -1,172 +0,0 @@ - -/* - * 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. - */ - -/* - * MultiGrainBloomFilter.C - * - * Description: - * - * - */ - -#include "mem/ruby/system/MultiGrainBloomFilter.hh" -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Address.hh" - -MultiGrainBloomFilter::MultiGrainBloomFilter(string str) -{ - string tail(str); - - // split into the 2 filter sizes - string head = string_split(tail, '_'); - - // head contains size of 1st bloom filter, tail contains size of 2nd bloom filter - - m_filter_size = atoi(head.c_str()); - m_filter_size_bits = log_int(m_filter_size); - - m_page_filter_size = atoi(tail.c_str()); - m_page_filter_size_bits = log_int(m_page_filter_size); - - m_filter.setSize(m_filter_size); - m_page_filter.setSize(m_page_filter_size); - clear(); -} - -MultiGrainBloomFilter::~MultiGrainBloomFilter(){ -} - -void MultiGrainBloomFilter::clear() -{ - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } - for(int i=0; i < m_page_filter_size; ++i){ - m_page_filter[i] = 0; - } -} - -void MultiGrainBloomFilter::increment(const Address& addr) -{ - // Not used -} - - -void MultiGrainBloomFilter::decrement(const Address& addr) -{ - // Not used -} - -void MultiGrainBloomFilter::merge(AbstractBloomFilter * other_filter) -{ - // TODO -} - -void MultiGrainBloomFilter::set(const Address& addr) -{ - int i = get_block_index(addr); - int j = get_page_index(addr); - assert(i < m_filter_size); - assert(j < m_page_filter_size); - m_filter[i] = 1; - m_page_filter[i] = 1; - -} - -void MultiGrainBloomFilter::unset(const Address& addr) -{ - // not used -} - -bool MultiGrainBloomFilter::isSet(const Address& addr) -{ - int i = get_block_index(addr); - int j = get_page_index(addr); - assert(i < m_filter_size); - assert(j < m_page_filter_size); - // we have to have both indices set - return (m_filter[i] && m_page_filter[i]); -} - -int MultiGrainBloomFilter::getCount(const Address& addr) -{ - // not used - return 0; -} - -int MultiGrainBloomFilter::getTotalCount() -{ - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - count += m_filter[i]; - } - - for(int i=0; i < m_page_filter_size; ++i){ - count += m_page_filter[i] = 0; - } - - return count; -} - -int MultiGrainBloomFilter::getIndex(const Address& addr) -{ - return 0; - // TODO -} - -int MultiGrainBloomFilter::readBit(const int index) { - return 0; - // TODO -} - -void MultiGrainBloomFilter::writeBit(const int index, const int value) { - // TODO -} - -void MultiGrainBloomFilter::print(ostream& out) const -{ -} - -int MultiGrainBloomFilter::get_block_index(const Address& addr) -{ - // grap a chunk of bits after byte offset - return addr.bitSelect( RubyConfig::dataBlockBits(), RubyConfig::dataBlockBits() + m_filter_size_bits - 1); -} - -int MultiGrainBloomFilter::get_page_index(const Address & addr) -{ - // grap a chunk of bits after first chunk - return addr.bitSelect( RubyConfig::dataBlockBits() + m_filter_size_bits - 1, - RubyConfig::dataBlockBits() + m_filter_size_bits - 1 + m_page_filter_size_bits - 1); -} - - - - diff --git a/src/mem/ruby/system/MultiGrainBloomFilter.hh b/src/mem/ruby/system/MultiGrainBloomFilter.hh deleted file mode 100644 index 943e5283b..000000000 --- a/src/mem/ruby/system/MultiGrainBloomFilter.hh +++ /dev/null @@ -1,89 +0,0 @@ - -/* - * 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. - */ - -/* - * MultiGrainBloomFilter.h - * - * Description: - * - * - */ - -#ifndef MULTIGRAIN_BLOOM_FILTER_H -#define MULTIGRAIN_BLOOM_FILTER_H - -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Global.hh" -#include "mem/ruby/slicc_interface/AbstractChip.hh" -#include "mem/ruby/config/RubyConfig.hh" -#include "mem/ruby/common/Address.hh" -#include "mem/ruby/system/AbstractBloomFilter.hh" - -class MultiGrainBloomFilter : public AbstractBloomFilter { -public: - - ~MultiGrainBloomFilter(); - MultiGrainBloomFilter(string str); - - void clear(); - void increment(const Address& addr); - void decrement(const Address& addr); - void merge(AbstractBloomFilter * other_filter); - void set(const Address& addr); - void unset(const Address& addr); - - bool isSet(const Address& addr); - int getCount(const Address& addr); - int getTotalCount(); - int getIndex(const Address& addr); - int readBit(const int index); - void writeBit(const int index, const int value); - - void print(ostream& out) const; - -private: - - int get_block_index(const Address& addr); - int get_page_index(const Address & addr); - - // The block filter - Vector<int> m_filter; - int m_filter_size; - int m_filter_size_bits; - // The page number filter - Vector<int> m_page_filter; - int m_page_filter_size; - int m_page_filter_size_bits; - - int m_count_bits; - int m_count; -}; - - -#endif diff --git a/src/mem/ruby/system/NonCountingBloomFilter.cc b/src/mem/ruby/system/NonCountingBloomFilter.cc deleted file mode 100644 index b8f35322d..000000000 --- a/src/mem/ruby/system/NonCountingBloomFilter.cc +++ /dev/null @@ -1,145 +0,0 @@ - -/* - * 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. - */ - -/* - * NonCountingBloomFilter.C - * - * Description: - * - * - */ - -#include "mem/ruby/system/NonCountingBloomFilter.hh" -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Address.hh" - -NonCountingBloomFilter::NonCountingBloomFilter(string str) -{ - string tail(str); - string head = string_split(tail, '_'); - - // head contains filter size, tail contains bit offset from block number - int smt_threads = RubyConfig::numberofSMTThreads(); - m_filter_size = atoi(head.c_str()); - m_offset = atoi(tail.c_str()); - m_filter_size_bits = log_int(m_filter_size); - - - m_filter.setSize(m_filter_size); - clear(); -} - -NonCountingBloomFilter::~NonCountingBloomFilter(){ -} - -void NonCountingBloomFilter::clear() -{ - for (int i = 0; i < m_filter_size; i++) { - m_filter[i] = 0; - } -} - -void NonCountingBloomFilter::increment(const Address& addr) -{ - // Not used -} - - -void NonCountingBloomFilter::decrement(const Address& addr) -{ - // Not used -} - -void NonCountingBloomFilter::merge(AbstractBloomFilter * other_filter){ - // assumes both filters are the same size! - NonCountingBloomFilter * temp = (NonCountingBloomFilter*) other_filter; - for(int i=0; i < m_filter_size; ++i){ - m_filter[i] |= (*temp)[i]; - } - -} - -void NonCountingBloomFilter::set(const Address& addr) -{ - int i = get_index(addr); - m_filter[i] = 1; -} - -void NonCountingBloomFilter::unset(const Address& addr) -{ - int i = get_index(addr); - m_filter[i] = 0; -} - -bool NonCountingBloomFilter::isSet(const Address& addr) -{ - int i = get_index(addr); - return (m_filter[i]); -} - - -int NonCountingBloomFilter::getCount(const Address& addr) -{ - return m_filter[get_index(addr)]; -} - -int NonCountingBloomFilter::getTotalCount() -{ - int count = 0; - - for (int i = 0; i < m_filter_size; i++) { - count += m_filter[i]; - } - return count; -} - -void NonCountingBloomFilter::print(ostream& out) const -{ -} - -int NonCountingBloomFilter::getIndex(const Address& addr) -{ - return get_index(addr); -} - -int NonCountingBloomFilter::readBit(const int index) { - return m_filter[index]; -} - -void NonCountingBloomFilter::writeBit(const int index, const int value) { - m_filter[index] = value; -} - -int NonCountingBloomFilter::get_index(const Address& addr) -{ - return addr.bitSelect( RubyConfig::dataBlockBits() + m_offset, - RubyConfig::dataBlockBits() + m_offset + m_filter_size_bits - 1); -} - - diff --git a/src/mem/ruby/system/NonCountingBloomFilter.hh b/src/mem/ruby/system/NonCountingBloomFilter.hh deleted file mode 100644 index 46ae3e84a..000000000 --- a/src/mem/ruby/system/NonCountingBloomFilter.hh +++ /dev/null @@ -1,89 +0,0 @@ - -/* - * 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. - */ - -/* - * NonCountingBloomFilter.h - * - * Description: - * - * - */ - -#ifndef NONCOUNTING_BLOOM_FILTER_H -#define NONCOUNTING_BLOOM_FILTER_H - -#include "mem/gems_common/Map.hh" -#include "mem/ruby/common/Global.hh" -#include "mem/ruby/slicc_interface/AbstractChip.hh" -#include "mem/ruby/config/RubyConfig.hh" -#include "mem/ruby/common/Address.hh" -#include "mem/ruby/system/AbstractBloomFilter.hh" - -class NonCountingBloomFilter : public AbstractBloomFilter { -public: - - ~NonCountingBloomFilter(); - NonCountingBloomFilter(string config); - - void clear(); - void increment(const Address& addr); - void decrement(const Address& addr); - void merge(AbstractBloomFilter * other_filter); - void set(const Address& addr); - void unset(const Address& addr); - - bool isSet(const Address& addr); - int getCount(const Address& addr); - int getTotalCount(); - - int getIndex(const Address& addr); - int readBit(const int index); - void writeBit(const int index, const int value); - - void print(ostream& out) const; - - int operator[](const int index) const{ - return this->m_filter[index]; - } - -private: - - int get_index(const Address& addr); - - Vector<int> m_filter; - int m_filter_size; - int m_offset; - int m_filter_size_bits; - - int m_count_bits; - int m_count; -}; - - -#endif diff --git a/src/mem/ruby/system/SConscript b/src/mem/ruby/system/SConscript index 1840ff0cc..5ce612107 100644 --- a/src/mem/ruby/system/SConscript +++ b/src/mem/ruby/system/SConscript @@ -30,18 +30,10 @@ Import('*') -Source('BlockBloomFilter.cc') -Source('BulkBloomFilter.cc') Source('DirectoryMemory.cc') -Source('GenericBloomFilter.cc') -Source('H3BloomFilter.cc') -Source('LSB_CountingBloomFilter.cc') Source('MemoryControl.cc') Source('MemoryNode.cc') -Source('MultiBitSelBloomFilter.cc') -Source('MultiGrainBloomFilter.cc') Source('NodePersistentTable.cc') -Source('NonCountingBloomFilter.cc') Source('PersistentTable.cc') Source('Sequencer.cc', Werror=False) Source('StoreBuffer.cc') |