Tuning of Algorithms for Independent Task Placement in the Context of Demand-Driven Parallel Ray Tracing

T Plachetka

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

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 contributionTuning of Algorithms for Independent Task Placement in the Context of Demand-Driven Parallel Ray Tracing
Original languageEnglish
Title of host publicationUnknown
PublisherACM SIGGRAPH
Pages101 - 109
Number of pages8
ISBN (Print)3905673118
Publication statusPublished - Jun 2004

Bibliographical note

Conference Proceedings/Title of Journal: Proceedings of the Eurographics Symposium on Parallel Graphics and Visualization (EGPGV04)

Fingerprint Dive into the research topics of 'Tuning of Algorithms for Independent Task Placement in the Context of Demand-Driven Parallel Ray Tracing'. Together they form a unique fingerprint.

Cite this