This theoretical absolute speed-up curve is shown in Figure 1B; the black line represents a perfect absolute speed-up curve, where the speed-up of an algorithm on N nodes is N times faster than the best serial algorithm.
In order to assess how effective our parallelisation of the Evolution Strategy was, we calculate relative and absolute speed-up.
The absolute speed-up measures how effective the parallel algorithm is compared to the best serial algorithm, as opposed to merely the serial version of the parallel algorithm.
Moreover, as the number of processors increases, the difference between relative and absolute speed-up increases due to the use of populations beyond the optimum number.
The absolute speed-up is not as striking as the relative speed-up, but it is also a far more stringent measure of algorithm efficiency.
As expected, the absolute speed-up is generally lower than the relative speed-up: these two measures increasingly diverge as the number of processors increases, reflecting the negative effect of adding islands beyond the optimum.
The absolute speed-up is defined as (12) where K* is the number of islands resulting in optimal serial algorithm performance, which we found to be equal to 1 (see below).
The time taken to reach 'good-enough' and 'good solutions' for the optimal serial Island ES, and the two parallel piES algorithms, along with the relative and absolute speed-up for each parallel algorithm (comparison is between 'good-enough' solutions).
The absolute speed-up (as defined in equation 12) remains significant regardless of the number of nodes used, showing that the parallel algorithm is always faster than the best serial algorithm.
In practice, however, we can easily tune the algorithm in serial (using the predicted absolute speed-up), which will make testing these hypotheses relatively simple, especially if compared to the complex and time-consuming tuning required to reach optimal behaviour of the pLSA algorithm [ 39].
We calculated the theoretical speed of a perfect parallel algorithm on N nodes (assuming no communication overhead) by dividing the speed of the serial algorithm with Nisl islands by N. From this value, we produced a theoretical absolute speed-up curve (Equation 12), by dividing each theoretical parallel speed by the highest mean speed of the serial algorithm for any number of islands.
