Search

Server consolidation and resource elasticity are among two of the most important resource management features in cloud and edge computing. One of two forms of elasticity is often adopted. While horizontal elasticity is concerned with the acquisition and release of computational nodes in accordance with demand, vertical elasticity focuses on the distribution of a node's resources among its hosted virtual machines (VMs) or containers, by adjusting the capacity of the resource types allocated to each individual VM in accordance with its respective application's needs. In the case of vertical elasticity, when insufficient resources are available to allocate to a given VM, its application's performance may suffer degradation. For online applications, the only alternative is to live-migrate the VM to another server. On the other hand, when running batch jobs, the resource-constrained VM could also be suspended or saved to disk and revived elsewhere or on the same host, when resources become available. Given that memory availability has a significant influence on performance and system throughput, this paper investigates the viability of integrating VM migration, pausing and suspension schemes as part of a VM scheduling strategy to support the execution of both online and batch applications in a virtualized infrastructure employing memory elasticity. Results show that combining such schemes can provide utilization benefits for cloud service providers when memory is scarce.

This paper proposes the Makespan and Reliability Cost Driven (MRCD) heuristic, a static scheduling strategy for heterogeneous distributed systems that not only minimizes the makespan, but also maximizes the reliability of the application. The MRCD scheduling decisions are guided by a weighted function that considers both objectives simultaneously, instead of prioritizing one of them. This work also introduces a classification of the solutions produced by weighted bi-objective schedulers to aid users to tune the weighting function such that an appropriate solution can be selected in accordance with their needs. In comparison with the related work, MRCD produced schedules with makespans that were significantly better then those produced by the other strategies at expense of an insignificant deterioration in reliability.

The execution of distributed applications on the Grid is already a reality. However, as both the number of applications grow and Grids increase in scale, the efficient utilization of the available but shared heterogeneous resources will become increasingly essential to the Grid's successful maturity. Furthermore, it is unclear whether existing Grid management systems are capable of meeting this challenge. The EasyGrid middleware is a hierarchically distributed application management system (AMS) that is embedded into MPI applications to autonomously orchestrate their execution efficiently in computational Grids. The overhead of employing a distinct AMS to make each application system aware brings at least two benefits. First, the adopted policies can be tailored to the specific needs of each application, leading to improved performance. Second, distributing the management effort among executing applications makes Grid management more scalable. This article focuses on scheduling policies of an AMS for a particular class of application, describing a low intrusion implementation of a hybrid scheduling strategy designed to elicit good performance even in dynamic environments such as Grids. Using application-specific scheduling policies, near-optimal runtimes highlight the advantages of self-scheduling when executing one or more system aware applications on a Grid. Copyright © 2006 John Wiley & Sons, Ltd.

Parallel applications composed of a set of tasks that follow a partial precedence order represent an important class of scientific applications. In high performance computing, environments dedicated to scientific applications are composed of clusters of multicore machines, which consist typically of a set of processing cores that partially share a hierarchy of cache memory. Harnessing the available memory is crucial to achieve good performance in these clusters. This paper proposes strategies based on the list scheduling framework to schedule application tasks on individual cores of multicore clusters. Our idea is to minimize the execution time of the application, by taking into consideration cache contention. Experiments with a representative set of applications show that the scheduling algorithms with contention-aware mechanisms can improve significantly the application performance.

Task scheduling is a key element in achieving high performance from multicomputer systems. Efficient scheduling algorithms reduce the interprocessor communication and improve processor utilization. To do so effectively, such algorithms must be based on a communication cost model appropriate for computing systems in use. The optimal scheduling of tasks is NP-hard, and a large number of heuristic algorithms have been proposed for a range of differing scheduling conditions (graph types, granularities and cost or architectural models). Unfortunately, due both to the variety of systems available and the rate at which these systems evolve, an appropriate representative cost model has yet to be established. In this paper we study the problem of task scheduling under a LogP-type model and we present both theoretical and experimental results for a cluster-based, task duplication methodology. The model is not only representative of parallel systems but also incorporates the traditional model used by the scheduling community. Results show that, for this model, an algorithm based on this LogP scheduling methodology can generate good makespans.

