# Parallel and Distributed Frugal Tracking of a Quantile +
## 3 The EasyQuantile Algorithm
We conclude that the parallel version of EasyQuantile is able to accurately track quantiles, especially higher quantiles, and provides the sought parallel performance as shown by the strong and weak scalability tests made. Therefore, it is the parallel algorithm of choice for tracking a quantile in a streaming setting, relying only on \(O(1)\) memory. ### Workstation

Here, we present the experimental results obtained on the HP workstation, using 2, 4, 8, and 16 cores. Figure 15 depicts the results related to the strong and weak scalability of parallel Frugal-1U. As shown, the algorithm scales until 8 cores, then the upward curvature for 16 cores indicates limited scalability. Regarding weak scalability, the upward trend of the curves indicates limited scalability as well. This is not really surprising, owing to the fact that the workstation has not been designed for HPC (high-performance computing), whilst the architecture of a parallel machine is--instead--specifically designed for HPC. Even though the workstation may certainly be used for this purpose, we can not expect the same performance level. To better understand the gap between the parallel machine and the workstation, we also recall here that the former provides weak scalability using only 45 million items per core, whilst the latter does not provide weak scalability

Figure 14: Normal distribution: relative error. Figure 13: Normal distribution: strong and weak scalability. even using 100 million items per core, more than double the amount of data used for the parallel supercomputer. Next, we analyze the relative error of parallel Frugal-1U. Figure 16 provides the results varying, respectively, the distributions and the quantiles. We observe that for almost all of the distributions, the relative error is quite low and close to zero. Only the uniform and the cauchy distributions exhibit high relative error, since the estimates obtained by each processor are already affected by a sufficiently high relative error, owing to the small size of the sub-stream assigned to each processor, which does not allow achieving a good estimate (lack of convergence). Regarding the quantiles, varying the processors does not affect the accuracy; indeed, the corresponding relative errors are very close to zero and do not change significantly by varying the cores. The parallel Frugal-2U presents the same behavior, as shown in Figures 17 and 18, respectively, for strong/weak scalability and for the accuracy with regard to distributions

Figure 8:0 Parallel Frugal-1U on workstation: relative error. Figure 8:1 Parallel Frugal-1U on workstation: strong and weak scalability. and quantiles. In particular, parallel Frugal-2U achieves slightly better accuracy results with regard to parallel Frugal-1U, but is not significantly better overall. Finally, we discuss the results obtained by parallel EasyQuantile. Figure 19 depicts the strong and weak scalability of the algorithm. As shown, the algorithm is characterized by good strong and weak scalability, taking into account that the overall range of elapsed time is quite small for the weak scalability case. The accuracy, depicted by Figure 20, confirms that the parallelization does not impact on the relative error, whose values are close to zero and practically constant for all of the distributions and quantiles varying the number of processors (even though the curve related to quantile 0.1 appears to be slightly increasing, the range of variation is less than \(10^{-3}\)). Figure 8:2 Parallel Frugal-2U on workstation: strong and weak scalability. Figure 8:3 Parallel Frugal-2U on workstation: relative error. We end this section by comparing the three parallel algorithms simultaneously. Figure 21 shows that EasyQuantile scales better than Frugal-1U and Frugal-2U with regard to both strong and weak scalability. Regarding the accuracy, Figure 22 shows that Frugal-1U and Frugal-2U provide slightly more accurate results in terms of relative error. Overall, the results are quite similar to those obtained on the parallel supercomputer.