diff options
Diffstat (limited to 'src/mem/ruby/common')
| -rw-r--r-- | src/mem/ruby/common/BigSet.cc | 249 | ||||
| -rw-r--r-- | src/mem/ruby/common/BigSet.hh | 125 | ||||
| -rw-r--r-- | src/mem/ruby/common/OptBigSet.cc | 576 | ||||
| -rw-r--r-- | src/mem/ruby/common/OptBigSet.hh | 202 | ||||
| -rw-r--r-- | src/mem/ruby/common/Set.cc | 549 | ||||
| -rw-r--r-- | src/mem/ruby/common/Set.hh | 117 |
6 files changed, 532 insertions, 1286 deletions
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 |