A parallel solution strategy for irregular, dynamic problems

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