NetDest.cc revision 9138
12SN/A/* 211274Sshingarov@labware.com * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 310595Sgabeblack@google.com * All rights reserved. 41762SN/A * 52SN/A * Redistribution and use in source and binary forms, with or without 62SN/A * modification, are permitted provided that the following conditions are 72SN/A * met: redistributions of source code must retain the above copyright 82SN/A * notice, this list of conditions and the following disclaimer; 92SN/A * redistributions in binary form must reproduce the above copyright 102SN/A * notice, this list of conditions and the following disclaimer in the 112SN/A * documentation and/or other materials provided with the distribution; 122SN/A * neither the name of the copyright holders nor the names of its 132SN/A * contributors may be used to endorse or promote products derived from 142SN/A * this software without specific prior written permission. 152SN/A * 162SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272SN/A */ 282SN/A 292665Ssaidi@eecs.umich.edu#include <algorithm> 302665Ssaidi@eecs.umich.edu 3111274Sshingarov@labware.com#include "mem/ruby/common/NetDest.hh" 322SN/A 332SN/ANetDest::NetDest() 342SN/A{ 352SN/A resize(); 362SN/A} 373960Sgblack@eecs.umich.edu 3877SN/Avoid 3912031Sgabeblack@google.comNetDest::add(MachineID newElement) 408229Snate@binkert.org{ 4112031Sgabeblack@google.com assert(bitIndex(newElement.num) < m_bits[vecIndex(newElement)].getSize()); 428229Snate@binkert.org m_bits[vecIndex(newElement)].add(bitIndex(newElement.num)); 432986Sgblack@eecs.umich.edu} 4410595Sgabeblack@google.com 4556SN/Avoid 4656SN/ANetDest::addNetDest(const NetDest& netDest) 478229Snate@binkert.org{ 482SN/A assert(m_bits.size() == netDest.getSize()); 492SN/A for (int i = 0; i < m_bits.size(); i++) { 502680Sktlim@umich.edu m_bits[i].addSet(netDest.m_bits[i]); 512SN/A } 521910SN/A} 533536Sgblack@eecs.umich.edu 5412031Sgabeblack@google.comvoid 5512031Sgabeblack@google.comNetDest::addRandom() 5612031Sgabeblack@google.com{ 572SN/A int i = random()%m_bits.size(); 5812031Sgabeblack@google.com m_bits[i].addRandom(); 5912031Sgabeblack@google.com} 6012031Sgabeblack@google.com 6112031Sgabeblack@google.comvoid 6212031Sgabeblack@google.comNetDest::setNetDest(MachineType machine, const Set& set) 6312031Sgabeblack@google.com{ 6412031Sgabeblack@google.com // assure that there is only one set of destinations for this machine 6512031Sgabeblack@google.com assert(MachineType_base_level((MachineType)(machine + 1)) - 6612031Sgabeblack@google.com MachineType_base_level(machine) == 1); 6712031Sgabeblack@google.com m_bits[MachineType_base_level(machine)] = set; 6812031Sgabeblack@google.com} 6912031Sgabeblack@google.com 7012031Sgabeblack@google.comvoid 7112031Sgabeblack@google.comNetDest::remove(MachineID oldElement) 7212031Sgabeblack@google.com{ 7312031Sgabeblack@google.com m_bits[vecIndex(oldElement)].remove(bitIndex(oldElement.num)); 7412031Sgabeblack@google.com} 753536Sgblack@eecs.umich.edu 763536Sgblack@eecs.umich.eduvoid 773536Sgblack@eecs.umich.eduNetDest::removeNetDest(const NetDest& netDest) 783536Sgblack@eecs.umich.edu{ 791910SN/A assert(m_bits.size() == netDest.getSize()); 801910SN/A for (int i = 0; i < m_bits.size(); i++) { 811910SN/A m_bits[i].removeSet(netDest.m_bits[i]); 821910SN/A } 8312031Sgabeblack@google.com} 8412031Sgabeblack@google.com 8512031Sgabeblack@google.comvoid 8612031Sgabeblack@google.comNetDest::clear() 8712031Sgabeblack@google.com{ 8812031Sgabeblack@google.com for (int i = 0; i < m_bits.size(); i++) { 8912031Sgabeblack@google.com m_bits[i].clear(); 9012031Sgabeblack@google.com } 9112031Sgabeblack@google.com} 9212031Sgabeblack@google.com 9312031Sgabeblack@google.comvoid 9412031Sgabeblack@google.comNetDest::broadcast() 9512031Sgabeblack@google.com{ 9612031Sgabeblack@google.com for (MachineType machine = MachineType_FIRST; 9712031Sgabeblack@google.com machine < MachineType_NUM; ++machine) { 9812031Sgabeblack@google.com broadcast(machine); 9912031Sgabeblack@google.com } 10012031Sgabeblack@google.com} 10112031Sgabeblack@google.com 1023536Sgblack@eecs.umich.eduvoid 1033536Sgblack@eecs.umich.eduNetDest::broadcast(MachineType machineType) 1043536Sgblack@eecs.umich.edu{ 1053536Sgblack@eecs.umich.edu for (int i = 0; i < MachineType_base_count(machineType); i++) { 10612031Sgabeblack@google.com MachineID mach = {machineType, i}; 10712031Sgabeblack@google.com add(mach); 10812031Sgabeblack@google.com } 10911274Sshingarov@labware.com} 11011274Sshingarov@labware.com 1113536Sgblack@eecs.umich.edu//For Princeton Network 11212031Sgabeblack@google.comstd::vector<NodeID> 11312031Sgabeblack@google.comNetDest::getAllDest() 11412031Sgabeblack@google.com{ 11512031Sgabeblack@google.com std::vector<NodeID> dest; 11612031Sgabeblack@google.com dest.clear(); 11712031Sgabeblack@google.com for (int i = 0; i < m_bits.size(); i++) { 11812031Sgabeblack@google.com for (int j = 0; j < m_bits[i].getSize(); j++) { 11912031Sgabeblack@google.com if (m_bits[i].isElement(j)) { 12012031Sgabeblack@google.com int id = MachineType_base_number((MachineType)i) + j; 12112031Sgabeblack@google.com dest.push_back((NodeID)id); 12212031Sgabeblack@google.com } 12312031Sgabeblack@google.com } 12412031Sgabeblack@google.com } 12512031Sgabeblack@google.com return dest; 12612031Sgabeblack@google.com} 12712031Sgabeblack@google.com 12812031Sgabeblack@google.comint 12912031Sgabeblack@google.comNetDest::count() const 13012031Sgabeblack@google.com{ 13112031Sgabeblack@google.com int counter = 0; 1323536Sgblack@eecs.umich.edu for (int i = 0; i < m_bits.size(); i++) { 1332SN/A counter += m_bits[i].count(); 13410598Sgabeblack@google.com } 1352SN/A return counter; 1362SN/A} 1373536Sgblack@eecs.umich.edu 1382SN/ANodeID 1392SN/ANetDest::elementAt(MachineID index) 14010598Sgabeblack@google.com{ 1412SN/A return m_bits[vecIndex(index)].elementAt(bitIndex(index.num)); 1422SN/A} 1432SN/A 14410598Sgabeblack@google.comMachineID 14510597Sgabeblack@google.comNetDest::smallestElement() const 14610597Sgabeblack@google.com{ 14710597Sgabeblack@google.com assert(count() > 0); 14810597Sgabeblack@google.com for (int i = 0; i < m_bits.size(); i++) { 14910597Sgabeblack@google.com for (int j = 0; j < m_bits[i].getSize(); j++) { 15010597Sgabeblack@google.com if (m_bits[i].isElement(j)) { 15110597Sgabeblack@google.com MachineID mach = {MachineType_from_base_level(i), j}; 15210597Sgabeblack@google.com return mach; 15310597Sgabeblack@google.com } 15410597Sgabeblack@google.com } 15510597Sgabeblack@google.com } 15610597Sgabeblack@google.com panic("No smallest element of an empty set."); 15710597Sgabeblack@google.com} 15810598Sgabeblack@google.com 15910598Sgabeblack@google.comMachineID 16010597Sgabeblack@google.comNetDest::smallestElement(MachineType machine) const 1611910SN/A{ 1621910SN/A int size = m_bits[MachineType_base_level(machine)].getSize(); 1632SN/A for (int j = 0; j < size; j++) { 1642SN/A if (m_bits[MachineType_base_level(machine)].isElement(j)) { 16512031Sgabeblack@google.com MachineID mach = {machine, j}; 1662SN/A return mach; 1672SN/A } 1682SN/A } 1692SN/A 1702SN/A panic("No smallest element of given MachineType."); 1712SN/A} 1722SN/A 1732680Sktlim@umich.edu// Returns true iff all bits are set 1742SN/Abool 1752SN/ANetDest::isBroadcast() const 17611274Sshingarov@labware.com{ 17711274Sshingarov@labware.com for (int i = 0; i < m_bits.size(); i++) { 17811274Sshingarov@labware.com if (!m_bits[i].isBroadcast()) { 17911274Sshingarov@labware.com return false; 18011274Sshingarov@labware.com } 18111274Sshingarov@labware.com } 18211274Sshingarov@labware.com return true; 18311274Sshingarov@labware.com} 1843536Sgblack@eecs.umich.edu 1853536Sgblack@eecs.umich.edu// Returns true iff no bits are set 18611274Sshingarov@labware.combool 18711274Sshingarov@labware.comNetDest::isEmpty() const 18811274Sshingarov@labware.com{ 18911274Sshingarov@labware.com for (int i = 0; i < m_bits.size(); i++) { 19011274Sshingarov@labware.com if (!m_bits[i].isEmpty()) { 19111274Sshingarov@labware.com return false; 19211274Sshingarov@labware.com } 19311274Sshingarov@labware.com } 19411274Sshingarov@labware.com return true; 19511274Sshingarov@labware.com} 19611274Sshingarov@labware.com 19711274Sshingarov@labware.com// returns the logical OR of "this" set and orNetDest 19811274Sshingarov@labware.comNetDest 19911274Sshingarov@labware.comNetDest::OR(const NetDest& orNetDest) const 20011274Sshingarov@labware.com{ 20111274Sshingarov@labware.com assert(m_bits.size() == orNetDest.getSize()); 20211274Sshingarov@labware.com NetDest result; 20311274Sshingarov@labware.com for (int i = 0; i < m_bits.size(); i++) { 20411274Sshingarov@labware.com result.m_bits[i] = m_bits[i].OR(orNetDest.m_bits[i]); 20511274Sshingarov@labware.com } 20611274Sshingarov@labware.com return result; 20711274Sshingarov@labware.com} 20811274Sshingarov@labware.com 20911274Sshingarov@labware.com// returns the logical AND of "this" set and andNetDest 21011274Sshingarov@labware.comNetDest 21111274Sshingarov@labware.comNetDest::AND(const NetDest& andNetDest) const 21211274Sshingarov@labware.com{ 21311274Sshingarov@labware.com assert(m_bits.size() == andNetDest.getSize()); 21411274Sshingarov@labware.com NetDest result; 21511274Sshingarov@labware.com for (int i = 0; i < m_bits.size(); i++) { 21611274Sshingarov@labware.com result.m_bits[i] = m_bits[i].AND(andNetDest.m_bits[i]); 21711274Sshingarov@labware.com } 21811274Sshingarov@labware.com return result; 21911274Sshingarov@labware.com} 2203536Sgblack@eecs.umich.edu 22112031Sgabeblack@google.com// Returns true if the intersection of the two sets is non-empty 22212031Sgabeblack@google.combool 2233536Sgblack@eecs.umich.eduNetDest::intersectionIsNotEmpty(const NetDest& other_netDest) const 22411274Sshingarov@labware.com{ 22511274Sshingarov@labware.com assert(m_bits.size() == other_netDest.getSize()); 2263536Sgblack@eecs.umich.edu for (int i = 0; i < m_bits.size(); i++) { 2273536Sgblack@eecs.umich.edu if (!m_bits[i].intersectionIsEmpty(other_netDest.m_bits[i])) { 22812031Sgabeblack@google.com return true; 22912031Sgabeblack@google.com } 2303536Sgblack@eecs.umich.edu } 23112031Sgabeblack@google.com return false; 23212031Sgabeblack@google.com} 2332SN/A 2342SN/Abool 23512031Sgabeblack@google.comNetDest::isSuperset(const NetDest& test) const 2362SN/A{ 2372SN/A assert(m_bits.size() == test.getSize()); 2382SN/A 2393536Sgblack@eecs.umich.edu for (int i = 0; i < m_bits.size(); i++) { 2403536Sgblack@eecs.umich.edu if (!m_bits[i].isSuperset(test.m_bits[i])) { 2412SN/A return false; 2422SN/A } 2432SN/A } 2442SN/A return true; 2452SN/A} 24611274Sshingarov@labware.com 2473536Sgblack@eecs.umich.edubool 24811274Sshingarov@labware.comNetDest::isElement(MachineID element) const 2492SN/A{ 2502680Sktlim@umich.edu return ((m_bits[vecIndex(element)])).isElement(bitIndex(element.num)); 251180SN/A} 2522SN/A 2532SN/Avoid 2542SN/ANetDest::resize() 2552SN/A{ 2563536Sgblack@eecs.umich.edu m_bits.resize(MachineType_base_level(MachineType_NUM)); 2572SN/A assert(m_bits.size() == MachineType_NUM); 2583960Sgblack@eecs.umich.edu 2593960Sgblack@eecs.umich.edu for (int i = 0; i < m_bits.size(); i++) { 2603960Sgblack@eecs.umich.edu m_bits[i].setSize(MachineType_base_count((MachineType)i)); 2613960Sgblack@eecs.umich.edu } 2622SN/A} 2632SN/A 26410601Sgabeblack@google.comvoid 26510601Sgabeblack@google.comNetDest::print(std::ostream& out) const 26610601Sgabeblack@google.com{ 26710601Sgabeblack@google.com out << "[NetDest (" << m_bits.size() << ") "; 26810601Sgabeblack@google.com 26910601Sgabeblack@google.com for (int i = 0; i < m_bits.size(); i++) { 27010601Sgabeblack@google.com for (int j = 0; j < m_bits[i].getSize(); j++) { 27110601Sgabeblack@google.com out << (bool) m_bits[i].isElement(j) << " "; 27210601Sgabeblack@google.com } 27310601Sgabeblack@google.com out << " - "; 27410601Sgabeblack@google.com } 27510601Sgabeblack@google.com out << "]"; 27610601Sgabeblack@google.com} 27710601Sgabeblack@google.com 27810601Sgabeblack@google.com