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:

[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 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.
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$