PerfectSwitch.cc revision 11321:02e930db812d
12SN/A/* 21762SN/A * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 35502Snate@binkert.org * All rights reserved. 42SN/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 */ 282665Ssaidi@eecs.umich.edu 292665Ssaidi@eecs.umich.edu#include <algorithm> 302665Ssaidi@eecs.umich.edu 312665Ssaidi@eecs.umich.edu#include "base/cast.hh" 322SN/A#include "base/random.hh" 332SN/A#include "debug/RubyNetwork.hh" 345501Snate@binkert.org#include "mem/ruby/network/MessageBuffer.hh" 352SN/A#include "mem/ruby/network/simple/PerfectSwitch.hh" 362SN/A#include "mem/ruby/network/simple/SimpleNetwork.hh" 372SN/A#include "mem/ruby/network/simple/Switch.hh" 382SN/A#include "mem/ruby/slicc_interface/Message.hh" 395502Snate@binkert.org 405501Snate@binkert.orgusing namespace std; 415501Snate@binkert.org 421717SN/Aconst int PRIORITY_SWITCH_LIMIT = 128; 435501Snate@binkert.org 4456SN/A// Operator for helper class 452SN/Abool 462SN/Aoperator<(const LinkOrder& l1, const LinkOrder& l2) 472SN/A{ 482SN/A return (l1.m_value < l2.m_value); 492SN/A} 502SN/A 512SN/APerfectSwitch::PerfectSwitch(SwitchID sid, Switch *sw, uint32_t virt_nets) 522SN/A : Consumer(sw), m_switch_id(sid), m_switch(sw) 532SN/A{ 545605Snate@binkert.org m_round_robin_start = 0; 552SN/A m_wakeups_wo_switch = 0; 564017Sstever@eecs.umich.edu m_virtual_networks = virt_nets; 574016Sstever@eecs.umich.edu} 584017Sstever@eecs.umich.edu 594016Sstever@eecs.umich.eduvoid 605768Snate@binkert.orgPerfectSwitch::init(SimpleNetwork *network_ptr) 615768Snate@binkert.org{ 625774Snate@binkert.org m_network_ptr = network_ptr; 637059Snate@binkert.org 645768Snate@binkert.org for (int i = 0;i < m_virtual_networks;++i) { 655768Snate@binkert.org m_pending_message_count.push_back(0); 665768Snate@binkert.org } 675768Snate@binkert.org} 685768Snate@binkert.org 695768Snate@binkert.orgvoid 705768Snate@binkert.orgPerfectSwitch::addInPort(const vector<MessageBuffer*>& in) 715768Snate@binkert.org{ 725768Snate@binkert.org NodeID port = m_in.size(); 735768Snate@binkert.org m_in.push_back(in); 745768Snate@binkert.org 755768Snate@binkert.org for (int i = 0; i < in.size(); ++i) { 765768Snate@binkert.org if (in[i] != nullptr) { 775602Snate@binkert.org in[i]->setConsumer(this); 785602Snate@binkert.org in[i]->setIncomingLink(port); 795502Snate@binkert.org in[i]->setVnet(i); 805503Snate@binkert.org } 815502Snate@binkert.org } 825502Snate@binkert.org} 835502Snate@binkert.org 845502Snate@binkert.orgvoid 855502Snate@binkert.orgPerfectSwitch::addOutPort(const vector<MessageBuffer*>& out, 865503Snate@binkert.org const NetDest& routing_table_entry) 875502Snate@binkert.org{ 885502Snate@binkert.org // Setup link order 895502Snate@binkert.org LinkOrder l; 905502Snate@binkert.org l.m_value = 0; 915503Snate@binkert.org l.m_link = m_out.size(); 925503Snate@binkert.org m_link_order.push_back(l); 935503Snate@binkert.org 945502Snate@binkert.org // Add to routing table 955503Snate@binkert.org m_out.push_back(out); 965502Snate@binkert.org m_routing_table.push_back(routing_table_entry); 975502Snate@binkert.org} 982SN/A 992SN/APerfectSwitch::~PerfectSwitch() 1002SN/A{ 1015502Snate@binkert.org} 1025502Snate@binkert.org 1035602Snate@binkert.orgvoid 1045502Snate@binkert.orgPerfectSwitch::operateVnet(int vnet) 1055502Snate@binkert.org{ 1062SN/A // This is for round-robin scheduling 1075502Snate@binkert.org int incoming = m_round_robin_start; 1085502Snate@binkert.org m_round_robin_start++; 1095503Snate@binkert.org if (m_round_robin_start >= m_in.size()) { 1105503Snate@binkert.org m_round_robin_start = 0; 1115503Snate@binkert.org } 1125503Snate@binkert.org 1135503Snate@binkert.org if (m_pending_message_count[vnet] > 0) { 1145502Snate@binkert.org // for all input ports, use round robin scheduling 1152SN/A for (int counter = 0; counter < m_in.size(); counter++) { 1165503Snate@binkert.org // Round robin scheduling 1175503Snate@binkert.org incoming++; 1185602Snate@binkert.org if (incoming >= m_in.size()) { 1195502Snate@binkert.org incoming = 0; 1202SN/A } 1215602Snate@binkert.org 1225602Snate@binkert.org // Is there a message waiting? 1235502Snate@binkert.org if (m_in[incoming].size() <= vnet) { 1245503Snate@binkert.org continue; 1255503Snate@binkert.org } 1265502Snate@binkert.org 1275503Snate@binkert.org MessageBuffer *buffer = m_in[incoming][vnet]; 1285503Snate@binkert.org if (buffer == nullptr) { 1295503Snate@binkert.org continue; 1305503Snate@binkert.org } 1315503Snate@binkert.org 1325503Snate@binkert.org operateMessageBuffer(buffer, incoming, vnet); 1335503Snate@binkert.org } 1345503Snate@binkert.org } 1355503Snate@binkert.org} 1365503Snate@binkert.org 1375503Snate@binkert.orgvoid 1385503Snate@binkert.orgPerfectSwitch::operateMessageBuffer(MessageBuffer *buffer, int incoming, 1395503Snate@binkert.org int vnet) 1405503Snate@binkert.org{ 1415502Snate@binkert.org MsgPtr msg_ptr; 1425502Snate@binkert.org Message *net_msg_ptr = NULL; 1435503Snate@binkert.org 1445503Snate@binkert.org // temporary vectors to store the routing results 1452SN/A vector<LinkID> output_links; 1465502Snate@binkert.org vector<NetDest> output_link_destinations; 1475503Snate@binkert.org Tick current_time = m_switch->clockEdge(); 1485503Snate@binkert.org 1495503Snate@binkert.org while (buffer->isReady(current_time)) { 1502SN/A DPRINTF(RubyNetwork, "incoming: %d\n", incoming); 1512SN/A 1522SN/A // Peek at message 1532SN/A msg_ptr = buffer->peekMsgPtr(); 1542SN/A net_msg_ptr = msg_ptr.get(); 1552SN/A DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr)); 1565502Snate@binkert.org 1572SN/A output_links.clear(); 1585502Snate@binkert.org output_link_destinations.clear(); 1595502Snate@binkert.org NetDest msg_dsts = net_msg_ptr->getDestination(); 1605502Snate@binkert.org 1615602Snate@binkert.org // Unfortunately, the token-protocol sends some 1622SN/A // zero-destination messages, so this assert isn't valid 1632SN/A // assert(msg_dsts.count() > 0); 1642SN/A 1655502Snate@binkert.org assert(m_link_order.size() == m_routing_table.size()); 1662SN/A assert(m_link_order.size() == m_out.size()); 1675502Snate@binkert.org 1685502Snate@binkert.org if (m_network_ptr->getAdaptiveRouting()) { 1692SN/A if (m_network_ptr->isVNetOrdered(vnet)) { 1705502Snate@binkert.org // Don't adaptively route 1712SN/A for (int out = 0; out < m_out.size(); out++) { 1722SN/A m_link_order[out].m_link = out; 1735502Snate@binkert.org m_link_order[out].m_value = 0; 1745502Snate@binkert.org } 1755502Snate@binkert.org } else { 1765503Snate@binkert.org // Find how clogged each link is 1775503Snate@binkert.org for (int out = 0; out < m_out.size(); out++) { 1785502Snate@binkert.org int out_queue_length = 0; 1795602Snate@binkert.org for (int v = 0; v < m_virtual_networks; v++) { 1802SN/A out_queue_length += m_out[out][v]->getSize(current_time); 1812SN/A } 1822667Sstever@eecs.umich.edu int value = 1832SN/A (out_queue_length << 8) | 1842SN/A random_mt.random(0, 0xff); 1855503Snate@binkert.org m_link_order[out].m_link = out; 1865503Snate@binkert.org m_link_order[out].m_value = value; 1875769Snate@binkert.org } 1885502Snate@binkert.org 1895503Snate@binkert.org // Look at the most empty link first 1905503Snate@binkert.org sort(m_link_order.begin(), m_link_order.end()); 1915503Snate@binkert.org } 1925503Snate@binkert.org } 1935503Snate@binkert.org 1945503Snate@binkert.org for (int i = 0; i < m_routing_table.size(); i++) { 1955503Snate@binkert.org // pick the next link to look at 1965502Snate@binkert.org int link = m_link_order[i].m_link; 1975502Snate@binkert.org NetDest dst = m_routing_table[link]; 1985503Snate@binkert.org DPRINTF(RubyNetwork, "dst: %s\n", dst); 1995502Snate@binkert.org 2002SN/A if (!msg_dsts.intersectionIsNotEmpty(dst)) 2012SN/A continue; 2022667Sstever@eecs.umich.edu 2032SN/A // Remember what link we're using 2042667Sstever@eecs.umich.edu output_links.push_back(link); 2055769Snate@binkert.org 2062667Sstever@eecs.umich.edu // Need to remember which destinations need this message in 2072667Sstever@eecs.umich.edu // another vector. This Set is the intersection of the 2082667Sstever@eecs.umich.edu // routing_table entry and the current destination set. The 2095769Snate@binkert.org // intersection must not be empty, since we are inside "if" 2102667Sstever@eecs.umich.edu output_link_destinations.push_back(msg_dsts.AND(dst)); 2112SN/A 2125769Snate@binkert.org // Next, we update the msg_destination not to include 2132SN/A // those nodes that were already handled by this link 2142667Sstever@eecs.umich.edu msg_dsts.removeNetDest(dst); 2152667Sstever@eecs.umich.edu } 2162SN/A 2172SN/A assert(msg_dsts.count() == 0); 218224SN/A 219224SN/A // Check for resources - for all outgoing queues 220224SN/A bool enough = true; 221224SN/A for (int i = 0; i < output_links.size(); i++) { 222224SN/A int outgoing = output_links[i]; 2235769Snate@binkert.org 2245769Snate@binkert.org if (!m_out[outgoing][vnet]->areNSlotsAvailable(1, current_time)) 225224SN/A enough = false; 226224SN/A 227224SN/A DPRINTF(RubyNetwork, "Checking if node is blocked ..." 228237SN/A "outgoing: %d, vnet: %d, enough: %d\n", 229224SN/A outgoing, vnet, enough); 2305695Snate@binkert.org } 2315695Snate@binkert.org 232224SN/A // There were not enough resources 233224SN/A if (!enough) { 234224SN/A scheduleEvent(Cycles(1)); 235224SN/A DPRINTF(RubyNetwork, "Can't deliver message since a node " 236224SN/A "is blocked\n"); 237224SN/A DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr)); 238224SN/A break; // go to next incoming port 2395769Snate@binkert.org } 2405769Snate@binkert.org 2415769Snate@binkert.org MsgPtr unmodified_msg_ptr; 2425769Snate@binkert.org 2435769Snate@binkert.org if (output_links.size() > 1) { 2445769Snate@binkert.org // If we are sending this message down more than one link 245224SN/A // (size>1), we need to make a copy of the message so each 246224SN/A // branch can have a different internal destination we need 247224SN/A // to create an unmodified MsgPtr because the MessageBuffer 2485695Snate@binkert.org // enqueue func will modify the message 249224SN/A 250224SN/A // This magic line creates a private copy of the message 251224SN/A unmodified_msg_ptr = msg_ptr->clone(); 2522SN/A } 253217SN/A 2542SN/A // Dequeue msg 255265SN/A buffer->dequeue(current_time); 256237SN/A m_pending_message_count[vnet]--; 257237SN/A 2585502Snate@binkert.org // Enqueue it - for all outgoing queues 2595502Snate@binkert.org for (int i=0; i<output_links.size(); i++) { 2605503Snate@binkert.org int outgoing = output_links[i]; 2615502Snate@binkert.org 2625503Snate@binkert.org if (i > 0) { 2635769Snate@binkert.org // create a private copy of the unmodified message 2645502Snate@binkert.org msg_ptr = unmodified_msg_ptr->clone(); 2655502Snate@binkert.org } 2665502Snate@binkert.org 2675502Snate@binkert.org // Change the internal destination set of the message so it 2685502Snate@binkert.org // knows which destinations this link is responsible for. 2695503Snate@binkert.org net_msg_ptr = msg_ptr.get(); 2705502Snate@binkert.org net_msg_ptr->getDestination() = output_link_destinations[i]; 2715502Snate@binkert.org 2722SN/A // Enqeue msg 273237SN/A DPRINTF(RubyNetwork, "Enqueuing net msg from " 274265SN/A "inport[%d][%d] to outport [%d][%d].\n", 275265SN/A incoming, vnet, outgoing, vnet); 2765502Snate@binkert.org 277265SN/A m_out[outgoing][vnet]->enqueue(msg_ptr, current_time, 278265SN/A m_switch->cyclesToTicks(Cycles(1))); 279265SN/A } 280265SN/A } 2812SN/A} 2822SN/A 283237SN/Avoid 284237SN/APerfectSwitch::wakeup() 285237SN/A{ 286265SN/A // Give the highest numbered link priority most of the time 287265SN/A m_wakeups_wo_switch++; 288265SN/A int highest_prio_vnet = m_virtual_networks-1; 289270SN/A int lowest_prio_vnet = 0; 290265SN/A int decrementer = 1; 291265SN/A 292270SN/A // invert priorities to avoid starvation seen in the component network 293265SN/A if (m_wakeups_wo_switch > PRIORITY_SWITCH_LIMIT) { 294265SN/A m_wakeups_wo_switch = 0; 295395SN/A highest_prio_vnet = 0; 296237SN/A lowest_prio_vnet = m_virtual_networks-1; 297237SN/A decrementer = -1; 298237SN/A } 2992SN/A 3005501Snate@binkert.org // For all components incoming queues 3012SN/A for (int vnet = highest_prio_vnet; 3022SN/A (vnet * decrementer) >= (decrementer * lowest_prio_vnet); 3032SN/A vnet -= decrementer) { 3042SN/A operateVnet(vnet); 3052SN/A } 3062SN/A} 3072SN/A 3082SN/Avoid 3095502Snate@binkert.orgPerfectSwitch::storeEventInfo(int info) 3105502Snate@binkert.org{ 3115502Snate@binkert.org m_pending_message_count[info]++; 3125503Snate@binkert.org} 3135503Snate@binkert.org 3145502Snate@binkert.orgvoid 3155503Snate@binkert.orgPerfectSwitch::clearStats() 3165502Snate@binkert.org{ 3175502Snate@binkert.org} 3182SN/Avoid 3192SN/APerfectSwitch::collateStats() 3202SN/A{ 3212SN/A} 3222SN/A 3232SN/A 3245502Snate@binkert.orgvoid 3255502Snate@binkert.orgPerfectSwitch::print(std::ostream& out) const 3265502Snate@binkert.org{ 3275502Snate@binkert.org out << "[PerfectSwitch " << m_switch_id << "]"; 3285502Snate@binkert.org} 3295502Snate@binkert.org