Page 237 - Invited Paper Session (IPS) - Volume 1
P. 237
IPS 151 Rub´en C.
The rest of the article is organized as follows: in the methodology section
the boostrap algorithm is presented to calculate the Pearson correlation and
a calculation is made of the space required for its execution. Also two parallel
implementations are presented. In the results section the execution times of
the four implementations are shown and in the discussion section and
conclusions the limitations and extensions of the implementations are
presented.
2. Methodology
The number of operations required in the bootstrap algorithm for
calculating the Pearson coefficient is where is the number of
observations of each of the two variables and is the number of iterations
boostrap . We do not consider the number of operations required to calculate
a Pearson coefficient since this calculation is done together with the reading
of the elements of the sample generated. Regarding the space required, this
is 2 + , where 2 is the space occupied by the observations and is the
space occupied by the Pearson coefficients calculated. This expression must
be multiplied by 4 if the data is stored as real numbers of simple precision
(float type in C language) to obtain the number of bytes required.
Table 1 shows the sequential version of the algorithm. Lines 2 and 3 can
be combined in a single cycle for operations. The parallel version can be
Table 1: Sequential Bootstrap Table 2: Parallel Bootstrap
Input: X, Y Set of observations Input: X, Y Set of observations
Number of bootstrap Number of bootstrap iterations
iterations Percent of the confidence interval
Number of Cores
Output: P Pearson Coefficients Output: P Pearson Coefficients
1 for ← 1 to do 1 For each core 1 . . . do parallel
2 ′, ′ ← SampleFrom(, , ) 2 for ← 1 to [ ] do
3 Pi ← CorrelationCoef( , ) 3 ′, ′ ← SampleFrom(, , )
′
′
4 endfor 4 Pi ← CorrelationCoef ( , )
′
′
5 return P 5 endfor
6 endfor
7 return P
easily implemented when executing each processor a bootstrap iteration. The
ideal scenario would be to have as many processors as bootstrap iterations, in
this case the algorithm make operations. If the number of available
processors is less than the number of bootstrap iterations, then they must be
distributed among the processors. Let , , , be the number of iterations
1
2
that each processor will perform, then + + + = . Then the
2
1
number of operations of the parallel algorithm will be × { , , . . . , }.
1 2
226 | I S I W S C 2 0 1 9