[HiPEAC-announce] Post-doctoral position in Computer Science and Operations research

[Sid Touati]

The 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 at lip6.fr)


-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4280 bytes
Desc: S/MIME Cryptographic Signature
Url : http://www.hipeac.net/pipermail/hipeac-announce/attachments/20090614/7e2651b5/attachment.bin