PerfectSwitch.cc revision 7054:7d6862b80049
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/gems_common/util.hh" 30#include "mem/protocol/Protocol.hh" 31#include "mem/ruby/buffers/MessageBuffer.hh" 32#include "mem/ruby/network/simple/PerfectSwitch.hh" 33#include "mem/ruby/network/simple/SimpleNetwork.hh" 34#include "mem/ruby/profiler/Profiler.hh" 35#include "mem/ruby/slicc_interface/NetworkMessage.hh" 36#include "mem/ruby/system/System.hh" 37 38const int PRIORITY_SWITCH_LIMIT = 128; 39 40// Operator for helper class 41bool 42operator<(const LinkOrder& l1, const LinkOrder& l2) 43{ 44 return (l1.m_value < l2.m_value); 45} 46 47PerfectSwitch::PerfectSwitch(SwitchID sid, SimpleNetwork* network_ptr) 48{ 49 m_virtual_networks = network_ptr->getNumberOfVirtualNetworks(); 50 m_switch_id = sid; 51 m_round_robin_start = 0; 52 m_network_ptr = network_ptr; 53 m_wakeups_wo_switch = 0; 54} 55 56void 57PerfectSwitch::addInPort(const Vector<MessageBuffer*>& in) 58{ 59 assert(in.size() == m_virtual_networks); 60 NodeID port = m_in.size(); 61 m_in.insertAtBottom(in); 62 for (int j = 0; j < m_virtual_networks; j++) { 63 m_in[port][j]->setConsumer(this); 64 string desc = csprintf("[Queue from port %s %s %s to PerfectSwitch]", 65 NodeIDToString(m_switch_id), NodeIDToString(port), 66 NodeIDToString(j)); 67 m_in[port][j]->setDescription(desc); 68 } 69} 70 71void 72PerfectSwitch::addOutPort(const Vector<MessageBuffer*>& out, 73 const NetDest& routing_table_entry) 74{ 75 assert(out.size() == m_virtual_networks); 76 77 // Setup link order 78 LinkOrder l; 79 l.m_value = 0; 80 l.m_link = m_out.size(); 81 m_link_order.insertAtBottom(l); 82 83 // Add to routing table 84 m_out.insertAtBottom(out); 85 m_routing_table.insertAtBottom(routing_table_entry); 86} 87 88void 89PerfectSwitch::clearRoutingTables() 90{ 91 m_routing_table.clear(); 92} 93 94void 95PerfectSwitch::clearBuffers() 96{ 97 for (int i = 0; i < m_in.size(); i++){ 98 for(int vnet = 0; vnet < m_virtual_networks; vnet++) { 99 m_in[i][vnet]->clear(); 100 } 101 } 102 103 for (int i = 0; i < m_out.size(); i++){ 104 for(int vnet = 0; vnet < m_virtual_networks; vnet++) { 105 m_out[i][vnet]->clear(); 106 } 107 } 108} 109 110void 111PerfectSwitch::reconfigureOutPort(const NetDest& routing_table_entry) 112{ 113 m_routing_table.insertAtBottom(routing_table_entry); 114} 115 116PerfectSwitch::~PerfectSwitch() 117{ 118} 119 120void 121PerfectSwitch::wakeup() 122{ 123 DEBUG_EXPR(NETWORK_COMP, MedPrio, m_switch_id); 124 125 MsgPtr msg_ptr; 126 127 // Give the highest numbered link priority most of the time 128 m_wakeups_wo_switch++; 129 int highest_prio_vnet = m_virtual_networks-1; 130 int lowest_prio_vnet = 0; 131 int decrementer = 1; 132 NetworkMessage* net_msg_ptr = NULL; 133 134 // invert priorities to avoid starvation seen in the component network 135 if (m_wakeups_wo_switch > PRIORITY_SWITCH_LIMIT) { 136 m_wakeups_wo_switch = 0; 137 highest_prio_vnet = 0; 138 lowest_prio_vnet = m_virtual_networks-1; 139 decrementer = -1; 140 } 141 142 // For all components incoming queues 143 for (int vnet = highest_prio_vnet; 144 (vnet * decrementer) >= (decrementer * lowest_prio_vnet); 145 vnet -= decrementer) { 146 147 // This is for round-robin scheduling 148 int incoming = m_round_robin_start; 149 m_round_robin_start++; 150 if (m_round_robin_start >= m_in.size()) { 151 m_round_robin_start = 0; 152 } 153 154 // for all input ports, use round robin scheduling 155 for (int counter = 0; counter < m_in.size(); counter++) { 156 // Round robin scheduling 157 incoming++; 158 if (incoming >= m_in.size()) { 159 incoming = 0; 160 } 161 162 // temporary vectors to store the routing results 163 Vector<LinkID> output_links; 164 Vector<NetDest> output_link_destinations; 165 166 // Is there a message waiting? 167 while (m_in[incoming][vnet]->isReady()) { 168 DEBUG_EXPR(NETWORK_COMP, MedPrio, incoming); 169 170 // Peek at message 171 msg_ptr = m_in[incoming][vnet]->peekMsgPtr(); 172 net_msg_ptr = dynamic_cast<NetworkMessage*>(msg_ptr.ref()); 173 DEBUG_EXPR(NETWORK_COMP, MedPrio, *net_msg_ptr); 174 175 output_links.clear(); 176 output_link_destinations.clear(); 177 NetDest msg_dsts = 178 net_msg_ptr->getInternalDestination(); 179 180 // Unfortunately, the token-protocol sends some 181 // zero-destination messages, so this assert isn't valid 182 // assert(msg_dsts.count() > 0); 183 184 assert(m_link_order.size() == m_routing_table.size()); 185 assert(m_link_order.size() == m_out.size()); 186 187 if (m_network_ptr->getAdaptiveRouting()) { 188 if (m_network_ptr->isVNetOrdered(vnet)) { 189 // Don't adaptively route 190 for (int out = 0; out < m_out.size(); out++) { 191 m_link_order[out].m_link = out; 192 m_link_order[out].m_value = 0; 193 } 194 } else { 195 // Find how clogged each link is 196 for (int out = 0; out < m_out.size(); out++) { 197 int out_queue_length = 0; 198 for (int v = 0; v < m_virtual_networks; v++) { 199 out_queue_length += m_out[out][v]->getSize(); 200 } 201 int value = 202 (out_queue_length << 8) | (random() & 0xff); 203 m_link_order[out].m_link = out; 204 m_link_order[out].m_value = value; 205 } 206 207 // Look at the most empty link first 208 m_link_order.sortVector(); 209 } 210 } 211 212 for (int i = 0; i < m_routing_table.size(); i++) { 213 // pick the next link to look at 214 int link = m_link_order[i].m_link; 215 NetDest dst = m_routing_table[link]; 216 DEBUG_EXPR(NETWORK_COMP, MedPrio, dst); 217 218 if (!msg_dsts.intersectionIsNotEmpty(dst)) 219 continue; 220 221 // Remember what link we're using 222 output_links.insertAtBottom(link); 223 224 // Need to remember which destinations need this 225 // message in another vector. This Set is the 226 // intersection of the routing_table entry and the 227 // current destination set. The intersection must 228 // not be empty, since we are inside "if" 229 output_link_destinations.insertAtBottom(msg_dsts.AND(dst)); 230 231 // Next, we update the msg_destination not to 232 // include those nodes that were already handled 233 // by this link 234 msg_dsts.removeNetDest(dst); 235 } 236 237 assert(msg_dsts.count() == 0); 238 //assert(output_links.size() > 0); 239 240 // Check for resources - for all outgoing queues 241 bool enough = true; 242 for (int i = 0; i < output_links.size(); i++) { 243 int outgoing = output_links[i]; 244 if (!m_out[outgoing][vnet]->areNSlotsAvailable(1)) 245 enough = false; 246 DEBUG_MSG(NETWORK_COMP, HighPrio, 247 "checking if node is blocked"); 248 DEBUG_EXPR(NETWORK_COMP, HighPrio, outgoing); 249 DEBUG_EXPR(NETWORK_COMP, HighPrio, vnet); 250 DEBUG_EXPR(NETWORK_COMP, HighPrio, enough); 251 } 252 253 // There were not enough resources 254 if (!enough) { 255 g_eventQueue_ptr->scheduleEvent(this, 1); 256 DEBUG_MSG(NETWORK_COMP, HighPrio, 257 "Can't deliver message since a node is blocked"); 258 DEBUG_EXPR(NETWORK_COMP, HighPrio, *net_msg_ptr); 259 break; // go to next incoming port 260 } 261 262 MsgPtr unmodified_msg_ptr; 263 264 if (output_links.size() > 1) { 265 // If we are sending this message down more than 266 // one link (size>1), we need to make a copy of 267 // the message so each branch can have a different 268 // internal destination we need to create an 269 // unmodified MsgPtr because the MessageBuffer 270 // enqueue func will modify the message 271 272 // This magic line creates a private copy of the 273 // message 274 unmodified_msg_ptr = *(msg_ptr.ref()); 275 } 276 277 // Enqueue it - for all outgoing queues 278 for (int i=0; i<output_links.size(); i++) { 279 int outgoing = output_links[i]; 280 281 if (i > 0) { 282 // create a private copy of the unmodified 283 // message 284 msg_ptr = *(unmodified_msg_ptr.ref()); 285 } 286 287 // Change the internal destination set of the 288 // message so it knows which destinations this 289 // link is responsible for. 290 net_msg_ptr = safe_cast<NetworkMessage*>(msg_ptr.ref()); 291 net_msg_ptr->getInternalDestination() = 292 output_link_destinations[i]; 293 294 // Enqeue msg 295 DEBUG_NEWLINE(NETWORK_COMP,HighPrio); 296 DEBUG_MSG(NETWORK_COMP, HighPrio, 297 csprintf("switch: %d enqueuing net msg from " 298 "inport[%d][%d] to outport [%d][%d] time: %d.", 299 m_switch_id, incoming, vnet, outgoing, vnet, 300 g_eventQueue_ptr->getTime())); 301 DEBUG_NEWLINE(NETWORK_COMP,HighPrio); 302 303 m_out[outgoing][vnet]->enqueue(msg_ptr); 304 } 305 306 // Dequeue msg 307 m_in[incoming][vnet]->pop(); 308 } 309 } 310 } 311} 312 313void 314PerfectSwitch::printStats(std::ostream& out) const 315{ 316 out << "PerfectSwitch printStats" << endl; 317} 318 319void 320PerfectSwitch::clearStats() 321{ 322} 323 324void 325PerfectSwitch::printConfig(std::ostream& out) const 326{ 327} 328 329void 330PerfectSwitch::print(std::ostream& out) const 331{ 332 out << "[PerfectSwitch " << m_switch_id << "]"; 333} 334 335