# Parallel fuzzy minimals on GPU
## 3 Parallel FM
### Parallel FM on GPU
\begin{table}
\begin{tabular}{c c c} \hline
**Execution** & **Number of Partitions** & **Coordinates of the Prototypes** \\ \hline \multirow{2}{*}{Sequential} & \multirow{2}{*}{1} & \((407.84,395.64)\), \\  & & \((393.62,1084.59)\), \\  & & \((1125.10,749.52)\) \\ \hline \multirow{2}{*}{Parallel} & \multirow{2}{*}{1} & \((407.84,395.64)\), \\  & & \((393.62,1084.59)\), \\  & & \((1125.10,749.52)\) \\ \hline \multirow{2}{*}{Parallel} & \multirow{2}{*}{2} & \((396.85,394.44)\), \\  & & \((406.28,1098.51)\), \\  & & \((1127.12,759.52)\) \\ \hline \multirow{2}{*}{Parallel} & \multirow{2}{*}{4} & \((359.52,409.88)\), \\  & & \((391.70,1099.75)\), \\  & & \((1124.16,761.82)\) \\ \hline \multirow{2}{*}{Parallel} & \multirow{2}{*}{8} & \((361.11,403.26)\), \\  & & \((350.18,1105.10)\), \\  & & \((1111.99,749.87)\) \\ \hline \end{tabular}
\end{table} 
Table 1: Prototypes found for the ellipsis benchmark. \begin{table}
\begin{tabular}{c c c c} \hline
**Execution** & **Partitions** & **Time** & **MPI Comm.** \\ \hline Sequential & 1 & 170.596 s & – \\ \hline PFMGPU & 1 & 50.330 s & – \\ \hline PFMGPU & 2 & 10.282 s & – \\ \hline PFMGPU & 4 & 3.582 s & – \\ \hline PFMGPU & 8 & 1.706 s & – \\ \hline PFMMPI & 1 & 170.664 s & 0.0 s \\ \hline PFMMPI & 2 & 47.395 s & 0.01763 s \\ \hline PFMMPI & 4 & 11.341 s & 0.04424 s \\ \hline PFMMPI & 8 & 3.020 s & 0.10290 s \\ \hline \end{tabular}
\end{table} 
Table 2: Runtimes for the ellipsis benchmark. Figure 5a-c shows the dendrograms for hierarchical clustering of prototypes generated with two, four and eight partitions, respectively. The coordinates of each cluster prototype are represented with respect to the \(x\)-axis. Obviously, PFMGPU and PFMMPI executions give the same dendrograms. However, the dendrograms are slightly different from each other due to data distribution across partitions. Thus, the prototypes found in each partition diverge at a certain degree. Moreover, we see at once that all executions found five prototypes at the dashed level. All prototypes found by executions with one, two, four and eight partitions are shown in Figure 6a-d, respectively. We note that the prototypes found by different executions appear to be the same. However, a more detailed analysis turns out that prototypes are slightly different. Accordingly, a minimal variation between executions with different partitions provide a high degree of precision. In Table 3, the runtimes for this benchmark are shown. We see at once that it achieved lower execution times. Thus, the performance does not depend uniquely on the number of objects, but it also take into account other factors (density, number of clusters, distances, etc.). Despite running on a GPU with only four SMs, PFMGPU showed lower execution times. More precisely, the eight-partition execution of PFMGPU was faster than PFMMPI running on eight nodes. The time spent on communication for PFMMPI increased from the previous experiment. Nevertheless, it has a minimal impact on the performance. Figure 4: Geographical coordinates of 20,237 USA schools (partial schools dataset). Figure 5: Hierarchical clustering of prototypes. Figure 6: Prototypes found for the partial schools dataset. ### Complete schools dataset

Our final simulation is also based on data from U.S. Board on Geographic Names [26]. More precisely, we analyzed 40,646 school locations across USA (see Figure 7). We note that these data has no well-defined boundaries among clusters. Figure 8a-c show dendrograms found for parallel executions with two, four and eight partitions, respectively. The coordinates of each cluster prototype are represented with respect to the \(x\)-axis. We see at once that all executions found five different clusters at the dashed level. The prototypes found are located in high density areas. Hence, the prototypes do not have to be at the center of the cluster as in K-Means based algorithms. The variation between dendrograms did not influence the precision of the final result.