A massively parallel Eikonal solver on unstructured meshes

The FIM is based on local solvers for (3) in each tetrahedron. An upwind scheme is used to compute an unknown solution \(\phi _4\), assuming that the given values \(\phi _1\), \(\phi _2\), and \(\phi _3\) comply with the causality property of the Eikonal solutions [8]. Since we assume a constant speed function within each tetrahedron the arrival time \(\phi _4\) is determined by the time associated with that segment from \(x_5\) to \(x_4\) that minimizes the solution value at \(x_4\), see Fig. 1. Therefore we have to determine the coordinates of that auxiliary point \(x_5\) where the wave-front intersects first the plane defined by the vertices \(x_1\), \(x_2\) and \(x_3\). If \(x_5\) is located outside the surface triangle of the three nodes then \(x_5\) is projected to the nearest boundary of this surface triangle, e.g., to edge \((x_1,x_3)\), and \(\phi _4\) is calculated via a wave propagation in the triangle \((x_1, x_3, x_4)\).

Based on Fermat’s principle [9] the goal is to find locally that location of \(x_5\) which minimizes the travel time from \(x_5\) to \(x_4\), i.e.,We interpret \(x_5\) as the center of mass of the surface and express it in barycentric coordinates as \(x_5 = \lambda _1 x_1 + \lambda _2 x_2 + (1-\lambda _1 - \lambda _2) x_3\). \(\phi _5\) is rewritten in the same way. If we plug \(\phi _5\) into equation (4) then we get the following expression for \(\phi _4\):In order to minimize \(\phi _4\), we have to calculate the partial derivatives of (5) with respect to \(\lambda _1\), \(\lambda _2\) and equate them to zero which results in a non-linear system of equations.

