## 4 Theory and Calculation
### Temporary Array Method
In our implementation we use [PERSON] 32 bit integer hash function [58]. This hash function is a custom, non-cryptographic function that operates on unsigned integers. It uses a combination of bitwise operations and arithmetic with specific constants to compute the hash of an input. The difficulty of applying this algorithm in a distributed graph comes from two sources. First, in each iteration of the previously described algorithm, we must know if the neighbor element already received a color, or not. Thus, we need to synchronize the assigned colored values on the borders of each subgraph (MPI partition). Secondly, it is difficult to figure out all the neighbors of an element on the border of a subgraph in a standard owner-computed model. We can see an example of this problem in Figure 6. Solid dots and continuous lines are the owned elements. In this example, we use an edge \(\rightarrow\) nodes mapping, thus we import one layer of halo elements (e.g., edge 7, 8, 9 on Process 0) so we can update the owned nodes from all attached edges (so far it is a standard owner compute model). However, to calculate the smallest hash value in a neighborhood, we also need to communicate edges even around the non-owned nodes (e.g., edge 0, 2, 5, 6 on Process 1). Our extension to distributed execution can also be applied to other iterative coloring techniques that use only local information (the algorithm is not sequential) and are deterministic even with different graph partitioning. The number of colors is not explicitly minimized. ```
1:create neighbor lists
2:global_done = 0
3:local_done = false
4:ifset_size == 0 then
5:local_done = true
6:endif
7:iteration = 0
8:low_color = 0
9:high_color = 1
10:while global_done < number of subgraphs do
11:if not local_done then
12:for all element e in from_set do
13:if e has no color then
14:calculate hash value of e in iteration i
15:is_min = true
16:is_max = true
17:for all neighbors n of e do
18:if n has no color then
19:calculate hash value of n in iteration i
20:if n's hash < = e's hash then
21:is_min = false
22:elseif n's hash > = e's hash then
23:is_max = false
24:endif
25:endif
26:endif
27:ifis_min then
28:give low_color as color of e
29:number of noncolored elements \(--=1\)
30:endif
31:if is_max then
32:give high_color as color of e
33:number of noncolored elements \(--=1\)
34:endif
35:endif
36:endif
37:endif
38:if number of noncolored elements == 0 then
39:local_done = true
40:endif
41:exchange halo color values
42:reduce local_done values into global_done
43:low_color += 2
44:high_color += 2
45:iteration += 1
46:endwhile
```

**Algorithm 3** Algorithm for reproducible coloring in a distributed graph

### Parallel Global Reduction

Global reductions are another source of non-reproducibility in MPI applications. This operation is commonly conducted by performing a local sum on each process, then calling MPI_Reduce, however, this assumes associativity. If we use different numbers of MPI processes, then we would sum different elements and even a different number of elements locally, which again can produce different results. To solve this issue, we introduced another temporary storage. If a kernel performs an increment reduction, then we give a temporary storage point to store the increment for the result of each element. Then, in each MPI process, we reduce these increments reproducibly by using the ReproBLAS library. First, we create a local ReproBLAS's double_binned variable for every MPI process, then we use binnedBLAS_dbdsum to collect those into the local_sum. After that, we use reproBLAS's method to call an MPI_Allreduce with the binnedMPI_DBDBADD operator. Finally, we convert the result back to a regular double precision variable and return it. ### Reproducible Codegeneration with OP2

Using OP2's source-to-source translator, a user can easily generate reproducible code from an app that already has an implementation using OP2. A few flags are responsible for controlling the mechanisms that allow reproducible code to be generated.