Hebdo
No 47. 15 octobre 2001

Sommaire : Trois questions à Albert Cohen, thèse primée Specif | L'actualité de la semaine | Théories et concepts | Enseignement | La recherche en pratique | Manifestations | Le livre de la semaine |

ABONNEMENT/DESABONNEMENT| PAGE D'ACCUEIL DE L'ASTI | NUMEROS PRECEDENTS

Trois questions à Albert Cohen

chargé de recherche, Inria projet A3

Asti-Hebdo : Votre thèse "Analyse et transformation de programmes, du modèle polyédrique aux langages formels" a été primée par Specif. Polyédrique... s'agit-il de porter en génie logiciel la poussée géométrique représentée en logique par un Jean-Yves Girard ou Giuseppe Longo (voir notre numéro 13) ?

Albert Cohen : Ce serait plutôt le contraire. Personnellement, je n'ai jamais été attiré par la géométrie. Au départ, j'étais plutôt intéressé par la physique, et j'avais tendance à éviter les mathématiques (tout en les aimant bien). Je préférais raisonner symboliquement que faire des calculs. Je me suis donc ré-orienté vers l'informatique, mais le choix n'a pas été facile.

Quand j'ai commencé, en DEA, à travailler sur les modèles polyédriques, les représentations matricielles ou tri-dimensionnelles ne m'aidaient pas beaucoup. Je saisissais mieux les objets par leurs aspects relationnels, plats, voire linéaires. Les systèmes d'équation me parlent mieux que les dessins de vecteurs, d'arcs ou de rayons.

C'est à l'ENS de Lyon que j'ai rencontré le professeur Luc Bougé et le doctorant Jean-François Collard, qui m'ont aidé à me décider et m'ont orienté vers le sujet de ma thèse, que j'ai soutenue à Versailles, sous la direction du même Jean-François Collard et de Paul Feautrier.

Mon travail sur la parallélisation automatique tend donc à éloigner cette activité de son approche géométrique. De ce fait, ma thèse est un peu en porte-à-faux entre cette démarche classique et des aspects nouveaux venant de la théorie des langages formels.

Je ne serais pas tellement favorable à la géométrisation à outrance de tous les problèmes et de toutes les solutions. Ce qui me paraît sympathique, en revanche, c'est l'apparition d'une sorte de collaboration entre les approches géométriques (en l'occurrence, des polyèdres et des contraintes sur des valeurs de variables ou des nombres d'itérations) et des démarches complètement différentes, où l'on décrit plutôt des arbres, se rapprochant de la théorie des graphes et des langages.

Cette combinaison pourrait conduire par exemple à ce que certains appellent les "automates hybrides" (automates finis munis de contraintes sur les compteurs et les variables temporelles notamment).

Le type d'algorithmes qui m'intéressent, comme le branch and bound, posent des problèmes intéressants, car la parallélisation y viole la sémantique. On sait par exemple garantir que la solution trouvée est valable, mais non que l'on fait moins de calculs inutiles que dans la version séquentielle. Ce type de transformation est difficile à modéliser, il demande une compréhension profonde de l'algorithme, et pas simplement une compréhension de la syntaxe du code. Quand je parle ici de sémantique, il s'agit de celle du code lui-même, et non, à un niveau plus élevé, de celle des spécifications que le programmeur a en tête.

Hebdo : Vos travaux ont-ils des débouchés industriels ?

A.C. : Pour les aspects récursifs de ma thèse, les débouchés industriels sont encore loin, car les automates hybrides restent très coûteux à manipuler dans un solveur, un prouveur ou un compilateur. Mon travail a surtout visé à montrer l'intérêt du sujet, plutôt qu'à proposer des solutions opérationnelles. Je co-encadre maintenant un autre doctorant qui tente de préciser, sur un cas particulier, la manière de définir des algorithmes efficaces et de les implémenter.

En revanche, il y a beaucoup à faire sur la recherche automatique de régularités dans des programmes moins parallélisables que les programmes scientifiques classiques (c'est-à-dire, principalement, les codes Fortran des physiciens), mais sans aller jusqu'au récursif à proprement parler. Cette forme de régularités peut être décrite, et ces descriptions peuvent répondre à d'autres objectifs que la parallélisation automatique et l'optimisation de performances. Je pense notamment à la vérification, à la robustesse ou encore à la réutilisation de code, grâce à la reconnaissance d'algorithmes. Nous avons un contrat avec Philips qui porte directement sur ce point.

Du point de vue de l'analyse de programmes, nous ne cherchons pas spécialement des formalismes très puissants. Nous visons surtout, pour un programme donné, à obtenir un maximum d'informations possible à son sujet, à voir par exemple qu'il fait un produit de matrices. Tant pis, dans un premier temps, si l'outil ne s'applique qu'à certains types de codes et si c'est lourd. C'est seulement dans un deuxième temps que nous chercherons une formalisation plus complète

Ces techniques s'appliquent bien aux systèmes enfouis (appellation officielle actuelle pour "systèmes embarqués") pour le traitement de code multimédia, les protocoles réseau ou la cryptographie. Certains contrats en ce domaine seraient déjà signés si la conjoncture ne l'avait pas empêché.

Hebdo : Etes-vous nombreux à travailler dans ce domaine ?

A.C. : On peut dire qu'il existe une "école française de parallélisation automatique", une petite communauté qui regroupe une trentaine de personnes. Aux Etats-Unis, le CNRS a des accords et beaucoup de contacts avec le laboratoire d'Urbana Champaign (université de l'Illinois, où j'ai passé deux hivers), mais la communauté n'est pas sensiblement plus importante qu'en France.

Nos travaux n'exigent pas de moyens matériels puissants. Il s'agit essentiellement de faire, sur le papier, des manipulations symboliques d'expressions... c'est plus proche de ce qu'on fait dans les classes de mathématiques du premier cycle que ce que font les informaticiens quand ils disent faire des mathématiques. Quant aux outils de calcul, j'ai pu, une fois, disposer d'une machine à 32 processeurs parallèles. Cela m'a permis de faire quelques simulations, mais ce n'est pas essentiel au développement de mon travail.

Notes bibliographiques

A ceux qui souhaiteraient approfondir le sujet, Albert Cohen recommande les ouvrages suivants :

• G.R. Perrin et A. Dartel : The data parallel programming model (Springer, 1996) : un bon ouvrage présentant le parallélisme de données et l'école française de parallélisation automatique (modèle polyédriques).
• A. Schrijver : Theory of linear and integer programming (Wiley & sons, 1986) : la bible des algorithmes du modèle polyédrique, la programmation linéaire en nombres entiers et l'arithmétique de Presburger.
• H. Comon et Y. Jurski : Multiple counters automata, safety analysis and Presburger arithmetics (in Proceedings, Computer aided verification, Hu and Vardi ed. , Springer 1998) : un bon article pour comprendre les problèmes soulevés par les automates hybrides.
• J. Berstel : Transductions and context-free languages (Teubner 1979) : la référence en matière de transductions rationnelles (modèle principal dans l'analyse des programmes récursifs selon l'approche de A. Cohen).