# Parallel and Distributed Frugal Tracking of a Quantile +
## 3 The EasyQuantile Algorithm
The parallel reduction operator is used internally by the ParallelReduction step. Since this function is called in each step of the ParallelReduction and its complexity is \(O(1)\), the overall complexity of the ParallelReduction step is \(O(\log p)\) (using, for instance, a binomial tree [14] or even a simpler binary tree). Therefore, the overall parallel complexity of the algorithm is \(O(n/p+\log p)\). We are now in the position to state the following theorem:

Theorem 6.1: _The algorithm is cost-optimal._

Proof. : Cost-optimality [24] requires by definition that asymptotically \(p\ T_{p}=T_{1}\), where \(T_{1}\) represents the time spent on one processor (sequential time) and \(T_{p}\) is the time spent on \(p\) processors. The sequential algorithm requires \(O(n)\), and the parallel complexity of the algorithm is \(O(n/p+\log\ p)\). It follows from the definition that the algorithm is cost-optimal for \(n=\Omega(p\log p)\). We proceed with the analysis of iso-efficiency and scalability. The sequential algorithm has complexity \(O(n)\); the parallel overhead is \(T_{o}=p\ T_{p}-T_{1}\). In our case, \(T_{o}=p\ (n/p+\log\ p)-n=p\ \log\ p\). The iso-efficiency relation [25] is then \(n\geq p\ \log\ p\). Finally, we derive the scalability function of this parallel system [26]. This function shows how memory usage per processor must grow to maintain efficiency at a desired level. If the iso-efficiency relation is \(n\geq f(p)\) and \(M(n)\) denotes the amount of memory required for a problem of size \(n\), then \(M(f(p))/p\) shows how memory usage per processor must increase to maintain the same level of efficiency. Indeed, in order to maintain efficiency when increasing \(p\), we must increase \(n\) as well, but on parallel computers, the maximum problem size is limited by the available memory, which is linear in \(p\). Therefore, when the scalability function \(M(f(p))/p\) is a constant \(C\), the parallel algorithm is perfectly scalable; \(C\)\(p\) represents instead the limit for scalable algorithms. Beyond this point, an algorithm is not scalable (from this point of view). In our case, the function describing how much memory is used for a problem of size \(n\) is given by \(M(n)=n\). Therefore, \(M(f(p))/p=O(\log\ p)\) with \(f(p)\) given by the iso-efficiency relation and the algorithm is moderately scalable (again, from this perspective, related to the amount of memory required per processor). ## 7 Experimental Results

In this section, we present and discuss the results of the experiments carried out for the parallel versions of Frugal-1U, Frugal-2U, and EasyQuantile, showing that the parallel versions of these algorithms are scalable and the parallelization does not affect the accuracy of the quantile estimates with respect to the estimate done with the sequential versions of the algorithms. The tests have been carried out on both a parallel machine and a workstation. The former is the Juno supercomputer (peak performance 1.134 petaflops, 12,240 total cores, 512 GB of memory per node, Intel OmniPath 100 Gbps interconnection, lustre parallel filesystem) kindly made available by CMCC. Each node is equipped with two 2.4 GHz Intel Xeon Platinum 8360Y processors, with 36 cores each, and some nodes are also equipped with two NVIDIA A100 GPUs. The source code has been compiled using the Intel C++ compiler and the Intel MPI library. The workstation is a HP (Hewlett-Packard) machine equipped with a 24 core Intel XEON W7-2495X processor and 256 GB of memory, and two NVIDIA RTX 4090 GPUs. The tests have been performed on the synthetic datasets reported on Figure 1:0 The experiments have been executed, varying the distribution, number of cores, stream length, and the quantile being tracked. Table 2 reports the default settings for the parameters used on the parallel machine. On the workstation, the number of cores was 2, 4, 8, and 16 whilst the stream length was 100 millions for strong scalability and 100 millions per core for weak scalability.