Pierre Sens

Les systèmes répartis à grande échelle

Ces dernières années, des structures informatiques faisant coopérer un très grand nombre de machines ont émergé. Ces environnements, en agrégeant les ressources de milliers d?ordinateurs, offrent aux applications de nouvelles possibilités en termes de puissance de calcul, de capacité de stockage et de distribution des programmes. Deux types d'infrastructures se sont imposés : les grilles (/Grid/) qui consistent à interconnecter des centres de calcul organisés en grappes d'ordinateurs (/clusters/) géographiquement réparties, et les architectures Pair à Pair (/Peer-to-peer/ ou /P2P/) dans lesquelles un ensemble d'ordinateurs individuels coopèrent d?égal à égal. Ces infrastructures de grande taille obligent à repenser les protocoles. Nous dresserons un panorama des principales architectures des systèmes pairs à pairs et des grilles. Nous intéressons plus particulièrement au problème de stockage de données dans les systèmes pair-à-pair et présenterons aussi l'impact de l'augmentation du nombre de ressources, de l'éloignement de machines ainsi que de leur volatilité sur l'algorithmique répartie.

Daniel Etiemble

La recherche en architecture des ordinateurs et des processeurs ou « comment lutter contre des exponentielles »

Dans de nombreuses disciplines, le temps nécessaire pour les avancées scientifiques n'a pas beaucoup d'importance. Les mathématiciens ont disposé de plusieurs siècles pour démontrer le théorème de Fermat, et les physiciens du solide peuvent utiliser des années pour installer un accélérateur pour trouver une particule. Si celle-ci existe, elle sera toujours là lorsque la « manip » sera prête. Les chercheurs dans le domaine du matériel informatique n'ont pas cette facilité : si la quantité de transistors dont ils disposent pour réaliser des systèmes informatiques croît exponentiellement et les performances croissent exponentiellement, cela signifie qu'ils sont confrontés en permanence à des exponentielles et que les référentiels dans lesquels ils travaillent changent en permanence.

Dans cette présentation, nous montrerons d'abord l'impact de ces progressions exponentielles sur l'évolution des ordinateurs de bureau, des ordinateurs portables et des serveurs avec les côtés positifs et les problèmes (« ruptures ») que cela implique sous différents aspects :

• écart croissant entre les performances des processeurs et des mémoires
• écart croissant entre les performances « crête » et les performances soutenus
• influence croissante des problèmes de consommation et de dissipation de chaleur
• limites physiques dont on se rapproche de la technologie dominante (CMOS).

Chacun de ces problèmes fait l'objet de recherches pour améliorer les techniques permettant de limiter l'impact de ces problèmes ou de les surmonter, ou trouver des solutions alternatives pour tenter de supprimer ces problèmes.

Si l'ordinateur de bureau et les serveurs sont les ordinateurs les plus connus, la très grande majorité des processeurs sont utilisés dans les dispositifs électroniques enfouis ou embarqués (« systèmes embarqués ») qui vont des « appliances » (PDA, téléphones portables, etc.) aux systèmes informatiques utilisés dans les automobiles et les avions. Ces domaines ont de nombreux points communs avec l'ordinateur « classique », mais les contraintes sont fortement différentes : ce n'est plus la performance brute qui importe, mais la performance par watt, la performance nécessaire avec des tailles mémoire limitées, un fonctionnement fiable, un fonctionnement « temps réel », etc.

Depuis la naissance des premiers microprocesseurs, la réalisation d'un système électronique ou informatique a utilisé deux types de solutions extrêmes : la réalisation de circuits intégrés spécifiques (très performants, mais à utilisation limitée à une application ) ou l'utilisation de microprocesseurs (d'utilisation très souple via la programmation, mais loin des performances maximales par rapport à chaque utilisation). L'apparition de circuits programmables (FPGA par exemple) a ouvert la voie à une solution « intermédiaire » moins performante que les circuits VLSI spécifiques, mais plus performante que les processeurs d'usage général à cause de la programmation du matériel en fonction de l'application. Les circuits « reconfigurables » constituent un domaine de recherche actif. Les FPGA les plus récents permettent de disposer à la fois de microprocesseurs et de circuits spécifiques, de spécialiser le jeu d'instructions du processeur en fonction de l'application. La reconfiguration est encore le plus souvent statique, mais des progrès significatifs sont réalisés dans le domaine de la reconfiguration dynamique, où le circuit se modifie lui-même en fonction des différentes étapes du calcul d'une application. Cette évolution remet en cause le modèle classique de Von Neuman, au profit de modèles où s'ajoute à la mémoire contenant le programme à exécuter une mémoire contenant les configurations successives des opérateurs matériels au cours de l'exécution de l'application.

Le dernier point abordé dans cette présentation sera l'irruption croissante des approches parallèles dans les architectures matérielles. Les processeurs des PC sont maintenant multi-c?urs et les systèmes sur puce (SoC) utilisent de plus en plus plusieurs processeurs, identiques ou de type différents. Nous montrerons les nouveaux problèmes, matériels, logiciels (modèles de programmation) et système que posent ces systèmes sur puce. 

Christel Baier

Automata over infinite words

Finite-state automata as acceptors for words play a central role in many areas of Computer Science and Mathematics, ranging from logic over verification purposes to the compilers for programming languages. Several types of automata for languages over finite or infinite words have been studied in the literature, that can be classified via their structure (deterministic, nondeterministic, universal, alternating, probabilistic) and acceptance condition. In this course we will discuss several aspects (expressiveness, efficiency, algorithms for checking emptiness, equivalence, etc.) of automata over infinite words, also often called omega-automata. The first part of the course will summarize the main concepts of deterministic and nondeterministic omega-automata with Buechi, Rabin and Streett acceptance condition. The second part of the course will present some recent results on probabilistic omega-automata.

Jean-Michel Coron

Gérard Berry

Pourquoi le monde devient numérique

Au cours des dix dernières annnées, des pans entier de notre environnent ont basculé dans le numérique: l'ensemble des moyens de communication, l'audio-visuel, la commande des objets. l'apareillage médical, etc. Il s'agit bel et bien d'une révolution qui met bien des modes de pensée et d'action classiques sens dessus-dessous. Tout le monde observe, accompagne, ou subit ce phénomène, mais sans nécessairement en comprendre les racines. Ce sont elles qui feront l'objet de cet exposé. Nous montrerons pouquoi et comment on peut désormais unifier des domaines auparavant très disparates à l'aide d'une seule machine, le circuit électronique, et de sa commande par logiciel. A travers des exemples en photographie, son, et télécommunications numériques, nous verrons l'importance des principes de traitement de l'information qui ont permis cette révolution. Enfin, à travers l'informatique embarquée qui commande désormais nos voitures et nos avions, nous étudierons les limites du système et la difficulté de faire juste. Un des buts fondamentaux de la science informatique est de passer des systèmes qui marchent à peu près à des systèmes qui marchent vraiment, ce qui pose des problèmes scientifiques et techniques fascinants et encore loin d'être résolus.

Guillaume Hanrot

François Denis

Denis Trystram

---

Contacter le Département Informatique
Dernières modifications : le 07/11/2008