Data parallel solution strategies for irregular problems

Irregular problems arise in many areas of computational physics and other scientific applications. A parallel solution for such a problem requires a suitable mapping strategy to map the irregular problem to the interconnection topology of the parallel machine so that communication overhead is as low as possible, there is proper load balancing among the processors and, locality of the problem graph is preserved. As a result, there is sufficient speedup in computation. In this thesis, we discuss some general strategies and associated results in data-parallel solutions of such problems. Some of these strategies use the geometrical co-ordinates of the nodes of the problem graph for partitioning them to the processors. In certain situations, geometrical co-ordinates alone may not capture the topology of the problem graph. To handle this, we design a number of schemes for assigning topological co-ordinates to nodes, and then use the same mapping strategies for partitioning nodes to processors based on their topological co-ordinates. We test our strategies on experimental problem graphs and discuss the results