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