Parallel Computation of Nearly Recurrent Components of Piecewise Constant Vector Fields

Abstract We describe a simple way to parallelize the algorithm for computing Morse decompositions and nearly recurrent sets for piecewise constant vector fields. In this chapter, we focus on the most computationally expensive component of the algorithm, namely refinement of the transition graph, which often takes up over 90% of the running time. The original implementation of the refinement algorithm refines nodes of the graph one at a time, in an arbitrary order. As a node is refined, arcs out of and into the resulting node are updated to preserve the key property of the graph, i.e. its ability to represent every trajectory of the vector field as a path in the graph. A significant portion of time is spent on updating and maintaining the integrity of the graph for each node that undergoes refinement. This approach is attractive and el-egant since it allows one to refine the nodes in arbitrary order and to an arbitrary depth while guaranteeing the correctness of the graph. However, its performance is suboptimal for most transition graph refinement scenarios, not only because of the cost of maintaining the integrity of the graph for each node refinement operation, but also because of uncontrollable memory access patterns. The method described in this chapter is tailored for the special case of nodes of the graph refined to the same depth, which is sufficient for most applications de-scribed in prior work. The idea is to stream through the set of arcs of the coarse graph to generate a compact bitmap based representation of the set of arcs of the refined graph. In the subsequent pass over the bitmap, the refined transition graph’s arcs are constructed from scratch, using only arc additions. The simplicity of the two passes makes them easy to parallelize and results in better cache performance. The bitmap building pass can be offloaded to the GPU to further increase the per-formance