Talk abstract
From LRDE
This is a property of type Text.
S
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. +
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. +
Nife est un langage de programmation ``Forth-like'': basé sur les principes du
langage Forth, défini par Charles H. Moore dans les années 1960, il n'en
reprend pas la totalité des fonctionnalités. Son ambition est d'offrir
aux non-informaticiens qui ont besoin de faire des mesures, de contrôler des
appareils distants, de surveiller des processus industriels, de manipuler
des grandes collections de données, de faire des calculs, des filtrages, des
statistiques, de pouvoir le réaliser facilement, dans un environnement Linux
à faible coût.
Simple, n'importe qui peut comprendre le fonctionnement de ce langage en
quelques minutes, et le maîtriser totalement en quelques heures - une
semaine tout au plus. Il peut aussi être utilisé plus modestement comme une
super calculatrice, pour faire ses comptes ou des calculs d'inversion de
matrice. Le public concerné est donc très large.
Une extension de Nife pour les systèmes embarqués lui permet de pouvoir être
directement chargé sur de petites ou moyennes unités de calcul. Pour cela,
on lui associe un noyau ``bootable'' et il devient Knife : Kernelable Nife.
Dans ce cas, il devient un outil puissant pour coder dans des environnements
où la mémoire est denrée rare, et où le côté ``langage dynamique'' va
permettre de résoudre des problèmes là où d'autres langages vont échouer. +
L'informatique graphique 3D, qu'il s'agisse de modélisation de formes,
d'analyse d'animation ou de synthèse d'images, exploite intensivement divers
types de structures spatiales telles que les hiérarchies volumes englobant,
les cages de déformation, les squelettes d'animation ou bien encore les
structures médianes.
Dans cette présentation, je reviendrai sur quelques uns de nos travaux
récents sur ce sujet. Je détaillerai notamment une nouvelle forme de
représentation d'objets 3D, les Sphere-Meshes, bien adaptés à
l'approximation extrême de forme et à l'auto-rigging pour la déformation
interaction. Je discuterai ensuite plusieurs projets liés à l'analyse de
formes, dont le système CageR pour l'ingénierie inverse de modèles issus
de performance capture. J'aborderai enfin le rendu temps-réel et le calcul
GPU dans le cadre l'éclairage global, qui s'appuie lui aussi sur la gestion
efficace d'une structure particulière : un arbre de radiance.
À chaque étape, je donnerai des éléments sur l'implémentation pratique de
ces approches et sur les nombreux défis qu'il reste à relever. +
Generic Tools, Specific Languages is an approach for developing tools and
applications in a way that supports easier and more meaningful adaptation to
specific domains. To achieve this goal, GTSL generalizes programming
language IDEs to domains traditionally not addressed by languages and
IDEs.
At its core, GTSL represents applications as documents / programs / models
expressed with suitable languages. Application functionality is provided
through an IDE that is aware of the languages and their semantics. The IDE
provides editing support, and also directly integrates domain-specific
analyses and execution services. Applications and their languages can be
adapted to increasingly specific domains using language engineering; this
includes developing incremental extensions to existing languages or creating
additional, tightly integrated languages. Language workbenches act as the
foundation on which such applications are built. +
Dans de nombreux domaines on cherche à améliorer les performances des
programmes en faisant appel au « GPGPU »: un ensemble d’outils et de
techniques permettant d’utiliser le GPU d’une machine afin de lui déléguer
d'autres calculs que les traditionnelles routines de dessins. Cependant,
écrire un programme qui exploite à la fois le GPU et le CPU n’est pas une
tâche facile. Même lorsque les algorithmes se prêtent bien à la
programmation GPU il arrive que le gain en performance soit décevant. L’un
des principaux problèmes reste la gestion de la mémoire et surtout du
transfert de données entre le GPU et le CPU. En effet l'optimisation des
temps de transfert est délicate et peut nécessiter plusieurs jours d’analyse
et de réécriture pour obtenir de bonnes performances.
CUDA offre de nouveaux outils pour résoudre ce problème. Des outils de
profilage de code permettent de voir où se situent les problèmes de
transfert. UVM (Unified Virtual Memory), le nouveau modèle de gestion de la
mémoire, permet de tirer pleinement parti de CUDA bien plus facilement que
par le passé.
C’est à l’utilisation de ces nouvelles techniques que nous nous intéressons
dans cette présentation. +
Au printemps 2014, j'ai animé un MOOC d'initiation à l'informatique, centré
sur la programmation récursive. Bien que loin d'être massif, ce MOOC a
permis d'expérimenter ce nouveau medium ainsi que de mettre à l'épreuve une
infrastructure de correction automatisée. L'exposé portera sur ces deux
aspects et présentera également les nouveautés prévues pour la prochaine
édition de ce MOOC. +
L’accroissement exponentiel de la complexité technique des logiciels métiers
a du mal à être compensée par les progrès du génie logiciel : les coûts et
les délais augmentent jusqu’à ce que l’intérêt de l’informatique soit
fondamentalement remis en cause dans certains cas, arguments rationnels et
légitimes à l’appui. Cette anomalie épistémologique s’explique pourtant par
des erreurs technologiques récurrentes dans l’histoire, des pièges et des
culs-de-sac ralentissant le progrès scientifique. Parmi ces freins : la
dette technique, l’utilisation de trop de technologies, trop élitistes pour
être correctement utilisées en général, et le niveau maximal de
compréhension et d’analyse de chaque humain, qui est fortement variable mais
toujours plafonné.
La technologie Faveod sert à éviter ces freins par la formalisation
structurée et factorisée des besoins métiers, applicatifs et techniques dans
un modèle générique et exhaustif. L’analyse continue des évolutions
collaboratives de ce modèle permet la production totalement automatisée et
instantanée de sa traduction technique : l’application cible en cohérence et
en qualité. La gestion de la complexité des facteurs influant sur la qualité
logicielle étant déléguée à la technologie, il devient possible d’augmenter
son niveau par accumulation linéaire sans dépendre des facteurs humains
limitants. +
Motivé par de nombreuses applications, allant de la cryptographie au
calcul mathématique, le calcul formel s'est fortement développé ces
dernières années tant au niveau des algorithmes que des implantations
efficaces. L'efficacité des calculs repose sur celle de bibliothèques
dédiées, pour certaines opérations de base, comme l'algèbre linéaire
dans un corps fini ou avec des entiers multi-précision. Devant la
multiplicité des domaines de calcul et des variantes algorithmiques
disponibles, la conception de ces bibliothèques doit concilier une
forte généricité avec l'efficacité.
Nous allons présenter comment cette problématique est abordée dans les
bibliothèques d'algèbre linéaire exacte FFLAS-FFPACK (2) et LinBox
(3). Après une présentation générale de ces projets, nous focaliserons
la présentation sur trois aspects représentatifs:
- l'exploitation des diverses arithmétiques de base (entière,
flottante, booléenne), de routines numériques optimisées et leur
intégration au sein d'algorithmes génériques haut niveau ;
- l'approche boîte-noire de la bibliothèque LinBox, proposant un
modèle algorithmique spécifique, particulièrement performant pour les
matrices creuses ou structurées ;
- La parallélisation de code dans FFLAS-FFPACK, basée sur un langage
spécifique (DSL) permettant d'utiliser de façon interchangeable
différents langages et moteurs exécutifs, et de tirer parti du
parallélisme de tâche avec dépendance par flot de données. +, Tout d'abord, nous présentons un cadre générique et rapide pour les
opérations SIMD (single instruction multiple data), écrit en C++ à
l'intérieur de la bibliothèque d'algèbre linéaire exacte FFLAS-FFPACK
(2).
Nous montrons aussi une technique de conception (modules "helper")
basée sur le patron de conception Strategy, qui permet une sélection
efficace d'algorithmes récursifs, des signatures de fonctions plus
simples et plus uniformes. Ensuite, nous appliquons ces techniques
pour accélérer la multiplication entre matrices creuses et vecteurs
denses (SpMV) sur des anneaux Z/pZ, en utilisant des formats conçus
pour les opérations vectorielles et en combinant diverses
représentations.
Finalement, nous généralisons ces techniques aux blocs de vecteurs
(matrices denses, SpMM) et étendons nos algorithmes aux entiers de
Z. Nous appliquons aussi ces briques de base au calcul du rang de
grandes matrices creuses avec l'algorithme bloc-Wiedemann. +
Le C++ est très impopulaire dans la communauté des développeurs web et ce
n'est pas sans raison. Le langage n'offre aucune introspection, ce qui
complique la sérialisation automatique de messages. De plus, l'injection de
dépendances, un design pattern très utile dans les frameworks web issus
d'autres langages, est complexe voire quasi impossible à implémenter en
C++98.
Nous verrons comment l'introspection statique et l'injection de dépendance
ont été implémentés en C++14 grâce à un concept innovant: les symboles de la
bibliothèque IOD (1). Nous verrons ensuite comment Silicon (2), un jeune
framework web, tire parti de ces abstractions et aide les développeurs à
construire des APIs web aussi simplement qu'ils le feraient en Go ou
JavaScript. +
Le traitement géométrique 3D temps-réel a progressivement atteint un niveau
de performance rendant un grand nombre de primitives inspirées du traitement
du signal compatible avec les applications interactives. Cela a souvent été
rendu possible grâce à la co-conception des opérateurs, des structures de
données et du support matériel d’exécution. Parmi les principales classes
d'opérateurs géométriques, le filtrage et le sur-échantillonnage (par
raffinement) ont été exprimés sous des contraintes temps-réel avec
succès. Cependant, l'opérateur de sous-échantillonnage - la simplification
adaptative - demeure un cas problématique pour les données non
triviales.
Dans ce contexte, nous proposons un nouvel algorithme de simplification
géométrique rapide basé sur un nouveau concept : les intégrales de
Morton. En sommant les quadriques d'erreurs associées aux échantillons
géométriques selon leur ordre de Morton, notre approche permet d'extraire de
manière concurrente les nœuds correspondants à une coupe adaptative dans la
hiérarchie implicite ainsi définie, et d'optimiser la position des sommets
du maillage simplifié en parallèle. Cette méthode est inspirée des images
intégrales et exploite les avancées récentes en construction et parcours
haute performance de hiérarchies spatiales.
L'implémentation GPU de notre approche peut simplifier des maillages
composés de plusieurs millions d'éléments à un taux de rafraîchissement
interactif, tout en fournissant une géométrie simplifiée de qualité
supérieure aux méthodes uniformes et en préservant notamment les structures
géométriques saillantes. Notre algorithme est compatible avec les maillages
indexés, les soupes polygonales et les nuages de points, et peut prendre en
compte des attributs de surfaces (normal ou couleur par exemple) et des
métriques d'erreurs alternatives. +