# Performance of Parallel K-Means Algorithms in Java
## 4 Experimental Results
Although the observed values of \(Speedup_{S}\) and \(Speedup_{T}\) are similar, from the Table 2 it emerges that the Theatre actor-based solutions perform better than the corresponding \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{\(K\)} & \multirow{2}{*}{\(\begin{array}{c}SET_{SSKM}\\ \textbf{(ms)}\end{array}\)} & \multirow{2}{*}{\(\begin{array}{c}PET_{PSKM}\\ \textbf{(ms)}\end{array}\)} & \multirow{2}{*}{\(\begin{array}{c}Speedup_{S}\end{array}\)} & \multirow{2}{*}{\(\begin{array}{c}SET_{STKM}\\ \textbf{(ms)}\end{array}\)} & \multirow{2}{*}{\(\begin{array}{c}PET_{PTKM}\\ \textbf{(ms)}\end{array}\)} & \multirow{2}{*}{\(\begin{array}{c}Speedup_{T}\end{array}\)} \\ \hline
10 & 70,566 & 9233 & 7.64 & 59,671 & 7620 & 7.83 \\ \hline
20 & 114,743 & 12,061 & 9.51 & 96,891 & 11,221 & 8.63 \\ \hline
40 & 428,389 & 44,877 & 9.55 & 357,731 & 38,535 & 9.28 \\ \hline
60 & 510,496 & 53,798 & 9.49 & 420,934 & 45,217 & 9.31 \\ \hline
80 & 769,109 & 68,158 & 11.28 & 597,489 & 63,497 & 9.41 \\ \hline
100 & 1,407,401 & 145,346 & 9.68 & 1,117,578 & 111,956 & 9.98 \\ \hline
120 & 1,920,530 & 199,335 & 9.63 & 1,552,306 & 146,059 & 10.63 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Serial/parallel elapsed times for Stream-based and Theatre-based K-Means vs. K (P = 16). Figure 10: The number of iterations (\(it\)) for convergence vs. K.  
Stream-based solutions, both in the serial and the parallel cases, which seems to indicate Theatre is more able to exploit the underlying computational resources. This is also confirmed by the measured \(Speedup_{T}\) which scales more regularly with the increase of the number \(K\) of clusters. The registered speedup values are in many cases examples of _super-speedups_, when one considers that the number of physical cores of the used machine is 8. Such super-speedup closely mirrors the number of physical and hardware emulated cores, and the important contribution of the L2 cache of cores, where segments of the dataset are pre-loaded and re-used thus avoiding, very often, the need to accessing data in the internal memory. Such a phenomenon is well documented in the literature, see e.g., [13; 25; 26] and it was formally predicted and practically observed in the parallel processing of large numerical arrays and matrices [25]. As a final remark, the developed stream-based versions of K-Means as well as the standalone Theatre-based version, have the limitation of allocating the whole dataset in a native array collection, which the parallel stream version can then split into consecutive segments and process them by separate threads. Of course the approach can be difficult to apply to some large datasets, although the memory size of current commodity multi-core machines is noticeable. On the other hand, the Theatre actor-based parallel version of K-Means is capable of feeding the master/worker actors with consecutive pieces of the dataset, directly read from the source file. In any case, the handling of very large datasets could be possible by using a multi-computer solution, based on distributed Theatre, which can partition the work and the data among the machines of a networked system, but this is further work to do.