Blacklist muti-objective genetic algorithm for energy saving in heterogeneous environments

The computing requirements of modern scientific applications are growing continuously, as is the amount of data to process. The use of more sophisticated and scalable infrastructure becomes necessary to cover these requirements. Different architectural environments, such as Federated Clusters, Grid infrastructures or Cloud computing, are examples of federated resource environments, where computing resources in different administrative domains work together to solve a problem [1, 2].

In this work, we focus on scheduling in Federated Cluster environments. These environments allow the execution of parallel applications in which the computing resource requirements exceed the resources available in a single cluster. Thus, parallel applications can be co-allocated to different clusters, sharing computation and communication resources. Co-allocation favor the reduction of internal cluster fragmentation, thus improving resource usage and increasing job throughput as the applications can reduce its waiting times [2, 3]. However, mapping jobs across cluster boundaries can result in rather poor overall performance when co-allocated jobs contend for inter-cluster network bandwidth.

Beside this, the high energy consumption from the large-scale use of computing resources translates into high energy cost and carbon emissions which are not environmentally sustainable. Hence, there is an urgent need for energy-efficient solutions that redefine our way of using computing resources. Recent research has been able to determine the quantity of resources to be used based on load predictions, QoS requirements, etc., or dynamically redefine the voltage supply based on the workload. Nonetheless, a major factor in efficient resource utilization is the proper mapping and scheduling of parallel jobs among the computing processors.

The problem of scheduling parallel jobs within a heterogeneous distributed resource environment is known to be NP-hard [4, 5], therefore, the use of heuristics and meta-heuristics is the best approach to cope with its difficulty. Current research is focused on minimizing the energy consumed by the processors together with the minimization of job completion time, flowtime, resource usage, etc, [6]. The motivation of this work is to provide a meta-heuristic technique able to obtain scheduling decisions efficiently considering resource heterogeneity and parallel application requirements within federated environments. The contribution of this paper is a novel scheduling approach based on a multi-objective Genetic algorithm (GA) which uses a weighted blacklist to determine dynamically, for each application, a clusterization of forbidden resources. The algorithm not only generates an optimal mapping of applications to resources but also a scheduling to complete the workload in a minimum period of time as well as utilizing the resources in an efficient way.

The remainder of this paper is organized as follows. Section 2 presents related work. The proposed genetic algorithm is elaborated in Sect. 3. Section 4 demonstrates the performance analysis and simulation results for real workload traces. Finally, the conclusions are presented in Sect. 5.

Scheduling strategies in heterogeneous distributed environments have generated great interest in recent years due to the growth of resources in organizations. The potential benefit of sharing computing resources among federated sites has been widely discussed in previous research [1, 2, 7]. Bucur et al. [2] carried out a performance evaluation of different scheduling strategies using co-allocation based on job queues. Their results show that unrestricted co-allocation is not recommended and performance is improved by correctly adjusting the component size of the co-allocated jobs. Other studies used co-allocation to develop load balancing techniques [8, 9] or optimize the application execution time by selecting the most suitable resources [4, 10].

Traditional scheduling techniques in the literature treat the jobs in the waiting queue individually without considering the remaining jobs in the batch queue [11], thus limiting the scheduling opportunities for future allocations and decreasing overall system performance. Shmueli et al. [12] proposed a backfilling technique in which later jobs are packaged to fill in holes and increase utilization without delaying the earlier jobs. Tsafrir et al. [13] proposed a method to select the most suitable jobs to be moved forward based on system-generated response time predictions. These techniques, however, are based on the job arrival order, only moving jobs forward that accomplish specific deadline requirements. Blanco et al. [14, 15] proposed diverse techniques for determining the best scheduling of sets of job packages, proposing a new job execution order to minimize their overall execution time, based on a Mixed-Integer programming model. Due to the intractable nature of the problem, it is desirable to explore other avenues for developing good heuristic algorithms for the problem.

