Energy–time modelling of distributed multi-population genetic algorithms with dynamic workload in HPC clusters

Energy-time Modelling of Distributed Multi-population Genetic Algorithms with Dynamic Workload in HPC Clusters Juan Jos ´ e Escobar a,∗ , Pablo S ´ anchez-Cuevas b , Beatriz Prieto c , Rukiye Savran Kızıltepe d,e , Fernando D ´ ıaz-del-R ´ ıo b , Dragi Kimovski f aDepartment of Software Engineering, CITIC, University of Granada, Spain bDepartment of Computer Architecture and Technology, University of Seville, Spain cDepartment of Computer Engineering, Automation, and Robotics, CITIC, University of Granada, Spain dDepartment of Software Engineering, Karadeniz Technical University, Turkey eDepartment of Software Engineering, Ankara University, Turkey fInstitute of Information Technology, University of Klagenfurt, Austria Abstract Time and energy efficiency is a highly relevant objective in high-performance computing systems, with high costs for executing the tasks. Among these tasks, evolutionary algorithms are of consideration due to their inherent parallel scalability and usually costly fitness evaluation functions. In this respect, several scheduling strategies for workload balancing in heterogeneous systems have been proposed in the literature, with runtime and energy consumption reduction as their goals. Our hypothesis is that a dynamic workload distribution can be fitted with greater precision using metaheuristics, such as genetic algorithms, instead of linear regression. Therefore, this paper proposes a new mathematical model to predict the energy-time behaviour of applications based on multi-population genetic algorithms, which dynamically distributes the evaluation of individuals among the CPU-GPU devices of heterogeneous clusters. An accurate predictor would save time and energy by selecting the best resource set before running such applications. The estimation of the workload distributed to each device has been carried out by simulation, while the model parameters have been fitted in a two-phase run using another genetic algorithm and the experimental energy-time values of the target application as input. When the new model is analysed and compared with another based on linear regression, the one proposed in this work significantly improves the baseline approach, showing normalised prediction errors of 0.081 for runtime and 0.091 for energy consumption, compared to 0.213 and 0.256 shown in the baseline approach. Keywords: Energy-time Modelling, Heterogeneous Clusters, Distributed Computing, Parameter Optimisation, Task Scheduling, Genetic Algorithms. 1. Introduction To deliver higher performance, modern processors can no longer rely on increasingly complex designs. In fact, the industry has focused on creating more efficient alternatives to solve this problem. In this sense, Instruction Level Parallelism (ILP) is no longer the only resource available to the designer and a new trend has appeared towards architectures that allow Data Level Parallelism (DLP) and Thread Level Parallelism (TLP) [ 1 ]. Nevertheless, these techniques are insufficient, since the vast amount of data requiring processing nowadays surpasses the computing capabilities of any parallel architecture. This is why distributed computing has gained importance for years through the use of clusters, where multiple computing nodes are grouped to cooperate in solving a specific problem. Another key factor that has motivated the creation of these new computer architectures is energy consumption, since it ∗Corresponding author Email addresses: [email protected] (Juan Jos´ e Escobar), [email protected] (Pablo S´ anchez-Cuevas), [email protected] (Beatriz Prieto), [email protected] (Rukiye Savran Kızıltepe), [email protected] (Fernando D´ ıaz-del-R´ ıo), [email protected] (Dragi Kimovski) has become a considerable problem in the case of single-core processors [ 2 ]. Currently, in the context of Big Data and HighPerformance Computing (HPC), energy must be minimised to lower service costs and cushion the environmental impact of massive computing [ 3 – 5 ]. In this sense, many proposals have been published to address the problem. One of them is to use heterogeneous clusters, since they offer multiple levels of parallelism through a set of interconnected nodes which contain multiple Central Processing Units (CPUs) and accelerators, such as Graphics Processing Units (GPUs). It has been demonstrated that these platforms can increase the performance of different applications while reducing the energy cost [ 6 – 8 ]. One of the most distinctive features of distributed computing on heterogeneous clusters is workload distribution, as it has the potential to lead to unbalanced workload [ 9 ]. Therefore, deciding which devices the tasks should be assigned at runtime in systems that include resources with different performance and energy efficiencies is crucial. A topic of research in this direction is energy-time modelling. The heterogeneous clusters with dynamic workload distribution require dealing with non-linear models to predict their energytime behaviour accurately. This subject consists of the definition Preprint submitted to Future Generation Computer Systems January 29, 2025 and evaluation of mathematical models that estimate the behaviour in performance and energy consumption of a given computing platform. Then, the parameters involved in the resulting model are fitted by regression or optimisation methods by using experimental data as input. This allows us to take advantage of the newly fitted model to study how each parameter affects performance and energy consumption and, therefore, to tackle costs because it can help designers optimise the behaviour of a given application for a specific platform. For this reason, this paper focuses on building a model to deal with this issue. Specifically, the proposed model copes with the energy-time modelling of applications based on multi-population genetic algorithms that run on heterogeneous clusters with multiple nodes. Genetic Algorithms (GAs) play a fundamental role in dealing with complex problems, such as those that frequently appear in Artificial Intelligence (AI) and Data Science, where, in general, the data is stochastic and high-dimensional. The traditional optimisation tools fail for such problems due to their complexity [ 10 ]. GAs, by their nature, require iteratively performing multiple operations with large amounts of data, which implies that they are easily parallelizable in parallel and distributed architectures. Given the high computational cost of GAs, it is necessary to adequately plan the workload distribution between the different computing nodes, especially when they are heterogeneous. In this way, a trade-offcan be found between the energy-time performance of the application and the quality of the solutions to the problem to be solved. The new model presented here aims to improve a previous model for the same type of applications, using another genetic algorithm to optimise its parameters instead of linear regression. Although there are numerous optimisation methods in the literature, a specific GA has been chosen since it offers several significant advantages for the fitting of mathematical models. GAs are highly effective at handling non-linear and high-dimensional problems, such as those encountered in dynamic workload distributions in heterogeneous clusters. This allows them to fit models where gradient-based methods like Gradient Descent or NewtonRaphson may struggle due to non-convex or highly complex cost surfaces. One of the main strengths of GAs is their independence from gradients, making them useful in scenarios where the cost function is non-differentiable or computationally expensive to evaluate. Furthermore, GAs are well-known for their ability to perform global exploration of the search space, enabling them to avoid local optima. This is particularly valuable in problems with multiple local minima, where methods like Bayesian optimisation or Newton-Raphson may become trapped in suboptimal solutions. Another key advantage of GAs is their dynamic adaptability, allowing them to adjust to changes in the problem, such as variations in workload distributions in heterogeneous clusters. In contrast, more static approaches, like Grid Search or convex programming, lack this capability. Finally, GAs provide remarkable flexibility in model structure, which is crucial when handling parameters with complex constraints and non-linear dependencies. This type of flexibility is challenging to achieve with other approaches, such as certain machine learning-specific methods like Hyperband or Tree-structured Parzen Estimator (TPE), which do not directly address these issues. In summary, the main contributions of this work are as follows: • Propose a new mathematical energy-time model for distributed multi-population GAs, executed in heterogeneous clusters, which is compared with another pre-existing model taken as a baseline. Despite the existence of some previous works on HPC modelling, those that simultaneously take into account performance and energy consumption are not common, and even less so for parallel and distributed GAs. Moreover, although the model developed here is designed for multi-population applications with specific features, most bioinspired algorithms share a great similarity in their structure so that the model could be easily adapted to them. • Tackle the vital role that dynamic workload represents by modelling the dynamic distribution of subpopulations among CPU-GPU computing devices. • Apply a GA to fit the set of parameters comprised in the proposed mathematical model with the objective of handling its non-linearity. The objective is to demonstrate that the use of metaheuristics, in this case, a GA, is more suitable than linear regressions to fit the model parameters in applications with dynamic workload distributions. • Successfully validate the proposed model, obtaining more accurate results than the baseline one. Moreover, we also analyse the weight on time and energy consumption of the components of the evaluated cluster, while identifying the critical ones. The rest of the article is structured as follows: Section 2 reviews different works in the literature related to energy-time modelling and energy-aware computing in HPC systems; an overview of genetic algorithm is provided in Section 3; the proposed mathematical model and the non-linear optimisation method used to fit the model are detailed in Sections 4 and 5, respectively; the description of the modelled application and the corresponding experimental results are shown in Section 6; the paper’s conclusions are provided in Section 7. Finally, Appendix Aincludes a glossary of the mathematical terms involved in the proposed model and Appendix B defines the acronyms that appear throughout this paper. 2. Related Work Given the great importance of a good balance between performance and energy efficiency in computing, different methods and solutions have been proposed to address this problem. The works [ 4 , 11 ] compile an extensive list of papers on HPC and categorises them based on compute device type, optimisation metrics, and energy reduction methods. The compatibility of employing techniques for HPC systems, such as Dynamic Voltage Scaling (DVS), Dynamic Frequency Scaling (DFS), and Dynamic Voltage and Frequency Scaling (DVFS), to find the best combination of computing performance and energy consumption has also been discussed. Studies like [ 12 – 17 ] are well-known examples following this trend. 2 As mentioned in Section 1, modelling an application in HPC is essential to have control over its energy-time behaviour. In the case of parallel architectures, these simple but wide-ranging models based on extensions of Amdahl’s Law serve as a basis for seeing the influence of task distribution on many-core systems [ 18 , 19 ], and cloud computing [ 20 ]. Other approaches calculate the runtime and energy consumption as the weighted sum of the frequency of a set of system events, which are measured by hardware counters. Since low-level events such as cache misses, floating-point operations, or interrupts directly cause a significant effect on performance and energy efficiency, this alternative approach has become very attractive [ 21 ]. Although such models can be built for a specific application [ 22 ], they can become general models for a given set of problems with the correct modelling. For example, in [ 23 ], an estimation of the time consumed to evaluate an individual of the GA is used to determine the population size among a heterogeneous cluster without being dependent on the concrete problem or application. Regarding models that attempt to predict the energy consumption of computing architectures, surveys such as [ 3 , 24 , 25 ], summarise a substantial set of possible models. Most of them are based on linear expressions, while only a few use non-linear models to describe the hierarchical nature of system components. This is because linear models generally use linear regression for such a task, while non-linear models use optimisation methods [ 26 ]. Since it is more common to find applications in HPC systems executed on homogeneous systems with static workload distributions, linear models have been more widespread. In a broad sense, linear models have the advantage of interpretability so that the designer can understand each component’s weight in the HPC system’s final costs. This allows the developer to tweak the software to the algorithms to reduce their energy cost and increase performance [ 27 ]. In contrast, non-linear models, such as those optimised using metaheuristics, could be less interpretable but more accurate and can be used on various problems. One of the main features that affect overall efficiency in distributed HPC systems is the scheduling and distribution of the workload. Deciding where the tasks should be assigned is an important factor in heterogeneous clusters with different performance and power requirements [ 28 , 29 ]. It is important to differentiate between procedures that plan the distribution of jobs between devices at the operating system level, considering jobs independent of each other, and procedures that distribute tasks associated with a specific application and whose execution must be carried out in a pre-established and synchronised order. In the latter case, numerous heuristics have been previously proposed [ 30 , 31 ]. Wang et al. [ 30 ] propose an energy-aware task scheduling framework to minimise the energy consumption of heterogeneous and geo-distributed MapReduce clusters. The framework constructs a reasonable task list, considering deadlines, the number of assigned task slots, and possible processing times. Tasks are then scheduled into promising slots of rack-local servers, cluster-local servers, and remote servers, which significantly improve data locality. After task and slot assignment, available slots in clusters are updated to improve server resource utilisation by fuzzy logic, based on the current CPU, memory, and bandwidth utilisation. Experimental results showed that the proposed heuristic reduces energy consumption compared to existing algorithms by varying the total number of slots. In the work [ 31 ], the authors address the problem of energy efficiency in heterogeneous edge computing systems for a large number of latency-sensitive applications. Indeed, they present an efficient technique to minimise the energy overhead of timeconstrained applications modelled by Directed Acyclic Graphs (DAGs). The technique is developed in three phases: firstly, they design a new method for calculating task priority and propose an energy-aware scheduling algorithm based on ant colonies to obtain a preliminary scheduling result; secondly, taking into consideration the slack time between tasks and their deadlines, they propose a proportional downward recovery slack algorithm to further reduce the energy overhead by using the DVFS technique; finally, taking into consideration the slack time between tasks executed on the same processor, they propose a proportional upward and downward recovery algorithm to reduce the power overhead using the DVFS technique again. The simulated results indicated that the presented technique is highly efficient in reducing power overhead compared to existing techniques using randomly generated and real-world benchmarks with different characteristics. Despite the above, more precise heuristics can be defined when the tasks are specific or identifiable. For example, in one of our previous works [ 32 ], a model is fitted to predict the energy-time behaviour of the application, taking into account both the input parameters of the algorithm, as well as the clock frequencies of the CPU-GPU devices. Later, in the work [ 33 ], the model was extended to allow predicting the behaviour of a parallel and distributed genetic algorithm when using heterogeneous clusters to evaluate multiple subpopulations of individuals. From both works, it is revealed that adequate scheduling can simultaneously reduce runtime and energy consumption by efficiently distributing the tasks among the different processing elements. Despite the good results, both models used linear regression to fit the parameters, which, as discussed above, is not ideal for dynamic workload distributions. 3. Overview of Genetic Algorithms As stated in a recent work [ 34 ], GA is one of the most popular optimisation algorithms currently employed in real-world applications, including image processing, programming, clustering, software engineering, natural language processing, recommendation systems, and scheduling tasks. The interest in and importance of this kind of algorithm and evolutionary computation has remained strong over the years. In the last four years alone, more than 73,000 publications on GA have been included in the Web of Science Platform (Clarivate). GAs mimic the process of natural selection, where each new generation is expected to be better than its parents. The goal of these algorithms is to find a solution to the problem using the individuals in the population as candidates for the solution. Each of them is represented by a chromosome that encodes the parameters (genes) of the problem to be solved. All individuals are evaluated according to a fitness function, obtaining a score 3 related to the quality of their solutions. The better the score, the greater the degree of approximation to the optimal solution and the probability of reproduction for that individual. There are several ways to determine the individuals (parents) that will generate offspring (children). One of the most common is the binary tournament, in which some individuals are randomly chosen and the two best are selected. After that, the crossover and mutation operators are applied. The crossover operator is responsible for conducting the search across the solution space by combining genes from the parents to create new individuals. On the contrary, the mutation is the modification of some genes in the children’s chromosomes. For each gene, the mutation is performed with a fixed probability, usually low, so as not to excessively alter the natural course of evolution. Nevertheless, its use provides diversity in the search space and serves as a measure to avoid falling into local optimum quickly. Finally, the selection operator will choose which individuals will be part of the next generation based on the value of the fitness function. All the above steps are repeated over several generations of individuals (iterations in computational terms) until a stopping condition is met. The objective after each generation is to continuously improve the quality of the solutions until converging on an optimal or near-optimal solution. A GA can have a more complex structure and involve more operators to improve the search for solutions. For example, there are multi-population models that allow the evolution of several populations simultaneously. In fact, the mathematical model proposed in this work is focused on this type of GAs. The idea is to divide the total population into several subpopulations, or islands, where each one evolves independently. This scheme allows some GAs the possibility of exchanging information between subpopulations every certain number of generations. The process is known as migration, and it is considered as an exclusive genetic operator of multi-population models. The introduction of migration gives the algorithm the ability to exploit the differences between subpopulations, thus allowing genetic diversity. However, the determination of the migration rate and when to migrate is a sensitive matter since an inappropriate value can cause premature convergence. Another concern is the performance. GAs are highly parallelizable since each individual in the population can be independently evaluated. However, the multi-population paradigm allows another level of parallelism since following the same philosophy, the subpopulations evolve independently of each other except at the time of migration. However, the more levels, the more complexity. One of them is the problem of workload balancing: depending on the parallel approach, workload imbalances and consequent loss of performance can occur. Assuming that the time needed to evaluate an individual is the same in all subpopulations, an example of workload imbalance appears when the size of the subpopulations differs. Another imbalance situation is present in heterogeneous computing because the devices responsible for evaluating individuals probably have different computational capabilities. Also the granularity of parallelism must be taken into account since, depending on its type, the cost of communications and workload imbalance can be less or greater, so finding a trade-offbetween the two is important. 4. The Proposed Energy-time Model This section exposes the new mathematical model intended to predict the energy-time behaviour of multi-population genetic algorithms, in which a master-worker approach dynamically distributes the evaluation of subpopulations among the CPU-GPU devices of heterogeneous clusters, and performs migrations between subpopulations every certain number of generations. We have taken as a baseline model the one proposed in [ 33 ], which we intend to improve. All variables involved in the definition of the new model are summarised in Appendix A. 4.1. Mathematical Formulation The starting hypothesis to create the new model is based on the following differences with the baseline model: 1. The new model is based on considering the computing by CPU-GPU devices instead of by nodes. Modelling a level where the workload granularity is finer provides more accurate results. 2. In the baseline model, the total workload sent to each device was assumed to be known. However, this does not capture the dynamic nature of the application because each device requests workload on demand, so it cannot be exactly known a priori. 3. The baseline model considered that the number of individuals to be evaluated within a device in each generation is equal to the subpopulation size. However, when the genetic algorithm applies the crossover operator to generate new offspring, the number of children will usually be smaller due to the influence of the crossover probability. It should be noted that although the mutation step modifies the computational workload by varying the number of selected features, it is assumed to be negligible due to its low probability ( β ), so it has not been included in the new model to simplify its complexity. Taking all of the above into account, the model is developed as follows: as the model proposed here starts from the distribution of subpopulations by devices, the runtime of the j -th device of the i -th node, necessary to evolve one subpopulation between two migrations, is: ˆ T1 i,j=g NGm ·&PE Ci,j'·Wi,j Fi,j (1) where g is the number of generations and NGm the number of global migrations. In this way, migration takes place every g NGm generations. Ci,j is the number of cores in the device running at a clock frequency Fi,j . Each subpopulation involves PE evaluations of individuals in parallel, being Wi,j , the number of clock cycles necessary to evaluate each. As the number of individuals to be evaluated in each generation should be less than the subpopulation size due to the crossover probability, PE can be estimated as: PE=SS p ·α= N NS p !·α(2) 4 where SS p is the subpopulation size, α is the crossover probability, and N and NS p are the number of individuals and subpopulations of the genetic algorithm, respectively. Extending Equation (1), the runtime of the j -th device of the i -th node necessary to evolve its NS pi,jsubpopulations is: ˆ Ti,j=NS pi,j·ˆ T1 i,j(3) Finally, the total runtime taken by the cluster to perform the whole genetic algorithm is modelled as follows: ˆ Tcluster =NGm ·(ˆ Tmaster +ˆ Tcom +ˆ Tevo) (4) being ˆ Tmaster and ˆ Tcom the time overheads that migration imposes on the master node and the switch, respectively. The variable ˆ Tevo corresponds to the time necessary to evolve all NS p subpopulations between two migrations. In the baseline model, ˆ Tevo was modelled as the time needed by the slowest worker node to evolve its subpopulations: max ˆ Ti;∀i=1,...,NWk , being NWk the number of available workers: ˆ Tcluster =NGm ·ˆ Tmaster +ˆ Tcom +max ˆ Ti;∀i=1,...,NWk (5) However, in the new model, parameter ˆ Tevo has been adapted at the device level to capture the dynamic essence of the algorithm. This means that the slowest device between migrations will not always be the same since it depends on the total number of subpopulations it received. For this reason, ˆ Tevo has been estimated using the Algorithm 1 presented in Section 4.2 by accumulating the time costs of each device. Once the time equations have been obtained, the next step is to estimate the energy cost. In this sense, Equations (3) and (4) are fundamental in this model since energy consumption corresponds to the product of instantaneous power and runtime. Thus, the energy consumption of the j -th device of the i -th node between two migrations can be calculated by adding its consumption when active and idle: ˆ Ei,j=Powi,j·ˆ Ti,j+Powidle i,j·ˆ Tevo −ˆ Ti,j(6) where Powi,j and Powidle i,j are the instantaneous power of the device when active and idle, respectively. The idle time can be calculated by subtracting the time taken by the device, ˆ Ti,j , from the total time of computing all the subpopulations, ˆ Tevo . If this subtraction result is zero, this device is always computing, which causes a bottleneck for the rest of the devices. Finally, the energy consumption of the entire cluster can be calculated as the sum of the energy of each device and that caused by the overhead of the master node and the switch: ˆ Ecluster =NGm · Powmaster ·ˆ Tmaster +Powswitch ·ˆ Tcom +X i,j ˆ Ei,j (7) being Powmaster and Powswitch the instantaneous power of the master node and switch, respectively. Algorithm 1: Simulated workload distribution implemented in the modelled application. 1Function WorkloadDistribution NS p,NWk,ND Input :Number of subpopulations, NS p Input :Number of worker nodes in the cluster, NWk Input :List with the number of devices of each node, ND Output :Predicted runtime to evolve all subpopulations, ˆ Tevo Output : List with the estimated number of subpopulations assigned to each device, NS pi,j,∀i=1,...,NWk, ∀j=1,...,NDi 2NS pi,j←0 3L← Init list with rows of type [node,device,total time =0] 4while NS p >0do 5i←getColumn (L[0],“node”) 6j←getColumn (L[0],“device”) 7t←getColumn (L[0],“total time”) 8setColumn L[0],“total time”,t+ˆ T1 i,j 9L←sortAscendingOrder (L,“total time”) 10 NS p ←NS p −1 11 NS pi,j←NS pi,j+1 12 end 13 ˆ Tevo ←getColumn (L[len (L)−1],“total time”) 14 return hˆ Tevo,NS pi,ji 15 End 4.2. Workload Distribution Computation The model proposed in this work reproduces the dynamic behaviour of a heterogeneous system. Since the total workload assigned to each device, NS pi,j , is dynamic, it is necessary to implement a simulation of the workload distribution within the model to estimate its value and that of the variable ˆ Tevo . For this purpose, Algorithm 1 has been developed. The algorithm considers a list of tuples, L , which records for each device the accumulated time of evaluating subpopulations (Line 3). The main loop from Lines 4 to 12 iterates over the input subpopulations, assigning one subpopulation to the device at the top of the list, L0 (Line 7). The reason is that this device is the one that computes the least and, therefore, is idle. Then, the runtime ˆ T1 i,j necessary to evolve the subpopulation is added to the accumulated runtime of the device (Line 8). Next, the list is sorted by the “total time” column in ascending order, and the subpopulation of this iteration is discarded (Lines 9 and 10). After finishing the loop, ˆ Tevo is obtained from the last element of the list, L[len (L)−1] , since it is the device that has accumulated the maximum time (Line 13). The algorithm ends in Line 14 by returning ˆ Tevo and the number of subpopulations computed by each device, NS pi,j. Although this method covers dynamic behaviour, one crucial feature appears, namely non-linearity. This is because devices with different performances compete to request new tasks in a heterogeneous cluster with a non-static workload distribution. Therefore, although the energy-time costs can be modelled with near-linear expressions at the device level, the states of each device (active or idle) are strongly related to this distributed 5 competition. In this context, our approach is not limited to efficiently distribute the workload but also aims to accurately understand and predict system behaviour in terms of execution time and energy consumption. The aforementioned variability in the computational capabilities of the devices, along with the nature of genetic algorithms, introduces complexities that a coarse-grain prediction model cannot fully capture. Accurate predictions are essential to avoid bottlenecks, unbalanced workload, and inefficient allocations that could increase energy costs and degrade performance. Thus, the proposed model offers granular predictions that complement the dynamic workload distribution algorithm. This is crucial for designing more efficient systems, as it allows fine-tuning of specific aspects such as node-to-node migrations or the allocation of subpopulations based on the profile of each device. 5. Model Fitting Method A genetic algorithm has been used to fit the model’s parameters due to its speed in finding acceptable solutions in a reasonable time [ 35 , 36 ]. A total of 22 parameters must be fitted, which are defined as unknowns and are associated with the cost of different cluster resources. The only known input variable is the number of subpopulations used in the evolutionary algorithm, NS p . The fitting is divided into two independent executions of the GA: first, 2 parameters related to time and 6 to workload are fitted. Subsequently, the 14 energy parameters are fitted using the fitted values of the previous step. Each parameter corresponds to a chromosome gene, which has a variable length since it depends on the type of fitting run. In addition, the number of genes also depends on the platform to be modelled, since for each device, its parameters Wi,j , Powi,j , and Powidle i,j must be added. The chromosome representation for time/workload and energy, cT W and cE, respectively, are defined as: cTW =W1,1,...,WNWk,NDWk ,ˆ Tcom,ˆ Tmaster(8) cE= Pow1,1,...,PowNWk,NDWk ,Powidle 1,1,...,Powidle NWk ,NDWk , Powmaster,Powswitch!(9) The cost functions for time and energy, RMS ET and RMS EE , respectively, are defined as the Root-Mean-Square Error (RMSE) between the predicted and experimental measurements: RMS ET=v u t1 32 · 32 X NS p=1ˆ Tcluster −Tcluster2(10) RMS EE=v u t1 32 · 32 X NS p=1ˆ Ecluster −Ecluster2(11) where Tcluster and Ecluster corresponds to the measured experimental data. In this way, both fittings aim to find a set of Individuals Number 120 Chromosome representation Real-valued Evolution Number of generations 100 Inconsistency penalty 109 Crossover Type SBB Probability 0.7 Mutation Type Polynomial Probability 0.01 Table 1: Input values of the GA used to fit the model. SBB: Simulated Binary Bounded. parameter values such that the predictions made with the fitted model are significantly similar to the real experimental values. To maintain consistency between solutions, the GA only accepts solutions that meet the following restrictions: R1:Powidle i,j<Powi,j≤T DPi,j·1.5 (12) R2:Powmaster ≤T DPmaster ·1.5 (13) R3:Powswitch ≤T DPswitch ·1.5 (14) The R1 constraint ensures that the instantaneous power of an idle device is lower than when the device is active. Moreover, all these restrictions have in common that the instantaneous power of a device does not exceed 150% of its Thermal Design Power (TDP). This decision is due to the fact that the TDP of a device can be exceeded under certain circumstances. For example, in Intel [ 37 ] processors, this value can be exceeded during Intel ® Turbo Boost or certain workload types such as Intel ® Advanced Vector Extensions (Intel ® AVX) for a limited time, until the processor hits a thermal throttle temperature, or until the processor hits a power delivery limit. However, since manufacturers do not usually indicate the maximum peak energy consumption of their devices, a 150% restriction for the TDP has been established since Hennessy et al. state in [ 1 ] that its value could be increased by up to 1.5 times. Finally, for the sake of reproducibility, the configuration for the GA can be found in Table 1, which uses a real encoding for the optimised model parameters. 6. Experimental Work The main tasks addressed in this section are to evaluate the fitting of the proposed model, to compare it with the one provided in [ 33 ], and to validate it. To make a fair comparison, the application to be modelled and the energy-time experimental data used in this work to fit the model are the same as those used in the baseline paper. The source code of the modelled application can be found in [38]. 6.1. Experimental Methodology The evaluation pipeline is as follows, where Points 1 and 2, necessary to obtain the experimental data, were already carried out in [33]: 6 Individuals Number (N) 3,840 Chromosome representation Binary Subpopulations Number (NS p) 1 to 32 Size (SS p)N/NS p Evolution Number of generations (g) 150 Global migrations (NGm) 5 Crossover Type Uniform Probability (α) 0.75 Mutation Type Bit-flip Probability (β) 0.0025 Table 2: Input values of the NSGA-II algorithm used in the modelled application. 1. Run the modelled application multiple times, varying the number of subpopulations from 1 to 32. The rest of the input values remain constant (see Table 2). All experiments are repeated 20 times to obtain more reliable measurements on the application’s behaviour. 2. While the application is running, both the runtime and the energy consumption of the cluster are measured. Time is measured as the time taken by the algorithm to finish the evolution of all the subpopulations after g generations, including the recombination of subpopulations carried out by the master node. Energy has been measured using a physical wattmeter for each cluster node. 3. Finally, the experimental energy-time data collected are used by the GA proposed in Section 5 to fit the model parameters. As in Point 1, the algorithm is executed 20 times due to its stochastic behaviour. 6.2. Experimental Setup The cluster used in [ 33 ] to obtain the experimental energytime data contains four heterogeneous Non-Uniform Memory Access (NUMA) nodes that execute CentOS (v7.4.1708). The modelled application is coded in C++ and has been compiled with the GNU Compiler Collection (GCC) v4.8.5 and optimisation level -O2 . The OpenMPI library v1.10.7 supports the Message Passing Interface (MPI) v3.0.0. The procedure evaluates 3,840 individuals, distributed between 1 to 32 subpopulations (depending on the run), along 150 generations. During execution, Node 1 is dedicated to the master process while others act as workers. The energy consumption was measured for each node and the switch using a wattmeter that calculates both instantaneous power (W) and accumulated energy (W · h) every second. The GA developed in this work to fit the model with the collected energy-time data has been developed by using the Distributed Evolutionary Algorithms in Python (DEAP) library [ 39 ]. It is worth mentioning that the versions of CentOS, MPI and GCC are relatively old. This is because we want to compare the results under the same experimental conditions as those used in the baseline paper, several years ago (2019). 6.3. Use Case Application As mentioned at the beginning of Section 6, the application used here to evaluate the new model is the same as the one End? Final recombination Node 1 2x CPU 1x GPU Node 2 1x CPU 1x GPU Node 3 2x CPU 1x GPU Master Process 0 Process 1 Process 2 Process 3 WA WA Level 1 (Distribution by nodes) Copy 𝑆𝑆𝑆𝑆𝑁𝑁𝐷𝐷 onto device Fitness evaluation Non-dominated sorting Replace subpopulation Crossover & mutation Dataset and centroids Pre-processing and initialization of the devices OpenMP threads 𝑆𝑆𝑆𝑆1 𝑆𝑆𝑆𝑆2 𝑆𝑆𝑆𝑆𝑁𝑁𝐷𝐷 Worker Algorithm WA Figure 1: The use case application. MPI-OpenMP scheme that shows the first and second parallelism levels. modelled in [ 33 ]. It corresponds to a wrapper approach where a Non-dominated Sorting Genetic Algorithm (NSGA-II) [ 40 ] evolves one or multiple subpopulations of individuals along several generations. The application includes a parallel masterworker scheduler that dynamically distributes individuals among the CPU-GPU devices of each computing node. It deals with an Electroencephalogram (EEG) classification problem in which the individuals codify different alternatives for feature selection and are evaluated through K -means algorithm. As the fitness evaluation is independent for each individual, the individuals are distributed among the computing devices according to a masterworker scheme too, which provides up to four parallelism levels depending on the device used to perform the task. The different levels of parallelism and workload distribution are summarised below. For more details, see [33]: 1. First level: distribution of subpopulations among the cluster nodes (Figure 1, bottom). All communications between nodes are done through message-passing with the MPI standard. 2. Second level: dynamic distribution of subpopulations among devices of the same node by using OpenMP threads 7 Level 4 (K-means) Yes CU Core Core Core Subpopulations? Subpopulations scheduling No Individuals scheduling Level 2 (Distribution by devices) CU CU Level 3 (Distribution by CUs/cores) 𝑆𝑆𝑆𝑆 = {𝑆𝑆𝑆𝑆1,𝑆𝑆𝑆𝑆2,…,𝑆𝑆𝑆𝑆𝑁𝑁𝑆𝑆𝑆𝑆}𝑆𝑆𝑆𝑆1= {𝑆𝑆𝑆𝑆1,1,𝑆𝑆𝑆𝑆1,2,…,𝑆𝑆𝑆𝑆1,𝑆𝑆𝑆𝑆𝑆𝑆 } 𝑆𝑆𝑆𝑆1,1…𝑆𝑆𝑆𝑆?,𝑆𝑆𝑆𝑆𝑆𝑆 𝑆𝑆𝑆𝑆?,1…𝑆𝑆𝑆𝑆𝑁𝑁𝑆𝑆𝑆𝑆,𝑆𝑆𝑆𝑆𝑆𝑆 𝑆𝑆𝑆𝑆1,? …𝑆𝑆𝑆𝑆1,𝑆𝑆𝑆𝑆𝑆𝑆 𝑆𝑆𝑆𝑆1,1…𝑆𝑆𝑆𝑆1,? Fitness evaluation Figure 2: The use case application. Evaluation of the fitness in the devices, which provides the third and fourth parallelism levels. (Figure 1, top: fitness evaluation, which is detailed in Figure 2). If there is only one subpopulation, the scheduler will distribute its individuals dynamically to each device. Currently, CPU and GPU devices are supported. 3. Third level: dynamic distribution of individuals among CPU cores and the GPU Compute Units (CUs) (Figure 2). In other words, each CU/core is in charge of evaluating an individual through a K -means algorithm, which has been parallelized with OpenMP on CPU and OpenCL on GPU. Using OpenMP for CPU is motivated by the ease of implementation, since with a single directive, it is possible to distribute the loop that iterates over the list of individuals. 4. Fourth level: GPU data parallelism in K -means (Figure 2). The Euclidean distances between each point and the centroids are parallelized by the work-items (threads) of the same CU. The application works as follows: a master MPI process is responsible for asynchronously distributing subpopulations among nodes and migrating individuals between subpopulations after a certain number of generations. In addition to this, the workers perform all the evolutionary steps of each subpopulation. After starting the MPI communications with the master, a worker requests the master as many subpopulations as devices are present in its node. The purpose of reducing idle states is to make all nodes busy as soon as possible. However, the worker node could receive a chunk of subpopulations less than or equal to the one indicated in the request if there are not enough subpopulations to be distributed. If this is not the case, once all workers are computing, the master waits for new requests. As each worker has already assigned work, a new request involves receiving only one subpopulation and sending another if available. The loop ends when all subpopulations have evolved. Then, the master merges all subpopulations to perform the next subpopulation set. 6.4. Model Fitting Results The best fitting is the vector (NRMS ET,NRMS EE) that provides the smallest Euclidean distance concerning the origin point, (0,0) . Here, the NRMSE (Normalised Root-Mean-Square Error) for time and energy is calculated as the RMSE divided by the standard deviation of the measured values when executing the application varying NS p from 1 to 32 subpopulations: NRMS ET=RMS ET std Tcluster ;∀NS p =1,...,32(15) NRMS EE=RMS EE std Ecluster ;∀NS p =1,...,32(16) The 20 repetitions of the fitting result in a set of 20 individuals that report low fitness, with mean and deviation values of NRMS ET =0 . 089 ± 0 . 012 and NRMS EE =0 . 139 ± 0 . 031. Hence, our method is capable of overall returning fairly well fitted solutions. Moreover, when picking the most accurate solution from the 20 fitted ones, the best individual achieves fitness values of NRMS ET =0 . 081 and NRMS EE =0 . 091. This means that the fitting exceeds greatly that obtained in the baseline study [ 33 ], whose best prediction results were NRMS ET =0 . 213 and NRMS EE =0 . 256. Both fittings are visually compared in Figure 3. As it can be seen, the values predicted by the new model closely follow the experimentally measured data for any number of subpopulations. Although the baseline model fitting has a similar trend, it does not correctly predict runtime and energy consumption for subpopulations 18 to 24. From that point on, it also shows an irregular prediction trend. Therefore, using a genetic algorithm and a non-linear model is an accurate approach to capture the heterogeneous behaviour of the cluster. Indeed, we have obtained similar results using the Particle Swarm Optimisation (PSO) algorithm ( NRMS ET =0 . 104 and NRMS EE =0 . 113). However, in order not to extend this paper too much, only the analyses related to the GA will be shown from now on. In summary, our methodology demonstrates its suitability in the path towards more complex models where features such as dynamic workload distribution or programs’ hyperparameters play a major role. 6.5. Model Validation Results Since the fitting method explores the parameter space scattered, all fittings have been repeated 20 times. The Relative Standard Deviation (RSD) for the p -th parameter of a chromosome, RS Dp, has been used to measure the dispersion: RS Dp=std (pr;∀r=1,...,20) mean (pr;∀r=1,...,20)·100 (17) where pr represents the r -th fitting (repetition) of the p -th parameter. The mean values and RSD of the 22 fitted parameters are displayed in Table 3. As it can be seen, most of the deviations are acceptable if the dynamic nature of the cluster is taken into account, except for Powidle 3,1 , Powidle 3,2 , and Tcom . Nevertheless, these three parameters do not seem to have an appreciable impact on NRMS ET and NRMS EE . It must be considered that the time 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 Number of subpopulations 0 50 100 150 200 250 300 350 400 450 Runtime (s) Baseline model Experimental data Proposed model (a) Runtime fitting 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 Number of subpopulations 0 10 20 30 40 50 60 70 80 Energy consumption (W · h) Baseline model Experimental data Proposed model (b) Energy consumption fitting Figure 3: Comparison between the energy-time fitting of the baseline model and the one proposed in this work when increasing the number of subpopulations. For most cases, the proposed model fits the experimental data better than the baseline model [33]. needed for communication is quite low. Regarding Powidle 3,1 and Powidle 3,2 , they present large deviations. This means that the values of the parameters are spread out in the solution search space, and therefore they may have different optimal values: as the use case application works through a dynamic master-worker scheme, the devices will always be busy and will only be idle during a migration, which is done in a short time. Thus, for this particular application, it could be stated that the instantaneous powers of the devices in an idle state are not essential for the model, although they must be included to obtain the best results. Besides, there is an explanation for the fact that some active instantaneous powers also have considerable deviations: the 20 experimental values collected from the cluster, used to fit the model, present disparate mean values. This could be due to a combination of the following factors: 1. Between iterations, the workload assigned to a device is variable, impacting the time the device is active or idle. The crossover probability, for example, affects the number of individuals to be evaluated in each generation. 2. It has been observed that the percentage of use of the CPUGPU devices when executing the case use application is not always 100%, probably due to the sequential parts of the algorithm. Since the percentage is variable, so it will be the instantaneous power. 3. In the GA used to fit the parameters, there is no restriction to establish a minimum instantaneous power higher than zero. Consequently, the model offers very low power values as solutions that will never correspond to the real ones. Values close to the TDP are unrealistic, too. There is no solution to this problem for now since CPU and GPU manufacturers only report the maximum consumption (TDP) and rarely indicate the minimum. Assuming that small deviation values are those less than 10%, the parameters whose fitted values converge in the same region are: (i) Powmaster , (ii) those related to the devices of Node 1, and (iii) those related to CPU of Node 2. The good fitting of these parameters could be due to the lack of good solutions in other regions of the search space. This hypothesis arose after verifying 9