# Parallel Computing of Edwards--Anderson Model
## 2 Algorithm
``` for(introw=1;row<Ly;row++) { for(intcol=0;col<n_exch;col++) { for(intthrd_num=0;thrd_num<thrd_amount;thrd_num++) {calc_E(min_E_array,col,Lx);} } interval_amount_of_thrds=2,interval_amount_of_thrds_div_2=1,amount_of_bunchs_of_connected_thrds=N_thrd/2; for(intcol=n_exch;col<Lx;col++) { //mmswapp....===v for(intthrd_num_out=0;thrd_num_out<amount_of_bunchs_of_connected_thrds; {thrd_num_out++} { for(intthrd_num_in=0;thrd_num_in<interval_amount_of_thrds+thrd_num_in,thrd_num_2; {thrd_num_in++} { intrd_num_1+thrd_num_out+interval_amount_of_thrds+thrd_num_in,thrd_num_2= {shwap_mem(min_E_array,thrd_num_1,thrd_num_2);//!! move \"in the opposite direction\", decreasing the subsystem at each step and starting from the subsystem equal to the initial system. ## 3 Performance

In Table 1 the performance parameters of the parallel algorithm of ground state search for 20 \(\times\) 20, 25 \(\times\) 25, 30 \(\times\) 30, 35 \(\times\) 35 lattices are given. Parallelisation was performed for 64 threads (threads). The time relations are also given in the table. It can be seen that the times grow exponentially with the increasing linear size of the square lattice. Knowing the time ratios for the 35 \(\times\) 35 and 40 \(\times\) 40 lattices, equal to 43.07, we can estimate the computation time of the 40 \(\times\) 40 lattice. It will be approximately 5 h.

Further Table 2 shows the performance data of the lattice calculation algorithm with the fixed side length \(Lx=35\) and different side lengths \(Ly\). Parallelisation was performed on 64 threads. The table shows that the time grows linearly with the increasing length of one side of the lattice. To estimate the effectiveness of the parallelisation scheme, a series of calculations were carried out for 1, 2, 4, 8, 16, 32 and 64 threads. 25 \(\times\) 25 and 28 \(\times\) 28 lattices were considered. The data are given in Figure 1:9

One can roughly accept that the running time depends on the size \(Lx\) as \(t\sim 2^{Lx}/N_{html}\) for \(N_{html}\) threads. In this case we neglect the data transfer time. Thus, if \(N_{html}\) increased by 2, the computation time will be reduced by 2. We can see from Table 3 that this ratio is more or less satisfied. Therefore, in our case the computational complexity is \(2^{Lx}\) (NP-hard). \begin{table}
\begin{tabular}{c c c c} \hline
**Calc. Number \(i\)** & **Lattice** & **Time \(t_{i}\)** & **Ratio of \(t_{i}\) to \(t_{i-1}\)** & **Memory Size** \\ \hline
1 & 20 \(\times\) 20 & 81 ms & 384 kb \\
2 & 25 \(\times\) 25 & 4 s 282 ms & 52.86 & 12 Mb \\
3 & 30 \(\times\) 30 & 3 min 15 s & 48.75 & 384 Mb \\
4 & 35 \(\times\) 35 & 2 h 20 min & 43.07 & 12 Gb \\ \hline \end{tabular}
\end{table} 
Table 1: Performance of the parallel algorithm for fbc spin lattice calculation for 20 \(\times\) 20, 25 \(\times\) 25, 30 \(\times\) 30, 35 \(\times\) 35 lattices on 64 threads. \begin{table}
\begin{tabular}{c c c c c} \hline
**Calc. Number \(i\)** & \(Ly\) & **Ratio of \(Ly_{i}\) to \(Ly_{i-1}\)** & **Time \(t_{i}\)** & **Ratio of \(t_{i}\) to \(t_{i-1}\)** \\ \hline
1 & 35 & & 2.33 h & \\
2 & 50 & 1.4 & 3.46 h & 1.49 \\
3 & 100 & 2.0 & 6.89 h & 1.99 \\
4 & 250 & 2.5 & 17.17 h & 2.49 \\
5 & 500 & 2.0 & 35.00 h & 2.03 \\ \hline \end{tabular}
\end{table} 
Table 2: Performance of the parallel algorithm of fbc spin lattice calculation for 35 \(\times\) 35, 50 \(\times\) 35, 100 \(\times\) 35, 250 \(\times\) 35, 500 \(\times\) 35 lattices on 64 threads. \begin{table}
\begin{tabular}{c c c c c} \hline
**Calc. Number \(i\)** & **Amount of Threads** & \(t_{i}\) & **Ratio of \(t_{i}\) to \(t_{i-1}\)** & **Time \(t_{i}\)** & **Ratio of \(t_{i}\) to \(t_{i-1}\)** \\ \hline
1 & 1 & 2 min 3 s & 20 min 5 s & \\
2 & 2 & 1 min 55 s & 1.07 & 19 min 37 s & 1.07 \\
3 & 4 & 59 s & 1.94 & 9 min 39 s & 2.03 \\
4 & 8 & 29 s & 2.00 & 4 min 50 s & 1.99 \\
5 & 16 & 17 s & 1.96 & 2 min 47 s & 1.73 \\
6 & 32 & 9 s & 2.0 & 1 min 34 s & 1.78 \\
7 & 64 & 5 s & 1.7 & 51 s & 1.84 \\ \hline \end{tabular}
\end{table}