Benoît Meister, PhD

Benoît Meister, PhD
ICPS/LSIIT
Pôle API
rue Sébastien Brant
67400 Illkirch, FRANCE
(+33)3.90.24.45.43

meister@icps.u-strasbg.fr

Position

I have been a PhD candidate since october 2001 at the ICPS (Image and Parallel Computing) Team, part of the LSIIT Laboratory in Strasbourg. LSIIT is common to Université Louis Pasteur (ULP) and the CNRS. I defended my PhD on friday, December 17th 2004. Then, i have been a temporary assistant professor (ATER) at ULP, where my research team was made of:

From april to august 2005, i have done a research mission at VERIMAG, a common laboratory of Université Joseph Fourier, the INPG and the CNRS. Since october, i work for a compiler R&D company in New York City, Reservoir Labs, Inc.

Research interests

All of them are related to embedded systems, but often concern other areas of research.

Data locality optimization

I began to have interests in program optimization in 1999 when Ph. Clauss offered me to work with him on a memory access optimization problem based on the polytope model.
This work yielded a technique for linearizing polytopes based on Ehrhart polynomials. Meanwhile, this technique has already shown its consequences in program optimization, in such areas as data locality improvement, which is known to reduce execution time as well as the energy consumption induced by the program execution. The technique of data reorganization we have developed also reduces the memory footprint of the program, as only the actually accessed data are put in memory. Our linearization technique is already used in embedded systems design, in an approach using communicating Kahn processes, the Compaan/Panda project.
I made a step further into the polytope model when Vincent Loechner joined our team. We worked on new data locality optimization techniques, taking into account both spatial and temporal locality. Our works also extended our linearization technique to more general cases: sequences of loop nests, case with self-reuse, and with uniform and non-uniform group-reuse.

Parametric polyhedra and combinatorial optimization

I'm also developing new methods for solving more general parametric polyhedral problems and enhancing Polylib , the polyhedral library.
I began in 2002 by finding an algorithm to compute the integer hull of a parametric rational polyhedron P. This work introduces new geometric objects called periodic polyhedra. The vertices of the integer hull are computed recursively by finding pseudo-facets of the P, which are similar to faces of P but on which some variables are integer. The vertices are derived from 0-dimensional pseudo-facets (called pseudo-vertices). Their definition depends periodically on the parameters.
Taking advantage of the property that vertices of the integer hull are solution to problems of integer linear programming problems, i presented a new algorithm for solving the parametric integer linear programming problem, as well as the parametric integer lexicographic maximum problem. Indeed, i consider them as subproblems of a hierarchically linear integer programming problem.
A solver for this class of problems is under development, and will published in the forthcoming months. It shall be merely called Parametric Integer Linear Solver (PILS).

Ehrhart polynomials

