Multi-objective evolutionary algorithms for energy-aware scheduling on distributed computing systems

in Applied Soft Computing (2014), 24

The ongoing increase of energy consumption by IT infrastructures forces data center managers to find innovative ways to improve energy efficiency. The latter is also a focal point for different branches ... [more ▼]

The ongoing increase of energy consumption by IT infrastructures forces data center managers to find innovative ways to improve energy efficiency. The latter is also a focal point for different branches of computer science due to its financial, ecological, political, and technical consequences. One of the answers is given by scheduling combined with dynamic voltage scaling technique to optimize the energy consumption. The way of reasoning is based on the link between current semiconductor technologies and energy state management of processors, where sacrificing the performance can save energy. This paper is devoted to investigate and solve the multi-objective precedence constrained application scheduling problem on a distributed computing system, and it has two main aims: the creation of general algorithms to solve the problem and the examination of the problem by means of the thorough analysis of the results returned by the algorithms. The first aim was achieved in two steps: adaptation of state-of-the-art multi-objective evolutionary algorithms by designing new operators and their validation in terms of performance and energy. The second aim was accomplished by performing an extensive number of algorithms executions on a large and diverse benchmark and the further analysis of performance among the proposed algorithms. Finally, the study proves the validity of the proposed method, points out the best-compared multi-objective algorithm schema, and the most important factors for the algorithms performance. [less ▲]

Energy Savings on a Cloud-based Opportunistic Infrastructure

in Service Oriented Computing ICSOC 2013 Workshops (2014)

In this paper, we address energy savings on a Cloud-based opportunistic infrastructure. The infrastructure implements opportunis- tic design concepts to provide basic services, such as virtual CPUs, RAM ... [more ▼]

In this paper, we address energy savings on a Cloud-based opportunistic infrastructure. The infrastructure implements opportunis- tic design concepts to provide basic services, such as virtual CPUs, RAM and Disk while profiting from unused capabilities of desktop computer laboratories in a non-intrusive way. We consider the problem of virtual machines consolidation on the oppor- tunistic cloud computing resources. We investigate four workload packing algorithms that place a set of virtual machines on the least number of physical machines to increase resource utilization and to transition parts of the unused resources into a lower power states or switching off. We em- pirically evaluate these heuristics on real workload traces collected from our experimental opportunistic cloud, called UnaCloud. The final aim is to implement the best strategy on UnaCoud. The results show that a consolidation algorithm implementing a policy taking into account fea- tures and constraints of the opportunistic cloud saves energy more than 40% than related consolidation heuristics, over the percentage earned by the opportunistic environment. [less ▲]

Scalable, Low complexity, and fast greedy scheduling heuristics for highly heterogeneous distributed computing systems

in Journal of Supercomputing (2013)

Forheterogeneousdistributedcomputingsystems,importantdesignissues are scalability and system optimization. Given such systems, it is crucial to develop low computational complexity algorithms to schedule ... [more ▼]

Forheterogeneousdistributedcomputingsystems,importantdesignissues are scalability and system optimization. Given such systems, it is crucial to develop low computational complexity algorithms to schedule tasks in a manner that exploits the heterogeneity of the resources and applications. In this paper, we report and evalu- ate three scalable, and fast scheduling heuristics for highly heterogeneous distributed computing systems. We conduct a comprehensive performance evaluation study us- ing simulation. The benchmarking outlines the performance of the schedulers, rep- resenting scalability, makespan, flowtime, computational complexity, and memory utilization. The set of experimental results shows that our heuristics perform as good as the traditional approaches, for makespan and flowtime, while featuring lower com- plexity, lower running time, and lower used memory. The experimental results also detail the various scenarios under which certain algorithms excel and fail. [less ▲]

Energy-aware VM allocation on An Opportunistic Cloud Infrastructure

in Proceedings of the 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing (2013)

UnaCloud is an opportunistic based cloud infras- tructure (IaaS) that allows to access on-demand computing capabilities using commodity desktops. Although UnaCloud maximizes the use of idle resources to ... [more ▼]

UnaCloud is an opportunistic based cloud infras- tructure (IaaS) that allows to access on-demand computing capabilities using commodity desktops. Although UnaCloud maximizes the use of idle resources to deploy virtual machines, it does not use energy-efficient resource allocation algorithms. In this paper, we design and develop different energy-aware algorithms to operate in an energy-efficient way and at the same time to guarantee the performance of the UnaCloud users. Performance tests with different algorithms and scenarios using real trace workloads from UnaCloud, show how different policies can change the energy consumption patterns and reduce the energy consumption in the opportunistic cloud infrastructure. The results show that some algorithms can reduce the energy-consumption power up to 30% over the percentage earned by the opportunistic environment [less ▲]

A survey on resource allocation in high performance distributed computing systems

in Parallel Computing (2013), 39(11), 709-736

An efficient resource allocation is a fundamental requirement in high performance computing (HPC) systems. Many projects are dedicated to large-scale distributed computing systems that have designed and ... [more ▼]

