# Parallel fuzzy minimals on GPU
## 3 Parallel FM
### Parallel FM on GPU
In Figure 9a-d, the prototypes found in tests with one, two, four and eight partitions are shown, respectively. From a clustering standpoint, the differences between prototypes are minimal for three main reasons (high volume of objects, data distribution across partitions and accuracy of our FM parallelization). Figure 8: Dendrograms for the complete schools dataset. \begin{table}
\begin{tabular}{c c c c} \hline
**Execution** & **Partitions** & **Time** & **MPI Comm.** \\ \hline Sequential & 1 & 52.683 s & – \\ \hline PFMGPU & 1 & 20.596 s & – \\ \hline PFMGPU & 2 & 5.468 s & – \\ \hline PFMGPU & 4 & 1.512 s & – \\ \hline PFMGPU & 8 & 0.973 s & – \\ \hline PFMMPI & 1 & 52.720 s & 0.0 s \\ \hline PFMMPI & 2 & 13.739 s & 0.039351 s \\ \hline PFMMPI & 4 & 3.667 s & 0.121386 s \\ \hline PFMMPI & 8 & 1.203 s & 0.249457 s \\ \hline \end{tabular}
\end{table} 
Table 3: Runtimes for the partial schools dataset. Figure 7: Geographical coordinates of 40,646 USA schools (complete schools dataset). As in Section 4.2, the results of our simulation are shown in Table 4. As in previous benchmarks, parallel executions achieved their highest performance with eight partitions (circa 60 times faster than the serial execution). From one to four partitions, PFMGPU was consistently faster than PFMMPI, but the execution with eight partitions gave similar runtimes for both implementations. This depends on the fact that our GPU has only four SMs. Thus, our performance decreases whenever we exceed the available resources. Moreover, the time that PFMMPI spent on communication increased at a lower ratio, which balances the latency overhead. ### Timing analysis

A comparison with other clustering algorithms may not produce realistic or significant results. In fact, the number of executions and thus the total runtime depend on parameters provided by the user. Accordingly, a practical analysis would involve the parallel implementation of the FM algorithm introduced in [25]. However, the authors did not provide the implementation, making impossible any comparison. Consequently our analysis is constrained to the technology and methods shown in in [25]. We can assume that the processor used was an Intel Core i5 clocked at 1.6 Ghz. There are several models for this 4\({}^{th}\) generation processor. According to the PassMark benchmarks website, the slowest processor from that generation has a rate of 2256, which is about four times slower than the i7-3770 processor used in our MPI implementation. Moreover, the speed was about 1.27 ms/object with 8 partitions, which is much slower than the 0.11 ms/object achieved in our MPI implementation. Therefore, even if the speed is adjusted with the speed of the processors used in each simulation, our approach is at least three times faster. Another \begin{table}
\begin{tabular}{c c c c} \hline
**Execution** & **Partitions** & **Time** & **MPI Comm.** \\ \hline Sequential & 1 & 248.284 s & – \\ \hline PFMGPU & 1 & 133.945 s & – \\ \hline PFMGPU & 2 & 40.166 s & – \\ \hline PFMGPU & 4 & 8.963 s & – \\ \hline PFMGPU & 8 & 4.724 s & – \\ \hline PFMMPI & 1 & 248.447 & 0 \\ \hline PFMMPI & 2 & 62.510 s & 0.072839 s \\ \hline PFMMPI & 4 & 14.974 s & 0.220595 s \\ \hline PFMMPI & 8 & 4.323 s & 0.497454 s \\ \hline \end{tabular}
\end{table} 
Table 4: Runtimes for the complete schools dataset. Figure 9: Clusters found for the complete schools dataset. possible solution is that we deal with the efficiency of our parallel implementations by scalability and speedups. These results are shown in Figure 10.

We see at once that both implementations are faster than the standard (and single process) implementation. In particular, we found that a speedup that generally quadruples when the number of partitions doubles. This depends on the hardware in use. Indeed, for the PFMGPU implementation we have that each partition is run in a different GPU SM, up to four partitions, and each SM is composed by hundreds of computing cores.