Kirby and Whitaker [1] built a low memory footprint solver by reducing the computations and memory storage based on the observation that \(e_{5,4}\) can be expressed as:with \(\lambda = [\lambda _1 ~ \lambda _2 ~ 1]^T\). Hence they obtain the substitution into (5)with the symmetric matrixFinally, the optimization problem (5) transforms into the non-linear system of equations for \(\lambda _1\) and \(\lambda _2\):Solving equations (9) needs the symmetric matrix \(M'\) requiring temporarily only six floats per tetrahedron. Additionally all the coordinates and the symmetric velocity matrix M (\(4*3 + 6\) floats) have to be transferred from main memory with a (GPU) non-coalesced memory pattern.

In order to reduce the non-coalesced memory accesses whenever system (9) has to be solved in a tetrahedron we precompute all possible 18 inner products, listed in Table 1.

This approach does not reduce the memory footprint significantly (we still have to transfer 18 floats from main memory) but we achieve a reduction of the non-coalesced accesses to global memory. No computation of the scalar products is done at all during the wave front calculations now. Instead only the access of the needed values of \(M'\)s is considered. All the accesses to matrix M and the edges are avoided, reducing in this way also the computations and the global memory access needed for these computations. The strike-through elements in Table 1 have no physical meaning in the tetrahedron and therefore these entries are never stored. Those entries needed for solving (9) in the reference configuration to determine \(\phi _4\), see also Fig. 1, are marked in blue.

The challenge consist in accessing the needed 6 inner products for \(M'\) from the the 18 precomputed entries in Table 1 without branched code whenever we face a non-reference configuration, e.g., \(\phi _i\) is the unknown value with \(i \in \{1,2,3\}\). The needed tools are described in the remaining subsection.

The possibility to reduce the memory footprint from 18 to 6 floats originates from the fact that \(\langle \mathbf {e}_{k,s}, \mathbf {e}_{s,\ell } \rangle _{M^{\tau }}\) (\(k\ne \ell \)) represents an angle of a surface triangle whereas \(\langle \mathbf {e}_{k,s}, \mathbf {e}_{k,s} \rangle _{M^{\tau }}\) represents the length of an edge in the M-metric which are also the products in the main diagonal. Basic geometry as well as vector arithmetics yield to the conclusion that the angle information can be expressed by the combination of three edge lengths. Therefore we only have to precompute the 6 edge lengths of one tetrahedron and compute on-the-fly only the 3 needed angle data therein instead of the potential 12 angle data. This finally reduces the memory footprint per tetrahedron to 6 numbers.

The determination of the involved edges and the sign changes are presented in detail in “Appendix B”. We finally achieve the generalized formulawith \(s^{\text {Gray}}= \textsc {xor}(k^{\text {Gray}},\ell ^{\text {Gray}})\) and \(k^{\text {Gray}}\ne \ell ^{\text {Gray}}\) are the Gray-code edge numbers from Table 2. The sign has to be calculated only for the off-diagonal elements in Table 1 as follows:Finally, we have to store only the diagonal part \(e_k^TMe_k\) as in Table 4 and all mixed elements are computed via formula (11). The mapping system remains the same. You only address 3 diagonal products out of 6 now and compute the 3 mixed products needed. In the reference case when we are computing for \(x_4\) the resulting edge numbers from the mapping system are (5, 2, 1). The reduced memory footprint approach has to access now only the three products referenced from edge numbers (1, 1), (2, 2) and (5, 5). These are the products marked in blue in Table 4. The other 3 needed products for the mixed edge numbers, respectively (1, 2), (1, 5) and (2, 5) which reference exactly the off-diagonal products in blue in Table 1, are calculated based on formula (11).

The memory footprint reduction is obvious. Instead of precomputing and storing all the 18 scalar products in Table 1, only the 6 scalar products of the main diagonal are precomputed and stored as in Table 4.

The marching and sweeping versions of the Eikonal solver restrict updates to a moving wave front which covers just a fraction of the domain. In Algorithm 3 the “for all” loop over the elements of the active set can be run in parallel. The efficiency of the resulting code depends on the way this loop can be executed. In a shared memory computing system with task based parallelism, this loop can be partitioned dynamically, as described in Algorithm 5.

Using many-core processors and many threads, programming paradigms like OpenMP allow this kind of parallelism. The efficiency depends on the size of the active set, which corresponds to the length of the wave front which changes during computation. Starting with a single excitation point, the Eikonal solver will start a wave with growing wave front size, until the wave reaches the boundary and is cut off, see Fig. 2. Furthermore, the amount of work per set element and the general memory layout play an important role.

Therefore, the multi threaded version of the algorithm is derived by just partitioning the active list for each iteration and assigning the work of each sublist to one thread. Each thread is updating its own active sublist but the solution is synchronized against the solution vector \(\Phi \) where all the values for each node are kept. In practice, we simply divide the active list arbitrarily into N sublists, assign the sublists to the N threads. We choose N to be the number of virtual CPU cores in multi-threading.

We have a very short convergence time of the algorithm and good quality results, see Fig. 2 wherein the wave propagation looks very smooth.

A GPU version of the Eikonal solver can be derived in the same way. An accelerator program, e.g. in CUDA for Nvidia GPUs is executed on the host. Whenever a large parallel loop occurs, a compute kernel on the GPU is launched including some data copy to and from the GPU. Host code offloads the computational tasks and continues, when all GPU processors have successfully executed the compute kernel code. This way the “for all” loop in Algorithm 3 is split into a number of kernels, which have to be executed successively. Efficiency depends on the size of the active set, the amount of work per element and memory considerations.

When designing an algorithm that will be used in a streaming unit such as a GPU, it is very important to optimize for throughput and not for latency. Together with the concept of coalesced memory access pattern we designed our algorithm based on one critical point: allowing data redundancy in order to achieve good coalesced memory access, throughput and occupancy.

The main idea of the Eikonal update scheme is to find the solution of one node calculating for all the one-ring tetrahedra. It means that in the general case one thread is supposed to solve for one node by doing the computations and solving for all its neighboring tetrahedra. Unfortunately, we would have non–coalesced access pattern, smaller number of threads (low level of parallelism), low throughput and a poor occupancy. A better solution consists in calculating a priori all the neighboring tetrahedra indices for each node in the active list, store them in a global array and then assign each element (tetrahedra) to one thread. Of course the information will be redundant as shown in Fig. 4 on the last array, but we trade in memory to gain in performance. In this way we achieve a better coalesced memory access, more threads to run (increased parallelism) and a better bandwidth which are the three most important concepts for a fast GPU algorithm.

The loop over all vertices is restricted to the vertices that belong to the current processor. The new set M is assembled as the union of the local sets. The local \(\Phi \) values are exchanged at the end of the loop. This implements the communication. The results may differ from the sequential algorithm, since the order of computation is different and the \(\phi \) updates are delayed. This may result in a slightly larger iteration count.

The main challenge of a static decomposition is load balancing. Since the wave front moves, the amount of elements per sub-domain varies largely. In the beginning and at the very end of the computation, many sub-domains will have an empty active set. A way to overcome this is a different mapping of elements to a processor. Several smaller sub-domains may increase the chance of a processor to have a non-empty active set.

In order to reduce communication even further, we do not update \(\Phi \) and M in the loop at all. We consider Algorithm 3 as a black box able to solve the local problem.

Once we have a solution, we have to update the boundary values on \(\partial \Omega _i\). In case of any changes, we have to run the local Eikonal solvers on \(\Omega _i\) again. Now the number of sweeps is slightly larger than in the sequential case. In the case of a GPU this scheme can be mapped to single GPU cores (CUDA, streaming multiprocessors (SM)). A single kernel is able to solve the Eikonal equation on a small sub-domain. This allows for memory optimizations like the use of “shared memory” local to an SM for the storage of \(\Phi \), local matrices etc. Furthermore, the amount of host interaction and synchronization is limited.

We use two different strategies to distribute the workload of the kernels to the available blocks in CUDA. Our first approach consist in mapping the work of a sub-domain into different blocks or SMs on the GPU where one thread can process for only one tetrahedron as explained in Sect. 5.2.2. This allows the shared memory of all blocks solving for a certain sub-domain to be used from the local sub-domain solver. It means more data are going to fit into the shared memory since the blocks share the load. The other approach is one block computes one sub-domain where the shared memory is limited to the shared memory of the block but the threads have more work to do increasing in this way the granularity. Every scan and scatter or any other kernel which prepares the data for the solution kernel computes independently for each domain. The only difference between the two versions is in the way the workload of the main kernel is distributed. Since the main difficulty of the static decomposition is the load balancing because the wavefront moves and many domains remain idle during execution, empty active sets, then distributing the load not only in one block but on many blocks increases the number of utilized blocks and multiprocessor units (SM) on the GPU. This has also the benefit that the wave front velocity information can be stored into the shared memory since more shared memory is available now compared to the model one block one sub-domain.

The advantage of the other model, where one block is responsible for one domain is the granularity or the number of elements processed by one thread. In this model one thread has more work to do and with the right type of access it can increase the efficiency especially if that fits into the registers of the thread. Access optimization of this feature is a future work. One idea is to use the CUB block load primitive from CUB library [20] which provides collective data movement methods for loading a linear segment of items from memory into a blocked arrangement across a CUDA thread block.

The other advantage compared to the first approach is the almost complete reduction of host synchronization. This results from the possibility to synchronize within each block for each sub-domain since the computation is independent from each other. In this case we do not need any host synchronization for each kernel as in the first approach where we had to make sure that all the blocks ended execution before continuing with the next kernel. This was also possible by using the dynamic memory allocation in CUDA. The only remaining synchronize is needed to check the termination condition.

In Table 5 we compare between our new implementation including the Gray-code method and our old implementation without that. We achieved an acceleration by \(35\%\) for the OpenMP implementation and by \(50\%\) in the CUDA implementation by using the local Gray-code numbering of edges to reduce the memory footprint.

A profiling of the CPU performance (Intel’s Vtune Amplifier) shows that the number of loads has been reduced to \(70\%\) and the number of stores dropped to \(40\%\) in the Gray-code version. The last level cache (LLC) miss count has been reduced to \(84\%\). The significant reduction in stores is caused by avoiding many local temporary variables from the original approach. The reduction of non-coalesced memory accesses is documented by the reduced number of loads and the lower LLC miss counts.

We see these improvements even more clearly with the CUDA implementation wherein we get an even larger performance improvement caused by avoiding expensive non-coalesced memory accesses. The reduced number of non-coalesced memory accesses to global memory is the same as on CPU but the GPU profits more from that. We compared the profiling results of both CUDA versions (Nvidia’s Visual Profiler nvvp). The old implementation had a high local memory overhead which accounted for \(54\%\) of total memory traffic which indicated excessive register spilling. After implementing the Gray-code method that problem disappeared and the number of register spills decreased significantly. We have only 60 bytes spill stores and 84 bytes spill loads in the new main kernel in contrast to the old kernel with 352 bytes spill stores and 472 bytes spill loads. The L2 cache utilization is maximized in the new kernel. The L2-bandwidth is doubled and achieves now 952.08 GB/s, compared to the version with only 456.103 GB/s. The number of loads and stores is also decreased for the L2 cache as well as for the device memory. For this reason the local memory overhead is also decreased and the achieved device memory bandwidth is increased to above \(90\%\) compared to the old version where the achieved memory bandwidth was below \(60\%\) indicating latency issues. And lastly the divergent execution also dropped and improved the warp execution efficiency from 75 to \(80\%\).

We tested our code also on Intel Phi (KNL) server with 64 physical cores, 1.3GHz for both meshes. The OpenMP implementation scales almost linearly until 64 threads, see Fig. 8. Then the performance to drops because of the hyper-threading. We achieve similar scaling results for the larger mesh for which the algorithm converges in 5.6 s using 256 threads. This is a comparable result with the CUDA implementation where we achieved a convergence time of 5.16 s.

Let us compare the numerical results between the first and the second DD approaches, and with the non-DD approach. We focus especially on hardware limitations observed on the GTX 1080 GPU and how they could be overcome.

Table 6 compares the run times between both DD versions for the coarser mesh with \(3\cdot 10^6\) tetrahedra. There are no global memory limitations for running the smaller example on the GTX 1080 with 8GB global memory and 4KB shared memory per block. All data fit into the global memory by preallocation. Therefore, we do not have to reallocate GPU-memory in each iteration as in the second DD approach. We observe that the second DD approach scales better with the increased number of sub-domains until we get 0.51 s convergence time for 320 sub-domains. It is already faster than the version without DD where the best time we achieved is 0.73 for the coarser mesh as shown in Table 5. The reason consists in the DD versions use the block scan implemented by the CUB library instead of the device scan primitive as in [21]. Besides the block scan we use block load and block store from the CUB library [20] for loading a linear segment of items from memory into a blocked arrangement across a CUDA thread block. The efficiency is increased by the increased granularity \(ITEMS\_PER\_THREAD\). Performance is also increased until the additional register pressure or shared memory allocation size causes SM occupancy to fall too low.

The block scan computes a parallel prefix sum/scan of items partitioned across a block. If we decompose the domain in sub-domains small enough such that block scan can use the available shared memory and the register pressure does not affect the occupancy then this method fits to our DD approaches. Additionally, the block scan can be called within a CUDA kernel and so we incorporated it into the one big kernel for the second DD approach. A device scan would require a separate kernel.

The drawback consists in the shared memory limitation. The block scan requires shared memory and the shared memory size limits the number of sub-domains. A small number of sub-domains means larger sub-domains for the same mesh and for this reason the data to be scanned for those sub-domains do not fit anymore into the shared memory. Hence we start the testing with 2700 sub-domains for the larger mesh and 74 sub-domains for the coarser mesh. Anyway the idea is always to increase the number of sub-domains as discussed in Sect. 6.3.1 since it improves the load balancing and therefore this limitation is not relevant for our code.

The shared memory usage together with the consecutive items per thread used by the block scan allows us to conclude that the block scan is the reason that the DD approaches are faster. We would like to emphasize that using the block scan is only possible because of the DD approach. One can notice from the convergence results for the finer mesh in Table 7 that the second DD approach is not scaling any more. This is caused by the limited global memory of a single GPU such as GTX 1080 in our case. While the global memory was large enough in the coarser example to allow the preallocation of the memory space needed for each sub-domain during the algorithm execution, it didn’t work out anymore for the larger example. As a consequence, the coarser example scales with the increased number of sub-domains as expected. The GPU cannot provide enough memory to preallocate the needed space for each sub-domain in the larger example. In order to get satisfactory results we still preallocate the needed space for each sub-domain but now we do it for each iteration and we free that memory once the blocks terminates. This is done only for the active sub-domains and no reallocation happens during the kernel execution. In this way the global memory suffices and we managed to run the DD approach within a single GPU. The DD version now is just 1 s slower than the version without DD. Now we compare results of Table 7 with the results shown in Table 5 for the CUDA implementation with Gray-code. With the increased number of sub-domains the dynamic allocation is also increased becoming in this way the limiting factor of the scalability. Without these limitation the algorithm would scale very well as it does for the coarser example and of course it would be faster than the non-DD version.

In order to check the scalability of our DD approaches on different GPUs we tested on an Nvidia Titan X Pascal card with 24 multiprocessors (SMs), 4 more than a GTX 1080 card and 4GB more global memory but still not enough to preallocate. The results we get for the mesh using 2700 sub-domains are approximately \(20\%\) faster than the results on a GTX 1080 for the first approach and \(13\%\) for the second approach. Respectively for the first DD approach we get a convergence time of 4.68 s and for the second approach we get a convergence time of 5.96 s. It scales worse for the second approach because of scalability issue we have on the DD approaches for the larger mesh but that affects more the second approach as explained above.