Thesis Abstract
Parallelizing irregular, dynamic data structures can be a very difficult
problem. An efficient solution often demands that work on the data
structure be divided up among processors, yet despite the large and growing
number of such applications there has been little work done on general
approaches to such situations. In part this is due to the extreme
difficulty of ensuring enough generality to be useful, while still
efficiently addressing each individual problem; irregular and dynamic
problems can vary dramatically, and direct, efficient solutions simply do
not exist. Most attempts have therefore either concentrated on
problem-specific areas, where good results can be obtained at the expense
of generality, or have defaulted to heuristic methods applicable to almost
any possible situation.
In this thesis we present a hybrid method, combining a direct and
problem-specific approach with a system general enough to be applicable to
the majority of applications. Our method is based on local graph
transformations; if the data structure does not change dramatically, then
the parallelization should not need to either. By reflecting data
structure manipulations in a particular graph grammar formalism, we
can show deterministic bounds on the quality of the resulting division of
work. Thus, since our formalism is reasonably general and accommodates
many of the more common data structures (and also allows for considerable
variation), we have a general strategy for dealing with problems requiring
dynamic, pointer-based structures.
The utility of our technique is then established by a non-trivial
application of it to a realistic problem: grid generation for irregular
domains in the Control Volume Finite Element Method used in computational
fluid dynamics. We first illustrate an algorithm solving the problem, and
then show the use of our approach. Theoretical bounds on the partitioning
issues pertinent to parallelization are then given, and supported by
experimental measurements. We also compare our method to existing
heuristic methods to ensure our results are competitive. Our method turns
out to produce good quality results, with a number of distinct advantages
over other techniques, particularly when applied to dynamic situations.