Some nature-inspired meta-heuristics, such as Simulated Annealing (SA), Genetic Algorithms (GA) and Particle Swarm Optimization (PSO), have been presented as effective schedulers in complex large-scale environments in attempts to obtain pseudo-optimal solutions in practical times for large-scale environments. GAs are well known for their robustness and have been applied successfully to solve scheduling problems in a variety of fields. Zomaya and Teh [16] used GAs in dynamic load balancing problems. Braun et al. [11] compared the efficiency of a simple GA-based scheduler and the MinMin, MinMax, Minimum Completion Time (MTC) algorithms. Carretero and Xhafa presented in [17] an extensive study of GAs for designing efficient Grid schedulers where makespan and flowtime are minimized to include QoS in the solutions, but considering independent jobs without inter-cluster communications. Gabaldon et al. [18] presented a GA-based scheduling meta-heuristic able to optimize the makespan together with the flowtime, thus providing a certain level of QoS from the users point of view.

Beside this, energy consumption has become a great challenge in the field of high performance computing, because of various concerns such as cost, environmental sustainability, and system performance. Two primary methods are commonly used: switching off underutilized resources [19‐21] or using voltage and frequency scaling (VFS) techniques [6, 22‐24]. Cocaña et al. [19] presented a software tool that predicts the future node requirements using a machine-learning approach, and then stopping those that will not be required in the near future. Chae et al. [20] illustrate a method of determining the aggregate system load and the minimal set of computational resources that can process the workload. Orgerie et al. in [21] present a three-step strategy based on a framework able to control the computing requirements by switching the unused nodes off, predicting their usage to switch on them again and finally aggregating some reservations to avoid frequent on/off cycles. Christobel et al. in [6] proposed an energy-aware scheduling approach for scientific workflows based on Particle Swarm Optimization and Dynamic Voltage Scaling. Kolodziej et al. in [22] and Kim et al. in [23] address independent batch scheduling in computational grids as a bi-objective global minimization problem with makespan and energy consumption criteria, using a VFS model directed by a GA-based grid scheduler.

Our proposal differs from research works [6, 19‐23] in two main aspects. We propose optimizing makespan and energy consumption at the level of the scheduler. Once the required computational nodes are identified, we treat the scheduling process not only to determine the job co-allocation to the computing resources but also to define the best execution order for parallel applications in the batch queue. We also deal with federated clusters environments, which are distinguished from Grid environments by the use of a dedicated interconnection network between cluster resources with a known topology and predictable performance characteristics.

In this paper, the main contribution is the implementation of a Multi-Objective GA-based scheduling algorithm, named MOGA, based on a weighted blacklist to determine the resource unavailability during the mapping process for a set of parallel jobs to be scheduled. Our proposal avoids the systematic allocation of jobs to resources with minimum consumption or maximum computational capacities, as is usual in the literature, providing new scheduling opportunities for the remaining jobs in the system queue, thus optimizing the energy consumption and the makespan.

A GA is a search heuristic to find near-optimal solutions using nature-based techniques. It starts by creating an initial population of solutions known as individuals, each one encoded using a chromosome. Four steps are carried out to create a new generation: ranking the individuals driven by a fitness function, selection, crossover of the selected individuals and mutation. The algorithm is motivated by the hope that after several generations, the new population will be better than the older ones.

In an earlier work [18], the authors presented GA-MF, a GA-based technique with the aim of increasing the system throughput for batch workloads, using the makespan and flowtime as the optimization criteria. Due to the increasing importance of developing energy-aware systems to reduce the environmental footprint, the authors propose a new multi-objective GA, named MOGA, focused on reducing both energy consumption and makespan.

The makespan (Eq. 1) is defined as the elapsed time between the submission of the first job until the finalization of the last one:where \(F_i\) is the finish time of the job i, calculated as \(F_i=S_i+T_i\); \(T_i\) is the execution time of the job i; and \(S_i\) is the starting time of the job i. The execution time of a job in an heterogeneous federated cluster is calculated using the model presented in [18], where resource heterogeneity and network saturation is considered.

