PerfectSwitch.cc revision 6285:ce086eca1ede
13101Sstever@eecs.umich.edu 28579Ssteve.reinhardt@amd.com/* 33101Sstever@eecs.umich.edu * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 43101Sstever@eecs.umich.edu * All rights reserved. 53101Sstever@eecs.umich.edu * 63101Sstever@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 73101Sstever@eecs.umich.edu * modification, are permitted provided that the following conditions are 83101Sstever@eecs.umich.edu * met: redistributions of source code must retain the above copyright 93101Sstever@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 103101Sstever@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 113101Sstever@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 123101Sstever@eecs.umich.edu * documentation and/or other materials provided with the distribution; 133101Sstever@eecs.umich.edu * neither the name of the copyright holders nor the names of its 143101Sstever@eecs.umich.edu * contributors may be used to endorse or promote products derived from 153101Sstever@eecs.umich.edu * this software without specific prior written permission. 163101Sstever@eecs.umich.edu * 173101Sstever@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 183101Sstever@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 193101Sstever@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 203101Sstever@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 213101Sstever@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 223101Sstever@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 233101Sstever@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 243101Sstever@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 253101Sstever@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 263101Sstever@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 273101Sstever@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 283101Sstever@eecs.umich.edu */ 293101Sstever@eecs.umich.edu 307778Sgblack@eecs.umich.edu/* 313101Sstever@eecs.umich.edu * PerfectSwitch.cc 323101Sstever@eecs.umich.edu * 333101Sstever@eecs.umich.edu * Description: See PerfectSwitch.hh 343101Sstever@eecs.umich.edu * 353101Sstever@eecs.umich.edu * $Id$ 363101Sstever@eecs.umich.edu * 373101Sstever@eecs.umich.edu */ 383101Sstever@eecs.umich.edu 393101Sstever@eecs.umich.edu 403101Sstever@eecs.umich.edu#include "mem/ruby/network/simple/PerfectSwitch.hh" 413101Sstever@eecs.umich.edu#include "mem/ruby/slicc_interface/NetworkMessage.hh" 423101Sstever@eecs.umich.edu#include "mem/ruby/profiler/Profiler.hh" 433101Sstever@eecs.umich.edu#include "mem/ruby/system/System.hh" 443101Sstever@eecs.umich.edu#include "mem/ruby/network/simple/SimpleNetwork.hh" 453101Sstever@eecs.umich.edu#include "mem/gems_common/util.hh" 463101Sstever@eecs.umich.edu#include "mem/ruby/buffers/MessageBuffer.hh" 473101Sstever@eecs.umich.edu#include "mem/protocol/Protocol.hh" 483101Sstever@eecs.umich.edu 493885Sbinkertn@umich.educonst int PRIORITY_SWITCH_LIMIT = 128; 503885Sbinkertn@umich.edu 514762Snate@binkert.org// Operator for helper class 523885Sbinkertn@umich.edubool operator<(const LinkOrder& l1, const LinkOrder& l2) { 533885Sbinkertn@umich.edu return (l1.m_value < l2.m_value); 547528Ssteve.reinhardt@amd.com} 553885Sbinkertn@umich.edu 564380Sbinkertn@umich.eduPerfectSwitch::PerfectSwitch(SwitchID sid, SimpleNetwork* network_ptr) 574167Sbinkertn@umich.edu{ 583102Sstever@eecs.umich.edu m_virtual_networks = network_ptr->getNumberOfVirtualNetworks(); 593101Sstever@eecs.umich.edu m_switch_id = sid; 604762Snate@binkert.org m_round_robin_start = 0; 614762Snate@binkert.org m_network_ptr = network_ptr; 624762Snate@binkert.org m_wakeups_wo_switch = 0; 634762Snate@binkert.org} 644762Snate@binkert.org 654762Snate@binkert.orgvoid PerfectSwitch::addInPort(const Vector<MessageBuffer*>& in) 664762Snate@binkert.org{ 674762Snate@binkert.org assert(in.size() == m_virtual_networks); 684762Snate@binkert.org NodeID port = m_in.size(); 695033Smilesck@eecs.umich.edu m_in.insertAtBottom(in); 705033Smilesck@eecs.umich.edu for (int j = 0; j < m_virtual_networks; j++) { 715033Smilesck@eecs.umich.edu m_in[port][j]->setConsumer(this); 725033Smilesck@eecs.umich.edu string desc = "[Queue from port " + NodeIDToString(m_switch_id) + " " + NodeIDToString(port) + " " + NodeIDToString(j) + " to PerfectSwitch]"; 735033Smilesck@eecs.umich.edu m_in[port][j]->setDescription(desc); 745033Smilesck@eecs.umich.edu } 755033Smilesck@eecs.umich.edu} 765033Smilesck@eecs.umich.edu 775033Smilesck@eecs.umich.eduvoid PerfectSwitch::addOutPort(const Vector<MessageBuffer*>& out, const NetDest& routing_table_entry) 785033Smilesck@eecs.umich.edu{ 793101Sstever@eecs.umich.edu assert(out.size() == m_virtual_networks); 803101Sstever@eecs.umich.edu 813101Sstever@eecs.umich.edu // Setup link order 825033Smilesck@eecs.umich.edu LinkOrder l; 833101Sstever@eecs.umich.edu l.m_value = 0; 848596Ssteve.reinhardt@amd.com l.m_link = m_out.size(); 858596Ssteve.reinhardt@amd.com m_link_order.insertAtBottom(l); 868596Ssteve.reinhardt@amd.com 878596Ssteve.reinhardt@amd.com // Add to routing table 887673Snate@binkert.org m_out.insertAtBottom(out); 897673Snate@binkert.org m_routing_table.insertAtBottom(routing_table_entry); 907673Snate@binkert.org 917673Snate@binkert.org // if (RubyConfig::getPrintTopology()) { 928596Ssteve.reinhardt@amd.com m_out_link_vec.insertAtBottom(out); 938596Ssteve.reinhardt@amd.com // } 948596Ssteve.reinhardt@amd.com} 957673Snate@binkert.org 967673Snate@binkert.orgvoid PerfectSwitch::clearRoutingTables() 977673Snate@binkert.org{ 983101Sstever@eecs.umich.edu m_routing_table.clear(); 993101Sstever@eecs.umich.edu} 1003101Sstever@eecs.umich.edu 1013101Sstever@eecs.umich.eduvoid PerfectSwitch::clearBuffers() 1023101Sstever@eecs.umich.edu{ 1033101Sstever@eecs.umich.edu for(int i=0; i<m_in.size(); i++){ 1043101Sstever@eecs.umich.edu for(int vnet=0; vnet < m_virtual_networks; vnet++) { 1053101Sstever@eecs.umich.edu m_in[i][vnet]->clear(); 1063101Sstever@eecs.umich.edu } 1073101Sstever@eecs.umich.edu } 1083101Sstever@eecs.umich.edu 1093101Sstever@eecs.umich.edu for(int i=0; i<m_out.size(); i++){ 1103101Sstever@eecs.umich.edu for(int vnet=0; vnet < m_virtual_networks; vnet++) { 1113101Sstever@eecs.umich.edu m_out[i][vnet]->clear(); 1123101Sstever@eecs.umich.edu } 1133101Sstever@eecs.umich.edu } 1143101Sstever@eecs.umich.edu} 1153101Sstever@eecs.umich.edu 1163101Sstever@eecs.umich.eduvoid PerfectSwitch::reconfigureOutPort(const NetDest& routing_table_entry) 1173101Sstever@eecs.umich.edu{ 1183101Sstever@eecs.umich.edu m_routing_table.insertAtBottom(routing_table_entry); 1193101Sstever@eecs.umich.edu} 1203101Sstever@eecs.umich.edu 1213101Sstever@eecs.umich.eduPerfectSwitch::~PerfectSwitch() 1223101Sstever@eecs.umich.edu{ 1233101Sstever@eecs.umich.edu} 1243101Sstever@eecs.umich.edu 1253101Sstever@eecs.umich.eduvoid PerfectSwitch::wakeup() 1263101Sstever@eecs.umich.edu{ 1273101Sstever@eecs.umich.edu 1283101Sstever@eecs.umich.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, m_switch_id); 1293101Sstever@eecs.umich.edu 1303101Sstever@eecs.umich.edu MsgPtr msg_ptr; 1313101Sstever@eecs.umich.edu 1323101Sstever@eecs.umich.edu // Give the highest numbered link priority most of the time 1333101Sstever@eecs.umich.edu m_wakeups_wo_switch++; 1343101Sstever@eecs.umich.edu int highest_prio_vnet = m_virtual_networks-1; 1353101Sstever@eecs.umich.edu int lowest_prio_vnet = 0; 1363101Sstever@eecs.umich.edu int decrementer = 1; 1373101Sstever@eecs.umich.edu bool schedule_wakeup = false; 1383101Sstever@eecs.umich.edu NetworkMessage* net_msg_ptr = NULL; 1393101Sstever@eecs.umich.edu 1403101Sstever@eecs.umich.edu // invert priorities to avoid starvation seen in the component network 1413101Sstever@eecs.umich.edu if (m_wakeups_wo_switch > PRIORITY_SWITCH_LIMIT) { 1423101Sstever@eecs.umich.edu m_wakeups_wo_switch = 0; 1433101Sstever@eecs.umich.edu highest_prio_vnet = 0; 1445033Smilesck@eecs.umich.edu lowest_prio_vnet = m_virtual_networks-1; 1456656Snate@binkert.org decrementer = -1; 1465033Smilesck@eecs.umich.edu } 1475033Smilesck@eecs.umich.edu 1485033Smilesck@eecs.umich.edu for (int vnet = highest_prio_vnet; (vnet*decrementer) >= (decrementer*lowest_prio_vnet); vnet -= decrementer) { 1493101Sstever@eecs.umich.edu 1503101Sstever@eecs.umich.edu // For all components incoming queues 1513101Sstever@eecs.umich.edu int incoming = m_round_robin_start; // This is for round-robin scheduling 1523101Sstever@eecs.umich.edu m_round_robin_start++; 1533101Sstever@eecs.umich.edu if (m_round_robin_start >= m_in.size()) { 1543101Sstever@eecs.umich.edu m_round_robin_start = 0; 1553101Sstever@eecs.umich.edu } 1563101Sstever@eecs.umich.edu 1573101Sstever@eecs.umich.edu // for all input ports, use round robin scheduling 1583101Sstever@eecs.umich.edu for (int counter = 0; counter < m_in.size(); counter++) { 1593101Sstever@eecs.umich.edu 1603101Sstever@eecs.umich.edu // Round robin scheduling 1613101Sstever@eecs.umich.edu incoming++; 1623102Sstever@eecs.umich.edu if (incoming >= m_in.size()) { 1633101Sstever@eecs.umich.edu incoming = 0; 1643101Sstever@eecs.umich.edu } 1653101Sstever@eecs.umich.edu 1667673Snate@binkert.org // temporary vectors to store the routing results 1677673Snate@binkert.org Vector<LinkID> output_links; 1683101Sstever@eecs.umich.edu Vector<NetDest> output_link_destinations; 1697673Snate@binkert.org 1707673Snate@binkert.org // Is there a message waiting? 1713101Sstever@eecs.umich.edu while (m_in[incoming][vnet]->isReady()) { 1727673Snate@binkert.org 1737673Snate@binkert.org DEBUG_EXPR(NETWORK_COMP, MedPrio, incoming); 1743101Sstever@eecs.umich.edu 1753101Sstever@eecs.umich.edu // Peek at message 1763101Sstever@eecs.umich.edu msg_ptr = m_in[incoming][vnet]->peekMsgPtr(); 1773101Sstever@eecs.umich.edu net_msg_ptr = dynamic_cast<NetworkMessage*>(msg_ptr.ref()); 1783101Sstever@eecs.umich.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, *net_msg_ptr); 1793101Sstever@eecs.umich.edu 1805033Smilesck@eecs.umich.edu output_links.clear(); 1815475Snate@binkert.org output_link_destinations.clear(); 1825475Snate@binkert.org NetDest msg_destinations = net_msg_ptr->getInternalDestination(); 1835475Snate@binkert.org 1845475Snate@binkert.org // Unfortunately, the token-protocol sends some 1853101Sstever@eecs.umich.edu // zero-destination messages, so this assert isn't valid 1863101Sstever@eecs.umich.edu // assert(msg_destinations.count() > 0); 1873101Sstever@eecs.umich.edu 1884762Snate@binkert.org assert(m_link_order.size() == m_routing_table.size()); 1894762Snate@binkert.org assert(m_link_order.size() == m_out.size()); 1904762Snate@binkert.org//changed by SS 1913101Sstever@eecs.umich.edu// if (RubyConfig::getAdaptiveRouting()) { 1928460SAli.Saidi@ARM.com if (m_network_ptr->getAdaptiveRouting()) { 1938459SAli.Saidi@ARM.com if (m_network_ptr->isVNetOrdered(vnet)) { 1948459SAli.Saidi@ARM.com // Don't adaptively route 1958459SAli.Saidi@ARM.com for (int outlink=0; outlink<m_out.size(); outlink++) { 1963101Sstever@eecs.umich.edu m_link_order[outlink].m_link = outlink; 1977528Ssteve.reinhardt@amd.com m_link_order[outlink].m_value = 0; 1987528Ssteve.reinhardt@amd.com } 1997528Ssteve.reinhardt@amd.com } else { 2007528Ssteve.reinhardt@amd.com // Find how clogged each link is 2017528Ssteve.reinhardt@amd.com for (int outlink=0; outlink<m_out.size(); outlink++) { 2027528Ssteve.reinhardt@amd.com int out_queue_length = 0; 2033101Sstever@eecs.umich.edu for (int v=0; v<m_virtual_networks; v++) { 2047528Ssteve.reinhardt@amd.com out_queue_length += m_out[outlink][v]->getSize(); 2057528Ssteve.reinhardt@amd.com } 2067528Ssteve.reinhardt@amd.com m_link_order[outlink].m_link = outlink; 2077528Ssteve.reinhardt@amd.com m_link_order[outlink].m_value = 0; 2087528Ssteve.reinhardt@amd.com m_link_order[outlink].m_value |= (out_queue_length << 8); 2097528Ssteve.reinhardt@amd.com m_link_order[outlink].m_value |= (random() & 0xff); 2107528Ssteve.reinhardt@amd.com } 2117528Ssteve.reinhardt@amd.com m_link_order.sortVector(); // Look at the most empty link first 2127528Ssteve.reinhardt@amd.com } 2137528Ssteve.reinhardt@amd.com } 2148321Ssteve.reinhardt@amd.com 2158321Ssteve.reinhardt@amd.com for (int i=0; i<m_routing_table.size(); i++) { 2167528Ssteve.reinhardt@amd.com // pick the next link to look at 2177528Ssteve.reinhardt@amd.com int link = m_link_order[i].m_link; 2187528Ssteve.reinhardt@amd.com 2197528Ssteve.reinhardt@amd.com DEBUG_EXPR(NETWORK_COMP, MedPrio, m_routing_table[link]); 2207528Ssteve.reinhardt@amd.com 2217528Ssteve.reinhardt@amd.com if (msg_destinations.intersectionIsNotEmpty(m_routing_table[link])) { 2227528Ssteve.reinhardt@amd.com 2237528Ssteve.reinhardt@amd.com // Remember what link we're using 2247528Ssteve.reinhardt@amd.com output_links.insertAtBottom(link); 2257528Ssteve.reinhardt@amd.com 2267528Ssteve.reinhardt@amd.com // Need to remember which destinations need this message 2277528Ssteve.reinhardt@amd.com // in another vector. This Set is the intersection of the 2287528Ssteve.reinhardt@amd.com // routing_table entry and the current destination set. 2293101Sstever@eecs.umich.edu // The intersection must not be empty, since we are inside "if" 2303101Sstever@eecs.umich.edu output_link_destinations.insertAtBottom(msg_destinations.AND(m_routing_table[link])); 2313101Sstever@eecs.umich.edu 2323101Sstever@eecs.umich.edu // Next, we update the msg_destination not to include 2333101Sstever@eecs.umich.edu // those nodes that were already handled by this link 2343101Sstever@eecs.umich.edu msg_destinations.removeNetDest(m_routing_table[link]); 2353101Sstever@eecs.umich.edu } 2363101Sstever@eecs.umich.edu } 2373101Sstever@eecs.umich.edu 2384762Snate@binkert.org assert(msg_destinations.count() == 0); 2394762Snate@binkert.org //assert(output_links.size() > 0); 2404762Snate@binkert.org 2414762Snate@binkert.org // Check for resources - for all outgoing queues 2427528Ssteve.reinhardt@amd.com bool enough = true; 2434762Snate@binkert.org for (int i=0; i<output_links.size(); i++) { 2444762Snate@binkert.org int outgoing = output_links[i]; 2454762Snate@binkert.org enough = enough && m_out[outgoing][vnet]->areNSlotsAvailable(1); 2468596Ssteve.reinhardt@amd.com DEBUG_MSG(NETWORK_COMP, HighPrio, "checking if node is blocked"); 2478596Ssteve.reinhardt@amd.com DEBUG_EXPR(NETWORK_COMP, HighPrio, outgoing); 2488596Ssteve.reinhardt@amd.com DEBUG_EXPR(NETWORK_COMP, HighPrio, vnet); 2497673Snate@binkert.org DEBUG_EXPR(NETWORK_COMP, HighPrio, enough); 2508596Ssteve.reinhardt@amd.com } 2514762Snate@binkert.org 2527673Snate@binkert.org // There were not enough resources 2538596Ssteve.reinhardt@amd.com if(!enough) { 2547675Snate@binkert.org g_eventQueue_ptr->scheduleEvent(this, 1); 2557675Snate@binkert.org DEBUG_MSG(NETWORK_COMP, HighPrio, "Can't deliver message to anyone since a node is blocked"); 2567675Snate@binkert.org DEBUG_EXPR(NETWORK_COMP, HighPrio, *net_msg_ptr); 2577675Snate@binkert.org break; // go to next incoming port 2587675Snate@binkert.org } 2597675Snate@binkert.org 2607673Snate@binkert.org MsgPtr unmodified_msg_ptr; 2617675Snate@binkert.org 2627675Snate@binkert.org if (output_links.size() > 1) { 2637675Snate@binkert.org // If we are sending this message down more than one link 2647675Snate@binkert.org // (size>1), we need to make a copy of the message so each 2657675Snate@binkert.org // branch can have a different internal destination 2667673Snate@binkert.org // we need to create an unmodified MsgPtr because the MessageBuffer enqueue func 2677675Snate@binkert.org // will modify the message 2687675Snate@binkert.org unmodified_msg_ptr = *(msg_ptr.ref()); // This magic line creates a private copy of the message 2697675Snate@binkert.org } 2707675Snate@binkert.org 2717675Snate@binkert.org // Enqueue it - for all outgoing queues 2727675Snate@binkert.org for (int i=0; i<output_links.size(); i++) { 2737675Snate@binkert.org int outgoing = output_links[i]; 2747675Snate@binkert.org 2757675Snate@binkert.org if (i > 0) { 2767675Snate@binkert.org msg_ptr = *(unmodified_msg_ptr.ref()); // create a private copy of the unmodified message 2777675Snate@binkert.org } 2787675Snate@binkert.org 2797675Snate@binkert.org // Change the internal destination set of the message so it 2807675Snate@binkert.org // knows which destinations this link is responsible for. 2817675Snate@binkert.org net_msg_ptr = dynamic_cast<NetworkMessage*>(msg_ptr.ref()); 2827675Snate@binkert.org net_msg_ptr->getInternalDestination() = output_link_destinations[i]; 2837673Snate@binkert.org 2847673Snate@binkert.org // Enqeue msg 2853101Sstever@eecs.umich.edu DEBUG_NEWLINE(NETWORK_COMP,HighPrio); 2867675Snate@binkert.org DEBUG_MSG(NETWORK_COMP,HighPrio,"switch: " + int_to_string(m_switch_id) 2877675Snate@binkert.org + " enqueuing net msg from inport[" + int_to_string(incoming) + "][" 2887673Snate@binkert.org + int_to_string(vnet) +"] to outport [" + int_to_string(outgoing) 2897673Snate@binkert.org + "][" + int_to_string(vnet) +"]" 2907673Snate@binkert.org + " time: " + int_to_string(g_eventQueue_ptr->getTime()) + "."); 2913101Sstever@eecs.umich.edu DEBUG_NEWLINE(NETWORK_COMP,HighPrio); 2927673Snate@binkert.org 2937673Snate@binkert.org m_out[outgoing][vnet]->enqueue(msg_ptr); 2943101Sstever@eecs.umich.edu } 2953101Sstever@eecs.umich.edu 2963101Sstever@eecs.umich.edu // Dequeue msg 2973101Sstever@eecs.umich.edu m_in[incoming][vnet]->pop(); 2983101Sstever@eecs.umich.edu } 2993101Sstever@eecs.umich.edu } 3003101Sstever@eecs.umich.edu } 3013101Sstever@eecs.umich.edu} 3023101Sstever@eecs.umich.edu 3033101Sstever@eecs.umich.eduvoid PerfectSwitch::printStats(ostream& out) const 3043101Sstever@eecs.umich.edu{ 3053101Sstever@eecs.umich.edu out << "PerfectSwitch printStats" << endl; 3063101Sstever@eecs.umich.edu} 3073101Sstever@eecs.umich.edu 3083101Sstever@eecs.umich.eduvoid PerfectSwitch::clearStats() 3095033Smilesck@eecs.umich.edu{ 3105033Smilesck@eecs.umich.edu} 3113101Sstever@eecs.umich.edu 3123101Sstever@eecs.umich.eduvoid PerfectSwitch::printConfig(ostream& out) const 3133101Sstever@eecs.umich.edu{ 3143101Sstever@eecs.umich.edu} 3153101Sstever@eecs.umich.edu 3163101Sstever@eecs.umich.eduvoid PerfectSwitch::print(ostream& out) const 3173101Sstever@eecs.umich.edu{ 3183101Sstever@eecs.umich.edu out << "[PerfectSwitch " << m_switch_id << "]"; 3193101Sstever@eecs.umich.edu} 3203101Sstever@eecs.umich.edu 3213101Sstever@eecs.umich.edu