Skip to Main content Skip to Navigation

Efficient, non obstructive scheduling on computing grids using virtual execution environments

Abstract : In the last decade, computing grids have brought together storage and servers located across multiple institutions to support large-scale scientific applications. By analogy with power grids, the original idea is to provide with seamless computing power anyone who plugs in. However, as applications increase in demand and multiply, the efficiency of the underlying resource allocation mechanisms deserves attention. This thesis presents the following contributions. - We identify resource allocation patterns in grids and we compare them to resource allocation patterns on single clusters. - We identify a common pattern (Late Binding) in the way that several applications have recently bypassed the mainstream grid mechanism (Metascheduling) in order to take more control for better perceived performance. - We propose a new pattern (Symmetric Mapping) that achieves separation of control between multiple participants in resource allocation. - We propose a new formal model to specify resource allocation strategies. This model allows to represent dynamic scheduling under multiple constraints and objectives. - We transpose the problem of Multiple Administrative Domains (MADs) from the area of fault tolerance to the area of distributed computing; we identify it as distinctive of grids among other computing systems; and we identify Symmetric Mapping as a solution. - We propose an implementation of Symmetric Mapping based on virtual machines. As part of the implementation, we propose a system that deploys and manages multiple virtual machines based on declarative descriptions. - We propose a system that detects service termination and resumes discontinued services on newly elected servers, in order to maintain an implementation of Symmetric Mapping, or any system that requires permanent services on transient servers. - We propose a new method to analyze tasks and predict cache performance on various servers, in order to dynamically match tasks to adequate heterogeneous computing resources such as obtained on a grid. The method relies on fitting memory access patterns with well known probability distributions. The task signature is reduced to constant size and prediction is reduced to constant time. - We propose the first evaluation of cache thrashing, in order to make realistic performance predictions for time-shared CPUs. The analysis is based on a new Markov model of LRU caches. It yields a lower and a higher bound of the cache miss ratio in presence of competing processes.
Document type :
Complete list of metadatas

Cited literature [162 references]  Display  Hide  Download
Contributor : Grehant Xavier <>
Submitted on : Thursday, February 24, 2011 - 8:34:01 PM
Last modification on : Tuesday, October 20, 2020 - 10:23:18 AM
Long-term archiving on: : Saturday, December 3, 2016 - 6:09:48 AM


  • HAL Id : pastel-00569373, version 1



Grehant Xavier. Efficient, non obstructive scheduling on computing grids using virtual execution environments. Performance [cs.PF]. Télécom ParisTech, 2010. English. ⟨pastel-00569373⟩



Record views


Files downloads