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