PerfectSwitch.cc revision 9117:49116b947194
12SN/A/* 212977Snikos.nikoleris@arm.com * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 39235Sandreas.hansson@arm.com * All rights reserved. 49235Sandreas.hansson@arm.com * 59235Sandreas.hansson@arm.com * Redistribution and use in source and binary forms, with or without 69235Sandreas.hansson@arm.com * modification, are permitted provided that the following conditions are 79235Sandreas.hansson@arm.com * met: redistributions of source code must retain the above copyright 89235Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer; 99235Sandreas.hansson@arm.com * redistributions in binary form must reproduce the above copyright 109235Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer in the 119235Sandreas.hansson@arm.com * documentation and/or other materials provided with the distribution; 129235Sandreas.hansson@arm.com * neither the name of the copyright holders nor the names of its 139235Sandreas.hansson@arm.com * contributors may be used to endorse or promote products derived from 141762SN/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 292SN/A#include <algorithm> 302SN/A 312SN/A#include "base/cast.hh" 322SN/A#include "debug/RubyNetwork.hh" 332SN/A#include "mem/ruby/buffers/MessageBuffer.hh" 342SN/A#include "mem/ruby/network/simple/PerfectSwitch.hh" 352SN/A#include "mem/ruby/network/simple/SimpleNetwork.hh" 362SN/A#include "mem/ruby/profiler/Profiler.hh" 372SN/A#include "mem/ruby/slicc_interface/NetworkMessage.hh" 382SN/A#include "mem/ruby/system/System.hh" 392665SN/A 402665SN/Ausing namespace std; 412665SN/A 429235Sandreas.hansson@arm.comconst int PRIORITY_SWITCH_LIMIT = 128; 432SN/A 442SN/A// Operator for helper class 459235Sandreas.hansson@arm.combool 469235Sandreas.hansson@arm.comoperator<(const LinkOrder& l1, const LinkOrder& l2) 472SN/A{ 4812977Snikos.nikoleris@arm.com return (l1.m_value < l2.m_value); 4910481Sandreas.hansson@arm.com} 509412Sandreas.hansson@arm.com 519412Sandreas.hansson@arm.comPerfectSwitch::PerfectSwitch(SwitchID sid, SimpleNetwork* network_ptr) 529411Sandreas.hansson@arm.com{ 539405Sandreas.hansson@arm.com m_virtual_networks = network_ptr->getNumberOfVirtualNetworks(); 5412334Sgabeblack@google.com m_switch_id = sid; 559235Sandreas.hansson@arm.com m_round_robin_start = 0; 569235Sandreas.hansson@arm.com m_network_ptr = network_ptr; 5710676Sandreas.hansson@arm.com m_wakeups_wo_switch = 0; 5810676Sandreas.hansson@arm.com 5910676Sandreas.hansson@arm.com for(int i = 0;i < m_virtual_networks;++i) 6010676Sandreas.hansson@arm.com { 6110676Sandreas.hansson@arm.com m_pending_message_count.push_back(0); 6210676Sandreas.hansson@arm.com } 6310676Sandreas.hansson@arm.com} 6410676Sandreas.hansson@arm.com 6510676Sandreas.hansson@arm.comvoid 6610676Sandreas.hansson@arm.comPerfectSwitch::addInPort(const vector<MessageBuffer*>& in) 6710676Sandreas.hansson@arm.com{ 6810676Sandreas.hansson@arm.com assert(in.size() == m_virtual_networks); 6910676Sandreas.hansson@arm.com NodeID port = m_in.size(); 7010676Sandreas.hansson@arm.com m_in.push_back(in); 7110676Sandreas.hansson@arm.com 7210676Sandreas.hansson@arm.com for (int j = 0; j < m_virtual_networks; j++) { 739235Sandreas.hansson@arm.com m_in[port][j]->setConsumer(this); 742SN/A string desc = csprintf("[Queue from port %s %s %s to PerfectSwitch]", 752SN/A to_string(m_switch_id), to_string(port), to_string(j)); 769405Sandreas.hansson@arm.com m_in[port][j]->setDescription(desc); 779405Sandreas.hansson@arm.com m_in[port][j]->setIncomingLink(port); 789411Sandreas.hansson@arm.com m_in[port][j]->setVnet(j); 7910435Snilay@cs.wisc.edu } 809405Sandreas.hansson@arm.com} 819405Sandreas.hansson@arm.com 829405Sandreas.hansson@arm.comvoid 839411Sandreas.hansson@arm.comPerfectSwitch::addOutPort(const vector<MessageBuffer*>& out, 849411Sandreas.hansson@arm.com const NetDest& routing_table_entry) 859411Sandreas.hansson@arm.com{ 8610676Sandreas.hansson@arm.com assert(out.size() == m_virtual_networks); 8710676Sandreas.hansson@arm.com 8810676Sandreas.hansson@arm.com // Setup link order 8910676Sandreas.hansson@arm.com LinkOrder l; 909411Sandreas.hansson@arm.com l.m_value = 0; 919411Sandreas.hansson@arm.com l.m_link = m_out.size(); 929411Sandreas.hansson@arm.com m_link_order.push_back(l); 939411Sandreas.hansson@arm.com 949411Sandreas.hansson@arm.com // Add to routing table 959411Sandreas.hansson@arm.com m_out.push_back(out); 969411Sandreas.hansson@arm.com m_routing_table.push_back(routing_table_entry); 979235Sandreas.hansson@arm.com} 982SN/A 999235Sandreas.hansson@arm.comvoid 10010676Sandreas.hansson@arm.comPerfectSwitch::clearRoutingTables() 10110676Sandreas.hansson@arm.com{ 1029411Sandreas.hansson@arm.com m_routing_table.clear(); 1039411Sandreas.hansson@arm.com} 1049411Sandreas.hansson@arm.com 10510676Sandreas.hansson@arm.comvoid 10610676Sandreas.hansson@arm.comPerfectSwitch::clearBuffers() 1079411Sandreas.hansson@arm.com{ 10810676Sandreas.hansson@arm.com for (int i = 0; i < m_in.size(); i++){ 10910676Sandreas.hansson@arm.com for(int vnet = 0; vnet < m_virtual_networks; vnet++) { 11010676Sandreas.hansson@arm.com m_in[i][vnet]->clear(); 11110676Sandreas.hansson@arm.com } 11210676Sandreas.hansson@arm.com } 11310676Sandreas.hansson@arm.com 11410676Sandreas.hansson@arm.com for (int i = 0; i < m_out.size(); i++){ 11510676Sandreas.hansson@arm.com for(int vnet = 0; vnet < m_virtual_networks; vnet++) { 11610676Sandreas.hansson@arm.com m_out[i][vnet]->clear(); 11710676Sandreas.hansson@arm.com } 11810676Sandreas.hansson@arm.com } 11910676Sandreas.hansson@arm.com} 12010676Sandreas.hansson@arm.com 12110676Sandreas.hansson@arm.comvoid 12210676Sandreas.hansson@arm.comPerfectSwitch::reconfigureOutPort(const NetDest& routing_table_entry) 12310676Sandreas.hansson@arm.com{ 12410676Sandreas.hansson@arm.com m_routing_table.push_back(routing_table_entry); 12510676Sandreas.hansson@arm.com} 12610676Sandreas.hansson@arm.com 12710676Sandreas.hansson@arm.comPerfectSwitch::~PerfectSwitch() 12810676Sandreas.hansson@arm.com{ 12910676Sandreas.hansson@arm.com} 13010676Sandreas.hansson@arm.com 13110676Sandreas.hansson@arm.comvoid 1329235Sandreas.hansson@arm.comPerfectSwitch::wakeup() 1339235Sandreas.hansson@arm.com{ 13410676Sandreas.hansson@arm.com MsgPtr msg_ptr; 13510676Sandreas.hansson@arm.com 1369235Sandreas.hansson@arm.com // Give the highest numbered link priority most of the time 1379235Sandreas.hansson@arm.com m_wakeups_wo_switch++; 1389405Sandreas.hansson@arm.com int highest_prio_vnet = m_virtual_networks-1; 1399412Sandreas.hansson@arm.com int lowest_prio_vnet = 0; 1409412Sandreas.hansson@arm.com int decrementer = 1; 1419412Sandreas.hansson@arm.com NetworkMessage* net_msg_ptr = NULL; 1429412Sandreas.hansson@arm.com 1439412Sandreas.hansson@arm.com // invert priorities to avoid starvation seen in the component network 1449412Sandreas.hansson@arm.com if (m_wakeups_wo_switch > PRIORITY_SWITCH_LIMIT) { 14510676Sandreas.hansson@arm.com m_wakeups_wo_switch = 0; 14610676Sandreas.hansson@arm.com highest_prio_vnet = 0; 1479412Sandreas.hansson@arm.com lowest_prio_vnet = m_virtual_networks-1; 1489412Sandreas.hansson@arm.com decrementer = -1; 1499412Sandreas.hansson@arm.com } 1509412Sandreas.hansson@arm.com 1519412Sandreas.hansson@arm.com // For all components incoming queues 1529412Sandreas.hansson@arm.com for (int vnet = highest_prio_vnet; 15310676Sandreas.hansson@arm.com (vnet * decrementer) >= (decrementer * lowest_prio_vnet); 1549412Sandreas.hansson@arm.com vnet -= decrementer) { 1559412Sandreas.hansson@arm.com 1569412Sandreas.hansson@arm.com // This is for round-robin scheduling 1579412Sandreas.hansson@arm.com int incoming = m_round_robin_start; 1589412Sandreas.hansson@arm.com m_round_robin_start++; 1599412Sandreas.hansson@arm.com if (m_round_robin_start >= m_in.size()) { 1609412Sandreas.hansson@arm.com m_round_robin_start = 0; 16110676Sandreas.hansson@arm.com } 16210676Sandreas.hansson@arm.com 1639412Sandreas.hansson@arm.com if(m_pending_message_count[vnet] > 0) { 1649412Sandreas.hansson@arm.com // for all input ports, use round robin scheduling 1659412Sandreas.hansson@arm.com for (int counter = 0; counter < m_in.size(); counter++) { 16610676Sandreas.hansson@arm.com // Round robin scheduling 1679412Sandreas.hansson@arm.com incoming++; 16810676Sandreas.hansson@arm.com if (incoming >= m_in.size()) { 1699412Sandreas.hansson@arm.com incoming = 0; 1709412Sandreas.hansson@arm.com } 1719412Sandreas.hansson@arm.com 1729412Sandreas.hansson@arm.com // temporary vectors to store the routing results 1739412Sandreas.hansson@arm.com vector<LinkID> output_links; 1749412Sandreas.hansson@arm.com vector<NetDest> output_link_destinations; 17510676Sandreas.hansson@arm.com 1769412Sandreas.hansson@arm.com // Is there a message waiting? 1779412Sandreas.hansson@arm.com while (m_in[incoming][vnet]->isReady()) { 1789412Sandreas.hansson@arm.com DPRINTF(RubyNetwork, "incoming: %d\n", incoming); 1799412Sandreas.hansson@arm.com 1809412Sandreas.hansson@arm.com // Peek at message 1819411Sandreas.hansson@arm.com msg_ptr = m_in[incoming][vnet]->peekMsgPtr(); 1829411Sandreas.hansson@arm.com net_msg_ptr = safe_cast<NetworkMessage*>(msg_ptr.get()); 1839411Sandreas.hansson@arm.com DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr)); 1849411Sandreas.hansson@arm.com 1859411Sandreas.hansson@arm.com output_links.clear(); 1869411Sandreas.hansson@arm.com output_link_destinations.clear(); 1879411Sandreas.hansson@arm.com NetDest msg_dsts = 18810676Sandreas.hansson@arm.com net_msg_ptr->getInternalDestination(); 18910676Sandreas.hansson@arm.com 19010676Sandreas.hansson@arm.com // Unfortunately, the token-protocol sends some 19110676Sandreas.hansson@arm.com // zero-destination messages, so this assert isn't valid 19210676Sandreas.hansson@arm.com // assert(msg_dsts.count() > 0); 1939411Sandreas.hansson@arm.com 1949411Sandreas.hansson@arm.com assert(m_link_order.size() == m_routing_table.size()); 1959411Sandreas.hansson@arm.com assert(m_link_order.size() == m_out.size()); 1969411Sandreas.hansson@arm.com 1979581Sandreas.hansson@arm.com if (m_network_ptr->getAdaptiveRouting()) { 1989581Sandreas.hansson@arm.com if (m_network_ptr->isVNetOrdered(vnet)) { 19912977Snikos.nikoleris@arm.com // Don't adaptively route 20012977Snikos.nikoleris@arm.com for (int out = 0; out < m_out.size(); out++) { 20112977Snikos.nikoleris@arm.com m_link_order[out].m_link = out; 20212977Snikos.nikoleris@arm.com m_link_order[out].m_value = 0; 20312977Snikos.nikoleris@arm.com } 20412977Snikos.nikoleris@arm.com } else { 20512977Snikos.nikoleris@arm.com // Find how clogged each link is 20612977Snikos.nikoleris@arm.com for (int out = 0; out < m_out.size(); out++) { 20712977Snikos.nikoleris@arm.com int out_queue_length = 0; 20812977Snikos.nikoleris@arm.com for (int v = 0; v < m_virtual_networks; v++) { 20912977Snikos.nikoleris@arm.com out_queue_length += m_out[out][v]->getSize(); 2109581Sandreas.hansson@arm.com } 2119411Sandreas.hansson@arm.com int value = 2129411Sandreas.hansson@arm.com (out_queue_length << 8) | (random() & 0xff); 2139411Sandreas.hansson@arm.com m_link_order[out].m_link = out; 2149411Sandreas.hansson@arm.com m_link_order[out].m_value = value; 2159411Sandreas.hansson@arm.com } 2169411Sandreas.hansson@arm.com 2179411Sandreas.hansson@arm.com // Look at the most empty link first 2189411Sandreas.hansson@arm.com sort(m_link_order.begin(), m_link_order.end()); 2199411Sandreas.hansson@arm.com } 2209411Sandreas.hansson@arm.com } 2219405Sandreas.hansson@arm.com 2229411Sandreas.hansson@arm.com for (int i = 0; i < m_routing_table.size(); i++) { 2239411Sandreas.hansson@arm.com // pick the next link to look at 2249405Sandreas.hansson@arm.com int link = m_link_order[i].m_link; 2259411Sandreas.hansson@arm.com NetDest dst = m_routing_table[link]; 2269411Sandreas.hansson@arm.com DPRINTF(RubyNetwork, "dst: %s\n", dst); 2279411Sandreas.hansson@arm.com 2289411Sandreas.hansson@arm.com if (!msg_dsts.intersectionIsNotEmpty(dst)) 229532SN/A continue; 2309405Sandreas.hansson@arm.com 2319405Sandreas.hansson@arm.com // Remember what link we're using 2329405Sandreas.hansson@arm.com output_links.push_back(link); 23310435Snilay@cs.wisc.edu 2349405Sandreas.hansson@arm.com // Need to remember which destinations need this 2359405Sandreas.hansson@arm.com // message in another vector. This Set is the 2369405Sandreas.hansson@arm.com // intersection of the routing_table entry and the 2379405Sandreas.hansson@arm.com // current destination set. The intersection must 2389405Sandreas.hansson@arm.com // not be empty, since we are inside "if" 2399405Sandreas.hansson@arm.com output_link_destinations.push_back(msg_dsts.AND(dst)); 2409405Sandreas.hansson@arm.com 24110678SCurtis.Dunham@arm.com // Next, we update the msg_destination not to 24210678SCurtis.Dunham@arm.com // include those nodes that were already handled 24310678SCurtis.Dunham@arm.com // by this link 24410678SCurtis.Dunham@arm.com msg_dsts.removeNetDest(dst); 24510678SCurtis.Dunham@arm.com } 2469405Sandreas.hansson@arm.com 2479405Sandreas.hansson@arm.com assert(msg_dsts.count() == 0); 2489405Sandreas.hansson@arm.com //assert(output_links.size() > 0); 2499405Sandreas.hansson@arm.com 2509405Sandreas.hansson@arm.com // Check for resources - for all outgoing queues 2519405Sandreas.hansson@arm.com bool enough = true; 25210676Sandreas.hansson@arm.com for (int i = 0; i < output_links.size(); i++) { 25310676Sandreas.hansson@arm.com int outgoing = output_links[i]; 25410676Sandreas.hansson@arm.com if (!m_out[outgoing][vnet]->areNSlotsAvailable(1)) 25510676Sandreas.hansson@arm.com enough = false; 25610676Sandreas.hansson@arm.com DPRINTF(RubyNetwork, "Checking if node is blocked ..." 25710676Sandreas.hansson@arm.com "outgoing: %d, vnet: %d, enough: %d\n", 25810676Sandreas.hansson@arm.com outgoing, vnet, enough); 25910676Sandreas.hansson@arm.com } 26010676Sandreas.hansson@arm.com 26110676Sandreas.hansson@arm.com // There were not enough resources 26210676Sandreas.hansson@arm.com if (!enough) { 26310676Sandreas.hansson@arm.com g_eventQueue_ptr->scheduleEvent(this, 1); 26410676Sandreas.hansson@arm.com DPRINTF(RubyNetwork, "Can't deliver message since a node " 26510676Sandreas.hansson@arm.com "is blocked\n"); 2669411Sandreas.hansson@arm.com DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr)); 26710676Sandreas.hansson@arm.com break; // go to next incoming port 2689411Sandreas.hansson@arm.com } 2699411Sandreas.hansson@arm.com 2709411Sandreas.hansson@arm.com MsgPtr unmodified_msg_ptr; 2719411Sandreas.hansson@arm.com 2729411Sandreas.hansson@arm.com if (output_links.size() > 1) { 2739411Sandreas.hansson@arm.com // If we are sending this message down more than 2749411Sandreas.hansson@arm.com // one link (size>1), we need to make a copy of 2759411Sandreas.hansson@arm.com // the message so each branch can have a different 2769411Sandreas.hansson@arm.com // internal destination we need to create an 2779411Sandreas.hansson@arm.com // unmodified MsgPtr because the MessageBuffer 2789411Sandreas.hansson@arm.com // enqueue func will modify the message 2799411Sandreas.hansson@arm.com 2809411Sandreas.hansson@arm.com // This magic line creates a private copy of the 2819411Sandreas.hansson@arm.com // message 28210676Sandreas.hansson@arm.com unmodified_msg_ptr = msg_ptr->clone(); 2839411Sandreas.hansson@arm.com } 2849405Sandreas.hansson@arm.com 2859279Sandreas.hansson@arm.com // Enqueue it - for all outgoing queues 2869279Sandreas.hansson@arm.com for (int i=0; i<output_links.size(); i++) { 2879279Sandreas.hansson@arm.com int outgoing = output_links[i]; 2889279Sandreas.hansson@arm.com 2899279Sandreas.hansson@arm.com if (i > 0) { 2909279Sandreas.hansson@arm.com // create a private copy of the unmodified 2919279Sandreas.hansson@arm.com // message 2929279Sandreas.hansson@arm.com msg_ptr = unmodified_msg_ptr->clone(); 2939279Sandreas.hansson@arm.com } 2949279Sandreas.hansson@arm.com 2959279Sandreas.hansson@arm.com // Change the internal destination set of the 29610853Sandreas.hansson@arm.com // message so it knows which destinations this 29710853Sandreas.hansson@arm.com // link is responsible for. 29810853Sandreas.hansson@arm.com net_msg_ptr = safe_cast<NetworkMessage*>(msg_ptr.get()); 29910853Sandreas.hansson@arm.com net_msg_ptr->getInternalDestination() = 30010853Sandreas.hansson@arm.com output_link_destinations[i]; 30110853Sandreas.hansson@arm.com 30210853Sandreas.hansson@arm.com // Enqeue msg 3039411Sandreas.hansson@arm.com DPRINTF(RubyNetwork, "Enqueuing net msg from " 30410853Sandreas.hansson@arm.com "inport[%d][%d] to outport [%d][%d].\n", 3059411Sandreas.hansson@arm.com incoming, vnet, outgoing, vnet); 3069411Sandreas.hansson@arm.com 3079411Sandreas.hansson@arm.com m_out[outgoing][vnet]->enqueue(msg_ptr); 3089411Sandreas.hansson@arm.com } 3099411Sandreas.hansson@arm.com 3109411Sandreas.hansson@arm.com // Dequeue msg 3119411Sandreas.hansson@arm.com m_in[incoming][vnet]->pop(); 3129411Sandreas.hansson@arm.com m_pending_message_count[vnet]--; 3139411Sandreas.hansson@arm.com } 31410853Sandreas.hansson@arm.com } 31510853Sandreas.hansson@arm.com } 3169279Sandreas.hansson@arm.com } 3179279Sandreas.hansson@arm.com} 3189279Sandreas.hansson@arm.com 3199279Sandreas.hansson@arm.comvoid 3209279Sandreas.hansson@arm.comPerfectSwitch::storeEventInfo(int info) 3219279Sandreas.hansson@arm.com{ 3229279Sandreas.hansson@arm.com m_pending_message_count[info]++; 3239279Sandreas.hansson@arm.com} 3249279Sandreas.hansson@arm.com 3259279Sandreas.hansson@arm.comvoid 3269279Sandreas.hansson@arm.comPerfectSwitch::printStats(std::ostream& out) const 3279279Sandreas.hansson@arm.com{ 3289411Sandreas.hansson@arm.com out << "PerfectSwitch printStats" << endl; 3299411Sandreas.hansson@arm.com} 33012977Snikos.nikoleris@arm.com 33112977Snikos.nikoleris@arm.comvoid 33212977Snikos.nikoleris@arm.comPerfectSwitch::clearStats() 33312977Snikos.nikoleris@arm.com{ 33412977Snikos.nikoleris@arm.com} 33512977Snikos.nikoleris@arm.com 33612977Snikos.nikoleris@arm.comvoid 33712977Snikos.nikoleris@arm.comPerfectSwitch::print(std::ostream& out) const 33812977Snikos.nikoleris@arm.com{ 33912977Snikos.nikoleris@arm.com out << "[PerfectSwitch " << m_switch_id << "]"; 34012977Snikos.nikoleris@arm.com} 3419279Sandreas.hansson@arm.com 3429405Sandreas.hansson@arm.com