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.
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 ![]() ![]() ![]() ![]() ![]() ![]() | |
WeightVec | equalize (const LoadVec &loads) |
LoadVec | linearCombo (const WeightVec &oldLoads, const LoadVec &newLoads) |
Private Attributes | |
double | newLoadWeight |
Friends | |
class | Serialization |
class | OozeBalancerTest1 |
class | OozeBalancerTest2 |
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.
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.
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:
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 works on
items, that this takes him
time and that all nodes are roughly equally fast, then the optimal distribution
can be determined by cutting the sequence of items into
subsets
so that.
where is the target load per node
and it the load (or time) necessary to compute item
:
( is currently computed on node
.)
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().
friend class OozeBalancerTest1 [friend] |
friend class OozeBalancerTest2 [friend] |
friend class Serialization [friend] |
Reimplemented from LibGeoDecomp::LoadBalancer.
double LibGeoDecomp::OozeBalancer::newLoadWeight [private] |
Referenced by linearCombo().