While the task scheduling problem under the delay model has been studied extensively, relatively little research exists for more realistic communication models such as the LogP model which considers, in addition to latency, the cost of sending and receiving messages, and the network or link capacity. The task scheduling problem is known to be NP-complete even under the delay model (a special case of the LogP model). This paper investigates the similarities and differences between task-clustering algorithms for the delay and LogP models, and describes task-scheduling algorithm for the allocation of arbitrary task graphs to fully connected networks of processors under the LogP model. The strategy exploits the replication and clustering of tasks to minimize the ill effects of communication overhead on the makespan. A number of restrictions are presented which are used to simplify the design of the new algorithm. The quality of the schedules produced by the algorithm compare favorably with two well-known delay model-based algorithms and a previously existing LogP strategy.

In general, scheduling models only consider the message delay or latency as the dominant communication parameter. However, in many of the current generation of parallel systems, latency is negligible compared to the CPU penalties for the communication-related activities that are incurred whenever pairs of dependent tasks on distinct processors need to communicate. This work considers a model where the CPU penalty , which is associated with sending and receiving, communication events , is an additional (potentially dominant) communication parameter. A multi-stage scheduling approach (MSA) is proposed which takes both of these types communication parameters into account. This scheduling approach can be customised to classes of parallel systems according to their communication performance characteristics by varying the order in which the rules (which guide the strategy) are applied.

This paper proposes the Makespan and Reliability Cost Driven (MRCD) heuristic, a static scheduling strategy for heterogeneous distributed systems that not only minimizes the makespan but also maximizes the reliability of the application. The scheduling decisions made by MRCD are guided by a weighted function that considers both objectives simultaneously instead of prioritizing only one of the objectives. This work also introduces a classification of the solutions produced by weighted bi-objective schedulers to aid users to tune the weighting function in order to generate an appropriate solution in accordance with their needs. In comparison with related work, MRCD produced schedules with makespans that were significantly better then those produced by other strategies at expense of an insignificant deterioration in reliability.

Grid and Internet Computing have proved their worth executing large-scale bag-of-task class applications. Numerous middlewares have been developed to manage their execution in either dedicated environments or opportunistic and shared ad-hoc grids. While job dependencies are now being resolved by middleware capable of scheduling workflows, these environments have yet to be shown beneficial for message passing parallel applications. Obtaining high performance in these widely available environments without rewriting existing parallel applications is of up most importance to e-Science . The key to an efficient solution may be an alternative execution model and the efficient dynamic scheduling of application processes. This paper presents a hierarchical scheme for dynamically scheduling parallel DAG applications across a set of non-dedicated heterogeneous resources. In order to efficiently tackle process dependencies and adapt to varying system characteristics, dynamic schedulers are distributed within the application and operate in a collaborative and pro-active fashion to keep overheads low.

As grids are in essence heterogeneous, dynamic, shared and distributed environments, managing these kinds of platforms efficiently is extremely complex. Few transparent grid management systems have been developed to cope with these characteristics simultaneously and therefore both new and existing applications must be modified to execute efficiently. A promising scalable approach to deal with these intricacies is the design of self-managing or autonomic applications. Autonomic applications adapt their execution accordingly by considering knowledge about their own behaviour and environmental conditions. This paper focuses on the dynamic scheduling that provides the self-optimizing ability in autonomic applications. Being distributed, collaborative and pro-active, the proposed hierarchical scheduling infrastructure addresses important issues to enable an efficient execution in a computational grid. Unlike other approaches, the cooperative, hybrid and application-specific strategy deals effectively with task dependencies. Several experiments have been analyzed in real grid environments highlighting the efficiency and scalability of the proposed infrastructure. This paper presents an intra-site dynamic scheduling heuristic for tightly coupled parallel applications represented by DAGs.

The execution of distributed applications on the grid is already a reality. As both the number of applications grow and grids scale, efficient utilization of the available but shared heterogeneous resources will be essential. The EasyGrid middleware is a hierarchically distributed Application Management System embedded into MPI applications to facilitate their efficient execution in computational grids. The overhead of employing a distinct AMS to make each application system aware does however bring at least two benefits. First, the (scheduling) policies adopted can be tailored to the specific needs of each application leading to improved performance. Second, distributing the management effort amongst the applications themselves makes grid management more scalable. This paper describes a low intrusion implementation of a hybrid scheduling strategy designed to cope with the dynamic behaviour of grid environments. Using application-specific scheduling policies, near-optimal runtimes highlight the advantages of self-scheduling when executing one or more system aware applications on a grid.

