diff options
| -rw-r--r-- | src/mem/ruby/common/NetDest.hh | 6 | ||||
| -rw-r--r-- | src/mem/ruby/common/SConscript | 1 | ||||
| -rw-r--r-- | src/mem/ruby/common/Set.cc | 341 | ||||
| -rw-r--r-- | src/mem/ruby/common/Set.hh | 209 |
4 files changed, 137 insertions, 420 deletions
diff --git a/src/mem/ruby/common/NetDest.hh b/src/mem/ruby/common/NetDest.hh index e09be0c2c..69bfa8a3e 100644 --- a/src/mem/ruby/common/NetDest.hh +++ b/src/mem/ruby/common/NetDest.hh @@ -26,11 +26,6 @@ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -// NetDest specifies the network destination of a Message -// This is backward compatible with the Set class that was previously -// used to specify network destinations. -// NetDest supports both node networks and component networks - #ifndef __MEM_RUBY_COMMON_NETDEST_HH__ #define __MEM_RUBY_COMMON_NETDEST_HH__ @@ -40,6 +35,7 @@ #include "mem/ruby/common/Set.hh" #include "mem/ruby/common/MachineID.hh" +// NetDest specifies the network destination of a Message class NetDest { public: diff --git a/src/mem/ruby/common/SConscript b/src/mem/ruby/common/SConscript index 3c149388a..f8660da39 100644 --- a/src/mem/ruby/common/SConscript +++ b/src/mem/ruby/common/SConscript @@ -38,5 +38,4 @@ Source('Consumer.cc') Source('DataBlock.cc') Source('Histogram.cc') Source('NetDest.cc') -Source('Set.cc') Source('SubBlock.cc') diff --git a/src/mem/ruby/common/Set.cc b/src/mem/ruby/common/Set.cc deleted file mode 100644 index 331aa569a..000000000 --- a/src/mem/ruby/common/Set.cc +++ /dev/null @@ -1,341 +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. - */ - -// modified (rewritten) 05/20/05 by Dan Gibson to accomimdate FASTER -// >32 bit set sizes - -#include <cassert> -#include <cstdio> - -#include "base/misc.hh" -#include "mem/ruby/common/Set.hh" - -Set::Set() -{ - m_p_nArray = NULL; - m_nArrayLen = 0; - m_nSize = 0; -} - -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; - m_nArrayLen = 0; - m_nSize = 0; - if (size > 0) - setSize(size); -} - -Set::~Set() -{ - if (m_p_nArray && m_p_nArray != &m_p_nArray_Static[0]) - delete [] m_p_nArray; - m_p_nArray = NULL; -} - -void -Set::clearExcess() -{ - // now just ensure that no bits over the maximum size were set -#ifdef _LP64 - unsigned long mask = 0x7FFFFFFFFFFFFFFF; -#else - unsigned long mask = 0x7FFFFFFF; -#endif - - // the number of populated spaces in the higest-order array slot - // is: m_nSize % LONG_BITS, so the uppermost LONG_BITS - - // m_nSize%64 bits should be cleared - if ((m_nSize % LONG_BITS) != 0) { - for (int j = 0; j < 64 - (m_nSize & INDEX_MASK); j++) { - m_p_nArray[m_nArrayLen - 1] &= mask; - mask = mask >> 1; - } - } -} - - -/* - * 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 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 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. - - clearExcess(); -} - -/* - * 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_nArrayLen; i++) { - unsigned long mask = 0x01; - - for (int j = 0; j < LONG_BITS; j++) { - // FIXME - significant performance loss when array - // population << LONG_BITS - if ((m_p_nArray[i] & mask) != 0) { - counter++; - } - mask = mask << 1; - } - } - - 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); - for (int i = 0; i < m_nArrayLen; i++) { - if (m_p_nArray[i] != 0) { - // the least-set bit must be in here - unsigned long x = m_p_nArray[i]; - - for (int j = 0; j < LONG_BITS; j++) { - if (x & 1) { - return LONG_BITS * i + j; - } - - x = x >> 1; - } - - panic("No smallest element of an empty set."); - } - } - - panic("No smallest element of an empty set."); -} - -/* - * 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 - - int max = (m_nSize % LONG_BITS) == 0 ? m_nArrayLen : m_nArrayLen - 1; - for (int i = 0; i < max; i++) { - if (m_p_nArray[i] != -1) { - return false; - } - } - - // now check the last word, which may not be fully loaded - unsigned long mask = 1; - for (int j = 0; j < (m_nSize % LONG_BITS); j++) { - if ((mask & m_p_nArray[m_nArrayLen-1]) == 0) { - return false; - } - mask = mask << 1; - } - - 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]) - 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 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; -} - -void -Set::setSize(int size) -{ - m_nSize = size; - m_nArrayLen = (m_nSize + LONG_BITS - 1) / LONG_BITS; - - // decide whether to use dynamic or static alloction - if (m_nArrayLen <= NUMBER_WORDS_PER_SET) { - // constant defined in RubySystem.hh - // 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 && 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 && m_p_nArray != &m_p_nArray_Static[0]) - delete [] m_p_nArray; - - m_p_nArray = new unsigned long[m_nArrayLen]; - } - - clear(); -} - -Set& -Set::operator=(const Set& obj) -{ - if (this != &obj) { - // 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(std::ostream& out) const -{ - if (!m_p_nArray) { - out << "[Set {Empty}]"; - return; - } - - out << "[Set (" << m_nSize << ")"; - for (int i = m_nArrayLen - 1; i >= 0; i--) { - out << csprintf(" 0x%08X", m_p_nArray[i]); - } - out << " ]"; -} diff --git a/src/mem/ruby/common/Set.hh b/src/mem/ruby/common/Set.hh index e97385e5e..3ab6979d4 100644 --- a/src/mem/ruby/common/Set.hh +++ b/src/mem/ruby/common/Set.hh @@ -32,129 +32,192 @@ #ifndef __MEM_RUBY_COMMON_SET_HH__ #define __MEM_RUBY_COMMON_SET_HH__ +#include <bitset> +#include <cassert> #include <iostream> -#include <limits> +#include "base/misc.hh" #include "mem/ruby/common/TypeDefines.hh" -/* - * This defines the number of longs (32-bits on 32 bit machines, - * 64-bit on 64-bit AMD machines) to use to hold the set... - * the default is 4, allowing 128 or 256 different members - * of the set. - * - * This should never need to be changed for correctness reasons, - * though increasing it will increase performance for larger - * set sizes at the cost of a (much) larger memory footprint - * - */ -const int NUMBER_WORDS_PER_SET = 1; +// Change for systems with more than 64 controllers of a particular type. +const int NUMBER_BITS_PER_SET = 64; class Set { private: - 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 - - // an word array to hold the bits in the set - unsigned long *m_p_nArray; - unsigned long m_p_nArray_Static[NUMBER_WORDS_PER_SET]; + // Number of bits in use in this set. + int m_nSize; + std::bitset<NUMBER_BITS_PER_SET> bits; - static const int LONG_BITS = - std::numeric_limits<unsigned long>::digits + 1; - static const int INDEX_SHIFT = LONG_BITS == 64 ? 6 : 5; - static const int INDEX_MASK = (1 << INDEX_SHIFT) - 1; + public: + Set() : m_nSize(0) {} - void clearExcess(); + Set(int size) : m_nSize(size) + { + if (size > NUMBER_BITS_PER_SET) + fatal("Number of bits(%d) < size specified(%d). " + "Increase the number of bits and recompile.\n", + NUMBER_BITS_PER_SET, size); + } - public: - Set(); - Set(int size); - Set(const Set& obj); - ~Set(); + Set(const Set& obj) : m_nSize(obj.m_nSize), bits(obj.bits) {} + ~Set() {} - Set& operator=(const Set& obj); + Set& operator=(const Set& obj) + { + m_nSize = obj.m_nSize; + bits = obj.bits; + return *this; + } void add(NodeID index) { - m_p_nArray[index >> INDEX_SHIFT] |= - (((unsigned long) 1) << (index & INDEX_MASK)); + bits.set(index); } - void addSet(const Set& set); + /* + * This function should set all the bits in the current set that are + * already set in the parameter set + */ + void + addSet(const Set& obj) + { + assert(m_nSize == obj.m_nSize); + bits |= obj.bits; + } + /* + * This function clears bits that are =1 in the parameter set + */ void remove(NodeID index) { - m_p_nArray[index >> INDEX_SHIFT] &= - ~(((unsigned long)1) << (index & INDEX_MASK)); + bits.reset(index); } - void removeSet(const Set& set); - + /* + * This function clears bits that are =1 in the parameter set + */ void - clear() + removeSet(const Set& obj) { - for (int i = 0; i < m_nArrayLen; i++) - m_p_nArray[i] = 0; + assert(m_nSize == obj.m_nSize); + bits &= (~obj.bits); } - void broadcast(); - int count() const; - bool isEqual(const Set& set) const; + void clear() { bits.reset(); } + + /* + * this function sets all bits in the set + */ + void broadcast() + { + bits.set(); + for (int j = m_nSize; j < NUMBER_BITS_PER_SET; ++j) { + bits.reset(j); + } + } + + /* + * This function returns the population count of 1's in the set + */ + int count() const { return bits.count(); } + + /* + * This function checks for set equality + */ + bool + isEqual(const Set& obj) const + { + assert(m_nSize == obj.m_nSize); + return bits == obj.bits; + } // return the logical OR of this set and orSet - Set OR(const Set& orSet) const; + Set + OR(const Set& obj) const + { + assert(m_nSize == obj.m_nSize); + Set r(m_nSize); + r.bits = bits | obj.bits; + return r; + }; // return the logical AND of this set and andSet - Set AND(const Set& andSet) const; + Set + AND(const Set& obj) const + { + assert(m_nSize == obj.m_nSize); + Set r(m_nSize); + r.bits = bits & obj.bits; + return r; + } // Returns true if the intersection of the two sets is empty bool - intersectionIsEmpty(const Set& other_set) const + intersectionIsEmpty(const Set& obj) const { - for (int i = 0; i < m_nArrayLen; i++) - if (m_p_nArray[i] & other_set.m_p_nArray[i]) - return false; - return true; + std::bitset<NUMBER_BITS_PER_SET> r = bits & obj.bits; + return r.none(); } - bool isSuperset(const Set& test) const; - bool isSubset(const Set& test) const { return test.isSuperset(*this); } - + /* + * Returns false if a bit is set in the parameter set that is NOT set + * in this set + */ bool - isElement(NodeID element) const + isSuperset(const Set& test) const { - return (m_p_nArray[element>>INDEX_SHIFT] & - (((unsigned long)1) << (element & INDEX_MASK))) != 0; + assert(m_nSize == test.m_nSize); + std::bitset<NUMBER_BITS_PER_SET> r = bits | test.bits; + return (r == bits); } - bool isBroadcast() const; - bool isEmpty() const; + bool isSubset(const Set& test) const { return test.isSuperset(*this); } + + bool isElement(NodeID element) const { return bits.test(element); } - NodeID smallestElement() const; + /* + * this function returns true iff all bits in use are set + */ + bool + isBroadcast() const + { + return (bits.count() == m_nSize); + } - void setSize(int size); + bool isEmpty() const { return bits.none(); } - NodeID - elementAt(int index) const + NodeID smallestElement() const { - if (isElement(index)) - return (NodeID)true; - else - return 0; + for (int i = 0; i < m_nSize; ++i) { + if (bits.test(i)) { + return i; + } + } + panic("No smallest element of an empty set."); } + bool elementAt(int index) const { return bits[index]; } + int getSize() const { return m_nSize; } - void print(std::ostream& out) const; + void + setSize(int size) + { + if (size > NUMBER_BITS_PER_SET) + fatal("Number of bits(%d) < size specified(%d). " + "Increase the number of bits and recompile.\n", + NUMBER_BITS_PER_SET, size); + m_nSize = size; + bits.reset(); + } + + void print(std::ostream& out) const + { + out << "[Set (" << m_nSize << "): " << bits << "]"; + } }; inline std::ostream& |