Note aux orateurs
Contact et renseignements : Daniel Hirschkoff.
Chaque année les ordinateurs sont de plus en plus rapides, mais
utilisent fondamentalement tous la même physique de Newton. Feynman
s'est interrogé en 1982 sur cette restriction. L'idée de l'ordinateur
quantique est d'utiliser des phénomènes quantiques pour mener à bien
des tâches que nos machines ne savent pas réaliser aujourd'hui.
En partant de cette reflexion, Bennett et Brassard ont exhibé en 1984
le premier protocole quantique permettant des conversations chiffrées
parfaitement sûres, alors qu'une telle sureté inconditionelle n'existe
pas en classique. A l'opposé, Shor a montré en 1994 comment la
plupart des systèmes cryptographiques classiques actuels deviendraient
vulnérables par l'utilisation d'un ordinateur quantique (par ex :
carte bleue, signatures numériques, conversation chiffrées...). Dans
cet exposé, je présenterai les notions importantes du calcul quantique
ainsi que plusieurs exemples d'algorithmes battant leurs analogues
classiques.
Cet exposé introduira le domaine de l'indexation automatique de données visuelles et plus particulièrement sous l'angle du traitement d'images, "Comment retrouver dans une banque d'images, une ou plusieurs images similaires à celle fournie en requête par un utilisateur ?" Pour cela, nous commencerons par un bref rappel historique de l'évolution du domaine du traitement numérique des images de ses origines (vers 1950) à nos jours avec l'émergence de ce nouveau domaine qu'est l'indexation. Puis nous introduirons et détaillerons les fonctions d'un système de gestion de données visuelles. Pour chaque fonction, des exemples permettront de mettre en avant les problèmes posés (et le plus souvent non encore résolus et donc donnant lieu a des programmes de recherche).
Depuis l'arrivée des processeurs superscalaires, VLIW (very long
instruction word), pipelinés, le parallélisme est exploité à un grain
très fin (au niveau des instructions élémentaires), au sein même des
microprocesseurs. L'optimisation au niveau des blocs de base se fait
par des techniques d'ordonnancement, de "compaction de microcode": les
instructions sont séquencées dans un ordre différent, soit à la
compilation, soit carrément à l'exécution. Les techniques de
compilation sont des variantes de l'ordonnancement de liste, sur des
graphes acycliques.
L'optimisation de blocs de base plus complexes comme les boucles
conduit, elle, à des problèmes d'ordonnancement cyclique. L'idée est
d'autoriser l'ordonnancement simultané d'instructions appartenant à
différentes itérations dans l'espoir d'augmenter le
parallélisme. C'est la technique du pipeline logiciel. De nombreuses
heuristiques ont été proposées au cours des 20 dernières années pour
aborder ce problème. Voici un extrait de la page web d'une des
actrices de ce domaine: ``We have discovered many interesting facts
and strategies. We have shown that Modulo scheduling is prone to
trashing because of the short-circuit methods used to approximate full
backtracking. We have shown that many methods for software pipelining
are not mathematically sound.'' Le but de cet exposé sera de ne pas
tomber dans ce travers, en présentant une technique basée sur des
critères d'optimisations bien définis et issue du domaine de la
synthèse de circuits.
J'expliquerai deux algorithmes portant sur des graphes cycliques,
valués par des entiers, le premier, dû à Leiserson et Saxe, permettant
de minimiser la période d'horloge d'un circuit (plus long chemin de
poids nul), le second, variante de l'algorithme Out-of-Kilter de
recherche de flots, permettant de minimiser le nombre d'arcs de poids
nul du circuit. Je montrerai comment la combinaison de ces deux
algorithmes permet de décaler les instructions entre différentes
itérations de façon à améliorer la compaction du microcode formé par
le corps de la boucle. Du point de vue théorique, cette technique
conduit à une heuristique garantie (c'est-à-dire pas arbitrairement
loin de l'optimal) sous certaines hypothèses que j'énoncerai. Du point
de vue pratique, elle est encore en cours d'évaluation, mais semble
pertinente.
On présente certains algorithmes récents permettant d'effectuer rapidement des divisions. Avant ceci, on explique pourquoi la division est une opération qu'il est important d'optimiser.
Mais au fait, qu'est-ce que la vie ?
Hélas, pour répondre un peu sérieusement à cette question, nous
manquons cruellement de planètes sur lesquelles faire des
expériences. Comment alors étudier quelles sont les conditions pour
que la vie, cette fascinante et envahissante augmentation de la
complexité, se développe dans une chimie donnée ? Et quelles sont les
propriétés de la vie qui dépendent de notre bonne vieille chimie du
carbone, et celles que l'on retrouverait sur une autre planète ? Et
comment faire apparaître celles de ces propriétes qui nous intéressent
dans un système artificiel comme un réseau de neurones ou une
éprouvette ? Et ..? Et ..?
Alors, depuis l'invention de l'ordinateur, on cherche à l'utiliser
pour simuler la vie -- enfin, ce que l'on entend par ce mot. Tout le
monde a entendu parler du jeu de la vie, de réseaux de neurones, des
fractales en formes de fougères, des algorithmes génétiques, etc.
Nous survolerons donc plusieurs travaux qui ont étudié différentes
propriétés de la vie : autoreproduction, évolution, et plus récemment
la notion d'émergence, qui désigne l'apparition dans un système
d'une complexité qui est supérieure à la somme des complexités des
parties.
Mais dans cet exposé, nous essayerons aussi de porter un regard
critique sur un domaine où une conférence peut faire la une du
Guardian sans même parler d'internet, où des chercheurs courant après
leurs robots évolutifs croisent d'autres robots courant après les
criquets
femelles, où l'on parle d'art émergent et de robots désespérés, et où
Heidegger est invoqué contre Descartes et Platon contre Heidegger pour
nous aider à distinguer une soupe froide d'une soupe chaude, un vol de
chauves-souris dans Batman des feilles mortes en automne, et une
fourmilière du réseau de France Télécom.
Pour décrire formellement l'implantation des langages de
programmation fonctionnelle (comme O'Caml) ou par objets (comme Java),
il faut une modèle qui intègre la notion d'«adresse» afin
de pouvoir parler de gestion de la mémoire et de partage des
structures. Un calcul de «substitutions explicites» est un bon
point de départ pour cette description, mais, pour obtenir un
modèle adéquat, nous y avons ajouté le concept d'adresse.
Ainsi nous obtenons un cadre générique qui permet de séparer
les transformations élémentaires des aspects
«stratégiques», mais aussi, dans le cas des langages
fonctionnels, de repousser le plus tard possible le choix entre
«machine à environnement» et «machines à
réécriture de graphes».
Si le temps le permet, nous traiterons le cas des langages à
objets. On y obtient aussi un modèle générique qui
intègre les approches «à plongement» et «à
délégation» et sépare aussi les aspects liés à la
stratégie.
Ce travail s'appuie sur des coopérations avec Zino Benaissa,
Frédéric Lang, Luigi Liquori et Kristoffer Rose
N.B.: Les mots entre guillemets seront définis et discutés.
Transparents de l'exposé (postscript gzippé)
Traditionellement, la resolution d'un systeme lineaire dense sur une machine a memoire distribuee s'effectue en factorisant la ma- trice de coefficients sous forme triangulaire par la methode de Gauss. De nombreuses variantes existent, et nous decrivons ici les aspects algorithmiques que nous avons etudies pour resoudre effi- cacement ces problemes sur des clusters de clusters. La hierarchie memoire complexe de ces machines, ainsi que la non-uniformite du reseau de communication posent en effet des problemes a la fois pratiques et algorithmiques. Ces considerations seront illustres par des resultats de performances convaincants.