Le 05/03/2008 par sadaz :

Research Master Proposal
Supervizers: Pascal Bouvry (Pascal.Bouvry@uni.lu) and
Sadia Azem (Sadia.Azem@uni.lu)
Research Unit : CSC (http://csc.uni.lu)
Laboratory : ILIAS Head of Lab : Pascal Bouvry
Location : University of Luxembourg,
6 rue Coudenhove Kalergi, 1359 Luxembourg, Luxembourg
Starting date : asap
Duration : 3 to 6 months
Training allocation : 850 euros/months

Context:

This study is about heterogeneous computing (HC) systems composed of interconnected machines with different capabilities and which objective is to satisfy matching and scheduling independent tasks and to maximize the system performance, here it is the makespan (completion time for all the tasks). The operating environment is uncertain: performance features degrade due to unpredictable events, such as higher than expected work load or inaccuracies in the estimation of task execution times and system parameters. Thus, resources should be allocated to tasks in a way that makes the system performance robust against unpredictable changes.
Resource allocation (mapping) consists on assigning (matching) each task to a machine and scheduling the tasks on each machine. It is an NP-hard problem in an HC environment. A mapping is considered to be robust with respect to specified system performance features against perturbations in given system parameters if degradation of these features is within acceptable limits when certain perturbations occur.

Objectives:

In the first part of the study, the goal is to model the static assignment of all tasks to a fixed set of machines so that the robustness of the mapping is maximized within makespan constraint.

In the second part of the study, the goal is how to model the selection of a fixed subset of machines, from different classes of machines (each class consists of machines of the same type), within a given dollar cost constraint, and the mapping of all the tasks to the subset (static mapping) in order to maximize the robustness.

Deliverables :
- Models for robust task allocations
- Algorithms (exact, deterministic ones and meta-heuristics)

Required Knowledge :

- Java /C++
- Notions of operation research and mathematical modeling
- Basic knowledge of genetic algorithms