An efficient resource allocation is a fundamental requirement in high performance computing (HPC) systems. Many projects are dedicated to large-scale distributed computing systems that have designed and developed resource allocation mechanisms with a variety of architectures and services. In our study, through analysis, a comprehensive survey for describing resource allocation in various HPCs is reported. The aim of the work is to aggregate under a joint framework, the existing solutions for HPC to provide a thorough analysis and characteristics of the resource management and allocation strategies. Resource allocation mechanisms and strategies play a vital role towards the performance improvement of all the HPCs classifications. Therefore, a comprehensive discussion of widely used resource allocation strategies deployed in HPC environment is required, which is one of the motivations of this survey. Moreover, we have classified the HPC systems into three broad categories, namely: (a) cluster, (b) grid, and (c) cloud systems and define the characteristics of each class by extracting sets of common attributes. All of the aforementioned systems are cataloged into pure software and hybrid/hardware solutions. The system classification is used to identify approaches followed by the implementation of existing resource allocation strategies that are widely presented in the literature. [less ▲]

Energy-Aware Scheduling on Multicore Heterogeneous Grid Computing Systems

in Journal of Grid Computing (2013), 11

We address a multicriteria nonpreemptive energy-aware scheduling problem for computationalGrid systems. This work introduces a new formulation of the scheduling problem for multicore heterogeneous ... [more ▼]

We address a multicriteria nonpreemptive energy-aware scheduling problem for computationalGrid systems. This work introduces a new formulation of the scheduling problem for multicore heterogeneous computational Grid systems in which the minimization of the energy consumption, along with the makespan metric, is considered. We adopt a two-level model, in which a meta-broker agent (level 1) receives all user tasks and schedules them on the available resources, belonging to different local providers (level 2). The computing capacity and energy consumption of resources are taken from real multi-core processors from the main current vendors. Twenty novel list scheduling methods for the problem are proposed, and a comparative analysis of all of them over a large set of problem instances is presented. Additionally, a scalability study is performed in order to analyze the contribution of the best new bi-objective list scheduling heuristics when the problem dimension grows. We conclude after the experimental analysis that accurate trade-off schedules are computed by using the new proposed methods. [less ▲]

Green Flexible Opportunistic Computing with task consolidation and virtualization

in Cluster Computing (2012)

Energy efficiency and high computing power are basic design considerations across modern-day computing solutions due to different concerns such as system perfor- mance, operational cost, and environmental ... [more ▼]

Energy efficiency and high computing power are basic design considerations across modern-day computing solutions due to different concerns such as system perfor- mance, operational cost, and environmental issues. Desktop Grid and Volunteer Computing System (DGVCS) so called opportunistic infrastructures offer computational power at low cost focused on harvesting idle computing cycles of ex- isting commodity computing resources. Other than allow- ing to customize the end user offer, virtualization is consid- ered as one key techniques to reduce energy consumption in large-scale systems and contributes to the scalability of the system. This paper presents an energy efficient approach for opportunistic infrastructures based on task consolidation and customization of virtual machines. The experimental re- sults with single desktops and complete computer rooms show that virtualization significantly improves the energy-efficiency of opportunistic grids compared with dedicated computing systems without disturbing the end-user. [less ▲]

On the Energy Optimization for Precedence Constrained Applications using Local Search Algorithms

in International Conference on High Performance Computing and Simulation (HPCS), 2012 (2012, July 02)

We investigate the problem of scheduling precedence constrained applications on a distributed heterogeneous computing system with the aim of minimizing schedule length and reducing energy consumption. We ... [more ▼]

We investigate the problem of scheduling precedence constrained applications on a distributed heterogeneous computing system with the aim of minimizing schedule length and reducing energy consumption. We present a scheduling algorithm based on the best-effort idea that promotes local search algorithms and dynamic voltage scaling to reduce energy consumption. The final goal is to maintain a given performance while minimizing energy use. The proposed approach first uses a list-based scheduling algorithm to find near-optimal solutions for schedule length, then local search algorithms with dynamic voltage scaling are applied to reduce energy consumption. However the algorithm it's not allowed to deteriorate the schedule length computed by the best-effort algorithm. We discuss simulation results obtained with sets of real-world applications that emphasize the interest of the approach. [less ▲]

Designing a Self-organized Approach for Scheduling Bag-of-Tasks

in Designing a Self-organized Approach for Scheduling Bag-of-Tasks (2012)

This paper proposes a decentralized and self-organized agent system for dynamically load-balancing tasks arriving in the form of Bags-of-Tasks (BoTs) in large-scale decentralized systems. The approach is ... [more ▼]

This paper proposes a decentralized and self-organized agent system for dynamically load-balancing tasks arriving in the form of Bags-of-Tasks (BoTs) in large-scale decentralized systems. The approach is inspired by the emergent behavior of the sandpile model; a cellular automaton behaving at the edge of chaos. Depending on the state of the cellular automaton, rather different responses may occur when a new task is assigned to a resource. It may change nothing or generate avalanches that reconfigure the state of the system. The proportion between the abundance of avalanches and their sizes shows a power-law relation, a scale-invariant behavior that does not need to be tuned. That means that large –catastrophic– avalanches are very rare but small ones occur very often. Such a smart and emergent behavior fits well with the idea of non-clairvoyant scheduling, where tasks are load balanced into computing resources trying to maximize the performance but without assuming any knowledge on the tasks features. In order to study the viability of the approach, we have conducted an empirical experimentation which shows that the sandpile is able to find near-optimal schedules by reacting differently to different conditions of workloads and architectures. [less ▲]

A two-phase heuristic for the energy-efficient scheduling of independent tasks on computational grids

in Cluster Computing (2012)