PerfectSwitch.cc revision 10348:c91b23c72d5e
11060SN/A/* 22702Sktlim@umich.edu * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 36973Stjones1@inf.ed.ac.uk * All rights reserved. 41060SN/A * 51060SN/A * Redistribution and use in source and binary forms, with or without 61060SN/A * modification, are permitted provided that the following conditions are 71060SN/A * met: redistributions of source code must retain the above copyright 81060SN/A * notice, this list of conditions and the following disclaimer; 91060SN/A * redistributions in binary form must reproduce the above copyright 101060SN/A * notice, this list of conditions and the following disclaimer in the 111060SN/A * documentation and/or other materials provided with the distribution; 121060SN/A * neither the name of the copyright holders nor the names of its 131060SN/A * contributors may be used to endorse or promote products derived from 141060SN/A * this software without specific prior written permission. 151060SN/A * 161060SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 171060SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 181060SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 191060SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 201060SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 211060SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 221060SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 231060SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 241060SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 251060SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 261060SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 271060SN/A */ 282665Ssaidi@eecs.umich.edu 292665Ssaidi@eecs.umich.edu#include <algorithm> 306973Stjones1@inf.ed.ac.uk 311060SN/A#include "base/cast.hh" 321060SN/A#include "base/random.hh" 331464SN/A#include "debug/RubyNetwork.hh" 341464SN/A#include "mem/ruby/network/MessageBuffer.hh" 351060SN/A#include "mem/ruby/network/simple/PerfectSwitch.hh" 362731Sktlim@umich.edu#include "mem/ruby/network/simple/SimpleNetwork.hh" 372292SN/A#include "mem/ruby/network/simple/Switch.hh" 381464SN/A#include "mem/ruby/slicc_interface/NetworkMessage.hh" 391060SN/A 402669Sktlim@umich.eduusing namespace std; 417720Sgblack@eecs.umich.edu 421060SN/Aconst int PRIORITY_SWITCH_LIMIT = 128; 431060SN/A 441858SN/A// Operator for helper class 456658Snate@binkert.orgbool 463770Sgblack@eecs.umich.eduoperator<(const LinkOrder& l1, const LinkOrder& l2) 471464SN/A{ 481464SN/A return (l1.m_value < l2.m_value); 492669Sktlim@umich.edu} 501060SN/A 516973Stjones1@inf.ed.ac.ukPerfectSwitch::PerfectSwitch(SwitchID sid, Switch *sw, uint32_t virt_nets) 522669Sktlim@umich.edu : Consumer(sw) 537678Sgblack@eecs.umich.edu{ 542292SN/A m_switch_id = sid; 556023Snate@binkert.org m_round_robin_start = 0; 561060SN/A m_wakeups_wo_switch = 0; 571060SN/A m_virtual_networks = virt_nets; 581060SN/A} 591060SN/A 601060SN/Avoid 611060SN/APerfectSwitch::init(SimpleNetwork *network_ptr) 621061SN/A{ 631061SN/A m_network_ptr = network_ptr; 641060SN/A 651060SN/A for(int i = 0;i < m_virtual_networks;++i) { 661061SN/A m_pending_message_count.push_back(0); 671060SN/A } 681060SN/A} 691060SN/A 702733Sktlim@umich.eduvoid 712733Sktlim@umich.eduPerfectSwitch::addInPort(const map<int, MessageBuffer*>& in) 721060SN/A{ 732292SN/A NodeID port = m_in.size(); 742107SN/A m_in.push_back(in); 752690Sktlim@umich.edu 762107SN/A for (auto& it : in) { 772690Sktlim@umich.edu it.second->setConsumer(this); 782690Sktlim@umich.edu 791060SN/A string desc = csprintf("[Queue from port %s %s %s to PerfectSwitch]", 802292SN/A to_string(m_switch_id), to_string(port), to_string(it.first)); 812292SN/A 822292SN/A it.second->setDescription(desc); 832292SN/A it.second->setIncomingLink(port); 842292SN/A it.second->setVnet(it.first); 852292SN/A } 861060SN/A} 875543Ssaidi@eecs.umich.edu 885543Ssaidi@eecs.umich.eduvoid 891060SN/APerfectSwitch::addOutPort(const map<int, MessageBuffer*>& out, 901060SN/A const NetDest& routing_table_entry) 912292SN/A{ 922107SN/A // Setup link order 931060SN/A LinkOrder l; 941060SN/A l.m_value = 0; 951060SN/A l.m_link = m_out.size(); 961060SN/A m_link_order.push_back(l); 971060SN/A 981060SN/A // Add to routing table 992292SN/A m_out.push_back(out); 1001060SN/A m_routing_table.push_back(routing_table_entry); 1011060SN/A} 1025358Sgblack@eecs.umich.edu 1035358Sgblack@eecs.umich.eduPerfectSwitch::~PerfectSwitch() 1045358Sgblack@eecs.umich.edu{ 1055358Sgblack@eecs.umich.edu} 1065358Sgblack@eecs.umich.edu 1075358Sgblack@eecs.umich.eduvoid 1085358Sgblack@eecs.umich.eduPerfectSwitch::operateVnet(int vnet) 1095358Sgblack@eecs.umich.edu{ 1105358Sgblack@eecs.umich.edu MsgPtr msg_ptr; 1115358Sgblack@eecs.umich.edu NetworkMessage* net_msg_ptr = NULL; 1125358Sgblack@eecs.umich.edu 1135358Sgblack@eecs.umich.edu // This is for round-robin scheduling 1145358Sgblack@eecs.umich.edu int incoming = m_round_robin_start; 1152292SN/A m_round_robin_start++; 1162292SN/A if (m_round_robin_start >= m_in.size()) { 1172292SN/A m_round_robin_start = 0; 1182292SN/A } 1192292SN/A 1202292SN/A if(m_pending_message_count[vnet] > 0) { 1212292SN/A // for all input ports, use round robin scheduling 1221060SN/A for (int counter = 0; counter < m_in.size(); counter++) { 1232132SN/A // Round robin scheduling 1241060SN/A incoming++; 1257520Sgblack@eecs.umich.edu if (incoming >= m_in.size()) { 1267520Sgblack@eecs.umich.edu incoming = 0; 1272292SN/A } 1282292SN/A 1292292SN/A // temporary vectors to store the routing results 1302292SN/A vector<LinkID> output_links; 1312292SN/A vector<NetDest> output_link_destinations; 1322292SN/A 1332292SN/A // Is there a message waiting? 1342292SN/A auto it = m_in[incoming].find(vnet); 1351060SN/A if (it == m_in[incoming].end()) 1366973Stjones1@inf.ed.ac.uk continue; 1376973Stjones1@inf.ed.ac.uk MessageBuffer *buffer = (*it).second; 1387520Sgblack@eecs.umich.edu 1397520Sgblack@eecs.umich.edu while (buffer->isReady()) { 1407520Sgblack@eecs.umich.edu DPRINTF(RubyNetwork, "incoming: %d\n", incoming); 1416974Stjones1@inf.ed.ac.uk 1426974Stjones1@inf.ed.ac.uk // Peek at message 1436974Stjones1@inf.ed.ac.uk msg_ptr = buffer->peekMsgPtr(); 1446974Stjones1@inf.ed.ac.uk net_msg_ptr = safe_cast<NetworkMessage*>(msg_ptr.get()); 1456973Stjones1@inf.ed.ac.uk DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr)); 1466974Stjones1@inf.ed.ac.uk 1476974Stjones1@inf.ed.ac.uk output_links.clear(); 1486973Stjones1@inf.ed.ac.uk output_link_destinations.clear(); 1496973Stjones1@inf.ed.ac.uk NetDest msg_dsts = net_msg_ptr->getInternalDestination(); 1506973Stjones1@inf.ed.ac.uk 1516973Stjones1@inf.ed.ac.uk // Unfortunately, the token-protocol sends some 1521060SN/A // zero-destination messages, so this assert isn't valid 1531684SN/A // assert(msg_dsts.count() > 0); 1541060SN/A 1551060SN/A assert(m_link_order.size() == m_routing_table.size()); 1561060SN/A assert(m_link_order.size() == m_out.size()); 1571060SN/A 1582731Sktlim@umich.edu if (m_network_ptr->getAdaptiveRouting()) { 1592731Sktlim@umich.edu if (m_network_ptr->isVNetOrdered(vnet)) { 1602731Sktlim@umich.edu // Don't adaptively route 1612731Sktlim@umich.edu for (int out = 0; out < m_out.size(); out++) { 1622731Sktlim@umich.edu m_link_order[out].m_link = out; 1632731Sktlim@umich.edu m_link_order[out].m_value = 0; 1642731Sktlim@umich.edu } 1652731Sktlim@umich.edu } else { 1662731Sktlim@umich.edu // Find how clogged each link is 1672731Sktlim@umich.edu for (int out = 0; out < m_out.size(); out++) { 1682731Sktlim@umich.edu int out_queue_length = 0; 1692731Sktlim@umich.edu for (int v = 0; v < m_virtual_networks; v++) { 1702731Sktlim@umich.edu out_queue_length += m_out[out][v]->getSize(); 1712731Sktlim@umich.edu } 1722731Sktlim@umich.edu int value = 1732731Sktlim@umich.edu (out_queue_length << 8) | 1742731Sktlim@umich.edu random_mt.random(0, 0xff); 1752731Sktlim@umich.edu m_link_order[out].m_link = out; 1762731Sktlim@umich.edu m_link_order[out].m_value = value; 1772731Sktlim@umich.edu } 1782731Sktlim@umich.edu 1792731Sktlim@umich.edu // Look at the most empty link first 1802731Sktlim@umich.edu sort(m_link_order.begin(), m_link_order.end()); 1812731Sktlim@umich.edu } 1822731Sktlim@umich.edu } 1832292SN/A 1842731Sktlim@umich.edu for (int i = 0; i < m_routing_table.size(); i++) { 1852731Sktlim@umich.edu // pick the next link to look at 1861060SN/A int link = m_link_order[i].m_link; 1871060SN/A NetDest dst = m_routing_table[link]; 1886221Snate@binkert.org DPRINTF(RubyNetwork, "dst: %s\n", dst); 1891060SN/A 1901060SN/A if (!msg_dsts.intersectionIsNotEmpty(dst)) 1911060SN/A continue; 1921060SN/A 1932292SN/A // Remember what link we're using 1942292SN/A output_links.push_back(link); 1952292SN/A 1962733Sktlim@umich.edu // Need to remember which destinations need this message in 1972733Sktlim@umich.edu // another vector. This Set is the intersection of the 1981060SN/A // routing_table entry and the current destination set. The 1992680Sktlim@umich.edu // intersection must not be empty, since we are inside "if" 2002292SN/A output_link_destinations.push_back(msg_dsts.AND(dst)); 2011060SN/A 2021060SN/A // Next, we update the msg_destination not to include 2032132SN/A // those nodes that were already handled by this link 2041060SN/A msg_dsts.removeNetDest(dst); 2052702Sktlim@umich.edu } 2062669Sktlim@umich.edu 2072292SN/A assert(msg_dsts.count() == 0); 2081060SN/A 2091060SN/A // Check for resources - for all outgoing queues 2101060SN/A bool enough = true; 2114032Sktlim@umich.edu for (int i = 0; i < output_links.size(); i++) { 2124032Sktlim@umich.edu int outgoing = output_links[i]; 2134032Sktlim@umich.edu 2141060SN/A if (!m_out[outgoing][vnet]->areNSlotsAvailable(1)) 2151060SN/A enough = false; 2161060SN/A 2171060SN/A DPRINTF(RubyNetwork, "Checking if node is blocked ..." 2181060SN/A "outgoing: %d, vnet: %d, enough: %d\n", 2191060SN/A outgoing, vnet, enough); 2201060SN/A } 2211060SN/A 2221060SN/A // There were not enough resources 2231060SN/A if (!enough) { 2241060SN/A scheduleEvent(Cycles(1)); 2251060SN/A DPRINTF(RubyNetwork, "Can't deliver message since a node " 2261464SN/A "is blocked\n"); 2271464SN/A DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr)); 2282356SN/A break; // go to next incoming port 2291464SN/A } 2301464SN/A 2311060SN/A MsgPtr unmodified_msg_ptr; 2321464SN/A 2331464SN/A if (output_links.size() > 1) { 2341464SN/A // If we are sending this message down more than one link 2351464SN/A // (size>1), we need to make a copy of the message so each 2361060SN/A // branch can have a different internal destination we need 2373326Sktlim@umich.edu // to create an unmodified MsgPtr because the MessageBuffer 2383326Sktlim@umich.edu // enqueue func will modify the message 2393326Sktlim@umich.edu 2407597Sminkyu.jeong@arm.com // This magic line creates a private copy of the message 2417597Sminkyu.jeong@arm.com unmodified_msg_ptr = msg_ptr->clone(); 2427597Sminkyu.jeong@arm.com } 2433965Sgblack@eecs.umich.edu 2447720Sgblack@eecs.umich.edu // Dequeue msg 2457720Sgblack@eecs.umich.edu buffer->dequeue(); 2461060SN/A m_pending_message_count[vnet]--; 2477720Sgblack@eecs.umich.edu 2487720Sgblack@eecs.umich.edu // Enqueue it - for all outgoing queues 2494636Sgblack@eecs.umich.edu for (int i=0; i<output_links.size(); i++) { 2503794Sgblack@eecs.umich.edu int outgoing = output_links[i]; 2513794Sgblack@eecs.umich.edu 2523794Sgblack@eecs.umich.edu if (i > 0) { 2533965Sgblack@eecs.umich.edu // create a private copy of the unmodified message 2543965Sgblack@eecs.umich.edu msg_ptr = unmodified_msg_ptr->clone(); 2552292SN/A } 2562292SN/A 2572292SN/A // Change the internal destination set of the message so it 2582292SN/A // knows which destinations this link is responsible for. 2592292SN/A net_msg_ptr = safe_cast<NetworkMessage*>(msg_ptr.get()); 2602292SN/A net_msg_ptr->getInternalDestination() = 2611060SN/A output_link_destinations[i]; 2621060SN/A 2631060SN/A // Enqeue msg 2643770Sgblack@eecs.umich.edu DPRINTF(RubyNetwork, "Enqueuing net msg from " 2653770Sgblack@eecs.umich.edu "inport[%d][%d] to outport [%d][%d].\n", 2663770Sgblack@eecs.umich.edu incoming, vnet, outgoing, vnet); 2673770Sgblack@eecs.umich.edu 2683770Sgblack@eecs.umich.edu m_out[outgoing][vnet]->enqueue(msg_ptr); 2693770Sgblack@eecs.umich.edu } 2703770Sgblack@eecs.umich.edu } 2713770Sgblack@eecs.umich.edu } 2723770Sgblack@eecs.umich.edu } 2733770Sgblack@eecs.umich.edu} 2743770Sgblack@eecs.umich.edu 2753770Sgblack@eecs.umich.eduvoid 2763770Sgblack@eecs.umich.eduPerfectSwitch::wakeup() 2773770Sgblack@eecs.umich.edu{ 2783770Sgblack@eecs.umich.edu // Give the highest numbered link priority most of the time 2793770Sgblack@eecs.umich.edu m_wakeups_wo_switch++; 2803770Sgblack@eecs.umich.edu int highest_prio_vnet = m_virtual_networks-1; 2813770Sgblack@eecs.umich.edu int lowest_prio_vnet = 0; 2823770Sgblack@eecs.umich.edu int decrementer = 1; 2833770Sgblack@eecs.umich.edu 2843770Sgblack@eecs.umich.edu // invert priorities to avoid starvation seen in the component network 2853770Sgblack@eecs.umich.edu if (m_wakeups_wo_switch > PRIORITY_SWITCH_LIMIT) { 2863770Sgblack@eecs.umich.edu m_wakeups_wo_switch = 0; 2873770Sgblack@eecs.umich.edu highest_prio_vnet = 0; 2883770Sgblack@eecs.umich.edu lowest_prio_vnet = m_virtual_networks-1; 2893770Sgblack@eecs.umich.edu decrementer = -1; 2901060SN/A } 2913770Sgblack@eecs.umich.edu 2923770Sgblack@eecs.umich.edu // For all components incoming queues 2933770Sgblack@eecs.umich.edu for (int vnet = highest_prio_vnet; 2943770Sgblack@eecs.umich.edu (vnet * decrementer) >= (decrementer * lowest_prio_vnet); 2953770Sgblack@eecs.umich.edu vnet -= decrementer) { 2963770Sgblack@eecs.umich.edu operateVnet(vnet); 2973770Sgblack@eecs.umich.edu } 2983770Sgblack@eecs.umich.edu} 2993770Sgblack@eecs.umich.edu 3003770Sgblack@eecs.umich.eduvoid 3013770Sgblack@eecs.umich.eduPerfectSwitch::storeEventInfo(int info) 3023770Sgblack@eecs.umich.edu{ 3033770Sgblack@eecs.umich.edu m_pending_message_count[info]++; 3043770Sgblack@eecs.umich.edu} 3053770Sgblack@eecs.umich.edu 3063770Sgblack@eecs.umich.eduvoid 3073770Sgblack@eecs.umich.eduPerfectSwitch::clearStats() 3083770Sgblack@eecs.umich.edu{ 3093770Sgblack@eecs.umich.edu} 3103770Sgblack@eecs.umich.eduvoid 3113770Sgblack@eecs.umich.eduPerfectSwitch::collateStats() 3123770Sgblack@eecs.umich.edu{ 3133770Sgblack@eecs.umich.edu} 3143770Sgblack@eecs.umich.edu 3153770Sgblack@eecs.umich.edu 3163770Sgblack@eecs.umich.eduvoid 3173770Sgblack@eecs.umich.eduPerfectSwitch::print(std::ostream& out) const 3183770Sgblack@eecs.umich.edu{ 3193770Sgblack@eecs.umich.edu out << "[PerfectSwitch " << m_switch_id << "]"; 3203770Sgblack@eecs.umich.edu} 3213770Sgblack@eecs.umich.edu