Load Balancing Methods For Ray Tracing And Binary Tree Computing Using Pvm

    Authors

    C. N. Sekharan; V. Goel;R. Sridhar

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Parallel Comput.

    Keywords

    load balancing; ray tracing; binary tree; distributed environment; PVM; workstation cluster; Computer Science, Theory & Methods

    Abstract

    We propose efficient load balancing methods for two computational problems namely ray tracing and bottom-up binary tree computing in a distributed environment. In the context of ray tracing, we propose a variant of a static load balancing technique presented in [15] where the sampling is based on partitioning the object space. Our approach partitions the image instead and uses an efficient scheduling technique for load balancing. Computations carried out on a binary tree arise naturally in image processing and network optimization problems. Many of these problems are solved efficiently in parallel by the popular tree contraction technique [1]. In this paper, we explore the tree-contraction technique in a distributed setting using the grain packing method [9]. Implementations of our algorithms on a cluster of workstations using Parallel Virtual Machine (PVM) [6] demonstrate near-perfect load balancing.

    Journal Title

    Parallel Computing

    Volume

    21

    Issue/Number

    12

    Publication Date

    1-1-1995

    Document Type

    Article

    Language

    English

    First Page

    1963

    Last Page

    1978

    WOS Identifier

    WOS:A1995TN61500006

    ISSN

    0167-8191

    Share

    COinS