NPAC Technical Report SCCS-687
Primitives for Problems using Hierarchical Algorithms on Distributed Memory Machines
Sanjay Goil
Submitted December 26 1994
Abstract
In scientific computing a class of problems has been identified that
consists of highly structured computations on sets of subdomains that
are coupled in a irregular manner. The computational relationship between
the subdomain is known only at runtime, which can also change between
computation phases. This can lead to load imbalance and unreasonable computation
overheads on parallel machines. We present an outline of primitives that are
required and the runtime support needed to ease the programming tasks involving
dynamic computation structures. We study some applications that exhibit different
computational structure but are classified under hierarchical methods and suggest
primitives that bind them in a common paradigm. This paper describes the structure
of the N-body simulation, Volume Rendering and Radiosity applications. The common
primitives they require for an efficient implementation on a distributed memory
parallel machine are elaborated.