  The fast marching method is a widely used numerical method for solving the
Eikonal equation arising from a variety of scientific and engineering fields.
It is long deemed inherently sequential and an efficient parallel algorithm
applicable to large-scale practical applications is not available in the
literature. In this study, we present a highly scalable massively parallel
implementation of the fast marching method using a domain decomposition
approach. Central to this algorithm is a novel restarted narrow band approach
that coordinates the frequency of communications and the amount of computations
extra to a sequential run for achieving an unprecedented parallel performance.
Within each restart, the narrow band fast marching method is executed; simple
synchronous local exchanges and global reductions are adopted for communicating
updated data in the overlapping regions between neighboring subdomains and
getting the latest front status, respectively. The independence of front
characteristics is exploited through special data structures and augmented
status tags to extract the masked parallelism within the fast marching method.
The efficiency, flexibility, and applicability of the parallel algorithm are
demonstrated through several examples. These problems are extensively tested on
six grids with up to 1 billion points using different numbers of processes
ranging from 1 to 65536. Remarkable parallel speedups are achieved using tens
of thousands of processes. Detailed pseudo-codes for both the sequential and
parallel algorithms are provided to illustrate the simplicity of the parallel
implementation and its similarity to the sequential narrow band fast marching
algorithm.
