Talk abstract
From LRDE
This is a property of type Text.
S
Dans cet exposé je présenterai la bibliothèque d'algorithmes
géometriques CGAL. Cette bibliothèque C++ fournit des algorithmes
comme le calcul d'enveloppes convexes, de triangulations, en 2D,
3D... J'illustrerai surtout les problèmes de robustesse numériques que
l'on y rencontre, puis je détaillerai les solutions que l'on utilise
pour les résoudre de manière efficace. Elles sont basées sur plusieurs
types d'arithmétique: arithmétique d'intervalles et
multiprécision. Ces différentes techniques sont combinées dans
l'implementation grâce à la généricité du code (template C++), ce qui
produit à la fois un code efficace, compact, et proche des concepts
mathématiques, donc plus facilement prouvable. +, Dans cet exposé, nous présenterons la bibliothèque d'algorithmes de
morphologie mathématique Morph-M. Cette bibliothèque C++ fournit un
grand nombre de fonctions en traitement d'image (arithmétiques,
colorimétrique...) et en morphologie mathématique (filtrage,
segmentation, graphes etc.). Nous discuterons principalement des
concepts proposés par la bibliothèque, et leurs utilisations dans la
mise en oeuvre de nouveaux algorithmes. Nous illustrerons les
potentialités par quelques algorithmes actuellement implémentés dans
cette bibliothèque. Enfin nous discuterons des inconvénients de
l'approche générique. +
Dans cet exposé nous verrons l'ensemble des outils de la plate-forme
Qgar, avec une attention particulière pour la généricité et les
performances du code de la bibliothèque QgarLib. Nous verrons
également les autres composants du logiciel, quelques standards de
développement Qgar, ainsi que les défis pour l'évolution de la
plate-forme. +
Separation of concerns is the idea of breaking down a program into
encapsulated pieces that overlap in functionality as little as
possible. Encapsulated entities, such as classes, methods or modules,
are more manageable, easier to test and maintain, and may be reused
more easily than a large, entangled program. A cross-cutting concern
is something that cannot be encapsulated using normal abstraction
mechanisms, thus defeating separation of concerns. A classical example
of this is logging (e.g., logging calls and returns to a file while
the program is running) - the logging code needs to be added to every
applicable method in the program. The logging code for each method may
be almost identical, creating an undesirable overlap in
functionality. Aspects let a programmer implement a cross-cutting
concern as a separate entity, through advice (how a concern should be
implemented) and join points (where it should be implemented). I will
give an introduction to aspect-orientation and aspect languages, and
also talk a bit about domain-specific aspect languages. +, Context-oriented Programming allows one to modularize a software
system using partial class and method definitions organized into
layers. Layers are composed into or out of the system depending on the
context apparent during program execution. The basic concept of layers
as partial program definitions has been suggested before, but with our
approach we extend this idea by the notion of dynamically scoped layer
activation, resulting in a viable approach for expressing
context-dependent behavior. We will discuss the basic language
constructs for Context-oriented Programming, the development of
non-trivial examples, implementation issues, especially with regard to
retaining efficient method dispatch, integration with the CLOS
Metaobject Protocol, and if time permits, advanced topics like
ContextL's reflective facilities for controlling layer activation and
deactivation. +
Mouldable programming is about looking at programs as mouldable
fragments of code, not as the static, brittle syntax software often
turns out to be. Some simple examples follow. The notation for calling
a method "push" which adds an element "E" to a stack "S" can be OO or
static method style, it can modify "S" or return the new stack
etc. Can we simplify usage to just one form, and mould it to the
actual call? A function which breaks down for some input can signal
this using return flags, special return values, or exceptions, to name
some common ways. Can we abstract over this, and mould to the relevant
error handling technique? Often we need to do run-time checking of
arguments, e.g., array indexing bounds, forcing us to introduce lots
of code to deal with the unwanted cases. Can we use mouldable ideas to
simplify the code? In the presentation, we will elaborate on such
examples, discussing how we can free us from awkward syntactic
constraints. +, Writing code in an abstract, high-level style can cut development time
and make code more maintainable and easier to reason about - but at
the cost of lower run-time performance. For performance-critical
applications, such as in numerical programming, this can render modern
abstraction techniques infeasible. Fortunately, code that is easy for
humans to reason about is also easier to reason about
automatically. We're studying different abstraction mechanisms and
generative programming techniques, as well as optimization techniques
to produce efficient code for them. As an example, basic element-wise
operations on arrays may be expressed in terms of high-level
operations, which may be automatically combined in order to increase
performance. I will present some of the things we've been working on
so far, and some of the ideas we have for the future. +
L'algorithmique constructive permet, partant d'une spécification écrite
sous forme d'une combinaison non-efficace de fonctions, de dériver, sous
certaines conditions, des algorithmes parallèles efficaces. Cette dérivation
s'appuie sur des théorèmes d'équivalence de programmes et est formellement
correcte. Elle aide le programmeur à concevoir des programmes parallèles.
Toutefois les bibliothèques de squelettes proposées ne sont pas certifiées.
Dans le cadre d'une collaboration avec l'université de Tokyo, nous proposons
de cibler des squelettes algorithmiques développés en BSML et certifiés à
l'aide de l'assistant de preuve Coq. +, Nous présenterons BSML (Bulk Synchronous Parallel ML), un langage de
programmation de haut-niveau pour machines parallèles, ainsi que des
exemples classiques de parallélisme implémentés dans ce langage. Nous
complèterons cette présentation par une étude comparative des coûts
théoriques de ces algorithmes réalisée sur la grappe de PC du LACL. +
Les besoins croissants en puissance de calcul exprimés par de nombreux
domaines scientifiques exercent une pression très forte sur les
architectures émergentes, les rendant toujours plus performantes mais
toujours plus complexes à maîtriser. Dans ce cadre, le développement
d'outils tirant parti des spécificités de ces architectures (quadri-
et bientôt octo-coeurs, processeurs Cell ou GPU par exemple) devient
une gageure car allier expressivité et efficacité est une tâche
ardue. Les travaux exposés ici montrent comment l'utilisation de la
programmation générative, et en particulier de la méta-programmation
template, permet de répondre au problème de performances et
d'abstractions.
Nous montrerons comment ces techniques ont permis de développer Quaff,
un outil de placement automatique d'applications data-flow sur des
cibles variées comme les clusters, les multi-coeurs ou le processeur
Cell. +, Dans cet exposé je présenterai le modèle bulk-synchronous parallelism (BSP)
des algorithmes et architectures parallèles, ainsi qu'un tour d'horizon des
domaines d'application du parallélisme. BSP propose une vue unifiée des
principaux paramètres de la performance des algorithmes parallèles et de
leur adéquation sur les architectures multi-processeur, multi-coeur et leurs
réseaux de communication interne. Il permet une analyse portable et
extensible des performances ce qui permet d'éviter les principaux pièges de
l'informatique parallèle: mauvaise granularité, réseau mal adapté,
déséquilibres. +
Dans un intergiciel schizophrène, une représentation intermédiaire
des interactions entre composants applicatifs est construite et
manipulée. Cette représentation est neutre vis-à-vis du choix d'une
personnalité application (interface entre les composants et
l'intergiciel) et d'une personnalité protocolaire (interface entre
intergiciels distants). Elle rend possible le découplage entre ces
deux aspects.
Cette représentation doit préserver la structure des données associées
aux interactions. Cependant, sa construction in extenso s'avère coûteuse
dans le cas de données composites complexes. Cette conversion peut être
économisée en remplaçant la réplication complète de la structure par la
définition d'un emballage « fantôme » autour de celle-ci (et de chacun
de ses composants) : il suffit que cet emballage fournisse les accesseurs
permettant de parcourir la structure et de construire un message la
représentant.
Après avoir présenté un exemple concret de représentation neutre
des données structurées, nous montrons comment cette optimisation
peut être mise en oeuvre pour réaliser de manière efficace la
fonction de représentation dans un intergiciel schirophrène. Nous
concluons cette discussion par une évaluation du gain de performance
ainsi obtenu. +, Le langage Ada est connu pour sa sûreté intrinsèque : son typage fort,
ses mécanismes de contrôle de valeurs et son système d'exceptions notamment
permettent d'avoir une grande confiance en les programmes. Comme dit
le vieux proverbe, « En Ada, quand ça compile, ça marche ».
Cependant, une des puissances d'Ada provient également de ses systèmes
de vérification lors de l'exécution du programme. Par exemple, si une
valeur se trouve en dehors de l'intervalle qui lui était autorisé, une
exception, rattrapable par le langage, sera automatiquement levée. Ce
système de vérification dynamique a bien évidemment un coût. Nous verrons
comment le système de compilation GNAT mélange analyse statique et
vérification lors de l'exécution pour fournir la totalité des
garanties définies par le langage tout en minimisant les surcoûts et
la perte de performance. +
L'outil BTL++ (Benchmark Template Library in C++) développé à EDF R&D se
fonde sur la programmation générique et permet de mesurer les performances
de noyaux de calcul intensif. Il s'agit d'une bibliothèque générique dont
la conception vise à faciliter l'extensibilité par l'utilisateur.
Récemment, le lien entre les mesures de performance et la génération
automatique de bibliothèques optimales à été étudié pour le domaine de
l'algèbre linéaire dense. Quelques mesures de performance de noyaux de
calcul à base d'"Expression Template" permettront d'illustrer l'usage de
l'outil BTL++. +, La multiplication des architectures HPC (CPU multi-coeurs, GPU, Cell,..)
implique autant de spécialisations des codes de calcul intensif. Dans un
contexte industriel, les codes de calcul multi-cibles posent alors des
problèmes de maintenance et d'évolutivité importants. La génération
automatique des spécialisations est une réponse à ces problématiques. Pour
le domaine de l'algèbre linéaire, nous étudions les possibilités offertes
par la programmation générique. La mise au point d'une bibliothèque
générique multi-cible et performante constitue le sujet de départ d'une
thèse dédiée aux méthodes de développement HPC qui minimisent l'adhérence
aux machines cibles. +
JoCaml est une extension d'Objective Caml pour la programmation
concurrente et distribuée, inspirée par le join-calcul. Nous avons
récemment publié une nouvelle version de JoCaml, dont la compatibilité
avec OCaml est meilleure que celle de la version initiale de F. Le
Fessant. La nouvelle version pourra facilement être mise à jour au
rythme d'OCaml et est binaire-compatible avec OCaml.
L'exposé s'attachera plus au langage JoCaml qu'au système JoCaml. Il
montrera comment, à partir d'un programme potentiellement
parallélisable écrit en OCaml (le ray tracer du concours ICFP 2001),
on peut facilement produire un programme distribué, dans le cas
abordé, très efficace. Ce sera l'occasion d'aborder la programmation
en JoCaml de la coordination de multiples agents coopérants, d'une
manière simple et concise dans l'esprit de la programmation
fonctionnelle.
JoCaml est disponible en http://jocaml.inria.fr/. +, ReactiveML est une extension d'OCaml basée sur le modèle réactif
synchrone introduit par F. Boussinot au début des années 90. Il permet
la programmation de systèmes tels que les jeux vidéo ou les
simulateurs.
Dans cet exposé, je présenterai ReactiveML à travers l'utilisation et
la programmation de rmltop, le pendant ReactiveML du toplevel
d'OCaml. Ce toplevel permet au programmeur d'écrire interactivement
des programmes ReactiveML qui sont typés, compilés et exécutés à la
volée. Toute expression ReactiveML valide peut être chargée dans le
toplevel et a la même sémantique et la même efficacité que sa version
compilée. +
Je présenterai sur la base d'une démo une application des extensions
de langages, à savoir une extension Java pour l'optimisation. Cet
exemple montre la mise en oeuvre concrète dans Eclipse, les gains de
productivité et de qualité obtenus par rapport aux approches
classiques Java+DSL, la différence entre cette approche et un
générateur de code ou un préprocesseur. Il montre également une
utilisation originale d'un compilateur: la génération automatique
d'interface graphique.
Je parlerai aussi des futurs projets d'Ateji dans le domaine des
extensions de langage. +, Dans cet exposé je présenterai un outil, appelé Tom, qui permet de
simplifier la programmation d'outils de manipulation et de
transformation de structures arborescentes, telles que les AST
(Abstract Syntax Trees) ou les documents XML par exemple.
Tom est un langage de programmation qui ajoute à Java des
constructions inspirées du calcul de réécriture et des langages à
base de règles. On peut, de manière approximative, voir Tom comme une
intégration d'un sous-ensemble de Caml dans Java.
Le langage repose sur trois notions fondamentales :
(i) les termes, qui sont un modèle universel permettant de
décrire des structures arborescentes, et en particulier les notions de
programmes et de preuves.
(ii) les règles, qui permettent de décrire de manière expressive des
transformations.
(iii) les stratégies, qui permettent de contrôler l'application des
règles.
La séparation transformation-contrôle est un point essentiel
permettant de rendre les règles indépendantes de leur contexte
d'utilisation, facilitant ainsi leur écriture, leur réutilisation et
l'établissement de propriétés.
Le Langage Tom est parfaitement adapté à la réalisation d'outils de
transformation et de prouveurs. Son intégration dans Java rend son
utilisation facile, aussi bien dans le milieu académique que dans le
milieu industriel. +
Si une fonction φ promet de manipuler une valeur de type α sans
l'observer, on peut utiliser son code sans risque pour toutes les
affectations possibles de α : que la valeur soit entière (α = int) ou
qu'elle soit un arbre (α = tree), la fonction se comportera
toujours de façon identique. Cette propriété s'appelle le polymorphisme
paramétrique, l'essence de la généricité.
Promettre de ne pas observer de trop près son argument est un fardeau
parfois insupportable pour une fonction, pour des raisons
algorithmiques (comment prendre une décision sans savoir ce que vaut
mon argument ?), ou encore pour des raisons de performances de
bas-niveau (si je sais que α = int, je peux utiliser une primitive
dédiée de mon processeur). Même si le type d'une valeur est caché
derrière un type plus abstrait α, on peut fournir des mécanismes pour
« le redécouvrir » grâce à des tests dynamiques ou à des raisonnements
purement statiques. La propriété qui permet de diriger son calcul par
la forme des types est appelée le polymorphisme intentionnel.
Dans cet exposé, nous présenterons plusieurs versions du
polymorphisme intentionnel offertes par différents systèmes de types
et de preuves sûrs (c'est-à-dire garantissant que les programmes
ne peuvent pas planter et sont corrects vis-à-vis de leur spécification). +
SmartEiffel, également connu sous le nom de GNU Eiffel, est à la fois
un langage et un ensemble d'outils de compilations, de documentation et
de validation.
Le langage SmartEiffel vise à favoriser la mise en pratique des
principales exigences liées au développement d'un gros logiciel par
une grande équipe. En plus d'exigences en terme de qualité, de
sécurité et de documentation, la définition de SmartEiffel est
également soucieuse de l'efficacité du programme à l'exécution. Ainsi,
le modèle des objets qui est à la base du langage intègre également
les types les plus élémentaires sans surcoût potentiel à l'exécution.
Pour sa part, le mécanisme de programmation par contrats qui est
essentiel en matière de documentation est également un bon moyen de
rechercher les meilleures performances à l'exécution.
Durant cet exposé, la visite guidée du langage présentera le modèle
d'objets, la programmation par contrats, la double forme d'héritage
multiple ainsi que le mécanisme des agents. +, Lisaac est un petit langage basé sur la technologie objet à base de
prototype. Plus flexible que l'objet à base de classe, elle permet un
dynamisme et un degré d'expressivité encore inégalés. Lisaac est
inspiré du langage Self pour les concepts d'objets à prototypes et du
langage Eiffel, pour les aspects d'ingénierie logicielle et notamment
pour la programmation par contrat. Enfin, l'objectif étant de
réaliser de la programmation de bas niveau à l'aide d'un langage de
haut niveau, un ensemble de concepts utiles à la programmation système
a été ajouté.
Le langage Lisaac utilise un nombre particulièrement restreint
d'idiomes orthogonaux rendant difficile l'élaboration d'un compilateur
efficace. Son compilateur en fait aujourd'hui l'unique langage à
prototype compilé. Les performances atteintes sont proche des
compilateurs C, voire même au-delà...
Pour étayer, approfondir et illustrer nos propos, nous ferons un
rapide tour d'horizon du développement du système d'exploitation
IsaacOS entièrement écrit en Lisaac.
Durant cet exposé, nous aborderons les thèmes suivants: concept à
prototype versus concept à classe; héritage multiple et dynamique et
autres particuliarité du Lisaac; technique de compilation et résultat
de performance; validation des concepts avec une brève présentation du
système d'exploitation IsaacOS. +
La Low-Level Virtual Machine (LLVM) est un ensemble de bibliothèques
et d'outils qui facilitent le développement et l'optimisation de
compilateurs, de générateurs de code et de machines virtuelles. Clang
et VMKit utilisent LLVM pour leur générateur de code à différents
niveaux: l'un pour la compilation statique de langages de la famille C
(C/C++/ObjectiveC), et l'autre pour la compilation dynamique
d'applications Java ou .Net.
Dans cet exposé, je présenterai ces trois projets, et rentrerai dans
les détails de VMKit, que j'ai développée dans le cadre de ma
thèse. Je finirai par montrer les exemples de recherche auxquels
nous nous adressons avec l'aide de VMKit, au sein de l'équipe de
recherche INRIA/Regal. +, Avec l'avènement du Web et des applications réparties, les machines
virtuelles applicatives sont devenues le support d'exécution de choix
pour la plupart des applications. Développer et optimiser une machine
virtuelle est un travail long et difficile qui requiert plusieurs
années. Il s'avère que la plupart des machines virtuelles possèdent
des composants communs: compilateur à la volée, ramasse-miettes,
vérifieur de type, gestionnaire de threads, gestionnaire
d'entrées/sorties, éditeur de liens paresseux, chargeur dynamique de
code.
AutoVM est une machine virtuelle générique qui factorise ces
composants communs et facilite le développement de nouvelles machines
virtuelles, ou l'amélioration de machines virtuelles existantes.
Dans cet exposé, je présenterai l'architecture logicielle de notre
prototype AutoVM et montrerai sa généricité et son extensibilité. +
Nous décrirons brièvement l'état de l'art de l'utilisation des processeurs graphiques grand public (GPU) pour accélérer le traitement d'image, et nous en discuterons les limites. Puis, nous décrirons GpuCV, une bibliothèque logicielle libre et multi-plateforme pour accélérer par GPU les opérateurs de traitement d'image et de vision artificielle. GpuCV a été conçue pour être compatible avec la bibliothèque OpenCV et permettre d'intégrer facilement des opérateurs accélérés sur GPU dans des applications développées sur CPU. L'environnement GpuCV gère de façon transparente les caractéristiques du matériel, la synchronisation des données, l'activation à bas niveau des procédures GLSL ou CUDA, l'étalonnage et l'aiguillage vers la mise en oeuvre la plus performante et finalement offre un ensemble d'opérateurs de traiement accélérés par GPU. +
Malgré la grande variété des types de données que l'on rencontre dans
le domaine du traitement d'images (1D,2D,3D, scalaires, couleurs,
multi-spectrales, séquences, etc...), nous sommes souvent amenés à
appliquer des algorithmes très classiques, ou des variations de ces
algorithmes, pour le pré-traitement, l'analyse ou la visualisation de
ces données images. Par conséquent, les logiciels et les bibliothèques
que nous utilisons dans notre recherche quotidienne, devraient
également être génériques, afin de s'adapter le mieux possible aux
données à traiter. Dans ce séminaire, je présenterai quelques outils
développés dans cette optique (au laboratoire GREYC, équipe IMAGE),
qui possèdent différents niveaux d'utilisations. Je commencerai tout
d'abord par présenter CImg, une bibliothèque C++ "template" (donc
générique par nature), qui a pour but de faciliter l'implémentation
d'algorithmes de traitements d'images personnalisés. Puis,
j'introduirais G'MIC, un langage de script reprenant la plupart des
éléments de CImg, qui est dédié au traitement et à l'analyse d'images
"de tous les jours". J'essaierai de montrer comment ces différents
outils indépendants sont organisés et comment ils cherchent à aider le
chercheur ou le programmeur en traitement d'images, autant d'un point
de vue programmation pure que d'un point de vue plus haut niveau. +
Le processeur CELL BE développé par le consortium IBM, Sony et Toshiba
a eu un impact important dans le monde du calcul scientifique mais
aussi dans le monde du jeu. Il est le processeur de base de la
première machine à avoir atteint 1 Pflops et aussi celui de la Play
Station 3 de Sony. Pour arriver à ce niveau de performance, il intègre
9 coeurs hétérogènes interconnectés par un bus. Le coeur principal
(PPE) appartient à la famille des PowerPC. Les 8 autres coeurs (SPE)
sont spécialisés pour le calcul. Après une présentation détaillée de
l'architecture du processeur, nous développerons son mode de la
programmation : lancement de threads de calcul sur les SPE, échange de
données, programmation SIMD. +, La méthode multipôle rapide (Fast Multipole Method, FMM) permet de
résoudre en temps linéaire le problème à N-corps, en astrophysique ou
en dynamique moléculaire par exemple. Nous présentons ici
l'implémentation sur le processeur Cell du calcul du champ proche de
la FMM, ce qui constitue un premier pas vers une implémentation
complète de la FMM sur ce processeur. Nous détaillerons les problèmes
rencontrés, au niveau de l'architecture comme au niveau de
l'algorithmique, ainsi que les diverses optimisations mises en
place. Notre implémentation permet de calculer jusqu'à 8,5 milliards
d'interactions par seconde (115,8 Gflop/s) sur un processeur Cell, et
jusqu'à 17 milliards d'interactions par seconde sur un IBM QS20 (230,4
Gflop/s), pour des distributions uniformes ou non uniformes de
particules. +
Dans cet exposé, nous présenterons Yayi, une bibliothèque générique de
traitement morphologique d'image. Cette base logicielle, écrite en C++
et interfacée avec Python, fournit un nombre croissant de fonctions en
traitement d'image et en morphologie mathématique (distance,
segmentation, etc.). Nous discuterons de la mise en oeuvre générale,
des concepts génériques utilisés dans la bibliothèque, et de leurs
utilisations dans l'élaboration de nouveaux algorithmes. Enfin, nous
présenterons quelques pistes actuellement en développement dans Yayi
pour adresser certains des problèmes levés par la programmation
générique. +
Ce séminaire porte sur certains de mes travaux en matière de
généricité et réutilisation en traitement d'images. Ces travaux sont
présentés à une échelle algorithmique, bas-niveau, et à une échelle
logicielle, plutôt haut-niveau. À l'échelle de l'algorithme, nous
présentons une technique permettant d'étendre la généricité des
algorithmes de traitement d'images par rapport à la région d'intérêt
traitée, en complément de la généricité par rapport aux données
(1D, 2D, 3D, scalaires, couleurs, multi-spectrales, séquences,
etc.) Cette méthode repose sur une adaptation du patron de
conception « Iterator » et sur le polymorphisme de compilation en
C++. Au niveau logiciel, l'objectif de la généricité et de
réutilisation est de faciliter le couplage des algorithmes « purs »
avec des fonctionnalités supplémentaires telles que la visualisation,
l'interface homme-machine, les entrées-sorties... Dans ce cas, je
présente les principes d'une architecture flexible et évolutive
implémentée en C++, combinant la notion de (programmation par) rôle et
la notion de (programmation par) composants réutilisables. Ces travaux
sont illustrés par des applications dans le domaine médical. +, L'une des caractéristiques de la programmation objet est l'intégration
(introduite par Eiffel dans un article de la première conférence OOPSLA en
1986) entre les mécanismes d'héritage, permettant de structurer clairement
la description des systèmes, et de généricité, permettant le paramétrage de
ces descriptions. La combinaison de ces deux techniques d'architecture est
la clé de l'extensibilité et de la réutilisabilité permises par la
technologie objets. L'exposé montrera l'interaction entre la généricité et
l'héritage en Eiffel et l'application de ces concepts aux tâches d'analyse,
de conception et d'implémentation en génie logiciel. De nombreux exemples
illustreront l'application de ces idées, et compareront avec les solutions
adoptées dans des langages tels que Java et C\#. +
La plupart des frameworks de traitement d'images ne sont pas assez
génériques pour garantir une réutilisabilité effective des structures
de données et des algorithmes, tout en préservant performances et
facilité d'utilisation, et en restant proche de la théorie. Dans
cette présentation, nous proposons un cadre logiciel pour le
traitement d'images centré sur le paradigme de programmation
générique, cherchant à répondre tant aux besoins pratiques que
théoriques des scientifiques et des développeurs : la mise au point de
méthodes rapides et réutilisables, un niveau de généricité progressif,
la possibilité de traiter des ensembles de données volumineux, une
gestion de la mémoire automatique et efficace, la vérification
statique des types, l'orthogonalité des structures de données et des
algorithmes, etc. Cette approche permet aux utilisateurs de concevoir
et d'implémenter de nouvelles méthodes délivrées des contraintes
habituellement imposées pas les outils logiciels, de pratiquer des
expériences inter-domaines, de généraliser certains résultats et de
transformer facilement des prototypes en de vraies applications. +, Les Diagrammes de Décision (DDs) forment une vaste famille de
structures de données, qui permettent de représenter et manipuler très
efficacement de grandes quantités d'informations. Cependant, parmi les
nombreux types de DDs, l'utilisateur est souvent désemparé pour
choisir le bon. Souvent, aucun type ne répondant exactement à ce qu'il
cherche, l'utilisateur doit faire adapter ses données au type de DDs
choisi.
Le problème est que chaque type de DDs possède sa propre
définition. Il n'existe aucun socle commun qui permette de définir
n'importe quel type de DD. Ce problème se reflète au niveau des
opérations manipulant les DDs. Celles-ci sont aussi spécifiques à
chaque type.
Cet exposé présente les Polymorphic Decision Diagrams, un cadre assez
général permettant de spécifier de nombreux types de DDs
existants. L'utilisateur peut ainsi décrire simplement les DDs
correspondant le mieux aux données qu'il souhaite représenter. Ce
cadre permet de plus d'ajouter dans la spécification les informations
qui permettront de retrouver les performances des types définis
jusqu'à présent. Un exemple concret impliquant des loutres permettra
de montrer les possibilités offertes par ce cadre. +
Le traitement d'images est par nature un procédé discret, au cours
duquel un signal continu est décomposé en un ensemble de pixels, ou de
voxels pour des images tri-dimensionnelles. Au niveau géométrique, cette
nature discrète pose peu de problèmes, car la plupart des opérations
géométriques sont indépendantes de la grille sous-jacente ; au niveau
topologique, le problème est tout autre. Deux des notions fondamentales
de la topologie, le voisinage et la connexité, sont radicalement
différentes entre un espace continu et un espace discret : il est entre
autres impossible de subdiviser un voisinage discret de façon infinie
comme c'est le cas dans un espace euclidien.
Bien que certaines bibliothèques de traitement d'images contiennent des
algorithmes topologiques, notamment de squelettisation, le type de
voisinage utilisé par ces algorithmes est généralement fixé par le code,
ce qui empêche une adaptation facile à un autre type de connexité ou à
un espace de dimension différente.
Ce séminaire présente une méthode générique pour intégrer les notions
discrètes de voisinage et de connexité à une bibliothèque de traitement
d'images programmée en C++. Je montrerai également comment obtenir de
façon simple un algorithme de squelettisation homotopique en utilisant
ces notions. +, Le projet BrainVISA (http://brainvisa.info) est en train de
développer, avec le soutien du projet européen HiPiP
(http://hipip.eu), une architecture générique pour la parallélisation
des applications. Cette architecture fournira un accès à divers moyens
de calculs (fermes de stations de travail, clusters, centres de
calculs, etc.) en s'appuyant sur des solutions existantes pour la
gestion des ressources (Sun Grid Engine, Condor, LSF, etc.) Cette
architecture est développée pour répondre aux besoins croissants de
moyens de calcul dans le monde de la recherche en neuroimagerie.
Au cours de ce séminaire, j'aborderai rapidement le contexte de la
recherche en neuroimagerie en me focalisant sur les besoins en
parallélisation d'applications. Ensuite, je détaillerai la solution
que nous avons choisie pour répondre à ces besoins. +
Dans la recherche multimédia basée contenu, on distingue trois champs d'applications différents : la recherche de cible dans laquelle on désire retrouver un document particulier ; la recherche interactive, dans laquelle l'utilisateur définit l'objet de la requête au fil de son interaction avec le système ; et la catégorisation, où il s'agit d'étiqueter les données en un certain nombre de classes prédéfinies.
Cette présentation fera le tour d'horizon de mes travaux de recherche dans deux de ces domaines. Une première partie concernera la recherche de cible, où je présenterai le cas particulier de la recherche de quasi-copies dans de très grands volumes de données, et en particulier une application à la recherche de scènes urbaines identiques dans le cadre du projet iTowns.
Dans la deuxième partie, je développerai mes travaux récents sur la classification d'images. L'accent y sera mis sur la fusion de descripteurs multimédias et les techniques d'apprentissage statistique permettant d'apprendre conjointement l'opération de fusion avec la fonction de classification. +
L'idée d'une fonction est que la quantité d'entrée détermine complètement la quantité de sortie. En informatique, la quantité est une structure de données qui peut être simple, booléenne, entière, ou complexe, image, graphe, arbre. Dans ce domaine, un champ de recherche est de construire un ensemble de fonctions élémentaires, puis par composition d'en créer des plus compliquées. Pour cette dernière, une solution pratique est le langage Caméléon conçu par V. Tariel et O. Cugnon de Sevricourt, qui est un langage de flux de données génériques dont la sortie est prévue en janvier 2011. Générique signifie que tous les types de données peuvent être intégrés dans le langage. Pour cette première, ce séminaire couvrira quelques définitions de fonctions primaires reliées à l'image, incorporées à la bibliothèque standard de Caméléon. A la manière de l'implémentation de la bibliothèque standard du C++, il y aura l'utilisation d'un côté de l'algorithme générique for\_each en typage statique et de l'autre des opérateurs et des itérateurs organisés en programmation orientée objet. L'itérateur localise l'action suivant différents paradigmes : ensemble fini et dénombrable, voisinage, convolution, zone d'influence. L'opérateur agit suivant différents paradigmes : arithmétique, croissance de régions. +
Depuis 2000, on assiste à un regain d'intérêt pour les langages typés dynamiquement
regroupés sous la bannière "langage de script". Pour les langages de script les plus
populaires, comme PHP, Python ou Ruby, il existe, en plus des implantations
écrites en C, des implantations plus récentes utilisant des environnements
comme la machine virtuelle Java (JVM) ou la plateforme .Net.
Ces implantations sont souvent plus efficaces que les implantations historiques,
pourtant, ces environnements d'exécution utilisent des langages intermédiaires
typés statiquement qui sont peu propices à l'implantation de langage typé dynamiquement.
Partant de ce constat, le Java Community Process a créé la JSR 292 intitulée
"Supporting Dynamically Typed Languages on the JavaTM Platform" dont le but
est de proposer une API facilitant l'implantation et les performances des
langages de script sur une machine virtuelle Java.
Mon exposé se compose de deux parties.
Dans un premier temps, en tant que membre du groupe d'experts, j'essaierai de restituer
de façon didactique les concepts introduits par la JSR 292 en expliquant les tenants et les aboutissants.
La seconde partie, plus personnelle, montrera comment développer l'environnement
d'exécution d'un langage de script en utilisant les outils fournis par la JSR 292.
Je m'appuierai pour cela sur un prototype de langage que j'ai développé et nommé
PHP.reboot. +
Nous étudions la problématique du mélange de paradigmes de programmation
variés plongés dans un environnement concurrent. Dans cette
perspective, nous poursuivons
un cheminement similaire à celui qui conduit du lambda-calcul aux
langages fonctionnels, mais
en prenant comme point de départ le π-calcul. Nous proposons la
machine abstraite des π-threads
dont la principale originalité est l’absence de pile d’exécution.
Cette caractéristique
permet de nous reposer dans nos implémentations sur des algorithmes
simples et naturellement
concurrents, notamment pour ce qui concerne l’ordonnancement et le
ramasse-miettes. Pour ce
dernier, nous proposons un algorithme permettant de récupérer très
simplement les cycles de
processus en interblocage et autres structures bloquantes. +
La plupart des bibliothèques génériques en traitement d’images mettent l’accent sur la généricité, la mise en pipeline d’opérations basiques, mais peu mettent l’accent sur la sélection d’un sous-ensemble de pixels concerné par un algorithme. En pratique de nombreux algorithmes ne s’appliquent que sur un sous-ensemble simple (rectangle) ou complexe (forme contiguë quelconque) de pixels qui ne sont qu’une petite fraction d’une image. La création d’un masque précisant les pixels concernés ne semble pas une solution optimale (contrainte mémoire et calculatoire). Dans le cadre de développement d’algorithmes en traitement d’images et vidéos, le laboratoire Canon Research Centre France (localisé à Rennes) développe une bibliothèque générique de traitement d’images qui ajoute la notion de forme à toute manipulation basique ou complexe d’une image. Une « arithmétique » des formes permet une sélection précise de pixels et une exécution efficace d’algorithme complexe. Les motivations, la mise en œuvre de cette bibliothèque, les outils template utilisés seront présentés et illustrés d’exemples concrets. +
Pour encoder de manière efficace une séquence vidéo, la redondance
temporelle est souvent utilisée. Pour cela, le mouvement entre l'image
considérée et une image de référence est estimé. Cela permet de
générer une prédiction à partir de l'image de référence et seule la
différence entre la prédiction et l'image réelle est enregistrée. Pour
estimer ce mouvement, les codecs se contentent souvent de suivre
l'évolution spatiale de blocs dans l'image. Ils associent, pour chaque
bloc de l'image considérée, un bloc similaire dans un voisinage proche
dans l'image de référence. Nous présentons ici une méthode originale
pour réaliser cette prédiction par compensation de mouvement. Notre
méthode utilise les distances tangentes. Cela permet non seulement
d'estimer l'évolution de la position des blocs de l'image mais en
partie aussi l'évolution du bloc lui-même. Nos prédictions sont donc
de meilleure qualité. Utilisée dans l'encodage de séquences, on peut
espérer un gain de compression non négligeable. Pour valider
l'efficacité de la méthode, nous intégrons cette méthode dans le codec
Theora et mesurons son efficacité en comparant les résultats obtenus
avec notre méthode et ceux obtenus par une stratégie classique (le
block-matching). +
Ces dernières années ont vu exploser le nombre de vidéos disponibles
sur internet. Pour permettre leur exploitation, il est nécessaire de
mettre en place des systèmes analysant automatiquement ces données
multimédia. De tels systèmes permettent notamment d'indexer
automatiquement des vidéos en fonction de leurs contenus. Durant
cette présentation, je m'intéresserai aux récentes avancées effectuées
dans ce domaine. Je présenterai des descripteurs vidéos, développés
dans le cadre de ma thèse, qui capturent le mouvement et l'apparence
d'une vidéo pour les résumer dans une courte signature. Ces
signatures peuvent être utilisées a posteriori pour détecter
différents évènements ou concepts dans les vidéos. +, Conçus à l'origine pour le rendu 2D et 3D, les processeurs graphiques
(GPU) peuvent aujourd'hui être considérés comme des processeurs
génériques massivement parallèles. Mais ce parallélisme impose des
contraintes sur les algorithmes implantés et les types de données
utilisés. D'autre part, le bus de communication entre le processeur
central (CPU) et le GPU peut être un goulot d'étranglement.
Ce séminaire débutera par un aperçu des avantages et inconvénients de
la programmation GPU, puis je présenterai l'implantation d'un
algorithme temps réel de suivi de points dans une vidéo. Je terminerai
par l’introduction de deux petites boîtes à outils : Cuimg et Dige.
Cuimg utilise C++ pour simplifier l'écriture d'algorithmes de
traitement d'images avec CUDA, tandis que Dige, basée sur le framework
Qt, permet le prototypage rapide d'interfaces graphiques. +
Dans ce séminaire je présenterai un algorithme de résolution approchée
pour le problème du Compressive Sensing basé sur la programmation convexe.
Cet algorithme a la particularité d'avoir été pensé dès sa conception pour
tirer partie des architectures matérielles modernes, ce qui permet une
implémentation efficace et rapide sur celles-ci. Bien qu'une résolution
approchée soit en pratique suffisante pour obtenir rapidement une solution
de très bonne qualité, une variante exacte très rapide sera aussi
présentée. Cette dernière n'est toutefois utilisable que sous certaines
conditions. Trois types d'architectures parallèles sont ici envisagées :
des processeurs multi-cœurs avec unités de calcul vectoriel, des
processeurs graphiques (GPU) et le processeur Cell. +
Comment Javascript, un langage dynamique, interprété et non typé,
parvient à être aussi rapide ? Quelles sont les avancées qu'il reste
à faire pour obtenir des performances identiques au langage C ?
Pour illustrer cette présentation, on s’intéressera à l’évolution du
navigateur Mozilla Firefox et aux différentes approches pour résoudre
ce problème. +
The ilastik system developed by our group uses machine learning and
simple interaction techniques to empower users without special image
processing expertise to segment and analyze their 2- and 3-dimensional
image data on their own. It offers a number of easy-to-use workflows
for various common analysis tasks. The talk will present two of these
workflows (“interactive classification” and “region carving”), going
from an online demonstration of the high-level user experience down to
the algorithmic and software design details. Special emphasis will be
put on aspects of genericity and parallelization which facilitate
convenient adaptation of basic building blocks to different contexts
without loss of performance. Examples from challenging biological
applications will illustrate our system's capabilities. +
«The effective exploitation of his powers of abstraction must be
regarded as one of the most vital activities of a competent
programmer.» disait Dijsktra.
En effet, pour aborder la complexité d'un problème, l'explicitation
des concepts utiles à sa formalisation et à sa résolution est bien
souvent une étape clé. Lorsque que l'on étend ce processus à une
classe de problèmes qui partagent les mêmes concepts, il est naturel
de se doter d'un langage le plus approprié possible pour manipuler ces
abstractions spécifiques à un domaine (en anglais, «Domain Specific
Language»).
Comment implémenter ces DSLs? Une première approche classique reflète
les constructions du DSL sous la forme d'un jeu de fonctions de
bibliothèque. L'avantage de cette approche est d'utiliser directement
son langage généraliste préféré, et sa chaîne de compilation
optimisée, de façon à générer du code machine à moindre frais. Par
contre, dans ce cadre, l'écriture de passe d'optimisations spécifiques
au DSL - à moins d'utiliser des techniques pointues de
méta-programmation - est a priori impossible.
Une seconde approche, opposée, consiste à écrire un compilateur pour
le DSL à partir de zéro. Toute liberté est alors donnée à
l'implémenteur d'intégrer à son compilateur des passes d'optimisation
spécifiques… mais au prix d'une réimplémentation de passes de
compilation déjà présentes, et certainement plus abouties, dans le
compilateur de son langage généraliste favori.
Dans cet exposé, je présenterai les travaux de Martin Odersky et
son équipe sur la virtualisation de DSLs à l'intérieur du langage de
programmation Scala. La virtualisation de langage utilise
intensivement le polymorphisme et la composition mixin de Scala ainsi
que des techniques de génération de code à l'exécution pour embarquer
des langages spécifiques dans Scala dont la compilation peut
réutiliser des modules du compilateur mais aussi étendre ces derniers
par des optimisations spécifiques au domaine. +, Nous traitons du problème de la conception d'un compilateur où des
informations sur le coût à l'exécution du code objet sont retournées
en tant qu'annotations de coût sur le code source, et ce de façon
certifiée correcte. Pour cela, nous avons besoin d'une idée souple et
précise : (i) du sens donné aux annotations de coût, (ii) de la
méthode pour les prouver correctes et précises, et (iii) de la manière
d'en composer les preuves. Nous proposons ce que nous appelons une
approche par étiquetage pour répondre à ces trois questions. Dans un
premier temps, nous montrons son application sur un compilateur jouet.
L'étude formelle qui en découle suggère que l'approche par étiquetage
a de bonnes propriétés de compositionnalité et de passage à l'échelle.
Afin de s'en convaincre davantage, nous rapportons notre retour
d'expérience sur l'implémentation d'un compilateur prototype écrit en
ocaml pour un large sous-ensemble du langage C. +
L'industrie des effets spéciaux produit une grande quantité d'images
qu'il faut traiter et afficher. Dans le cadre de ses développements
internes, Mikros Image a développé et mis en Open Source un player
d'images temps réel : duke. Dans cet exposé je décrirai quels sont
les enjeux techniques d'un tel logiciel (allocation mémoire, accès
disque, multiplicité des formats, affichage, traitement...) puis
j'expliquerai plus en détails les étapes de la conception d'un
composant essentiel permettant de lire et décoder le plus rapidement
possible les images à afficher. Ce composant ayant pour but d'être
intégré dans d'autres outils, il doit être réutilisable. +
Une question fondamentale pour mes recherches est de savoir ce qu'est
une image. Cela peut sembler à première vue une question trop simple :
une image, c'est un ensemble de points. Mais ces points sont reliés
entre eux, c'est ce qu'on appelle une structure, et ils ont des
données de types multiples qui leur sont attachées. La bibliothèque
Milena, développée au LRDE, est une bibliothèque générique dédiée au
traitement d'images. Dans Milena, trois axes indépendants sont
développés : l'axe des structures, l'axe des données, et celui des
algorithmes, c'est-à-dire de ce qu'on peut faire avec une image.
Dans cet exposé, je vais développer plusieurs exemples dans lesquels
je choisirai un algorithme et un type de données, en faisant varier la
structure. Changer la structure, c'est penser les images d'une manière
différente, et c'est quelque chose d'extrêmement porteur en recherche.
- Un premier exemple est celui d'un algorithme classique de
segmentation : la ligne de partage des eaux. Originellement pensé sur
les pixels, sa traduction dans le cadre des arêtes donne le problème
classique d'arbre couvrant de poids minimum. Si la ligne de partage
des eaux est très connue en traitement d'images, les arbres de
poids minimum sont très utilisés en classification. Un pont naturel
est alors établi entre deux communautés différentes, et les idées
provenant de ces deux communautés peuvent être combinées.
- Un deuxième exemple est celui de la représentation arborescente des
images. Pour illustrer, tant les lignes de niveaux que les
composantes connexes des ensembles de niveaux (les coupes) des
images sont naturellement structurées en arbre : deux lignes ou deux
composantes sont soit disjointes soit emboîtées. On peut filtrer
une image en éliminant de l'arbre tous les nœuds qui ne vérifient
pas un critère. Mais on peut aussi considérer l'arbre lui-même comme
une image, et appliquer sur cet arbre un algorithme de traitement
d'images. C'est une idée récursive très riche.
D'autres exemples pourront être développés en fonction du temps : liens
entre ligne de partage des eaux topologique et segmentation
hiérarchique, topologie discrète dans divers cadres...
La bibliothèque Milena permet d’appliquer la plupart des algorithmes
existants à une nouvelle structure, ce qui est un gain de temps
incontestable. Cela permet de se concentrer sur ce qui fait le cœur
de mon métier: chercher un algorithme plus efficace, adapté à un type
de structure, ou encore chercher quelles sont les propriétés
mathématiques d’un algorithme sur une structure donnée.
Concilier généricité et performance des systèmes de vision a toujours
été au cœur des préoccupations scientifiques du laboratoire
d'Électronique et Informatique d'ENSTA-ParisTech. Nous y avons abordé
ce problème sous différents points de vue: électronique,
algorithmique, et logiciel. Depuis nos travaux sur les rétines
programmables et leur algorithmique exotique, nous avons
progressivement intégré la multiplicité des modèles et structures de
données, ainsi que l'emprise des architectures sur étagères, pour
appréhender l'hétérogénéité des systèmes multi-plateformes.
Dans cette présentation à deux voix, on abordera le problème sous deux
angles complémentaires, l'un touchant au modèle et aux algorithmes,
l'autre au logiciel et aux plateformes de calcul.
Ce premier exposé présente un modèle générique de traitement et de
représentation des images fondé sur les espaces de caractéristiques
"local jets" (LJ, ou dérivées partielles multi-échelles), comme
exemple de cadre algorithmique unifié. Grâce à un espace où la
métrique naturelle est directement liée à la similarité visuelle, ce
cadre permet d'aborder un grand nombre d'opérateurs de traitement
d'images de bas niveau, qui correspondent généralement à la
rétro-projection dans l'espace image de points de l'espace des
caractéristiques transformé. Il permet aussi d'aborder des
représentations visuelles de plus haut niveau (modèles d'objet par
exemple) à partir de statistiques globales extraites de l'espace des
caractéristiques. On justifiera cette représentation et on
l'illustrera par diverses applications : Moyennes non locales
(NL-Means) par Convolution dans l'espace LJ pour le débruitage de
vidéos, Calcul du flux optique par recherche du plus proche voisin
dans l'espace LJ, Modélisation de fond statique par échantillonnage de
l'espace LJ, Détection d'objets par transformée de Hough dense... +, Dans ce second exposé, Matthieu Garrigues parlera de ses travaux sur
l'analyse des mouvements apparents dans un flux vidéo. La primitive de
base, présentée dans un séminaire précédent, permet le suivi temps
réel (supérieur à 30 images par seconde) de plusieurs milliers de
particules. Ces travaux nous ont permis de développer un cadre
générique facilitant l'analyse de scènes dynamiques prises de caméras
fixes ou mobiles. Nous montrerons comment cette brique logicielle a
été utilisée dans deux exemples d'applications : l'extraction des
plans principaux et l'estimation de la profondeur dans un système
mono-caméra. Le suivi de particules a été implémenté sur processeurs
graphiques avec le framework CUDA, et sur CPU-multicœurs avec
OpenMP. Nous expliquerons comment C++ a été utilisé pour factoriser un
maximum de code entre ces deux implémentations. +
L'arrivée des GPU (Graphics Processing Unit) a profondément changé la
manière de concevoir la notion de coprocesseur. A moins de 500€, il est
désormais possible d'avoir à sa disposition une puissance de calcul qui
n'était réservée jusqu'à un passé récent qu'aux grands centres de calcul. La
société Nvidia, en mettant au point l'environnement CUDA, a fourni à la
communauté des développeurs des moyens simples et efficaces pour rendre
cette puissance de calcul accessible au plus grand nombre. Depuis, sous
l'impulsion de la société Apple, le standard OpenCL est venu ouvrir la voie
d'une véritable parallélisation des applications sur l'ensemble des
ressources processeur offertes aux développeurs.
Cet exposé décrira les différentes technologies permettant la programmation
parallèle des GPU en mettant l'accent sur les contraintes actuelles et les
progrès à venir des futures architectures comme le processeur Kepler. Des
démonstrations ainsi que des exemples de code viendront compléter cet
exposé. +
(Morphological Filtering in Shape Spaces: Applications using Tree-Based Image
Representations)
Connected operators are filtering tools that act by merging elementary
regions of an image. A popular strategy is based on tree-based image
representations: for example, one can compute a shape-based attribute on
each node of the tree and keep only the nodes for which the attribute is
sufficiently strong. This operation can be seen as a thresholding of the
tree, seen as a graph whose nodes are weighted by the attribute. Rather than
being satisfied with a mere thresholding, we propose to expand on this idea,
and to apply connected filters on this latest graph. Consequently, the
filtering is done not in the image space, but in the space of shapes built
from the image. Such a processing is a generalization of the existing
tree-based connected operators. Indeed, the framework includes classical
existing connected operators by attributes. It also allows us to propose a
class of novel connected operators from the leveling family, based on shape
attributes. Finally, we also propose a novel class of self-dual connected
operators that we call morphological shapings. +, Le model checking est une technique de vérification formelle
automatique. Prenant en entrée un modèle décrivant toutes les exécutions
possibles du système et une propriété exprimée sous la forme d'une formule
de logique temporelle, un algorithme de model checking répond si le modèle
satisfait ou non la formule. Le problème principal du model-checking est
l'explosion combinatoire de l'espace d'états décrivant le système.
Afin d'améliorer les performances, on a apporté les contributions suivantes
à l'approche automate du model checking. D'abord l'amélioration de
l'algorithme de vérification en deux passes de l'approche basée sur les
automates Testeur TA (Testing Automaton). Ensuite la proposition d'une
méthode permettant de transformer un automate TA en un automate vérifiable
en une seule passe, qu'on a appelé STA (Single-pass Testing
Automaton). Enfin, la contribution la plus significative est un nouveau type
d'automate baptisé TGTA (Transition-based Generalized Testing
Automaton). L'apport principal de cette nouvelle approche consiste à
proposer une méthode permettant de supprimer les transitions bégayantes dans
un TGTA sans avoir besoin, ni d'ajouter une seconde passe comme dans
l'approche TA, ni d'ajouter un état artificiel comme dans l'approche STA. +, Le model checking est une technique qui permet de s'assurer qu'un système
vérifie un ensemble de caratéristiques appelées propriétés. Le système et la
négation de la formule sont ensuite représentés de manière abstraite (ici un
automate) pour pouvoir détecter des comportements incohérents. Ces
propriétés ont été classifiées et possèdent des particularités qui peuvent
être exploitées afin de réduire la complexité du processus de
vérification. Nous montrerons ici comment tirer parti dynamiquement des
différentes classes de formules. +
The Single-chip Cloud Computer (SCC) is a 48-core experimental processor
created by Intel Labs targeting the many-core research community. The 6x4
mesh Network-on-Chip provides 24 tiles with 2 cores each. All cores are
independent and run their own instance of an operating system. It has
hardware support (local buffers on the tiles) for sending short messages
between cores, and allows for voltage and frequency control at 8 and 2 cores
respectively.
We have already modified the SVP runtime system to use these on-chip buffers
for the communication between threads executed on separate cores. We also
created a visual application for manual process migration and scheduling on
the SCC as well as a library for customized voltage and frequency scaling on
the chip.
Currently we focus on automated parallelization and mapping of one or
multiple sequential programs onto the 48 cores by modifying the daedalus
framework to target the SCC. The daedalus framework parallelizes sequential
C programs using Kahn Process Networks (KPNs) and generates code to run the
KPN on multiple hardware platforms like for example an FPGA, SMP CPU or
GPU. The SCC backend, which is work in progress, should result in a tool
that utilizes the SCC cores in an optimal way by means of performance and
energy consumption. It should also allow the system to dynamically adapt on
changes in the computational or communicational needs of the processes by
scaling frequency and migrating processes. +, Afin d'exploiter le potentiel des puces multi-cœurs pour une performance
évolutive et à haut rendement énergétique, le projet Apple-CORE a
co-conçu un modèle général d'architecture matérielle et une interface de
contrôle de parallélisme. Cette interface, appelée SVP, est réalisée par
du matériel sur puce dédié à la gestion de la concurrence de programmes
parallèles exécutés sur plusieurs cœurs. SVP se base sur les principes
de synchronisation de flux de données («data flow»), de programmation
impérative et d'exécution efficace du parallélisme en termes de budget
temps et énergie. Les composants matériels correspondants peuvent
coordonner plusieurs cœurs RISC équipés de multi-threading matériel,
organisés en clusters de calcul sur puce, dits «Microgrids».
Comparés à l'approche traditionnelle «accélérateurs», les Microgrids sont
destinés à être utilisés comme composants dans les systèmes distribués sur
puce contenant à la fois des grappes de petits cœurs et optionnellement de
gros cœurs –optimisés pour l'exécution séquentielle– disponibles en tant que
«services» pour les applications. Les principaux aspects de cette
architecture sont l'asynchronisme, c'est-à-dire la capacité à tolérer les
opérations irrégulières avec des temps de latence longs, un modèle de
programmation à échelle invariante, une vision distribuée de la puce, et une
mise à l'échelle transparente de la performance d'un seul code binaire à
plusieurs tailles de grappes de cœurs.
Cette présentation décrit le modèle d'exécution, la micro-architecture des
cœurs, sa réalisation au sein d'une plateforme et son environnement
logiciel. +
Avec l'avènement du Web et du besoin de protéger les utilisateurs contre des
logiciels malicieux, les machines virtuelles langages, comme les machines
virtuelles Java et .Net, sont devenues la norme pour exécuter des
programmes. Dans cet exposé, je vais présenter les travaux que j'ai menés
ces dernières années et qui se sont concentrés sur trois aspects des
machines virtuelles: leur design, leur sûreté de fonctionnement, et leur
performance sur les architectures multi-cœurs.
Ma première contribution est VMKit, une bibliothèque qui facilite le
développement de nouvelles machines virtuelles performantes en cachant leur
complexité dans un ensemble de composants réutilisables. Ma seconde
contribution est I-JVM, une machine virtuelle Java qui élimine les huit
vulnérabilités connues qu'un composant de la plateforme OSGi pouvait
exploiter. Ma troisième contribution vise à améliorer les performances des
machines virtuelles sur les architectures multi-cœurs en se focalisant sur
les verrous et les ramasse-miettes: avec un mécanisme de verrouillage qui
surpasse tous les autres mécanismes connus lorsque le nombre de cœurs
augmente, et avec avec une étude des goulets d'étranglement des
ramasse-miettes sur les architectures multi-cœurs. +
En morphologie mathématique, la représentation d'une image par l'arbre
des formes n'est en fait pas vraiment auto-duale: elle se heurte à la
dualité entre séparation et connexité (c4 vs. c8 en 2D) et au final
des aberrations apparaissent. À la recherche d'un algorithme original
pour le calcul de l'arbre des formes, une nouvelle représentation
discrète d'images 2D est apparue. Définie sur la grille de Khalimsky
avec la topologie d'Alexandroff et s'appuyant sur l'analyse
multivoque, cette représentation a la particularité de satisfaire à de
nombreuses propriétés du continu et de s'affranchir des problèmes
topologiques classiques. +
SMIL est une bibliothèque de traitement d'images 2D/3D. Elle a été
développée pour répondre à une demande de plus en plus forte (en
particulier dans le cas de projets industriels) en termes de
performances : taille d'images (2D ou 3D) et temps d'exécution.
Développée en C++ et utilisant les templates, elle peut être utilisée
avec n'importe quel type standard de données. Un effort important a
été porté sur la factorisation du code (par le biais de functors),
d'une part, pour faciliter l'intégration de nouvelles fonctions, et
d'autre part pour concentrer les parties du code permettant
l'optimisation. Ces "briques" communes optimisées utilisent le code
SIMD généré par l'auto-vectorisation de gcc et sont également
parallélisées grâce à l'utilisation d'OpenMP. +
Large distributed systems on the Internet are subject to hostile
environmental conditions such as node failures, erratic communications, and
partitioning, and global problems such as hotspots, attacks, multicast
storms, chaotic behavior, and cascading failures. How can we build these
systems to function in predictable fashion in such situations as well as
being easy to understand and maintain? In our work on building
self-managing systems in the SELFMAN project, we have discovered a useful
design pattern for building complex systems, namely as a set of Weakly
Interacting Feedback Structures (WIFS). A feedback structure consists of a
graph of interacting feedback loops that together maintain one global system
property. We give examples of biological and computing systems that use
WIFS, such as the human respiratory system and the TCP family of network
protocols. We then show the usefulness of the design pattern by applying it
to the Scalaris key/value store from SELFMAN. Scalaris is based on a
structured peer-to-peer network with extensions for data replication and
transactions. Scalaris achieves high performance: from 4000 to 14000
read-modify-write transactions per second on a cluster with 1 to 15 nodes
each containing two dual-core Intel Xeon processors at 2.66 GHz. Scalaris
is a self-managing system that consists of five WIFS, for connectivity,
routing, load balancing, replication, and transactions. We conclude by
explaining why WIFS are an important design pattern for building complex
systems and we outline how to extend the WIFS approach to allow proving
global properties of these systems. +
Le compilateur GCC est extensible via des greffons (plugins) depuis
plusieurs années. Mais c'est un logiciel libre complexe (de 10MLOC) et
encore en évolution, dont on décrira grossièrement l'architecture. Écrire
des greffons en C est fastidieux.
Le language d'extension MELT (domain specific language) permet d'étendre
moins péniblement le compilateur GCC. Il offre une syntaxe régulière et
simple, inspirée de LISP. MELT est traduit en du code C (ou C++) adapté aux
internes de GCC et son implémentation (en logiciel libre) est
auto-amorcée. Il offre des traits permettant des styles de programmation de
haut niveau (styles fonctionnel, objet, réflexif).
On décrira un peu l'implémentation de MELT, sa syntaxe et ses traits
caractéristiques, et les exemples d'extensions. +
Il existe de nombreux langages informatiques, et les débats concernant leurs
avantages et inconvénients respectifs sont nombreux, mais peu considèrent la
question du développement d'applications sécurisées, c'est-à-dire robustes
contre les actions d'agents malveillants. C'est l'optique abordée dans cette
présentation, qui rebondit sur de nombreuses illustrations dans différents
langages afin de pouvoir cerner ce que seraient les bonnes propriétés d'un
langage vis-à-vis de la sécurité, mais aussi des recommandations de codage
pertinentes ou encore des outils pertinents pour le développement et
l'évaluation d'applications de sécurité. +
Le réductionnisme est une technique réaliste de conception et implantation
de vrais langages de programmation, et conduit à des solutions plus faciles
à étendre, expérimenter et analyser. Je vais décrire la conception et
l'implantation de GNU epsilon, un langage de programmation extensible, basé
sur un langage-noyau minimaliste impératif du premier ordre, équipé de
mécanismes d'abstraction forts et avec des possibilités de réflexion et
auto-modification. Le langage peut être étendu à des niveaux très hauts: en
utilisant des macros à la Lisp et des transformations de code à code
réécrivant les expressions étendues en expressions-noyau, on arrive à
ajouter les clôtures et les continuations de première classe au dessus du
noyau.
Les programmes qui ne s'auto-modifient pas peuvent être analysés
formellement, grâce à la simplicité de la sémantique. Je vais parler
rapidement d'une analyse statique dont j'ai prouvé une propriété de
«soundness» par rapport à la sémantique dynamique. Le langage se prête à une
implantation efficace: je vais montrer un prototype de compilateur natif
particulièrement simple. +
Address & Thread sanitizer sont des outils destinés à détecter les
erreurs d'accès à la mémoire ainsi que les erreurs d'accès concurrents
en environnement multi-threads.
Ces outils sont constitués de deux parties logiques distinctes: une
partie instrumentant le code généré de manière statique, et un
environnement d'exécution.
Cet exposé présente l'implémentation de Address & Thread Sanitizer dans
GCC, les principes de fonctionnement de l'environnement d'exécution de
ces deux outils ainsi que les futures directions du projet. +
CPC est une extension concurrente du langage C. Le code CPC, en style à
threads, est traduit par le compilateur CPC en un code à style à événements;
ce code peut ensuite être exécuté, au choix du programmeur, par des threads
natifs « lourds » ou par un ordonnanceur à événements manipulant des
structures de données extrêmement légères. Cette technique d'implémentation
induit un style de programmation original, où les threads sont « gratuits ».
Cependant, le programmeur peut choisir d'utiliser des threads natifs
« lourds » lorsque c'est nécessaire, par exemple pour exploiter le
parallélisme du matériel ou utiliser des bibliothèques bloquantes.
La technique de compilation de CPC est basée sur des techniques formalisées
et bien connues de la communauté de la programmation fonctionnelle, telles
que la conversion en style à passage de continuations (CPS), le
lambda-lifting, ou l'introduction de fonctions terminales. La correction de
ces techniques a été prouvée formellement.
Dans cet exposé, je donnerai quelques exemples du style typique de
programmation en CPC tirées de Hekate, un seeder BitTorrent écrit en CPC.
Je décrirai ensuite la transformation en style à passage de continuations et
je décrirai la technique de traduction utilisée par le compilateur CPC. +
Component trees are essential tools in several morphological processing
methods, such as attribute filtering, or visualization, or the computation
of topological watersheds. Algorithms for computation of these trees fall
into two main categories: (i) Flood-filling algorithms, exemplified by the
algorithms of Salembier et al (1998), Hesselink (2003), and Wilkinson
(2011), and (ii) Union-find methods, such as Najman and Couprie (2006),
and Berger et al (2007). As images become larger, and parallel computers
become commonplace, there is an increased need for concurrent algorithms to
compute these trees. The first such algorithm was published by Wilkinson et
al in 2008, and was based on the divide-and-conquer principle. It splits up
the data spatially, computes local component trees using any arbitrary
algorithm which yields a union-find type representation of each node, and
glues these together hierarchically. The main drawback of this method is
that it does not work well on high-dynamic-range images, because the
complexity of the glueing phase scales linearly with the number of grey
levels.
In the current work, carried out by Moschini, Meijster, and Wilkinson within
the HyperGAMMA project, we develop a new algorithm for floating point or
high-dynamic-range integer images. It works in a two-tier process, in which
we first compute a pilot component tree at low dynamic range in parallel,
with one grey level per processor using dynamic quantization, and
Salembier's flood-filling method to build the local trees, and the previous
parallellization scheme. After this, a refinement stage is performed. This
refinement stage is based on the algorithm of Berger et al. As such, the new
algorithm combines the two main types of algorithm in a single framework.
Timings on images of up to 3.9 GPixel indicate a speed-up of up to 22 on 64
cores. The algorithm is more than 14x faster than the fastest sequential
algorithm on the same machine. We will apply the new algorithm to
astronomical data sets, including improvements to the SExtractor tool for
object detection. The importance of the new algorithm extends beyond
computation of component trees because it allows development of a fast
alpha-tree algorithm suitable for any pixel-difference metric in case of
vector images (i.e. not just $L_\infty$-based metrics on low dynamic range
colour images).
Le Web a subi en quelques années une évolution radicale, passant d'une
plateforme de données à une plateforme d'applications. Mais la plupart des
outils de programmation n'ont pas été conçus pour cette nouvelle vision du
Web.
Le projet Ocsigen a pour but d'inventer de nouvelles techniques de
programmation adaptées aux besoins des sites Web modernes et des
applications Web distribuées. Il permet de programmer les parties client et
serveur dans le même langage, et même, comme une seule et même
application. La puissance expressive du langage OCaml permet d'introduire
une abstraction des technologies sous-jacentes dans le but de simplifier la
programmation d'interactions Web complexes. Le système de types très avancé
du langage permet d'améliorer la fiabilité des programmes et le respect des
standards. Cela permet aussi de réduire beaucoup le temps de
développement.
Cet exposé donnera un aperçu global du projet et montrera comment écrire un
exemple d'application simple. +
Les automates acycliques sont utilisés dans tous les logiciels de traitement
de la langue naturelle essentiellement pour la représentation des lexiques,
des dictionnaires et des interprétations morpho-syntaxiques des textes.
Nous présenterons des résultats sur les stratégies de construction, de
manipulation et de stockage de ces automates. En particulier un algorithme
de construction dynamique. +
CLAIRE est un langage créé il y a une vingtaine d'années pour développer,
partager et enseigner des algorithmes pour la recherche
opérationnelle. Notre ambition première était de créer un pseudo-code
exécutable, qui permette à la fois de décrire simplement des algorithmes
complexes et de les exécuter facilement, grâce à un interprète, et
rapidement, grâce à un compilateur.
Après avoir brièvement rappelé l'histoire et les motivations de ce projet,
la deuxième partie de l'exposé donnera des exemples de fragments de code,
ainsi que quelques exemples d'applications réussies qui donnent un peu de
crédit à cette ambition.
La troisième partie fera un zoom sur certaines propriétés originales de
CLAIRE, qui font que ce langage de programmation conserve un certain intérêt
dans le paysage de 2014. En particulier, CLAIRE permet de décrire des
algorithmes d'exploration arborescents avec des mécanismes natifs de
raisonnement hypothétique. Un autre intérêt de ce langage est le haut niveau
de polymorphisme paramétrique, qui permet de traiter des fragments de code
comme des structures de données. CLAIRE a été utilisé pour développer
différents outils d'aide à la décision, de la résolution de problèmes
d'optimisation combinatoire à la simulation, en particulier dans le cadre de
GTES (simulation par jeux et apprentissage).
La dernière partie de cet exposé fera la liste des ressources disponibles
pour répondre à la question: pourquoi s'intéresser à un langage désuet ``20
ans après'' ? Le code de CLAIRE - méta-description, interprète et
plate-forme de compilation - est disponible. Une partie des fragments de
code disponibles peuvent soit servir de source d'inspiration (lorsqu'il
s'agit de fonctionnalités qui restent originales) soit de code réutilisable. +