Josef Weinbub Dipl.-Ing. Dr.techn. Publications

Simulating an expanding front is a fundamental step in many computational science and engineering applications, such as image segmentation, brain connectivity mapping, medical tomography, seismic wave propagation, geological folds, semiconductor process simulation, or computational geometry. In general, an expanding front originating from a start position is described by its first time of arrival to the points of a domain. This problem can be described by solving the Eikonal equation.
The most widely used method for solving the Eikonal equation is the fast marching method. This method is inherently sequential and attempts to parallelize it have been unsatisfactory. Other approaches for solving the Eikonal equation include the Fast Sweeping Method (FSM) and the Fast Iterative Method (FIM). Both methods support parallel execution; FIM supports fine-grained parallelism, thus inherently offering greater potential for parallelism over the entire spectrum than the coarse-grained parallelism of FSM. Although FIM provides superior parallel performance to other available methods (in most cases), its performance is problem dependent. Complex speed functions tend to significantly increase the solution time.
To overcome this shortcoming, the Semi-Ordered Fast Iterative (SOFI) method has been developed. SOFI is based on both the FIM as well as on the Two-Queue method, and enforces an ordering to get the iterative behavior closer to front tracking methods, i.e., fast marching and wavefront tracking methods. This in turn offers increased stability when faced with intricate speed functions. Front tracking methods inherently favor sequential execution, therefore parallel scalability is expected to be inferior to that of the FIM. Rather than computing all active nodes in parallel (as in FIM), the SOFI method pauses some of the awaiting updates according to a cutoff criterion based on statistical in-situ analysis of the solution values. Therefore, the computational resources are not fully used, limiting the potential for parallel speedup relative to the FIM. However, SOFI offers excellent performance for two-dimensional, sequential problems. In turn, the Two-Queue method also pauses nodes to get a partially ordered technique, but it is only applicable to isotropic problem formulations, whereas the SOFI method additionally supports anisotropic problems.
A shared-memory parallel version of the SOFI method has been investigated based on OpenMP. Fig. 1. compares the achieved parallel efficiency relative to a reference FIM implementation, also parallelized with OpenMP. An excellent 60% efficiency is achieved for multiple input sources (i.e., points which describe the initial surface from which the front starts propagating) using a computationally demanding speed function. Future work will further focus on parallel efficiency as well as applying the method to real-world problems in the area of semiconductor process simulation.

Fig. 1: Parallel efficiency of the parallelized SOFI method (green) in comparison to a reference FIM implementation (black) using a computational demanding speed function. Single and multiple input sources, describing the initial front, are compared, showing that parallel SOFI works reasonable well for multiple input sources (around 60% efficiency for 12 threads).