PerfectSwitch.cc revision 7056:b66b558578bd
1/* 2 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29#include "mem/protocol/Protocol.hh" 30#include "mem/ruby/buffers/MessageBuffer.hh" 31#include "mem/ruby/network/simple/PerfectSwitch.hh" 32#include "mem/ruby/network/simple/SimpleNetwork.hh" 33#include "mem/ruby/profiler/Profiler.hh" 34#include "mem/ruby/slicc_interface/NetworkMessage.hh" 35#include "mem/ruby/system/System.hh" 36 37using namespace std; 38 39const int PRIORITY_SWITCH_LIMIT = 128; 40 41// Operator for helper class 42bool 43operator<(const LinkOrder& l1, const LinkOrder& l2) 44{ 45 return (l1.m_value < l2.m_value); 46} 47 48PerfectSwitch::PerfectSwitch(SwitchID sid, SimpleNetwork* network_ptr) 49{ 50 m_virtual_networks = network_ptr->getNumberOfVirtualNetworks(); 51 m_switch_id = sid; 52 m_round_robin_start = 0; 53 m_network_ptr = network_ptr; 54 m_wakeups_wo_switch = 0; 55} 56 57void 58PerfectSwitch::addInPort(const Vector<MessageBuffer*>& in) 59{ 60 assert(in.size() == m_virtual_networks); 61 NodeID port = m_in.size(); 62 m_in.insertAtBottom(in); 63 for (int j = 0; j < m_virtual_networks; j++) { 64 m_in[port][j]->setConsumer(this); 65 string desc = csprintf("[Queue from port %s %s %s to PerfectSwitch]", 66 NodeIDToString(m_switch_id), NodeIDToString(port), 67 NodeIDToString(j)); 68 m_in[port][j]->setDescription(desc); 69 } 70} 71 72void 73PerfectSwitch::addOutPort(const Vector<MessageBuffer*>& out, 74 const NetDest& routing_table_entry) 75{ 76 assert(out.size() == m_virtual_networks); 77 78 // Setup link order 79 LinkOrder l; 80 l.m_value = 0; 81 l.m_link = m_out.size(); 82 m_link_order.insertAtBottom(l); 83 84 // Add to routing table 85 m_out.insertAtBottom(out); 86 m_routing_table.insertAtBottom(routing_table_entry); 87} 88 89void 90PerfectSwitch::clearRoutingTables() 91{ 92 m_routing_table.clear(); 93} 94 95void 96PerfectSwitch::clearBuffers() 97{ 98 for (int i = 0; i < m_in.size(); i++){ 99 for(int vnet = 0; vnet < m_virtual_networks; vnet++) { 100 m_in[i][vnet]->clear(); 101 } 102 } 103 104 for (int i = 0; i < m_out.size(); i++){ 105 for(int vnet = 0; vnet < m_virtual_networks; vnet++) { 106 m_out[i][vnet]->clear(); 107 } 108 } 109} 110 111void 112PerfectSwitch::reconfigureOutPort(const NetDest& routing_table_entry) 113{ 114 m_routing_table.insertAtBottom(routing_table_entry); 115} 116 117PerfectSwitch::~PerfectSwitch() 118{ 119} 120 121void 122PerfectSwitch::wakeup() 123{ 124 DEBUG_EXPR(NETWORK_COMP, MedPrio, m_switch_id); 125 126 MsgPtr msg_ptr; 127 128 // Give the highest numbered link priority most of the time 129 m_wakeups_wo_switch++; 130 int highest_prio_vnet = m_virtual_networks-1; 131 int lowest_prio_vnet = 0; 132 int decrementer = 1; 133 NetworkMessage* net_msg_ptr = NULL; 134 135 // invert priorities to avoid starvation seen in the component network 136 if (m_wakeups_wo_switch > PRIORITY_SWITCH_LIMIT) { 137 m_wakeups_wo_switch = 0; 138 highest_prio_vnet = 0; 139 lowest_prio_vnet = m_virtual_networks-1; 140 decrementer = -1; 141 } 142 143 // For all components incoming queues 144 for (int vnet = highest_prio_vnet; 145 (vnet * decrementer) >= (decrementer * lowest_prio_vnet); 146 vnet -= decrementer) { 147 148 // This is for round-robin scheduling 149 int incoming = m_round_robin_start; 150 m_round_robin_start++; 151 if (m_round_robin_start >= m_in.size()) { 152 m_round_robin_start = 0; 153 } 154 155 // for all input ports, use round robin scheduling 156 for (int counter = 0; counter < m_in.size(); counter++) { 157 // Round robin scheduling 158 incoming++; 159 if (incoming >= m_in.size()) { 160 incoming = 0; 161 } 162 163 // temporary vectors to store the routing results 164 Vector<LinkID> output_links; 165 Vector<NetDest> output_link_destinations; 166 167 // Is there a message waiting? 168 while (m_in[incoming][vnet]->isReady()) { 169 DEBUG_EXPR(NETWORK_COMP, MedPrio, incoming); 170 171 // Peek at message 172 msg_ptr = m_in[incoming][vnet]->peekMsgPtr(); 173 net_msg_ptr = dynamic_cast<NetworkMessage*>(msg_ptr.ref()); 174 DEBUG_EXPR(NETWORK_COMP, MedPrio, *net_msg_ptr); 175 176 output_links.clear(); 177 output_link_destinations.clear(); 178 NetDest msg_dsts = 179 net_msg_ptr->getInternalDestination(); 180 181 // Unfortunately, the token-protocol sends some 182 // zero-destination messages, so this assert isn't valid 183 // assert(msg_dsts.count() > 0); 184 185 assert(m_link_order.size() == m_routing_table.size()); 186 assert(m_link_order.size() == m_out.size()); 187 188 if (m_network_ptr->getAdaptiveRouting()) { 189 if (m_network_ptr->isVNetOrdered(vnet)) { 190 // Don't adaptively route 191 for (int out = 0; out < m_out.size(); out++) { 192 m_link_order[out].m_link = out; 193 m_link_order[out].m_value = 0; 194 } 195 } else { 196 // Find how clogged each link is 197 for (int out = 0; out < m_out.size(); out++) { 198 int out_queue_length = 0; 199 for (int v = 0; v < m_virtual_networks; v++) { 200 out_queue_length += m_out[out][v]->getSize(); 201 } 202 int value = 203 (out_queue_length << 8) | (random() & 0xff); 204 m_link_order[out].m_link = out; 205 m_link_order[out].m_value = value; 206 } 207 208 // Look at the most empty link first 209 m_link_order.sortVector(); 210 } 211 } 212 213 for (int i = 0; i < m_routing_table.size(); i++) { 214 // pick the next link to look at 215 int link = m_link_order[i].m_link; 216 NetDest dst = m_routing_table[link]; 217 DEBUG_EXPR(NETWORK_COMP, MedPrio, dst); 218 219 if (!msg_dsts.intersectionIsNotEmpty(dst)) 220 continue; 221 222 // Remember what link we're using 223 output_links.insertAtBottom(link); 224 225 // Need to remember which destinations need this 226 // message in another vector. This Set is the 227 // intersection of the routing_table entry and the 228 // current destination set. The intersection must 229 // not be empty, since we are inside "if" 230 output_link_destinations.insertAtBottom(msg_dsts.AND(dst)); 231 232 // Next, we update the msg_destination not to 233 // include those nodes that were already handled 234 // by this link 235 msg_dsts.removeNetDest(dst); 236 } 237 238 assert(msg_dsts.count() == 0); 239 //assert(output_links.size() > 0); 240 241 // Check for resources - for all outgoing queues 242 bool enough = true; 243 for (int i = 0; i < output_links.size(); i++) { 244 int outgoing = output_links[i]; 245 if (!m_out[outgoing][vnet]->areNSlotsAvailable(1)) 246 enough = false; 247 DEBUG_MSG(NETWORK_COMP, HighPrio, 248 "checking if node is blocked"); 249 DEBUG_EXPR(NETWORK_COMP, HighPrio, outgoing); 250 DEBUG_EXPR(NETWORK_COMP, HighPrio, vnet); 251 DEBUG_EXPR(NETWORK_COMP, HighPrio, enough); 252 } 253 254 // There were not enough resources 255 if (!enough) { 256 g_eventQueue_ptr->scheduleEvent(this, 1); 257 DEBUG_MSG(NETWORK_COMP, HighPrio, 258 "Can't deliver message since a node is blocked"); 259 DEBUG_EXPR(NETWORK_COMP, HighPrio, *net_msg_ptr); 260 break; // go to next incoming port 261 } 262 263 MsgPtr unmodified_msg_ptr; 264 265 if (output_links.size() > 1) { 266 // If we are sending this message down more than 267 // one link (size>1), we need to make a copy of 268 // the message so each branch can have a different 269 // internal destination we need to create an 270 // unmodified MsgPtr because the MessageBuffer 271 // enqueue func will modify the message 272 273 // This magic line creates a private copy of the 274 // message 275 unmodified_msg_ptr = *(msg_ptr.ref()); 276 } 277 278 // Enqueue it - for all outgoing queues 279 for (int i=0; i<output_links.size(); i++) { 280 int outgoing = output_links[i]; 281 282 if (i > 0) { 283 // create a private copy of the unmodified 284 // message 285 msg_ptr = *(unmodified_msg_ptr.ref()); 286 } 287 288 // Change the internal destination set of the 289 // message so it knows which destinations this 290 // link is responsible for. 291 net_msg_ptr = safe_cast<NetworkMessage*>(msg_ptr.ref()); 292 net_msg_ptr->getInternalDestination() = 293 output_link_destinations[i]; 294 295 // Enqeue msg 296 DEBUG_NEWLINE(NETWORK_COMP,HighPrio); 297 DEBUG_MSG(NETWORK_COMP, HighPrio, 298 csprintf("switch: %d enqueuing net msg from " 299 "inport[%d][%d] to outport [%d][%d] time: %d.", 300 m_switch_id, incoming, vnet, outgoing, vnet, 301 g_eventQueue_ptr->getTime())); 302 DEBUG_NEWLINE(NETWORK_COMP,HighPrio); 303 304 m_out[outgoing][vnet]->enqueue(msg_ptr); 305 } 306 307 // Dequeue msg 308 m_in[incoming][vnet]->pop(); 309 } 310 } 311 } 312} 313 314void 315PerfectSwitch::printStats(std::ostream& out) const 316{ 317 out << "PerfectSwitch printStats" << endl; 318} 319 320void 321PerfectSwitch::clearStats() 322{ 323} 324 325void 326PerfectSwitch::printConfig(std::ostream& out) const 327{ 328} 329 330void 331PerfectSwitch::print(std::ostream& out) const 332{ 333 out << "[PerfectSwitch " << m_switch_id << "]"; 334} 335 336