Line data Source code
1 :
2 : /* Copyright (c) 2008-2013, Stefan Eilemann <eile@equalizergraphics.com>
3 : * 2011, Cedric Stalder <cedric.stalder@gmail.com>
4 : * 2012, Daniel Nachbaur <danielnachbaur@gmail.com>
5 : *
6 : * This library is free software; you can redistribute it and/or modify it under
7 : * the terms of the GNU Lesser General Public License version 2.1 as published
8 : * by the Free Software Foundation.
9 : *
10 : * This library is distributed in the hope that it will be useful, but WITHOUT
11 : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 : * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
13 : * details.
14 : *
15 : * You should have received a copy of the GNU Lesser General Public License
16 : * along with this library; if not, write to the Free Software Foundation, Inc.,
17 : * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 : */
19 :
20 : #include "loadEqualizer.h"
21 :
22 : #include "../compound.h"
23 : #include "../log.h"
24 :
25 : #include <eq/fabric/statistic.h>
26 : #include <lunchbox/debug.h>
27 :
28 : namespace eq
29 : {
30 : namespace server
31 : {
32 : std::ostream& operator<<(std::ostream& os, const LoadEqualizer::Node*);
33 :
34 : // The tree load balancer organizes the children in a binary tree. At each
35 : // level, a relative split position is determined by balancing the left subtree
36 : // against the right subtree.
37 :
38 188 : LoadEqualizer::LoadEqualizer()
39 188 : : _tree(0)
40 : {
41 188 : LBVERB << "New LoadEqualizer @" << (void*)this << std::endl;
42 188 : }
43 :
44 18 : LoadEqualizer::LoadEqualizer(const fabric::Equalizer& from)
45 : : Equalizer(from)
46 18 : , _tree(0)
47 : {
48 18 : }
49 :
50 618 : LoadEqualizer::~LoadEqualizer()
51 : {
52 206 : _clearTree(_tree);
53 206 : delete _tree;
54 206 : _tree = 0;
55 :
56 206 : _history.clear();
57 412 : }
58 :
59 36 : void LoadEqualizer::notifyUpdatePre(Compound* compound,
60 : const uint32_t frameNumber)
61 : {
62 36 : _checkHistory(); // execute to not leak memory
63 36 : if (isFrozen() || !compound->isActive() || !isActive())
64 32 : return;
65 :
66 4 : if (!_tree)
67 : {
68 2 : LBASSERT(compound == getCompound());
69 2 : const Compounds& children = compound->getChildren();
70 2 : switch (children.size())
71 : {
72 : case 0:
73 0 : return; // no child compounds, can't do anything.
74 : case 1: // one child, 'balance' it:
75 0 : if (getMode() == MODE_DB)
76 0 : children.front()->setRange(Range());
77 : else
78 0 : children.front()->setViewport(Viewport());
79 0 : return;
80 :
81 : default:
82 2 : _tree = _buildTree(children);
83 2 : break;
84 : }
85 : }
86 :
87 : // compute new data
88 4 : if (getDamping() < 1.f)
89 : {
90 4 : _history.push_back(LBFrameData());
91 4 : _history.back().first = frameNumber;
92 : }
93 :
94 4 : _update(_tree, Viewport(), Range());
95 4 : _computeSplit();
96 : }
97 :
98 6 : LoadEqualizer::Node* LoadEqualizer::_buildTree(const Compounds& compounds)
99 : {
100 6 : Node* node = new Node;
101 :
102 6 : const size_t size = compounds.size();
103 6 : if (size == 1)
104 : {
105 4 : Compound* compound = compounds.front();
106 :
107 4 : node->compound = compound;
108 :
109 4 : Channel* channel = compound->getChannel();
110 4 : LBASSERT(channel);
111 4 : channel->addListener(this);
112 4 : return node;
113 : }
114 :
115 2 : const size_t middle = size >> 1;
116 :
117 4 : Compounds left;
118 4 : for (size_t i = 0; i < middle; ++i)
119 2 : left.push_back(compounds[i]);
120 :
121 4 : Compounds right;
122 4 : for (size_t i = middle; i < size; ++i)
123 2 : right.push_back(compounds[i]);
124 :
125 2 : node->left = _buildTree(left);
126 2 : node->right = _buildTree(right);
127 :
128 2 : return node;
129 : }
130 :
131 210 : void LoadEqualizer::_clearTree(Node* node)
132 : {
133 210 : if (!node)
134 204 : return;
135 :
136 6 : if (node->compound)
137 : {
138 4 : Channel* channel = node->compound->getChannel();
139 4 : LBASSERTINFO(channel, node->compound);
140 4 : channel->removeListener(this);
141 : }
142 : else
143 : {
144 2 : _clearTree(node->left);
145 2 : _clearTree(node->right);
146 : }
147 : }
148 :
149 4 : void LoadEqualizer::notifyLoadData(Channel* channel, const uint32_t frameNumber,
150 : const Statistics& statistics,
151 : const Viewport& region)
152 : {
153 4 : LBLOG(LOG_LB2) << statistics.size() << " samples from "
154 4 : << channel->getName() << " @ " << frameNumber << std::endl;
155 36 : for (std::deque<LBFrameData>::iterator i = _history.begin();
156 24 : i != _history.end(); ++i)
157 : {
158 12 : LBFrameData& frameData = *i;
159 12 : if (frameData.first != frameNumber)
160 8 : continue;
161 :
162 : // Found corresponding historical data set
163 4 : LBDatas& items = frameData.second;
164 6 : for (LBDatas::iterator j = items.begin(); j != items.end(); ++j)
165 : {
166 6 : Data& data = *j;
167 6 : if (data.channel != channel)
168 2 : continue;
169 :
170 : // Found corresponding historical data item
171 4 : const uint32_t taskID = data.taskID;
172 4 : LBASSERTINFO(taskID > 0, channel->getName());
173 :
174 : // gather relevant load data
175 4 : int64_t startTime = std::numeric_limits<int64_t>::max();
176 4 : int64_t endTime = 0;
177 4 : bool loadSet = false;
178 4 : int64_t transmitTime = 0;
179 26 : for (size_t k = 0; k < statistics.size(); ++k)
180 : {
181 22 : const Statistic& stat = statistics[k];
182 22 : if (stat.task == data.destTaskID)
183 8 : _updateAssembleTime(data, stat);
184 :
185 : // from different compound
186 22 : if (stat.task != taskID || loadSet)
187 14 : continue;
188 :
189 8 : switch (stat.type)
190 : {
191 : case Statistic::CHANNEL_CLEAR:
192 : case Statistic::CHANNEL_DRAW:
193 : case Statistic::CHANNEL_READBACK:
194 6 : startTime = LB_MIN(startTime, stat.startTime);
195 6 : endTime = LB_MAX(endTime, stat.endTime);
196 6 : break;
197 :
198 : case Statistic::CHANNEL_ASYNC_READBACK:
199 : case Statistic::CHANNEL_FRAME_TRANSMIT:
200 2 : transmitTime += stat.endTime - stat.startTime;
201 2 : break;
202 : case Statistic::CHANNEL_FRAME_WAIT_SENDTOKEN:
203 0 : transmitTime -= stat.endTime - stat.startTime;
204 0 : break;
205 :
206 : // assemble blocks on input frames, stop using subsequent data
207 : case Statistic::CHANNEL_ASSEMBLE:
208 0 : loadSet = true;
209 0 : break;
210 :
211 : default:
212 0 : break;
213 : }
214 : }
215 :
216 4 : if (startTime == std::numeric_limits<int64_t>::max())
217 4 : return;
218 :
219 4 : data.vp.apply(region); // Update ROI
220 4 : data.time = endTime - startTime;
221 4 : data.time = LB_MAX(data.time, 1);
222 4 : data.time = LB_MAX(data.time, transmitTime);
223 4 : data.assembleTime = LB_MAX(data.assembleTime, 0);
224 4 : LBLOG(LOG_LB2) << "Added time " << data.time << " (+"
225 0 : << data.assembleTime << ") for "
226 0 : << channel->getName() << " " << data.vp << ", "
227 4 : << data.range << " @ " << frameNumber << std::endl;
228 4 : return;
229 :
230 : // Note: if the same channel is used twice as a child, the
231 : // load-compound association does not work.
232 : }
233 : }
234 : }
235 :
236 8 : void LoadEqualizer::_updateAssembleTime(Data& data, const Statistic& stat)
237 : {
238 8 : switch (stat.type)
239 : {
240 : case Statistic::CHANNEL_FRAME_WAIT_READY:
241 2 : data.assembleTime -= stat.endTime - stat.startTime;
242 2 : break;
243 :
244 : case Statistic::CHANNEL_ASSEMBLE:
245 2 : data.assembleTime += stat.endTime - stat.startTime;
246 2 : break;
247 :
248 : default:
249 4 : break;
250 : }
251 8 : }
252 :
253 36 : void LoadEqualizer::_checkHistory()
254 : {
255 : // 1. Find youngest complete load data set
256 36 : uint32_t useFrame = 0;
257 168 : for (std::deque<LBFrameData>::reverse_iterator i = _history.rbegin();
258 168 : i != _history.rend() && useFrame == 0; ++i)
259 : {
260 20 : const LBFrameData& frameData = *i;
261 20 : const LBDatas& items = frameData.second;
262 20 : bool isComplete = true;
263 :
264 120 : for (LBDatas::const_iterator j = items.begin();
265 120 : j != items.end() && isComplete; ++j)
266 : {
267 20 : const Data& data = *j;
268 :
269 20 : if (data.time < 0)
270 2 : isComplete = false;
271 : }
272 :
273 20 : if (isComplete)
274 18 : useFrame = frameData.first;
275 : }
276 :
277 : // 2. delete old, unneeded data sets
278 36 : while (!_history.empty() && _history.front().first < useFrame)
279 0 : _history.pop_front();
280 :
281 36 : if (_history.empty()) // insert fake set
282 : {
283 18 : _history.resize(1);
284 :
285 18 : LBFrameData& frameData = _history.front();
286 18 : LBDatas& items = frameData.second;
287 :
288 18 : frameData.first = 0; // frameNumber
289 18 : items.resize(1);
290 :
291 18 : Data& data = items.front();
292 18 : data.time = 1;
293 18 : LBASSERT(data.taskID == 0);
294 18 : LBASSERT(data.channel == 0);
295 : }
296 36 : }
297 :
298 4 : float LoadEqualizer::_getTotalResources() const
299 : {
300 4 : const Compounds& children = getCompound()->getChildren();
301 :
302 4 : float resources = 0.f;
303 12 : for (CompoundsCIter i = children.begin(); i != children.end(); ++i)
304 : {
305 8 : const Compound* compound = *i;
306 8 : if (compound->isActive())
307 8 : resources += compound->getUsage();
308 : }
309 :
310 4 : return resources;
311 : }
312 :
313 12 : void LoadEqualizer::_update(Node* node, const Viewport& vp, const Range& range)
314 : {
315 12 : if (!node)
316 0 : return;
317 :
318 12 : node->mode = getMode();
319 12 : if (node->mode == MODE_2D)
320 : {
321 12 : PixelViewport pvp = getCompound()->getChannel()->getPixelViewport();
322 12 : pvp.apply(vp);
323 :
324 12 : if (pvp.w > pvp.h) // split along longest axis
325 4 : node->mode = MODE_VERTICAL;
326 : else
327 8 : node->mode = MODE_HORIZONTAL;
328 : }
329 :
330 12 : if (node->compound)
331 8 : _updateLeaf(node);
332 : else
333 4 : _updateNode(node, vp, range);
334 : }
335 :
336 8 : void LoadEqualizer::_updateLeaf(Node* node)
337 : {
338 8 : const Compound* compound = node->compound;
339 8 : const Channel* channel = compound->getChannel();
340 8 : LBASSERT(channel);
341 8 : const PixelViewport& pvp = channel->getPixelViewport();
342 8 : node->resources = compound->isActive() ? compound->getUsage() : 0.f;
343 8 : LBLOG(LOG_LB2) << channel->getName() << " active " << compound->isActive()
344 8 : << " using " << node->resources << std::endl;
345 8 : LBASSERT(node->resources >= 0.f);
346 :
347 8 : node->maxSize.x() = pvp.w;
348 8 : node->maxSize.y() = pvp.h;
349 8 : node->boundaryf = getBoundaryf();
350 8 : node->boundary2i = getBoundary2i();
351 8 : node->resistancef = getResistancef();
352 8 : node->resistance2i = getResistance2i();
353 8 : if (!compound->hasDestinationChannel())
354 4 : return;
355 :
356 4 : const float nResources = _getTotalResources();
357 4 : if (getAssembleOnlyLimit() <= nResources - node->resources)
358 : {
359 0 : node->resources = 0.f;
360 0 : return; // OPT
361 : }
362 :
363 4 : const float time = float(_getTotalTime());
364 4 : const float assembleTime = float(_getAssembleTime());
365 4 : if (assembleTime == 0.f || node->resources == 0.f)
366 4 : return;
367 :
368 0 : const float timePerResource = time / (nResources - node->resources);
369 0 : const float renderTime = timePerResource * node->resources;
370 :
371 0 : const float clampedAssembleTime = LB_MIN(assembleTime, renderTime);
372 0 : const float newTimePerResource = (time + clampedAssembleTime) / nResources;
373 0 : node->resources -= (clampedAssembleTime / newTimePerResource);
374 0 : if (node->resources < 0.f) // may happen due to fp rounding
375 0 : node->resources = 0.f;
376 : }
377 :
378 4 : void LoadEqualizer::_updateNode(Node* node, const Viewport& vp,
379 : const Range& range)
380 : {
381 4 : Node* left = node->left;
382 4 : Node* right = node->right;
383 :
384 4 : LBASSERT(left);
385 4 : LBASSERT(right);
386 :
387 4 : Viewport leftVP = vp;
388 4 : Viewport rightVP = vp;
389 4 : Range leftRange = range;
390 4 : Range rightRange = range;
391 :
392 4 : switch (node->mode)
393 : {
394 : default:
395 0 : LBUNIMPLEMENTED;
396 :
397 : case MODE_VERTICAL:
398 4 : leftVP.w = vp.w * .5f;
399 4 : rightVP.x = leftVP.getXEnd();
400 4 : rightVP.w = vp.getXEnd() - rightVP.x;
401 4 : node->split = leftVP.getXEnd();
402 4 : break;
403 :
404 : case MODE_HORIZONTAL:
405 0 : leftVP.h = vp.h * .5f;
406 0 : rightVP.y = leftVP.getYEnd();
407 0 : rightVP.h = vp.getYEnd() - rightVP.y;
408 0 : node->split = leftVP.getYEnd();
409 0 : break;
410 :
411 : case MODE_DB:
412 0 : leftRange.end = range.start + (range.end - range.start) * .5f;
413 0 : rightRange.start = leftRange.end;
414 0 : node->split = leftRange.end;
415 0 : break;
416 : }
417 :
418 4 : _update(left, leftVP, leftRange);
419 4 : _update(right, rightVP, rightRange);
420 :
421 4 : node->resources = left->resources + right->resources;
422 :
423 4 : if (left->resources == 0.f)
424 : {
425 0 : node->maxSize = right->maxSize;
426 0 : node->boundary2i = right->boundary2i;
427 0 : node->boundaryf = right->boundaryf;
428 0 : node->resistance2i = right->resistance2i;
429 0 : node->resistancef = right->resistancef;
430 : }
431 4 : else if (right->resources == 0.f)
432 : {
433 0 : node->maxSize = left->maxSize;
434 0 : node->boundary2i = left->boundary2i;
435 0 : node->boundaryf = left->boundaryf;
436 0 : node->resistance2i = left->resistance2i;
437 0 : node->resistancef = left->resistancef;
438 : }
439 : else
440 : {
441 4 : switch (node->mode)
442 : {
443 : case MODE_VERTICAL:
444 4 : node->maxSize.x() = left->maxSize.x() + right->maxSize.x();
445 4 : node->maxSize.y() = LB_MIN(left->maxSize.y(), right->maxSize.y());
446 4 : node->boundary2i.x() = left->boundary2i.x() + right->boundary2i.x();
447 8 : node->boundary2i.y() =
448 4 : LB_MAX(left->boundary2i.y(), right->boundary2i.y());
449 4 : node->boundaryf = LB_MAX(left->boundaryf, right->boundaryf);
450 8 : node->resistance2i.x() =
451 4 : LB_MAX(left->resistance2i.x(), right->resistance2i.x());
452 8 : node->resistance2i.y() =
453 4 : LB_MAX(left->resistance2i.y(), right->resistance2i.y());
454 4 : node->resistancef = LB_MAX(left->resistancef, right->resistancef);
455 4 : break;
456 : case MODE_HORIZONTAL:
457 0 : node->maxSize.x() = LB_MIN(left->maxSize.x(), right->maxSize.x());
458 0 : node->maxSize.y() = left->maxSize.y() + right->maxSize.y();
459 0 : node->boundary2i.x() =
460 0 : LB_MAX(left->boundary2i.x(), right->boundary2i.x());
461 0 : node->boundary2i.y() = left->boundary2i.y() + right->boundary2i.y();
462 0 : node->boundaryf = LB_MAX(left->boundaryf, right->boundaryf);
463 0 : node->resistance2i.x() =
464 0 : LB_MAX(left->resistance2i.x(), right->resistance2i.x());
465 0 : node->resistance2i.y() =
466 0 : LB_MAX(left->resistance2i.y(), right->resistance2i.y());
467 0 : node->resistancef = LB_MAX(left->resistancef, right->resistancef);
468 0 : break;
469 : case MODE_DB:
470 0 : node->boundary2i.x() =
471 0 : LB_MAX(left->boundary2i.x(), right->boundary2i.x());
472 0 : node->boundary2i.y() =
473 0 : LB_MAX(left->boundary2i.y(), right->boundary2i.y());
474 0 : node->boundaryf = left->boundaryf + right->boundaryf;
475 0 : node->resistance2i.x() =
476 0 : LB_MAX(left->resistance2i.x(), right->resistance2i.x());
477 0 : node->resistance2i.y() =
478 0 : LB_MAX(left->resistance2i.y(), right->resistance2i.y());
479 0 : node->resistancef = LB_MAX(left->resistancef, right->resistancef);
480 0 : break;
481 : default:
482 0 : LBUNIMPLEMENTED;
483 : }
484 : }
485 4 : }
486 :
487 8 : int64_t LoadEqualizer::_getTotalTime()
488 : {
489 8 : const LBFrameData& frameData = _history.front();
490 16 : LBDatas items = frameData.second;
491 8 : _removeEmpty(items);
492 :
493 8 : int64_t totalTime = 0;
494 16 : for (LBDatas::const_iterator i = items.begin(); i != items.end(); ++i)
495 : {
496 8 : const Data& data = *i;
497 8 : totalTime += data.time;
498 : }
499 16 : return totalTime;
500 : }
501 :
502 4 : int64_t LoadEqualizer::_getAssembleTime()
503 : {
504 4 : if (getDamping() >= 1.f)
505 0 : return 0;
506 :
507 4 : const LBFrameData& frameData = _history.front();
508 4 : const LBDatas& items = frameData.second;
509 :
510 4 : int64_t assembleTime = 0;
511 8 : for (LBDatas::const_iterator i = items.begin(); i != items.end(); ++i)
512 : {
513 4 : const Data& data = *i;
514 4 : LBASSERT(assembleTime == 0 || data.assembleTime == 0);
515 4 : assembleTime += data.assembleTime;
516 : }
517 4 : return assembleTime;
518 : }
519 :
520 4 : void LoadEqualizer::_computeSplit()
521 : {
522 4 : LBASSERT(!_history.empty());
523 :
524 4 : const LBFrameData& frameData = _history.front();
525 4 : const Compound* compound = getCompound();
526 4 : LBLOG(LOG_LB2) << "----- balance " << compound->getChannel()->getName()
527 0 : << " using frame " << frameData.first << " tree "
528 0 : << std::endl
529 4 : << _tree;
530 :
531 : // sort load items for each of the split directions
532 8 : LBDatas items(frameData.second);
533 4 : _removeEmpty(items);
534 :
535 8 : LBDatas sortedData[3] = {items, items, items};
536 :
537 4 : if (getMode() == MODE_DB)
538 : {
539 0 : LBDatas& rangeData = sortedData[MODE_DB];
540 0 : sort(rangeData.begin(), rangeData.end(), _compareRange);
541 : }
542 : else
543 : {
544 4 : LBDatas& xData = sortedData[MODE_VERTICAL];
545 4 : sort(xData.begin(), xData.end(), _compareX);
546 :
547 4 : LBDatas& yData = sortedData[MODE_HORIZONTAL];
548 4 : sort(yData.begin(), yData.end(), _compareY);
549 :
550 : #ifndef NDEBUG
551 8 : for (LBDatas::const_iterator i = xData.begin(); i != xData.end(); ++i)
552 : {
553 4 : const Data& data = *i;
554 4 : LBLOG(LOG_LB2) << " " << data.vp << ", time " << data.time << " (+"
555 4 : << data.assembleTime << ")" << std::endl;
556 : }
557 : #endif
558 : }
559 :
560 4 : const float time = float(_getTotalTime());
561 4 : LBLOG(LOG_LB2) << "Render time " << time << " for " << _tree->resources
562 4 : << " resources" << std::endl;
563 4 : if (_tree->resources > 0.f)
564 4 : _computeSplit(_tree, time, sortedData, Viewport(), Range());
565 4 : }
566 :
567 12 : void LoadEqualizer::_removeEmpty(LBDatas& items)
568 : {
569 24 : for (LBDatas::iterator i = items.begin(); i != items.end();)
570 : {
571 12 : Data& data = *i;
572 :
573 12 : if (!data.vp.hasArea() || !data.range.hasData())
574 0 : i = items.erase(i);
575 : else
576 12 : ++i;
577 : }
578 12 : }
579 :
580 12 : void LoadEqualizer::_computeSplit(Node* node, const float time, LBDatas* datas,
581 : const Viewport& vp, const Range& range)
582 : {
583 12 : LBLOG(LOG_LB2) << "_computeSplit " << vp << ", " << range << " time "
584 12 : << time << std::endl;
585 12 : LBASSERTINFO(vp.isValid(), vp);
586 12 : LBASSERTINFO(range.isValid(), range);
587 12 : LBASSERTINFO(node->resources > 0.f || !vp.hasArea() || !range.hasData(),
588 : "Assigning " << node->resources << " work to viewport " << vp
589 : << ", " << range);
590 :
591 12 : Compound* compound = node->compound;
592 12 : if (compound)
593 : {
594 8 : _assign(compound, vp, range);
595 8 : return;
596 : }
597 :
598 4 : LBASSERT(node->left && node->right);
599 :
600 8 : LBDatas workingSet = datas[node->mode];
601 4 : const float leftTime = node->resources > 0
602 4 : ? time * node->left->resources / node->resources
603 4 : : 0.f;
604 4 : float timeLeft = LB_MIN(leftTime, time); // correct for fp rounding error
605 :
606 4 : switch (node->mode)
607 : {
608 : case MODE_VERTICAL:
609 : {
610 4 : LBASSERT(range == Range::ALL);
611 :
612 4 : float splitPos = vp.x;
613 4 : const float end = vp.getXEnd();
614 :
615 16 : while (timeLeft > std::numeric_limits<float>::epsilon() &&
616 4 : splitPos < end)
617 : {
618 4 : LBLOG(LOG_LB2) << timeLeft << "ms left using " << workingSet.size()
619 4 : << " tiles" << std::endl;
620 :
621 : // remove all irrelevant items from working set
622 24 : for (LBDatas::iterator i = workingSet.begin();
623 16 : i != workingSet.end();)
624 : {
625 4 : const Data& data = *i;
626 4 : if (data.vp.getXEnd() > splitPos)
627 4 : ++i;
628 : else
629 0 : i = workingSet.erase(i);
630 : }
631 4 : if (workingSet.empty())
632 0 : break;
633 :
634 : // find next 'discontinouity' in loads
635 4 : float currentPos = 1.0f;
636 24 : for (LBDatas::const_iterator i = workingSet.begin();
637 16 : i != workingSet.end(); ++i)
638 : {
639 4 : const Data& data = *i;
640 4 : if (data.vp.x > splitPos && data.vp.x < currentPos)
641 0 : currentPos = data.vp.x;
642 4 : const float xEnd = data.vp.getXEnd();
643 4 : if (xEnd > splitPos && xEnd < currentPos)
644 0 : currentPos = xEnd;
645 : }
646 :
647 4 : const float width = currentPos - splitPos;
648 4 : LBASSERTINFO(width > 0.f, currentPos << "<=" << splitPos);
649 4 : LBASSERT(currentPos <= 1.0f);
650 :
651 : // accumulate normalized load in splitPos...currentPos
652 4 : LBLOG(LOG_LB2) << "Computing load in X " << splitPos << "..."
653 4 : << currentPos << std::endl;
654 4 : float currentTime = 0.f;
655 24 : for (LBDatas::const_iterator i = workingSet.begin();
656 16 : i != workingSet.end(); ++i)
657 : {
658 4 : const Data& data = *i;
659 :
660 4 : if (data.vp.x >= currentPos) // not yet needed data sets
661 0 : break;
662 :
663 4 : float yContrib = data.vp.h;
664 4 : if (data.vp.y < vp.y)
665 0 : yContrib -= (vp.y - data.vp.y);
666 :
667 4 : const float dataEnd = data.vp.getYEnd();
668 4 : const float vpEnd = vp.getYEnd();
669 4 : if (dataEnd > vpEnd)
670 0 : yContrib -= (dataEnd - vpEnd);
671 :
672 4 : if (yContrib > 0.f)
673 : {
674 : const float percentage =
675 4 : (width / data.vp.w) * (yContrib / data.vp.h);
676 4 : currentTime += (data.time * percentage);
677 :
678 4 : LBLOG(LOG_LB2)
679 0 : << data.vp << " contributes " << yContrib << " in "
680 0 : << vp.h << " (" << percentage << ") with " << data.time
681 0 : << ": " << (data.time * percentage) << " vp.y " << vp.y
682 0 : << " dataEnd " << dataEnd << " vpEnd " << vpEnd
683 4 : << std::endl;
684 4 : LBASSERT(percentage < 1.01f)
685 : }
686 : }
687 :
688 4 : LBLOG(LOG_LB2) << splitPos << "..." << currentPos
689 0 : << ": t=" << currentTime << " of " << timeLeft
690 4 : << std::endl;
691 :
692 4 : if (currentTime >= timeLeft) // found last region
693 : {
694 4 : splitPos += (width * timeLeft / currentTime);
695 4 : timeLeft = 0.0f;
696 : }
697 : else
698 : {
699 0 : timeLeft -= currentTime;
700 0 : splitPos = currentPos;
701 : }
702 : }
703 :
704 4 : LBLOG(LOG_LB2) << "Should split at X " << splitPos << std::endl;
705 4 : if (getDamping() < 1.f)
706 4 : splitPos =
707 4 : (1.f - getDamping()) * splitPos + getDamping() * node->split;
708 4 : LBLOG(LOG_LB2) << "Dampened split at X " << splitPos << std::endl;
709 :
710 : // There might be more time left due to MIN_PIXEL rounding by parent
711 : // LBASSERTINFO( timeLeft <= .001f, timeLeft );
712 :
713 : // Ensure minimum size
714 4 : const Compound* root = getCompound();
715 : const float pvpW =
716 4 : static_cast<float>(root->getInheritPixelViewport().w);
717 4 : const float boundary = static_cast<float>(node->boundary2i.x()) / pvpW;
718 4 : if (node->left->resources == 0.f)
719 0 : splitPos = vp.x;
720 4 : else if (node->right->resources == 0.f)
721 0 : splitPos = end;
722 4 : else if (boundary > 0)
723 : {
724 4 : const float lengthRight = vp.getXEnd() - splitPos;
725 4 : const float lengthLeft = splitPos - vp.x;
726 : const float maxRight =
727 4 : static_cast<float>(node->right->maxSize.x()) / pvpW;
728 : const float maxLeft =
729 4 : static_cast<float>(node->left->maxSize.x()) / pvpW;
730 4 : if (lengthRight > maxRight)
731 0 : splitPos = end - maxRight;
732 4 : else if (lengthLeft > maxLeft)
733 0 : splitPos = vp.x + maxLeft;
734 :
735 4 : if ((splitPos - vp.x) < boundary)
736 0 : splitPos = vp.x + boundary;
737 4 : if ((end - splitPos) < boundary)
738 0 : splitPos = end - boundary;
739 :
740 : const uint32_t ratio =
741 4 : static_cast<uint32_t>(splitPos / boundary + .5f);
742 4 : splitPos = ratio * boundary;
743 : }
744 :
745 4 : splitPos = LB_MAX(splitPos, vp.x);
746 4 : splitPos = LB_MIN(splitPos, end);
747 :
748 4 : const float newPixelW = pvpW * splitPos;
749 4 : const float oldPixelW = pvpW * node->split;
750 4 : if (int(fabs(newPixelW - oldPixelW)) < node->resistance2i.x())
751 0 : splitPos = node->split;
752 : else
753 4 : node->split = splitPos;
754 :
755 4 : LBLOG(LOG_LB2) << "Constrained split " << vp << " at X " << splitPos
756 4 : << std::endl;
757 :
758 : // balance children
759 4 : Viewport childVP = vp;
760 4 : childVP.w = (splitPos - vp.x);
761 4 : _computeSplit(node->left, leftTime, datas, childVP, range);
762 :
763 4 : childVP.x = childVP.getXEnd();
764 4 : childVP.w = end - childVP.x;
765 : // Fix 2994111: Rounding errors with 2D LB and 16 sources
766 : // Floating point rounding may create a width for the 'right'
767 : // child which is slightly below the parent width. Correct it.
768 4 : while (childVP.getXEnd() < end)
769 0 : childVP.w += std::numeric_limits<float>::epsilon();
770 4 : _computeSplit(node->right, time - leftTime, datas, childVP, range);
771 4 : break;
772 : }
773 :
774 : case MODE_HORIZONTAL:
775 : {
776 0 : LBASSERT(range == Range::ALL);
777 0 : float splitPos = vp.y;
778 0 : const float end = vp.getYEnd();
779 :
780 0 : while (timeLeft > std::numeric_limits<float>::epsilon() &&
781 0 : splitPos < end)
782 : {
783 0 : LBLOG(LOG_LB2) << timeLeft << "ms left using " << workingSet.size()
784 0 : << " tiles" << std::endl;
785 :
786 : // remove all unrelevant items from working set
787 0 : for (LBDatas::iterator i = workingSet.begin();
788 0 : i != workingSet.end();)
789 : {
790 0 : const Data& data = *i;
791 0 : if (data.vp.getYEnd() > splitPos)
792 0 : ++i;
793 : else
794 0 : i = workingSet.erase(i);
795 : }
796 0 : if (workingSet.empty())
797 0 : break;
798 :
799 : // find next 'discontinuouity' in loads
800 0 : float currentPos = 1.0f;
801 0 : for (LBDatas::const_iterator i = workingSet.begin();
802 0 : i != workingSet.end(); ++i)
803 : {
804 0 : const Data& data = *i;
805 0 : if (data.vp.y > splitPos && data.vp.y < currentPos)
806 0 : currentPos = data.vp.y;
807 0 : const float yEnd = data.vp.getYEnd();
808 0 : if (yEnd > splitPos && yEnd < currentPos)
809 0 : currentPos = yEnd;
810 : }
811 :
812 0 : const float height = currentPos - splitPos;
813 0 : LBASSERTINFO(height > 0.f, currentPos << "<=" << splitPos);
814 0 : LBASSERT(currentPos <= 1.0f);
815 :
816 : // accumulate normalized load in splitPos...currentPos
817 0 : LBLOG(LOG_LB2) << "Computing load in Y " << splitPos << "..."
818 0 : << currentPos << std::endl;
819 0 : float currentTime = 0.f;
820 0 : for (LBDatas::const_iterator i = workingSet.begin();
821 0 : i != workingSet.end(); ++i)
822 : {
823 0 : const Data& data = *i;
824 :
825 0 : if (data.vp.y >= currentPos) // not yet needed data sets
826 0 : break;
827 :
828 0 : float xContrib = data.vp.w;
829 :
830 0 : if (data.vp.x < vp.x)
831 0 : xContrib -= (vp.x - data.vp.x);
832 :
833 0 : const float dataEnd = data.vp.getXEnd();
834 0 : const float vpEnd = vp.getXEnd();
835 0 : if (dataEnd > vpEnd)
836 0 : xContrib -= (dataEnd - vpEnd);
837 :
838 0 : if (xContrib > 0.f)
839 : {
840 : const float percentage =
841 0 : (height / data.vp.h) * (xContrib / data.vp.w);
842 0 : currentTime += (data.time * percentage);
843 :
844 0 : LBLOG(LOG_LB2)
845 0 : << data.vp << " contributes " << xContrib << " in "
846 0 : << vp.w << " (" << percentage << ") with " << data.time
847 0 : << ": " << (data.time * percentage) << " total "
848 0 : << currentTime << " vp.x " << vp.x << " dataEnd "
849 0 : << dataEnd << " vpEnd " << vpEnd << std::endl;
850 0 : LBASSERT(percentage < 1.01f)
851 : }
852 : }
853 :
854 0 : LBLOG(LOG_LB2) << splitPos << "..." << currentPos
855 0 : << ": t=" << currentTime << " of " << timeLeft
856 0 : << std::endl;
857 :
858 0 : if (currentTime >= timeLeft) // found last region
859 : {
860 0 : splitPos += (height * timeLeft / currentTime);
861 0 : timeLeft = 0.0f;
862 : }
863 : else
864 : {
865 0 : timeLeft -= currentTime;
866 0 : splitPos = currentPos;
867 : }
868 : }
869 :
870 0 : LBLOG(LOG_LB2) << "Should split at Y " << splitPos << std::endl;
871 0 : if (getDamping() < 1.f)
872 0 : splitPos =
873 0 : (1.f - getDamping()) * splitPos + getDamping() * node->split;
874 0 : LBLOG(LOG_LB2) << "Dampened split at Y " << splitPos << std::endl;
875 :
876 0 : const Compound* root = getCompound();
877 :
878 : const float pvpH =
879 0 : static_cast<float>(root->getInheritPixelViewport().h);
880 0 : const float boundary = static_cast<float>(node->boundary2i.y()) / pvpH;
881 :
882 0 : if (node->left->resources == 0.f)
883 0 : splitPos = vp.y;
884 0 : else if (node->right->resources == 0.f)
885 0 : splitPos = end;
886 0 : else if (boundary > 0)
887 : {
888 0 : const float lengthRight = vp.getYEnd() - splitPos;
889 0 : const float lengthLeft = splitPos - vp.y;
890 : const float maxRight =
891 0 : static_cast<float>(node->right->maxSize.y()) / pvpH;
892 : const float maxLeft =
893 0 : static_cast<float>(node->left->maxSize.y()) / pvpH;
894 0 : if (lengthRight > maxRight)
895 0 : splitPos = end - maxRight;
896 0 : else if (lengthLeft > maxLeft)
897 0 : splitPos = vp.y + maxLeft;
898 :
899 0 : if ((splitPos - vp.y) < boundary)
900 0 : splitPos = vp.y + boundary;
901 0 : if ((end - splitPos) < boundary)
902 0 : splitPos = end - boundary;
903 :
904 : const uint32_t ratio =
905 0 : static_cast<uint32_t>(splitPos / boundary + .5f);
906 0 : splitPos = ratio * boundary;
907 : }
908 :
909 0 : splitPos = LB_MAX(splitPos, vp.y);
910 0 : splitPos = LB_MIN(splitPos, end);
911 :
912 0 : const float newPixelH = pvpH * splitPos;
913 0 : const float oldPixelH = pvpH * node->split;
914 0 : if (int(fabs(newPixelH - oldPixelH)) < node->resistance2i.y())
915 0 : splitPos = node->split;
916 : else
917 0 : node->split = splitPos;
918 :
919 0 : LBLOG(LOG_LB2) << "Constrained split " << vp << " at Y " << splitPos
920 0 : << std::endl;
921 :
922 0 : Viewport childVP = vp;
923 0 : childVP.h = (splitPos - vp.y);
924 0 : _computeSplit(node->left, leftTime, datas, childVP, range);
925 :
926 0 : childVP.y = childVP.getYEnd();
927 0 : childVP.h = end - childVP.y;
928 0 : while (childVP.getYEnd() < end)
929 0 : childVP.h += std::numeric_limits<float>::epsilon();
930 0 : _computeSplit(node->right, time - leftTime, datas, childVP, range);
931 0 : break;
932 : }
933 :
934 : case MODE_DB:
935 : {
936 0 : LBASSERT(vp == Viewport::FULL);
937 0 : float splitPos = range.start;
938 0 : const float end = range.end;
939 :
940 0 : while (timeLeft > std::numeric_limits<float>::epsilon() &&
941 : splitPos < end)
942 : {
943 0 : LBLOG(LOG_LB2) << timeLeft << "ms left using " << workingSet.size()
944 0 : << " tiles" << std::endl;
945 :
946 : // remove all irrelevant items from working set
947 0 : for (LBDatas::iterator i = workingSet.begin();
948 0 : i != workingSet.end();)
949 : {
950 0 : const Data& data = *i;
951 0 : if (data.range.end > splitPos)
952 0 : ++i;
953 : else
954 0 : i = workingSet.erase(i);
955 : }
956 0 : if (workingSet.empty())
957 0 : break;
958 :
959 : // find next 'discontinouity' in loads
960 0 : float currentPos = 1.0f;
961 0 : for (LBDatas::const_iterator i = workingSet.begin();
962 0 : i != workingSet.end(); ++i)
963 : {
964 0 : const Data& data = *i;
965 0 : currentPos = LB_MIN(currentPos, data.range.end);
966 : }
967 :
968 0 : const float size = currentPos - splitPos;
969 0 : LBASSERTINFO(size > 0.f, currentPos << "<=" << splitPos);
970 0 : LBASSERT(currentPos <= 1.0f);
971 :
972 : // accumulate normalized load in splitPos...currentPos
973 0 : LBLOG(LOG_LB2) << "Computing load in range " << splitPos << "..."
974 0 : << currentPos << std::endl;
975 0 : float currentTime = 0.f;
976 0 : for (LBDatas::const_iterator i = workingSet.begin();
977 0 : i != workingSet.end(); ++i)
978 : {
979 0 : const Data& data = *i;
980 :
981 0 : if (data.range.start >= currentPos) // not yet needed data
982 0 : break;
983 : #if 0
984 : // make sure we cover full area
985 : LBASSERTINFO( data.range.start <= splitPos,
986 : data.range.start << " > " << splitPos );
987 : LBASSERTINFO( data.range.end >= currentPos,
988 : data.range.end << " < " << currentPos);
989 : #endif
990 0 : currentTime += data.time * size / data.range.getSize();
991 : }
992 :
993 0 : LBLOG(LOG_LB2) << splitPos << "..." << currentPos
994 0 : << ": t=" << currentTime << " of " << timeLeft
995 0 : << std::endl;
996 :
997 0 : if (currentTime >= timeLeft) // found last region
998 : {
999 0 : const float width = currentPos - splitPos;
1000 0 : splitPos += (width * timeLeft / currentTime);
1001 0 : timeLeft = 0.0f;
1002 : }
1003 : else
1004 : {
1005 0 : timeLeft -= currentTime;
1006 0 : splitPos = currentPos;
1007 : }
1008 : }
1009 0 : LBLOG(LOG_LB2) << "Should split at " << splitPos << std::endl;
1010 0 : if (getDamping() < 1.f)
1011 0 : splitPos =
1012 0 : (1.f - getDamping()) * splitPos + getDamping() * node->split;
1013 0 : LBLOG(LOG_LB2) << "Dampened split at " << splitPos << std::endl;
1014 :
1015 0 : const float boundary(node->boundaryf);
1016 0 : if (node->left->resources == 0.f)
1017 0 : splitPos = range.start;
1018 0 : else if (node->right->resources == 0.f)
1019 0 : splitPos = end;
1020 :
1021 0 : const uint32_t ratio = static_cast<uint32_t>(splitPos / boundary + .5f);
1022 0 : splitPos = ratio * boundary;
1023 0 : if ((splitPos - range.start) < boundary)
1024 0 : splitPos = range.start;
1025 0 : if ((end - splitPos) < boundary)
1026 0 : splitPos = end;
1027 :
1028 0 : if (fabs(splitPos - node->split) < node->resistancef)
1029 0 : splitPos = node->split;
1030 : else
1031 0 : node->split = splitPos;
1032 :
1033 0 : LBLOG(LOG_LB2) << "Constrained split " << range << " at pos "
1034 0 : << splitPos << std::endl;
1035 :
1036 0 : Range childRange = range;
1037 0 : childRange.end = splitPos;
1038 0 : _computeSplit(node->left, leftTime, datas, vp, childRange);
1039 :
1040 0 : childRange.start = childRange.end;
1041 0 : childRange.end = range.end;
1042 0 : _computeSplit(node->right, time - leftTime, datas, vp, childRange);
1043 0 : break;
1044 : }
1045 :
1046 : default:
1047 0 : LBUNIMPLEMENTED;
1048 : }
1049 : }
1050 :
1051 8 : void LoadEqualizer::_assign(Compound* compound, const Viewport& vp,
1052 : const Range& range)
1053 : {
1054 8 : LBASSERTINFO(vp == Viewport::FULL || range == Range::ALL,
1055 : "Mixed 2D/DB load-balancing not implemented");
1056 :
1057 8 : compound->setViewport(vp);
1058 8 : compound->setRange(range);
1059 8 : LBLOG(LOG_LB2) << compound->getChannel()->getName() << " set " << vp << ", "
1060 8 : << range << std::endl;
1061 :
1062 8 : if (getDamping() >= 1.f)
1063 0 : return;
1064 :
1065 : // save data for later use
1066 8 : Data data;
1067 8 : data.vp = vp;
1068 8 : data.range = range;
1069 8 : data.channel = compound->getChannel();
1070 8 : data.taskID = compound->getTaskID();
1071 :
1072 8 : const Compound* destCompound = getCompound();
1073 8 : if (destCompound->getChannel() == compound->getChannel())
1074 4 : data.destTaskID = destCompound->getTaskID();
1075 :
1076 8 : LBASSERT(data.taskID > 0);
1077 :
1078 8 : if (!vp.hasArea() || !range.hasData()) // will not render
1079 0 : data.time = 0;
1080 :
1081 8 : LBFrameData& frameData = _history.back();
1082 8 : LBDatas& items = frameData.second;
1083 :
1084 8 : items.push_back(data);
1085 : }
1086 :
1087 0 : std::ostream& operator<<(std::ostream& os, const LoadEqualizer::Node* node)
1088 : {
1089 0 : if (!node)
1090 0 : return os;
1091 :
1092 0 : os << lunchbox::disableFlush;
1093 :
1094 0 : if (node->compound)
1095 0 : os << node->compound->getChannel()->getName() << " resources "
1096 0 : << node->resources << " max size " << node->maxSize << std::endl;
1097 : else
1098 0 : os << "split " << node->mode << " @ " << node->split << " resources "
1099 0 : << node->resources << " max size " << node->maxSize << std::endl
1100 0 : << lunchbox::indent << node->left << node->right << lunchbox::exdent;
1101 :
1102 0 : os << lunchbox::enableFlush;
1103 0 : return os;
1104 : }
1105 :
1106 130 : std::ostream& operator<<(std::ostream& os, const LoadEqualizer* lb)
1107 : {
1108 130 : if (!lb)
1109 0 : return os;
1110 :
1111 130 : os << lunchbox::disableFlush << "load_equalizer" << std::endl
1112 130 : << '{' << std::endl
1113 260 : << " mode " << lb->getMode() << std::endl;
1114 :
1115 130 : if (lb->getDamping() != 0.5f)
1116 16 : os << " damping " << lb->getDamping() << std::endl;
1117 :
1118 130 : if (lb->getBoundary2i() != Vector2i(1, 1))
1119 0 : os << " boundary [ " << lb->getBoundary2i().x() << " "
1120 0 : << lb->getBoundary2i().y() << " ]" << std::endl;
1121 :
1122 130 : if (lb->getBoundaryf() != std::numeric_limits<float>::epsilon())
1123 0 : os << " boundary " << lb->getBoundaryf() << std::endl;
1124 :
1125 130 : if (lb->getResistance2i() != Vector2i(0, 0))
1126 0 : os << " resistance [ " << lb->getResistance2i().x() << " "
1127 0 : << lb->getResistance2i().y() << " ]" << std::endl;
1128 :
1129 130 : if (lb->getResistancef() != .0f)
1130 0 : os << " resistance " << lb->getResistancef() << std::endl;
1131 :
1132 130 : os << '}' << std::endl << lunchbox::enableFlush;
1133 130 : return os;
1134 : }
1135 : }
1136 60 : }
|
