Cited By
View all- Santos LValentim SFernandes ASlavik P(2006)Parallel progressive precomputed radiance transferProceedings of the 22nd Spring Conference on Computer Graphics10.1145/2602161.2602165(33-40)Online publication date: 20-Apr-2006
Tuning of algorithms for independent task placement in the context of demand-driven parallel ray tracing
Pages 101 - 109
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 worstcase 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.
References
[1]
BADOUEL D., BOUATOUCH K., PRIOL T.: Distributing data and control for ray tracing in parallel. IEEE Computer Graphics and Applications 14, 4 (1994), 69-77.
[2]
BANICESCU I., FLYNN-HUMMEL S.: Balancing Processor Loads and Exploiting Data Locality in Irregular Computations. Tech. Rep. RC 19934, IBM Research, 1995.
[3]
DIPPÉ M., SWENSSEN J.: An adaptive subdivision algorithm and parallel architecture for realistic image synthesis. Computer Graphics 18, 3 (1984).
[4]
FLYNN L. E., FLYNN-HUMMEL S.: Scheduling Variable-Length Parallel Subtasks. Tech. Rep. RC 15492, IBM Research, 1990.
[5]
FREISLEBEN B., HARTMANN D., KIELMANN T.: Parallel raytracing: A case study on partitioning and scheduling on workstation clusters. In Proc. of Hawaii International Conference on System Sciences (HICSS-30) (1997), vol. 1, IEEE Computer Society Press, pp. 596-605.
[6]
FREISLEBEN B., HARTMANN D., KIELMANN T.: Parallel incremental raytracing of animations on a network of workstations. In Proc. of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'98) (1998), Arabnia H., (Ed.), vol. 3, CSREA Press, pp. 1305-1312.
[7]
FLYNN-HUMMEL S., SCHONBERG E., FLYNN L. E.: Factoring: A practical and robust method for scheduling parallel loops. In Proc. of Supercomputing '91 (1991), IEEE Computer Society /ACM, pp. 610-619.
[8]
GLASSNER A. S.: An Introduction to Ray Tracing. Academic Press, 1989.
[9]
GREEN S.: Parallel Processing for Computer Graphics. Research Monographs in Parallel and Distributed Computing. Pitman Publishing, 1991.
[10]
HEIRICH A., ARVO J.: A competitive analysis of load balancing strategies for parallel ray tracing. The Journal of Supercomputing 12, 1-2 (1998), 57-68.
[11]
HAGERUP T.: Allocating independent tasks to parallel processors: An experimental study. Journal of Parallel and Distributed Computing 47, 2 (1997), 185-197.
[12]
KEATES M. J., HUBBOLD R. J.: Interactive ray tracing on a virtual shared-memory parallel computer. Computer Graphics Forum 14, 4 (1995), 189-202.
[13]
KRUSKAL C. P., WEISS A.: Allocating independent subtasks on parallel processors. IEEE Transactions on Software Engineering 11, 10 (1985), 1001-1016.
[14]
PITOT P.: The Voxar project. IEEE Computer Graphics and Applications (1993), 27-33.
[15]
PLACHETKA T.: POV||Ray: Persistence of Vision parallel raytracer. In Proc. of Spring Conference on Computer Graphics (1998), Szirmay-Kalos L., (Ed.), Comenius University, Bratislava, pp. 123-129.
[16]
PLACHETKA T.: Perfect load balancing for demand-driven parallel ray tracing. In Proc. of Euro-Par 2002 (2002), Monien B., Feldman R., (Eds.), vol. 2400 of Lecture Notes in Computer Science, Springer-Verlag, pp. 410-419.
[17]
PLACHETKA T.: (Quasi-) thread-safe PVM and (quasi-) thread-safe MPI without active polling. In Proc. of the 9th EuroPVM/MPI User's Group Conference (2002), Kranzlmüller D., Kacsuk P., Dongarra J., Volkert J., (Eds.), vol. 2474 of Lecture Notes in Computer Science, Springer-Verlag, pp. 296-305.
[18]
PARKER S., MARTIN W., SLOAN P. P. J., SHIRLEY P., SMITS B., HANSEN C.: Interactive ray tracing. In Proc. of the 1999 Symposium on Interactive 3D Graphics (1999), pp. 119-126.
[19]
WALD I., BENTHIN C., DIETRICH A., SLUSALLEK P.: Interactive ray tracing on commodity PC clusters--state of the art and practical applications. In Proc. of Euro-Par 2003 (2003), Kosch H., Böszörmenyi L., Hellwagner H., (Eds.), vol. 2790 of Lecture Notes in Computer Science, Springer-Verlag, pp. 499-508.
[20]
WHITTED T.: An improved illumination model for shaded display. Communications of the ACM 23, 6 (1980), 343-349.
Index Terms
- Tuning of algorithms for independent task placement in the context of demand-driven parallel ray tracing
Recommendations
Parameterized Ray-tracing
SIGGRAPH '89: Proceedings of the 16th annual conference on Computer graphics and interactive techniquesThe construction and refinement of a computer graphics scene is unacceptably slow when using ray tracing. We introduce a new technique to speed up the generation of successive ray traced images when the geometry of the scene remains constant and only ...
Distributed ray tracing
Ray tracing is one of the most elegant techniques in computer graphics. Many phenomena that are difficult or impossible with other techniques are simple with ray tracing, including shadows, reflections, and refracted light. Ray directions, however, ...
Ray Tracing with Polarization Parameters
Incorporating polarization parameters into the lighting model can enhance the physical realism of images rendered with a ray tracer. Polarization effects can be important in certain scenes, and the difference in rendering even simple scenes with and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- INPG: INPG Grenoble
- INRIA: INRIA Rhône-Alpes
In-Cooperation
- SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
- EUROGRAPHICS: The European Association for Computer Graphics
Publisher
Eurographics Association
Goslar, Germany
Publication History
Published: 10 June 2004
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Dec 2024
Other Metrics
Citations
Cited By
View all- Santos LValentim SFernandes ASlavik P(2006)Parallel progressive precomputed radiance transferProceedings of the 22nd Spring Conference on Computer Graphics10.1145/2602161.2602165(33-40)Online publication date: 20-Apr-2006