Abstract
This paper investigates assignment strategies (load balancing algorithms)
for process farms which solve the problem of online placement of a constant
number of independent tasks with given, but unknown, time complexities onto
a homogeneous network of processors with a given latency. Results for the
chunking and factoring assignment strategies are summarised for a
probabilistic model which models tasks' time complexities as realisations of
a random variable with known mean and variance. Then a deterministic model
is presented which requires the knowledge of the minimal and maximal tasks'
complexities. While the goal in the probabilistic model is the minimisation
of the expected makespan, the goal in the deterministic model is the
minimisation of the worst-case makespan. We give a novel analysis of
chunking and factoring for the deterministic model. In the context of
demand-driven parallel ray tracing, tasks' time complexities are
unfortunately unknown until the actual computation finishes. Therefore we
propose automatic self-tuning procedures which estimate the missing
information in run-time. We experimentally demonstrate for an ``everyday ray
tracing setting'' that chunking does not perform much worse than factoring
on up to 128 processors, if the parameters of these strategies are properly
tuned. This may seem surprising. However, the experimentally measured
efficiencies agree with our theoretical predictions.
| Translated title of the contribution | Tuning of Algorithms for Independent Task Placement in the Context of Demand-Driven Parallel Ray Tracing |
|---|---|
| Original language | English |
| Title of host publication | Unknown |
| Publisher | ACM SIGGRAPH |
| Pages | 101 - 109 |
| Number of pages | 8 |
| ISBN (Print) | 3905673118 |
| Publication status | Published - Jun 2004 |