NPAC Technical Report SCCS-773
Phantom
Sanjay Goil
Submitted September 1 1996
Abstract
In this report we address a class of problems consisting of highly structured
computations on data sets that are described by hierarchical data structures.
These are often represented as {\em tree} structures to optimize
data storage requirements and perform efficient queries for data access.
Specifically, applications that are dynamic and perform many iterations on data
are of interest to us, since the requirements for data evolve over time and require
modifying data structures incrementally. The computational relationship between the
subdomains is known only at runtime, and may change between computation phases.
Parallelization of such applications requires efficient distributed data management
and has received some attention recently.
We study the computational structure of a few irregular applications falling
in this category. This helps us to evaluate data structures and the address issues
of data partitioning, load balancing and communication requirements for these
applications. Most recent efforts have been application specific and solutions are not
portable across applications or parallel computing platforms.
In this research we wish to characterize requirements for primitives and runtime
software support needed to parallelize irregular applications.
A study of the computational structure of applications allows us to identify requirements
for parallelization across a broad spectrum. Each application uses a tree data structure
to organize data for efficient construction, manipulation and querying of related data.
We enumerate algorithms that are used for solving these applications
and discuss their parallelization. We present an outline of primitives that are needed to
parallelize such applications. These can be used to provide language support by high
performance languages to parallelize hierarchical applications.