Post-doctoral position in Computer Science and Operations research
22 06 2009The Computer Science laboratory LIP6 of UPMC (University Pierre and Marie Curie), DIGITEO DIM and the Ile de France region are offering a post-doctoral position.
Location : LIP6, 104 av du Président Kennedy 75016, Paris, France.
LIP6 website: <http://www.lip6.fr <http://www.limsi.fr/index.en.html>>
Requirements for a candidate
============================
* A PhD in Computer Science or operations research;
* Expertise in at least one of the following fields : Scheduling, load balancing, approximation algorithms.
Offered
=======
* A full time, temporary appointment for a period of 1 year;
* Starting date: october 2009;
* Monthly salary: about 2000 Euros .
Framework: ORCYMELAN Project
========================
LIP6 and PRISM jointly lead ORCYMELAN, a project aimed at investigating scheduling problems issued from the code generation for loops on VLIW architectures, taking into account new constraints induced by register pressure and pipelined functional units.
This project is supported and funded by both the Région Île-de-France and the Digiteo Research Park (see <http://www.digiteo.fr/>).
Subject
======
The aim of the ORCYMELAN project is to provide efficient scheduling algorithms in terms of computation time as well as competitive ratio for an optimization criteria, that would map programs on VLIW architectures, taking into account register pressure and pipelined functional units.
Such a problem is usually decomposed in two parts. First, solving a scheduling problem without register pressure, and then a register allocation problem, leading sometimes to unfeasible solutions.
However, the PRISM team has developed and successfully experimented an approach which first consider register pressure and introduces new precedence constraints in the scheduling problem.
This approach may lead to a kind of constraints which has not been very much investigated until now: negative latencies.
If i and j are two jobs, and if we denote by s(i) the starting time of i, a negative latency constraint between i and j can be expressed as follows:
s(i)+l(i,j)<=s(j), with l(i,j)<=0
Such a constraint can be seen as a relative due-date between i and j: i must start at most -l(i,j) (positive) time units after j starts.
Notice that such constraints can be easily handled by graph algorithms if no resource constraints are considered. But even for simple resources like parallel processors, these constraints may lead to infeasibility, and require much attention to design good algorithms.
The postdoc candidate will take part in the study the theoretical scheduling problems arising from a precedence graph G with positive and negative latencies, and various resource constraints (parallel processors, typed processors, unitary RCPSP). Complexity results, as well as performance analysis of approximation algorithms, and experiments results are expected.
This study will take advantage of previous work in the field of approximation algorithms for scheduling problems with ordinary precedence constraints, and fixed due-dates. It should lead to both international journal publications and conferences with the members of the project.
Participating Teams and members
===============================
* Claire Hanen from Operations research team at LIP6, UPMC
* Sid Touati, Karine Deschinkel from PRISM, UVSQ
Application details
===================
* Dates: please apply as soon as possible.
* Please send:
- a CV (including publication list);
- links to PhD thesis and/or selected papers;
- a motivation letter presenting topics of interest.
to: Claire Hanen (claire.hanen@lip6.fr)
Categories : Post-doc
