## 4 Theory and Calculation
### Temporary Array Method
This method is generally applicable to other types of mappings as well. ```
set_from_size = source set's size of the original map \(original\_map\_dim\) = the dimension of the original map \(set\_to\_size\) = target set's size of the original map for\(n=0\) to set_from_size * original_map_dim do \(tmp\_incs[n]\gets 0\) endfor for\(n=0\) to set_from_size do  prepare regular access indices for \(OP\_READ\) and \(OP\_WRITE\) parameters  call kernel function, using the \(tmp\_incs\) array for \(OP\_INC\) parameters endfor for\(n=0\) to set_to_size do for all connection \(i\) of \(n\)do  apply the temporary increment from connection \(i\) on the final location of the data endfor endfor
```  
**Algorithm 2** Algorithm for applying the order of increments  
```
set_from_size = source set's size of the original map \(original\_map\_dim\) = the dimension of the original map \(set\_to\_size\) = target set's size of the original map for\(n=0\) to set_from_size * original_map_dim * \(tmp\_incs[n]\gets 0\) endfor for\(n=0\) to set_from_size * \(OP\_READ\) = prepare regular access indices for \(OP\_READ\) and \(OP\_WRITE\) parameters  call kernel function, using the \(tmp\_incs



### Reproducible Coloring

The temporary arrays method only works for increment-type operations, where increments can be stored separately. If a kernel not only increments a variable but also reads and rewrites it (OP_RW), then the kernel call from one edge must be executed, storing its result in the cell before another edge accessing that cell can be executed. Although OP2 still requires that the computation be associative, we cannot store the increments separately. This problem needs a solution to be able to really execute the kernel calls in a predefined fixed order and achieve reproducibility. To solve this issue, we can apply a regular coloring scheme with the following restriction, we are looking for an equivalence class of colorings where if the color of one element is smaller than that of another connected element in the case of one coloring, then it should also be the same in the case of any other coloring. We have three main approaches to solve this problem. An initial trivial solution is to choose the global index of the edge as the color. With this, we have as many colors as edges in any given subgraph, but we do not have multiple edges with the same color. This is useful for MPI-only parallelization, but not for a shared memory method. The advantage is that this trivial method can be solved without actually coloring the elements. We can just use the numbering from the global_ids for ordering sequential execution. This trivial execution schedule can be considered as a special case of colored execution and in fact they use the same generated code. Therefore, we refer to it as a coloring method. The second method is a non-distributed method, we apply a greedy coloring algorithm on the whole mesh in a single process as a pre-processing step and save the assigned colors in a file. When we rerun the application on multiple processes, we load and distribute the saved colors the same way as we distribute the mesh elements between the processes. With greedy coloring, we can generate a near-optimal number of colors, thus we have a high degree of parallelism. The drawback of this option is that we have to execute the pre-processing part in a single process. This carries the restriction that the whole mesh must be able to fit into the memory on a single node. The third method is a novel distributed coloring scheme, which does not suffer from this restriction. Distributed Reproducible Coloring Method

We base our method on an algorithm developed by [PERSON] et al. [57]. This original non-reproducible parallel method can be seen in Algorithm 3 between lines 7 and 40. We iterate through each element, calculate a local hash value and then compare it to its (as yet uncolored) neighbors' hash values. If the examined hash value is a local minimum or maximum in its neighborhood in a given iteration, then we can assign it a color.