University of Minnesota
University Relations
myU OneStop

Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Friday, March 2, 2007

DTC Seminar Series

Bi-objective Scheduling Algorithms for Optimizing Makespan and Reliability on Heterogeneous Systems


Emmanuel Jeannot

Friday, March 2, 2007
2:00 pm

404 Walter Library

We tackle the problem of scheduling task graphs onto a heterogeneous set of machines, where each processor has a probability of failure governed by an exponential law. The goal is to design algorithms that optimize both makespan and reliability. First, we provide an optimal scheduling algorithm for independent unitary tasks where the objective is to maximize the reliability subject to makespan minimization. For the bi-criteria case we provide an algorithm that approximates the Pareto-curve. Next, for independent non-unitary tasks we provide an approximation algorithm where the objective is to maximize the reliability subject to makespan minimization. We show that the product is crucial to distinguish processors in this context. Based on this results we are able to let the user choose a trade-off between reliability maximization and makespan minimization. For general task graph we provide a method for converting scheduling heuristics on heterogeneous cluster into heuristics that take reliability into account. Here again, we show how we can help the user to choose a trade-off between makespan and reliability. Unrelated to this first part, we will take some time to describe two environments that we use for experimenting algorithms and program. First we will talk about Grid'5000 that is an nationwide distributed testbed that gathers more that 3000 CPU's on 9 different sites; and Wrekavoc that is a tool that helps to transform an homogeneous environments into an heterogeneous one.