# Parallel and Distributed Frugal Tracking of a Quantile +
## 3 The EasyQuantile Algorithm
### Parallel Machine

We begin by providing the results obtained for each algorithm when considered in isolation. Figure 7 depicts the results for parallel Frugal-1U with regard to both strong and weak scalability. To analyze the strong scalability, we set the length of the input stream to 25.6 billion items, track the 0.99 quantile, and vary the number of cores and the distributions. Figure 7a shows the results using a log-log plot of the parallel runtime versus the number of cores. A straight line with slope \(-1\) indicates good scalability, whereas any upward curvature away from that line indicates limited scalability. As shown, parallel Frugal-1U exhibits overall strong scaling almost independently from the underlying input distribution being used. \begin{table}
\begin{tabular}{l l} \hline \hline
**Parameter** & **Values** \\ \hline quantiles & \(\{0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,0.95,0.99\}\) \\ number of cores \(P\) & \(\{36,72,144,288\}\) \\ stream length & \(\{25.6B\) (strong scaling), \(45M\) (weak scaling) \} \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Default settings of the parameters. Next, we discuss the weak scalability. In this case, the problem size increases at the same rate as the number of processors, with a fixed amount of work per processor. A horizontal straight line indicates good scalability, whereas any upward trend of that line indicates limited scalability. In Figure 6(b), the amount of work per core is fixed at 45 million items and we track the 0.99 quantile. Almost all of the distributions considered exhibit good weak scalability starting from 72 cores. Figure 8 provides the results obtained for the accuracy, measured using the relative error between the true and the estimated quantile value. We perform the test for both distributions (Figure 7(a)) and quantiles (Figure 7(b)). As shown, the cauchy distribution confirms its adversarial character for the algorithm, with a relative error steadily rising from slightly more than 0.3 on 36 cores to about 0.6 on 288 cores. The other distributions do not impact the relative error, which is almost zero. This holds true also for the uniform distribution, whose relative error steadily rises from about \(10^{-5}\) on 36 cores to about \(10^{-2}\) on 288 cores. Figure 8: Parallel Frugal-1U: relative error. Figure 7: Parallel Frugal-1U: strong and weak scalability. Figure 9 depicts the results for parallel Frugal-2U with regard to both strong and weak scalability. As shown, the behavior of this algorithm is substantially equal to that of Frugal-1U with regard to strong scaling. However, weak scalability is consistently worse. The behavior, with regard to accuracy, shown in Figure 10, is again quite similar to that of Frugal-1U. Figure 11 depicts the results for parallel EasyQuantile with regard to both strong and weak scalability. As shown, EasyQuantile exhibits very good strong scaling. Regarding weak scaling, even though the plot does not show the expected horizontal straight lines, it is worth noting here that the parallel runtime is between 0.44 and 0.48 s for all of the core counts. Finally, the accuracy depicted in Figure 12 is extremely good for both distributions and quantiles. Figure 10: Parallel Frugal-2U: relative error. Figure 9: Parallel Frugal-2U: strong and weak scalability. Having discussed the parallel algorithms' results in isolation, we now turn our attention to selected experimental results, in which we simultaneously compare all of the parallel algorithms with regard to the normal distribution. As shown in Figure 13, EasyQuantile scales much better than Frugal-1U and Frugal-2U with regard to both strong and weak scaling. Regarding the accuracy Frugal-1U and Frugal-2U are slightly better than EasyQuantile when tracking the 0.99 quantile, as shown in Figure 14.

Figure 11: Parallel EasyQuantile: strong and weak scalability. Figure 12: Parallel EasyQuantile: relative error.