Ehrhart polynomials give the number of integer points in a rational parametric polyhedron P. It can be seen as a polynomial whose coefficients are periodic numbers (rational-valued periodic functions). They have been defined by the alsacian mathematician Ehrhart (see Philippe Clauss's Ehrhart pages) and extended by Philippe Clauss.
Noticing that the periodic character of Ehrhart polynomials can be seen as a drawback, and that many approaches using Ehrhart polynomials only need an approximate value of the Ehrhart polynomial, i have been looking for ways to compute the approximation of an Ehrhart polynomial. By refining a conjecture given by Ehrhart that links properties of the faces of P to the periodicity of its Ehrhart polynomial, i found two approximation methods. They are both good approximations (their relative error asymptotically tends to zero) and their complexity is polynomial if the number of variables and parameters is fixed. One of the approximation methods allows to compute upper and lower bounds of an Ehrhart polynomial, in the form of (non-periodic) polynomials. A new promising method for computing Ehrhart polynomials, based on the Barvinok-Seghir-Verdoolaege method, is also given.

Processing delegation for communicating embedded systems

In the frame of EME, a common project among research teams of the LSIIT, i also work on the problem of adaptating dynamically the execution of a program to its running environment. This environment includes the local computing load, the available memory, network bandwidth and availability, the remaining time (in the case of real-time programs) and energy (in the case of embedded systems). A program is decomposed into pieces that can be dynamically executed by a remote computer under certain conditions. The decomposition takes place at compilation time. Instances of these pieces will be called tasks at execution time. The dynamic scheduling and mapping of the different tasks are then endorsed by intelligent (mobile) agents.
In 2003, i directed a master student, Gilles Bitran, who studied the feasability of this system with GCC and XML. He also implemented some static liveness analysis parts in GCC. His work focuses on the concrete construction of the different pieces, as well as a precise analysis of the input/output data to be communicated. The framework is limited to static data for now. However, it is foreseen that dynamic data manipulation should not affect it significantly. Have a look on Gilles' master thesis (PDF format, french text, updated (by him) in april 2004), where you can find an overview of the system.

Other Research and Development Experience

Before my thesis, i worked as summer intern from july to october 2001 at Hewlett-Packard Labs, Palo Alto, CA. There, i was involved in the development of the PICO tool. The purpose of this system is, given a program in C, to build an application-specific processor doing the same job. The obtained chip must correspond to the best compromise between minimizing the silicon surface and the maximizing fine- and coarse-grain parallelism that are inherent to the program.
My job was to make PICO deal with sequences of loop nests.

List of Publications

Get it here

Other Research Reports

B. Meister, "Localité de données et compression mémoire dans les opérations stencil", A set of independent methods for improving data locality, extracting communication-free parallelism, and reducing the amount of required memory in stencil-like operations, January 2002, revised March 2002. french text.
B. Meister,V. Loechner and Ph. Clauss, "The Polytope Model for Optimizing Cache Locality", an attempt to improve temporal and spatial locality for loop nest with non-uniform reuse (dependence) functions, [ICPS RR 00-03].
B. Meister, "De l'utilisation des périodiques dans les problèmes polyédriques en nombres entiers". A study of periodics, generalizing periodic numbers. Here we try to show the link between integer linear problems and periodics, as it exists in Ehrhart Polynomials. Updated some times since the end of 2002. French text, translated into english in "Using periodics in integer polyhedral problems".

Short Research Reports

B. Meister, "On a matrix decomposition" (PS.GZ / PDF), where we decompose, by two slightly different manners, an integral full row rank matrix into a product of diagonal and unimodular integral matrices. Implemented in C using polylib : available here. March 2002, rev. April 2002.

PILS

Get and try Ancre-PILS, the rational hierarchically linear programming solver (non-parametric for now). It uses Polylib.
Ancre-PILS is part of the bigger solver project PILS (Parametric Integer Linear Solver).

Teaching

I have been teaching since October 2001 at the Mathematics and Computer Sciences Departement of the Louis Pasteur University in Strasbourg, France.

2004/2005:

Computer Architecture (available at Arnaud Giersch's page)
Algorithms and Imperative Programming; (teaching material used with courtesy of Alexandre Blansché)
Algorithms and Data Structures (Students in Biocomputing)

2003/2004:

Computer Architecture

2002/2003:

Computer Architecture

2001/2002:

Introduction to (functional) Programming; Computer Architecture

Practice Assignements / Projets (french text)

Assembleur SPARC:
- Un petit Morpion [PS.GZ] [PDF]
- Racine nème d'un entier [PS.GZ] [PDF]

Links

My hosting lab in Strasbourg (Illkirch): ICPS/LSIIT
The project in which my works take place : EME (Embedded Mobile Environments)
My research group : PCO (Program Compilation and Optimization)
My doctoral associations : Addal, CJC and Eurodoc

I also suggest to have a look at some other web sites of high interest (for me at least):
- CAR was the research team where I made an internship in 2001. Their project, PICO, is a dense industrial project and therefore a source of many interesting problems and methodologies.
- Alain Darte and Frédéric Vivien, whose works on parallelism and optimisation have to be read. They both work in the ENS Lyon, France.
- Albert Cohen is a wide-range actor in compilation and parallelism at the INRIA Rocquencourt, France.
- Ludo Van Put is a fellow PhD candidate who works on link-time optimization at the University of Ghent, Belgium.

meister@icps.u-strasbg.fr

Last Update: 9 October 2005