777 ASTI-HEBDO No 47 Albert Cohen Specif
Association Française des
Sciences et Technologies de l'Information

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 conduit 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).


L'actualité de la semaine

Un Nobel pour ... de futurs composants Stic ?

En attribuant le prix de physique à trois physiciens (Eric Cornell, Wolfgang Ketterle et Carl Wieman) pour leurs travaux sur les condensats de Bose-Einstein, les Nobel couronnent des travaux dont les Stic pourraient bénéficier d'ici à une dizaine d'années, par le calcul quantique.

Ces condensats peuvent en effet prendre des états méta-stables suffisamment contrôlables pour leur faire représenter des informations. Mais dans des conditions très particulières, fortement aléatoires, qui font à la fois la difficulté et l'utilité de ce type futur de calculateur.

Lutte contre le cybercrime

L'Office central de lutte contre la criminalité liée aux technologies de l'information et de la communication vient d'être inauguré par Daniel Vaillant, ministre de l'Intérieur. Comme les autres offices centraux spécialisés (répression du banditisme, lutte contre le trafic des stupéfiants, lutte contre la grande délinquance financière...), celui-ci a été créé au sein de la direction générale de la Police nationale.

Par ailleurs, le gouvernement a déposé, mardi 9 octobre, ses amendements destinés à lutter contre l'utilisation criminelle des réseaux informatiques. Transfert.net note que ceux-ci figuraient déjà dans la LSI. Pour en savoir plus, le site du gouvernement.

Les aveugles, mal lotis des sites publics français

Sur les trente sites publics étudiés cette année par le ministère de la Fonction publique, aucun ne satisfait pleinement aux exigences du W3C en ce qui concerne l'accessibilité aux personnes aveugles et mal voyantes. Certains sont cependant bien notés pour la navigation courante. Cette étude sera reconduite l'année prochaine, accompagnée d'un plan de formation spéciale destinée aux webmestres des sites en question. Selon M.J., Internet Actu 9/10/2001

Méthodes agiles ou Extreme programming

Ces techniques visent à répondre aux besoins de qualité et de rapidité de développement des entreprises. Elles étaient par exemple à l'honneur au cours des récentes journées Développeurs de Borland.

Le Monde Informatique signale un livre blanc que Business Interactif vient de rendre disponible en téléchargement.

Enseignement

Tableau virtuel

«Le tableau virtuel : un outil qui renouvelle d’anciennes pratiques scolaires et modernise l’enseignement de la géométrie.» Bruno Delacôte est le promoteur du «tableau virtuel». Cette forme d'enseignement assisté par ordinateur permet de réactualiser d’anciennes pratiques et de les compléter par une approche dynamique, spectaculaire en géométrie. Lire l’interview réalisée par Cyberécoles


La recherche en pratique

Labellisation des espaces publics numériques

La labellisation des Espaces publics numériques (EPN) est lancée. De quoi s'agit-il ? Un dossier composé d'une note d'information et d'un formulaire est à la disposition de tous les responsables de points d'accès publics à l'internet souhaitant bénéficier de ce label.

Sécurité informatique

Le numéro d'octobre 2001 de "Sécurité informatique" est disponible en téléchargement.À lire, notamment, un article sur "Les anti-virus dans l’enseignement supérieur et au CNRS".

Manifestations

Collège international de philosophie

La lettre de diffusion Paris 7 indique le site du collège, d'où le programme, en format PDF, peut être téléchargé.

Le livre de la semaine

Bases de données spatiales et SIG

Bien que publié en anglais (chez Academic press), "Spatial databases, with application to GIS" est signé de trois français : Philippe Rigaux, Michel Scholl et Agnès Voisard (les deux premiers sont professeurs au Cnam, la troisième est architecte de systèmes chez Kivera).

Il s'agit d'un travail de fond sur la représentation des objets spatiaux, les modèles de données qu'ils exigent et la gestion des bases de données qui les regroupent. Le dernier chapitre présente et compare cinq produits du commerce (ArcInfo, ArcView GIS, Smallworld, Oracle (extension for handling spatial data) et Postgres SQL).

Approches formelles pour l'aide au développement de logiciels

Le numéro 7/2001 de la revue TSI, sous la direction d'Yves Ledru et Marie-Laure Potet regroupe quelques articles issus, au terme d'un long processus de révision, de l'atelier Afadl (Approches formelles dans l'assistance au développement de logiciels)qui s'est tenu à Grenoble en janvier 2000.

Afadl 2001 devait se tenir en juin dernier.


L'équipe ASTI-HEBDO : Directeur de la publication : Jean-Paul Haton. Rédacteur en chef : Pierre Berger. Secrétaire général de la rédaction : François Louis Nicolet, Chef de rubrique : Mireille Boris. Asti-Hebdo est diffusé par FTPresse.