# A Multithreaded Algorithm for the Computation of Sample Entropy
## 5 Experimental Results  
In order to compare the examined paralelization policies, we collected and compared execution times from parallel versions of the bucket-assisted algorithm, each one implementing a different paralelization policy. We performed the experiments on an Intel(r) Core(tm) i5-10400 CPU @ 2.90 GHz, with 6 threads and capability for 6 more virtual ones, and 7.6 GB of system memory. We developed the code in the C language and compiled it with gcc (v11.3) [23], in a Linux (Ubuntu 20.04.6 LTS) environment, with the standard optimization parameter -_O2_. POSIX threads (p-threads) [24] used as the parallelization infrastructure.  
As input we used (a) a randomly generated time series of 100,000 samples with values uniformly distributed between 0 and 1 and (b) a data set of 54 Holter recordings from healthy people in sinus rhythm, publicly available on the internet [25] (each recording is approximately 24 h long, corresponding to approximately 100,000 beats). For the computation of sample entropy, we used the typical parameters \(m=2\), \(r=0.2\). No preprocessing (filtering) was applied to the Holter recordings.  
Average times over 1000 executions for the random signals and over 100 times for the Holter recordings are summarized in Tables 1 and 2. In Table 1 times are per signal, while in Table 2 for the whole data set (54 recordings). Each table is separated into two parts. On the top part, the execution times of the two sequential algorithms are shown. The first one is a straightforward implementation based on the definition of the method. All possible pairs of vectors are checked, employing a loop with three nested levels. We give the exact structure of the loop here for clarity and in order to be used by researchers as a basis for future comparisons. See Algorithm 1.  
The second algorithm is the bucket-assisted algorithm, as described earlier in Section 3 and analytically in [13].  
\begin{table}
\begin{tabular}{c c c c} \hline \hline  & \multicolumn{3}{c}{Serial executions} \\ \hline  & \multicolumn{3}{c}{_Straightforward algorithm_: 9.153 s} \\  & \multicolumn{3}{c}{_Bucket-assisted algorithm_: 0.546 s} \\ \hline  & \multicolumn{3}{c}{Parallel executions} \\ \hline  & \multicolumn{3}{c}{_Static-load balancing_} & _In-bucket balancing_ & _Dynamic-load balancing_ \\
2 threads: & 0.291 s & 0.330 s & 0.295 s \\
4 threads: & 0.144 s & 0.192 s & 0.157 s \\
6 threads: & 0.099 s & 0.150 s & 0.103 s \\
12 threads: & 0.082 s & 0.145 s & 0.081 s \\ \hline \hline \end{tabular}
\end{table}
Table 1: Execution times to compute sample entropy (\(m=2,r=0.2\)) for randomly generated signals.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline  & \multicolumn{3}{c}{Serial executions} \\ \hline  & \multicolumn{3}{c}{_Straightforward algorithm_: 517.58 s} \\  & \multicolumn{3}{c}{_Bucket-assisted algorithm_: 68.56 s} \\ \hline  & \multicolumn{3}{c}{Parallel executions} \\ \hline  & \multicolumn{3}{c}{_Static-load balancing_} & _In-bucket balancing_ & _Dynamic-load balancing_ \\
2 threads: & 44.17 s & 41.25 s & 35.57 s \\
4 threads: & 20.03 s & 25.47 s & 19.32 s \\
6 threads: & 16.43 s & 17.75 s & 13.37 s \\
12 threads: & 14.10 s & 19.72 s & 12.42 s \\ \hline \hline \end{tabular}
\end{table}
Table 2: Execution times to compute sample entropy (\(m=2,r=0.2\)) for 54 Holter (24 h) recordings.  
Figure 2 depicts the speedups achieved for each parallel execution compared to the execution time of the bucket-assisted algorithm. The panel on the left reports speedups for the randomly generated time series, while the one on the right shows speedups for the 54 Holter (24 h) recordings.  
In the following section, we will further discuss the findings of this research and examine the factors that influence the performance of the sample entropy computation algorithms.