The energy consumption is modeled by Eq. 2.where \(C_{n}\) is the energy consumed by node n when it is computing, \(I_{n}\) when it is idle, \(CT_{n}\) is the computing time of the node n and \(IT_{n}\) is its idle time. Both models are related because of their dependency on the job execution time, thus trying to minimize one of them could have negative effects on the other one.

The first decision in developing a GA is the chromosome design used to represent the individuals in the population. The individual representation we designed is made up of two parts: the first part represents the order the jobs are going to be executed in the system; the second part is a weighted blacklist representing the resource unavailability for each job. The blacklist (BL) is implemented for each job as a list of real numbers, where each value is in the range [0, 1]. This value represents the percentage of cluster nodes forbidden from the allocation of the corresponding job, providing a reservation mechanism for further jobs on the queue. To illustrate our proposed individual design, we present the following example:

The method to create the job scheduling is described in Algorithm 1. For every job in the set of jobs, and for every task in the job, a node in the list of free nodes is selected, taking into account the availability given by the blacklist, which is configured by the MOGA based on the optimization of both criteria energy and makespan. The method first searches for the most powerful nodes (lines 2–5), where Power(n) is the computational power for node n. Note that for parallel jobs, the execution time is given by the slowest computational node selected. Then, the method tries to shift the tasks from powerful nodes to available slow nodes if the execution time remains the same, which may free up the assigned powerful nodes (lines 6–12). The solution is a list of assignments of every task to a node.

If we run out of computational nodes in the allocation process, MOGA predicts the first job to finish using the job execution model presented in [18] and then releases the allocated nodes for the subsequent jobs.

At each iteration, MOGA selects the best individuals placed on the non-dominated Pareto fronts using the NSGA-II algorithm [25]. To evolve to a new population, the crossover affects the two components of the individual representation maintaining some similarities with the parents:Finally, a mutation operator is applied to maintain the diversity across the generations. This process is applied in both components of the chromosome with a probability defined by the Mutation Frequency parameter: for the Order component, two randomly selected jobs from the list are swapped; for the Allocation component, a value from the blacklist is exchanged for a new random value.

In this section, we conducted an experimental study with the aim of analyzing the reduction in makespan and energy consumption obtained by applying the proposed MOGA scheduling technique, which was implemented using the Non-dominated Sorting Genetic Algorithm II (NSGA-II) [25] and also prove its robustness and efficiency. The experimentation was carried out by simulation, using the Gridsim simulator [26] configured to emulate a Federated Cluster environment made up of 4 different clusters. The characteristics of each cluster are shown in Table 1. The consumptions of the computing nodes were defined using the study done by Orgerie et al. in [21].

To process the experimental study, 30 different job-sets corresponding to one month of execution time were selected, and each was processed 30 times. These job-sets were extracted from real cluster traces in the workloads HPC2N, RICC and CEA CURIE described by Feitelson [27].

The most relevant characteristics of these traces are:

In the present paper, a Multi-Objective Genetic Algorithm (MOGA) is presented to efficiently obtain an efficient scheduling process taking into account not only optimization of the global makespan, but also reduction of energy consumption. Our proposal was developed using a novel technique based on a resource allocation blacklist that has the ability to forbid access to some computational nodes, providing a reservation mechanism for those jobs with computational requirements that can provide higher benefits.

The experimental study was carried out by simulation and was conducted with real workload traces in a heterogeneous federated cluster environment. The MOGA results were compared with other techniques in the literature and demonstrated its capability to obtain better results while optimizing both objectives, makespan and energy efficiency. Furthermore, the solutions provided had lower dispersion results allowing us to conclude that the robustness of MOGA does not depend on the nature of the workloads.

MOGA is focused on the low-level scheduling process, which relates the job to resources allocation. Accordingly, in future work, we aim to combine our proposal with high-level strategies that predict the minimal set of computational resources to deal with a future workload.