# Parallel fuzzy minimals on GPU
## 3 Parallel FM
### Parallel FM on GPU
Output: all kernels return void procedure PFMPGPU(\(r\), \(X[\ ]\), \(V[\ ]\)) \(id=threadIdx\) \(dim=gridDim\) \(start=\) initial index of the partition end = final index of the partition _shared_\(V_{s}[\ ]\), \(tmp[\ ]\), \(size=0\) for\(k=start+id\); \(k<end\); \(k+=dim\)do \(v_{(0)}=X[k]\) \(t=0\); \(E_{0}=1\) while\(E_{(t)}\geq\epsilon_{1}\)do \(t=t+1\) \(\mu_{xv}=\frac{1}{1+r^{2}d_{xv}^{2}}\), using \(v_{t-1}\) \(v_{t}=\frac{\sum\limits_{x\in X}\mu_{xv}^{2}x}{\sum\limits_{x\in X}\mu_{xv}^{ 2}}\) \(E_{(t)}=\sum\limits_{a=1}^{F}(v_{(t)}^{a}-v_{(t-1)}^{a})^{2}\) endwhile \(tmp[id]=v_{(t)}\) \(\textit{syntthreads}()\) if\(id==0\)then for\(i=0\) until\(dim\)do if\(\sum\limits_{a=1}^{F}(tmp[i]^{a}-w^{a})^{2}>\epsilon_{2}\), \(\forall w\in V_{s}\)then \(V_{s}=V_{s}+\{tmp[i]\}\) \(size=size+1\) endif endfor endif endfor _syntthreads_() for\(i=id\); \(i<size\); \(i+=dim\)do \(V[i]=V_{s}[i]\) endfor endprocedure
```
**Algorithm 3** FM kernel on GPUs. ### Parallel FM on MPI

Our parallel implementation using MPI is similar in spirit to that based on GPU. Thus, we have again the four phases described for the parallel FM on GPU (i.e., determination of factor R, data-partitioning, parallel FM and hierarchical clustering). However, the final implementation using MPI is more straightforward than the version in GPU. Indeed, the mapping between the sequential and the parallel version is minimal. Algorithm 4 shows the main program of our MPI implementation. First, we define the number of processes (i.e., the number of data-partitions) and the rank of the current process. Next, a coordinator process reads the objects and computes the factor R, distributing the data across \(p\) logical partitions. Moreover, the coordinator process sends them to the peer processes. All processes run the FM function by Algorithm 1. Finally, the peers complete their execution sending the result to the coordinator process. Now, the coordinator process can perform the hierarchical clustering of prototypes. ```
procedureMain \(p\) = number of processes \(rank\) = process identifier if\(rank\) == 0 then \(X\) = objects \(r\) = factor R  Dist. objects uniformly in \(p\) partitions \(size=n/p\) for\(k=1\) until\(k<p\)do \(Send(r,\)\(size,X[size*k])\) endfor else Receive(\(r,\)\(size,X\)) endif \(V\) = \(FuzzyMinimals(X,r,\)\(size)\) if\(rank>0\)then \(Send(V)\); else for\(k=1\) until\(k<p\)do \(V\) = \(V\) + \(Receive(V)\) endfor endif if\(rank\) == 0 then \(C\) = Hierarchical clustering of \(V\)  Show \(C\) prototypes endif endprocedure
```

**Algorithm 4** Main program in PFMMPI. ## 4 Numerical simulations and results

In this section, we analyze the perfomr of parallel FM algorithm. Obviously, we do not need to deal with correctness and quality of the FM algorithm already discussed in [24; 25]. The results of this section involve a synthetically developed dataset and two real-world benchmarks. Most popular fuzzy clustering algorithms rely on input parameters to find clusters. Thus, these algorithms require several executions to achieve the same performance of the FM algorithm. Comparison between the accuracy of the FM algorithm and other similar techniques has been extensively studied in recent years. Since the number of executions required by other solutions depend on input parameters provided by the user, we cannot perform a fair runtime comparison between FM algorithm and other similar techniques. Accordingly, our benchmarks are based on different implementations of the FM algorithm. All results for PFMGPU were collected on a single machine, using from one to eight blocks with 960 threads per block. In each run, the number of blocks matches the number data-partitions. On the other hand, PFMMPI was executed on a cluster, using from one to eight nodes with one process per machine. Moreover, the number of processes matches the number of data-partitions. All machines (i.e., single and cluster machines) have the same configuration: CPU Intel Core i7 3.4 Ghz, 16 GB of RAM and GPU Nvidia GeForce GTS 450 with 4 SMs.