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