3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
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;
10 * redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution;
13 * neither the name of the copyright holders nor the names of its
14 * contributors may be used to endorse or promote products derived from
15 * this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
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.
33 * Description: see Throttle.hh
37 #include "mem/ruby/network/simple/Throttle.hh"
38 #include "mem/ruby/buffers/MessageBuffer.hh"
39 #include "mem/ruby/network/Network.hh"
40 #include "mem/ruby/system/System.hh"
41 #include "mem/ruby/slicc_interface/NetworkMessage.hh"
42 #include "mem/protocol/Protocol.hh"
44 const int HIGH_RANGE
= 256;
45 const int ADJUST_INTERVAL
= 50000;
46 const int MESSAGE_SIZE_MULTIPLIER
= 1000;
47 //const int BROADCAST_SCALING = 4; // Have a 16p system act like a 64p systems
48 const int BROADCAST_SCALING
= 1;
49 const int PRIORITY_SWITCH_LIMIT
= 128;
51 static int network_message_to_size(NetworkMessage
* net_msg_ptr
);
53 extern std::ostream
* debug_cout_ptr
;
55 Throttle::Throttle(int sID
, NodeID node
, int link_latency
, int link_bandwidth_multiplier
)
57 init(node
, link_latency
, link_bandwidth_multiplier
);
61 Throttle::Throttle(NodeID node
, int link_latency
, int link_bandwidth_multiplier
)
63 init(node
, link_latency
, link_bandwidth_multiplier
);
67 void Throttle::init(NodeID node
, int link_latency
, int link_bandwidth_multiplier
)
72 ASSERT(link_bandwidth_multiplier
> 0);
73 m_link_bandwidth_multiplier
= link_bandwidth_multiplier
;
74 m_link_latency
= link_latency
;
76 m_bash_counter
= HIGH_RANGE
;
77 m_bandwidth_since_sample
= 0;
78 m_last_bandwidth_sample
= 0;
79 m_wakeups_wo_switch
= 0;
83 void Throttle::clear()
85 for (int counter
= 0; counter
< m_vnets
; counter
++) {
86 m_in
[counter
]->clear();
87 m_out
[counter
]->clear();
91 void Throttle::addLinks(const Vector
<MessageBuffer
*>& in_vec
, const Vector
<MessageBuffer
*>& out_vec
)
93 assert(in_vec
.size() == out_vec
.size());
94 for (int i
=0; i
<in_vec
.size(); i
++) {
95 addVirtualNetwork(in_vec
[i
], out_vec
[i
]);
98 m_message_counters
.setSize(MessageSizeType_NUM
);
99 for (int i
=0; i
<MessageSizeType_NUM
; i
++) {
100 m_message_counters
[i
].setSize(in_vec
.size());
101 for (int j
=0; j
<m_message_counters
[i
].size(); j
++) {
102 m_message_counters
[i
][j
] = 0;
106 m_out_link_vec
.insertAtBottom(out_vec
);
109 void Throttle::addVirtualNetwork(MessageBuffer
* in_ptr
, MessageBuffer
* out_ptr
)
111 m_units_remaining
.insertAtBottom(0);
112 m_in
.insertAtBottom(in_ptr
);
113 m_out
.insertAtBottom(out_ptr
);
115 // Set consumer and description
116 m_in
[m_vnets
]->setConsumer(this);
117 string desc
= "[Queue to Throttle " + NodeIDToString(m_sID
) + " " + NodeIDToString(m_node
) + "]";
118 m_in
[m_vnets
]->setDescription(desc
);
122 void Throttle::wakeup()
124 // Limits the number of message sent to a limited number of bytes/cycle.
125 assert(getLinkBandwidth() > 0);
126 int bw_remaining
= getLinkBandwidth();
128 // Give the highest numbered link priority most of the time
129 m_wakeups_wo_switch
++;
130 int highest_prio_vnet
= m_vnets
-1;
131 int lowest_prio_vnet
= 0;
133 bool schedule_wakeup
= false;
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_vnets
-1;
143 for (int vnet
= highest_prio_vnet
; (vnet
*counter
) >= (counter
*lowest_prio_vnet
); vnet
-= counter
) {
145 assert(m_out
[vnet
] != NULL
);
146 assert(m_in
[vnet
] != NULL
);
147 assert(m_units_remaining
[vnet
] >= 0);
149 while ((bw_remaining
> 0) && ((m_in
[vnet
]->isReady()) || (m_units_remaining
[vnet
] > 0)) && m_out
[vnet
]->areNSlotsAvailable(1)) {
151 // See if we are done transferring the previous message on this virtual network
152 if (m_units_remaining
[vnet
] == 0 && m_in
[vnet
]->isReady()) {
154 // Find the size of the message we are moving
155 MsgPtr msg_ptr
= m_in
[vnet
]->peekMsgPtr();
156 NetworkMessage
* net_msg_ptr
= dynamic_cast<NetworkMessage
*>(msg_ptr
.ref());
157 m_units_remaining
[vnet
] += network_message_to_size(net_msg_ptr
);
159 DEBUG_NEWLINE(NETWORK_COMP
,HighPrio
);
160 DEBUG_MSG(NETWORK_COMP
,HighPrio
,"throttle: " + int_to_string(m_node
)
161 + " my bw " + int_to_string(getLinkBandwidth())
162 + " bw spent enqueueing net msg " + int_to_string(m_units_remaining
[vnet
])
163 + " time: " + int_to_string(g_eventQueue_ptr
->getTime()) + ".");
166 m_out
[vnet
]->enqueue(m_in
[vnet
]->peekMsgPtr(), m_link_latency
);
170 m_message_counters
[net_msg_ptr
->getMessageSize()][vnet
]++;
172 DEBUG_MSG(NETWORK_COMP
,LowPrio
,*m_out
[vnet
]);
173 DEBUG_NEWLINE(NETWORK_COMP
,HighPrio
);
176 // Calculate the amount of bandwidth we spent on this message
177 int diff
= m_units_remaining
[vnet
] - bw_remaining
;
178 m_units_remaining
[vnet
] = max(0, diff
);
179 bw_remaining
= max(0, -diff
);
182 if ((bw_remaining
> 0) && ((m_in
[vnet
]->isReady()) || (m_units_remaining
[vnet
] > 0)) && !m_out
[vnet
]->areNSlotsAvailable(1)) {
183 DEBUG_MSG(NETWORK_COMP
,LowPrio
,vnet
);
184 schedule_wakeup
= true; // schedule me to wakeup again because I'm waiting for my output queue to become available
188 // We should only wake up when we use the bandwidth
189 // assert(bw_remaining != getLinkBandwidth()); // This is only mostly true
191 // Record that we used some or all of the link bandwidth this cycle
192 double ratio
= 1.0-(double(bw_remaining
)/double(getLinkBandwidth()));
193 // If ratio = 0, we used no bandwidth, if ratio = 1, we used all
196 // Sample the link bandwidth utilization over a number of cycles
197 int bw_used
= getLinkBandwidth()-bw_remaining
;
198 m_bandwidth_since_sample
+= bw_used
;
200 // FIXME - comment out the bash specific code for faster performance
202 // Update the predictor
203 Time current_time
= g_eventQueue_ptr
->getTime();
204 while ((current_time
- m_last_bandwidth_sample
) > ADJUST_INTERVAL
) {
205 // Used less bandwidth
208 // Make sure we don't overflow
209 m_bash_counter
= min(HIGH_RANGE
, m_bash_counter
);
210 m_bash_counter
= max(0, m_bash_counter
);
213 m_last_bandwidth_sample
+= ADJUST_INTERVAL
;
214 m_bandwidth_since_sample
= 0;
218 if ((bw_remaining
> 0) && !schedule_wakeup
) {
219 // We have extra bandwidth and our output buffer was available, so we must not have anything else to do until another message arrives.
220 DEBUG_MSG(NETWORK_COMP
,LowPrio
,*this);
221 DEBUG_MSG(NETWORK_COMP
,LowPrio
,"not scheduled again");
223 DEBUG_MSG(NETWORK_COMP
,LowPrio
,*this);
224 DEBUG_MSG(NETWORK_COMP
,LowPrio
,"scheduled again");
225 // We are out of bandwidth for this cycle, so wakeup next cycle and continue
226 g_eventQueue_ptr
->scheduleEvent(this, 1);
230 bool Throttle::broadcastBandwidthAvailable(int rand
) const
232 bool result
= !(m_bash_counter
> ((HIGH_RANGE
/4) + (rand
% (HIGH_RANGE
/2))));
236 void Throttle::printStats(ostream
& out
) const
238 out
<< "utilized_percent: " << getUtilization() << endl
;
241 void Throttle::clearStats()
243 m_ruby_start
= g_eventQueue_ptr
->getTime();
244 m_links_utilized
= 0.0;
246 for (int i
=0; i
<m_message_counters
.size(); i
++) {
247 for (int j
=0; j
<m_message_counters
[i
].size(); j
++) {
248 m_message_counters
[i
][j
] = 0;
253 void Throttle::printConfig(ostream
& out
) const
258 double Throttle::getUtilization() const
260 return (100.0 * double(m_links_utilized
)) / (double(g_eventQueue_ptr
->getTime()-m_ruby_start
));
263 void Throttle::print(ostream
& out
) const
265 out
<< "[Throttle: " << m_sID
<< " " << m_node
<< " bw: " << getLinkBandwidth() << "]";
271 int network_message_to_size(NetworkMessage
* net_msg_ptr
)
273 assert(net_msg_ptr
!= NULL
);
275 // Artificially increase the size of broadcast messages
276 if (BROADCAST_SCALING
> 1) {
277 if (net_msg_ptr
->getDestination().isBroadcast()) {
278 return (RubySystem::getNetwork()->MessageSizeType_to_int(net_msg_ptr
->getMessageSize()) * MESSAGE_SIZE_MULTIPLIER
* BROADCAST_SCALING
);
281 return (RubySystem::getNetwork()->MessageSizeType_to_int(net_msg_ptr
->getMessageSize()) * MESSAGE_SIZE_MULTIPLIER
);