Public Member Functions | Private Member Functions | Private Attributes | Friends

LibGeoDecomp::OozeBalancer Class Reference

The OozeBalancer is based on the (false) assumption that each node is equally fast, that each item (see LoadBalancer) costs about the same time to be computed (this is also false) and that these costs don't change all too much during the runtime (again: plain wrong). More...

#include <oozebalancer.h>

Inherits LibGeoDecomp::LoadBalancer.

Collaboration diagram for LibGeoDecomp::OozeBalancer:
Collaboration graph
[legend]

List of all members.

Public Member Functions

 OozeBalancer (double newLoadWeight=GOLDEN_RATIO/EULERS_NUMBER)
 returns a new OozeBalancer instance, whose weighting for new load distributions is set to newLoadWeight .
virtual WeightVec balance (const WeightVec &weights, const LoadVec &relativeLoads)
 Given the current workload distribution weights and the work time / wall clock time ratio relativeLoads for each node, return a new, possibly better distribution "newLoads".

Private Member Functions

LoadVec expectedOptimalDistribution (const WeightVec &weights, const LoadVec &relativeLoads) const
 Given that each node $n$ works on $weights[n]$ items, that this takes him $relativeLoads[n]$ time and that all nodes are roughly equally fast, then the optimal distribution $dist$ can be determined by cutting the sequence of items into $n$ subsets $s_i$ so that.
WeightVec equalize (const LoadVec &loads)
LoadVec linearCombo (const WeightVec &oldLoads, const LoadVec &newLoads)

Private Attributes

double newLoadWeight

Friends

class Serialization
class OozeBalancerTest1
class OozeBalancerTest2

Detailed Description

The OozeBalancer is based on the (false) assumption that each node is equally fast, that each item (see LoadBalancer) costs about the same time to be computed (this is also false) and that these costs don't change all too much during the runtime (again: plain wrong).

From all these questionable assumptions a possibly optimal new load distribution is derived but, to keep errors at bounds, the OozeBalancer will return a weighted linear combination of the old distribution (weights) and the new one is returned.


Constructor & Destructor Documentation

LibGeoDecomp::OozeBalancer::OozeBalancer ( double  newLoadWeight = GOLDEN_RATIO / EULERS_NUMBER  )  [explicit]

returns a new OozeBalancer instance, whose weighting for new load distributions is set to newLoadWeight .

A higher value will increase balancing speed (in terms of migrated items per balancing step), but also decrease accuracy (because of unfulfilled preconditions, see above) and vice versa. A quotient of the Golden Ratio and Eulers Number is believed to be optimal for most applications.


Member Function Documentation

OozeBalancer::WeightVec LibGeoDecomp::OozeBalancer::balance ( const WeightVec weights,
const LoadVec relativeLoads 
) [virtual]

Given the current workload distribution weights and the work time / wall clock time ratio relativeLoads for each node, return a new, possibly better distribution "newLoads".

Wall clock time is the sum of the work time and the waiting time during which a node is blocking on communication to other nodes.

NOTE: The sum of the elements in weights and the return value "newLoads" has to match, as the underlying assumption is, that this sum is the number of smallest, atomic work items that can be exchanged between to nodes. More formally:

\[ \sum_{i=0}^{i<n} \mbox{weights}[i] = \sum_{i=0}^{i<n} \mbox{newLoads}[i] \qquad \mbox{where:}\quad n = |\mbox{weights}| = |\mbox{newLoads}| \]

Implements LibGeoDecomp::LoadBalancer.

References equalize(), expectedOptimalDistribution(), linearCombo(), and LibGeoDecomp::sum().

Referenced by equalize().

OozeBalancer::WeightVec LibGeoDecomp::OozeBalancer::equalize ( const LoadVec loads  )  [private]

References balance(), and LibGeoDecomp::frac().

Referenced by balance().

OozeBalancer::LoadVec LibGeoDecomp::OozeBalancer::expectedOptimalDistribution ( const WeightVec weights,
const LoadVec relativeLoads 
) const [private]

Given that each node $n$ works on $weights[n]$ items, that this takes him $relativeLoads[n]$ time and that all nodes are roughly equally fast, then the optimal distribution $dist$ can be determined by cutting the sequence of items into $n$ subsets $s_i$ so that.

\[ \bigwedge_i \int_{t \in s_i} f(t) dt = l \]

where $l$ is the target load per node

\[ l = \frac{1}{n} \sum_{i=0}^{i<n} \cdot \mbox{weights}[i] \]

and $f(t)$ it the load (or time) necessary to compute item $t$:

\[ f(t) = \frac{\mbox{relativeLoads}[a]}{\mbox{weights}[a]} \]

( $t$ is currently computed on node $a$.)

References LibGeoDecomp::append(), and LibGeoDecomp::sum().

Referenced by balance().

OozeBalancer::LoadVec LibGeoDecomp::OozeBalancer::linearCombo ( const WeightVec oldLoads,
const LoadVec newLoads 
) [private]

References newLoadWeight.

Referenced by balance().


Friends And Related Function Documentation

friend class OozeBalancerTest1 [friend]
friend class OozeBalancerTest2 [friend]
friend class Serialization [friend]

Reimplemented from LibGeoDecomp::LoadBalancer.


Member Data Documentation

Referenced by linearCombo().


The documentation for this class was generated from the following files: