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; --- 12 unchanged lines hidden (view full) --- 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 |