One of the objectives of computational grids is to offer applications the collective computational power of distributed but typically shared heterogeneous resources. Unfortunately, efficiently harnessing the performance potential of such systems (i.e. how and where applications should execute on the grid) is a challenging endeavor due principally to the distributed, shared and heterogeneous nature of the resources involved. This paper presents a tool to aid the design and evaluation of scheduling policies suitable for efficient execution of parallel applications on computational grids.

While the NP-complete problem of scheduling weighted arbitrary directed acyclic graphs under the delay model has been studied extensively, comparatively little work exists for this problem under more realistic models such as the LogP model. Recently, a number of LogP-based scheduling heuristics and related works have appeared in the literature, including a task clustering algorithm design methodology which identifies four crucial design issues (Boeres et al., 1997). Through the use of five task replication-based scheduling heuristics based on this design methodology, this paper investigates the effect of various implementations of these design issues on the schedules produced for the allocation of arbitrary task graphs to fully connected networks of processors under a LogP-type model. The quality of the schedules produced by these algorithms are also compared with good, well-known delay model-based algorithms and an existing LogP strategy.

While the task scheduling problem under the delay model has been studied extensively, relatively little research exists for more realistic communication models such as the LogP model. The task scheduling problem is known to be NPcomplete even under the delay model (a simplified instance of the LogP model). This chapter describes the LogP model and the influence of its communication parameters on task scheduling. The similarities and differences between clustering algorithms under the delay and LogP models are discussed and a design methodology for clustering-based scheduling algorithms for the LogP model is presented. Using this design methodology, a task scheduling algorithm for the allocation of arbitrary task graphs to fully connected networks of processors under LogP model is proposed. The strategy exploits the replication and clustering of tasks to minimize the ill effects of communication on the makespan.

While the problem of scheduling weighted arbitrary DAGs under the delay model has been studied extensively, comparatively little work exists for this problem under a more realistic model such as LogP. This paper investigates the similarities and differences between task clustering algorithms for the delay and LogP models. The principles behind three new algorithms for tackling the scheduling problem under the LogP model are described. The quality of the schedules produced by the algorithms are compared with good delay model-based algorithms and a previously existing LogP strategy.

This paper investigates the effect of communication overhead on the scheduling problem. We present a scheduling algorithm, based on LogP-type models, for allocating task graphs to networks of processors. The makespans of schedules produced by our multi-stage scheduling approach (MSA) are compared with other well-known scheduling heuristics. The results indicate that new classes of scheduling heuristics are required to generate efficient schedules for realistic abstractions of today’s parallel computers. The scheduling strategy of MSA can also be used to generate BSP-structured programs from more abstract representations. The performance of such programs are compared with “conventional” versions.

In general, scheduling models only consider message latency as the sole dominant communication parameter. However, in many parallel systems, latency is negligible when compared to the CPU penalties associated with sending and receiving communication events. Our work considers a model in which this CPU penalty can also be a significant communication parameter. This paper focusses on analysing the effect of such a model on the scheduling of Full Binary Trees. We briefly describe a versatile, multi-stage scheduling approach that can be customised to classes of parallel systems according to their communication performance characteristics and which produces better makespans when compared with traditional techniques.

Effective tools for the design of parallel algorithms must be based on a computational model for parallel computing that is a trade-off between realism and simplicity. Where the underlying programming model requires the mapping and scheduling of tasks, the computational model should incorporate some notion of interprocessor communication delay. If the target architecture is massively parallel then a more complex model, including some notion of locality, may be required.

Computational grids aim to aggregate significant numbers of resources to provide sufficient, but low cost, computational power to various applications. Writing applications capable of executing efficiently in grids, is however extremely difficult. Their geographically distributed resources are typically heterogeneous, non-dedicated, and offer no performance or availability guarantees. This makes the collective management of resources and application both complex and arduous. This work investigates an alternative approach (based on system-awareness) to solve the problem of developing and managing the execution of grid applications efficiently. Results show that these system-aware applications are indeed faster than their conventional implementations and easily grid enabled.

The complexity of the static scheduling problem on heterogeneous resources has motivated the development of low complexity heuristics such as list scheduling. However, the greedy characteristic of such heuristics can, in many cases, generate poor results. This work proposes the integration of list scheduling heuristics with search mechanisms based on both genetic algorithms and GRASP, to efficiently schedule tasks on distributed systems. The results show that the hybrid approach is robust and can converge quickly to good quality solutions.