Georgios Diamantopoulos was born in Athens,Greece in 1988. He holds a degree in applied mathematics from the University of Crete, Greece and a Master's degree in computational engineering from the Friedrich-Alexander University of Erlangen-Nuremberg, Germany. He joined the Institute for Microelectronics on January 2016 as a research assistant. He is researching high performance numerical approaches for Technology CAD within the scope of the Christian Doppler Laboratory for High Performance TCAD.
Parallel Fast Marching Method for Redistancing Problems
A common task in process TCAD is the simulation of an interface evolution over time. One of the steps in the simulation is the re-calculation of the distance from the interface. After performing one (or more) advection step(s) on the interface, the distance from the interface is distorted. A re-calculation of the distance is therefore necessary in order to maintain the signed-distance property of the field.
This re-distancing process (i.e. re-calculation of the distance) can be treated as an expanding front problem with a unit speed, and it can be described by the Eikonal equation. This problem not only occurs in microelectronics but also in other fields, such as computer vision, computational fluid dynamics, computational geometry, material science, etc.
A widely used method for the solution of the Eikonal equation is the fast marching method (FMM). It is a non-iterative, highly accurate method. However, the sequential nature of the algorithm is not conducive to a straightforward parallelization. Many parallelization approaches have been put forth so far, but they do not provide a reasonable parallel efficiency.
Recently, a promising new approach based on an overlapping domain decomposition technique has been introduced, providing a scalable, widely applicable parallel algorithm. However, investigations so far have been limited to synthetic point-based problem cases that do not cover the much more challenging cases of interface re-distancing, in which, instead of simplistic point sets, challenging interface geometries are processed.
We filled this gap by evaluating a shared-memory implementation of the parallel FMM for interfaces inspired by practical problems and for different domain decomposition scenarios. One of these interfaces is the step problem displayed in Fig. 1. The parallel efficiency and run-time performance was examined on a dual-socket Ivy Bridge-EP compute node. As can be observed in Fig. 2, this method shows good scalability for the case where the interface is (close to) evenly partitioned among the sub-domains. On the other hand, poor performance has been observed in the case of uneven domain decomposition. Our analyses outline the feasibility limits of a shared-memory parallel FMM.
Fig. 1: Planar surface in XY with a step in the domain [-0.96,0.96]3. The interface is in grey. The numerical solution is displayed: High values are represented with red hues and low values with blue hues.
Fig. 2: Parallel speedup for the step case with various partitions. The speedup is good for the decomposition in the y-direction but poor for the xy-direction and even poorer for the x-direction. Decomposing the domain in the y-direction results in a load-balanced domain decomposition. On the other hand, a domain decomposition in the x-direction results in an inhomogeneous decomposition, which necessitates additional calculations in order to reach the solution for the parallel algorithm.