Cette thèse s'appuie sur et reflète l'interaction entre la théorie des modèles et la géométrie de Berkovich. En utilisant les méthodes de Hrushovski et Loeser, nous montrerons que plusieurs phénomènes topologiques concernant des analytifications de variétés sont contrôlés par certains complexes simpliciaux contenus dans les analytifications. Ce travail comporte les résultats suivants. Soit $k$ un corps algébriquement clos et complet pour une valuation non-archimédienne non-triviale à valeurs réelles. 1) Soit $\phi : C' \to C$ un morphisme fini entre deux courbes projectives, lisses et irréductibles. Le morphisme $\phi$ induit un morphisme $\phi^{an} : C'^{an} \to C^{an}$ entre les deux analytifications. Nous construisons une paire de rétractions par déformations qui sont compatible pour le morphisme $\phi^{an}$. Les images des déformations $\Upsilon_{C'^{an}}$, $\Upsilon_{C^{an}$ sont des sous-espaces fermés de $C'^{an}$ and $C^{an}$ et homéomorphes à des graphes finis. Ce type de sous-espace est appelé \emph{squelette}. En outre, les espaces analytiques $C'^{an} \smallsetminus \Upsilon_{C'^{an}}$ et $C^{an} \smallsetminus \Upsilon_{C^{an}}$ se décomposent en une union disjointe de copies de disques unités de Berkovich. Un squelette $\Upsilon \subset C^{an}$ peut-être décomposé en un ensemble des sommets et un ensemble d'arêtes et on peut définir son genre $g(\Upsilon)$.Nous montrons que $g(\Upsilon)$ est un invariant bien défini de la courbe $C$. On appelle cet invariant $g^{an}(C)$. Le morphisme $\phi^{an}$ induira un morphisme $\Upsilon_{C'^{an}} \to \Upsilon_{C^{an}}$ entre les deux squelettes. Nous montrons que le genre du squelette $\Upsilon_{C'^{an}}$ peut être calculé en utilisant certains invariants associés aux points de $\Upsilon_{C^{an}}$. 2) Soit $\phi$ un endomorphisme fini de $\mathbb{P}^1_k$. Soit $x \in \mathbb{P}^1_k(k)$ et $f(x)$ le rayon de la plus grande boule de Berkovich de centre $x$, sur laquelle le morphisme $\phi^{an}$ est une fibration topologique. Nous voyons que la fonction $f : \mathbb{P}_k^1(k) \to \mathbb{R}_{\geq 0}$ est contrôlée par un graphe fini et non-vide contenu dans $\mathbb{P}^{1,an}_k$. Nous montrons que ce résultat peut être généralisé au cas d'un morphisme fini $\phi : V' \to V$ entre deux variétés intégrales, projectives avec $V$ normale. / This thesis is a reflection of the interaction between Berkovich geometry and model theory. Using the results of Hrushovski and Loeser, we show that several interesting topological phenomena that concern the analytifications of varieties are governed by certain finite simplicial complexes embedded in them. Our work consists of the following two sets of results. Let k be an algebraically closed non-Archimedean non trivially real valued field which is complete with respect to its valuation. 1) Let $\phi : C' \to C$ be a finite morphism between smooth projective irreducible $k$-curves.The morphism $\phi$ induces a morphism $\phi^{an} : C'^{an} \to C^{an}$ between the Berkovich analytifications of the curves. We construct a pair of deformation retractions of $C'^{an}$ and $C^{an}$ which are compatible with the morphism $\phi^{\mathrm{an}}$ andwhose images $\Upsilon_{C'^{an}}$, $\Upsilon_{C^{an}}$ are closed subspaces of $C'^{an}$, $C^{an}$ that are homeomorphic to finite metric graphs. We refer to such closed subspaces as skeleta.In addition, the subspaces $\Upsilon_{C'^{an}}$ and $\Upsilon_{C^{an}}$ are such that their complements in their respective analytifications decompose into the disjoint union of isomorphic copies of Berkovich open balls. The skeleta can be seen as the union of vertices and edges, thus allowing us to define their genus. The genus of a skeleton in a curve $C$ is in fact an invariant of the curve which we call $g^{an}(C)$. The pair of compatible deformation retractions forces the morphism $\phi^{an}$ to restrict to a map $\Upsilon_{C'^{an}} \to \Upsilon_{C^{an}}$. We study how the genus of $\Upsilon_{C'^{an}}$ can be calculated using the morphism $\phi^{an}_{|\Upsilon_{C'^{an}}$ and invariants defined on $\Upsilon_{C^{an}}$. 2) Let $\phi$ be a finite endomorphism of $\mathbb{P}^1_k$. Given a closed point $x \in \mathbb{P}^1_k$, we are interested in the radius $f(x)$ of the largest Berkovich open ball centered at $x$ over which the morphism $\phi^{\mathrm{an}}$ is a topological fibration. Interestingly, the function $f : \mathbb{P}_k^1(k) \to \mathbb{R}_{\geq 0}$ admits a strong tameness property in that it is controlled by a non-empty finite graph contained in $\mathbb{P}^{1,an}_k$. We show that this result can be generalized to the case of finite morphisms $\phi : V' \to V$ between integral projective $k$-varieties where $V$ is normal.

Cette thèse propose une solution logicielle au problème du développement et de l'exécution en temps réel d'applications de vision sur des machines de type cluster. Pour cela, avons développé deux bibliothèques utilisant des techniques d'évaluation partielle et de méta-programmation template qui permettent de programmer ces machines en s'attachant à rendre accessible les modèles de programmation parallèles à des développeurs issus de la communauté Vision pour qui ces problématiques ne sont pas triviales, tout en conservant des performances élevées. Ces deux bibliothèques : EVE, qui prend en charge la gestion du parallélisme SIMD, et QUAF, qui propose un modèle de programmation à base de squelettes algorithmiques pour la programmation sur machines MIMD, ont été validées par deux applications de vision de complexité réaliste, une reconstruction 3D et un suivi de piéton par filtrage particulaire, développées et exécutées sur un cluster dédié à la vision artificielle

Cette thèse vise à définir une méthodologie de mise en œuvre d’applications performantes sur les processeurs embarqués du futur. Ces architectures nécessitent notamment d’exploiter au mieux les différents niveaux de parallélisme (grain fin, gros grain) et de gérer les communications et les accès à la mémoire. Pour étudier cette méthodologie, nous avons utilisé un processeur cible représentatif de ces architectures émergentes, le processeur CELL. Le détecteurde points d’intérêt de Harris est un exemple de traitement régulier nécessitant des unités de calcul intensif. En étudiant plusieurs schémas de mise en oeuvre sur le processeur CELL, nous avons ainsi pu mettre en évidence des méthodes d’optimisation des calculs en adaptant les programmes aux unités spécifiques de traitement SIMD du processeur CELL. L’utilisation efficace de la mémoire nécessite par ailleurs, à la fois une bonne exploitation des transferts et un arrangement optimal des données en mémoire. Nous avons développé un outil d’abstraction permettant de simplifier et d’automatiser les transferts et la synchronisation, CELL MPI. Cette expertise nous a permis de développer une méthodologie permettant de simplifier la mise en oeuvre parallèle optimisée de ces algorithmes. Nous avons ainsi conçu un outil de programmation parallèle à base de squelettes algorithmiques : SKELL BE. Ce modèle de programmation propose une solution originale de génération d’applications à base de métaprogrammation. Il permet, de manière automatisée, d’obtenir de très bonnes performances et de permettre une utilisation efficace de l’architecture, comme le montre la comparaison pour un ensemble de programmes test avec plusieurs autres outils dédiés à ce processeur. / This thesis aims to define a design methodology for high performance applications on future embedded processors. These architectures require an efficient usage of their different level of parallelism (fine-grain, coarse-grain), and a good handling of the inter-processor communications and memory accesses. In order to study this methodology, we have used a target processor which represents this type of emerging architectures, the Cell BE processor.We have also chosen a low level image processing application, the Harris points of interest detector, which is representative of a typical low level image processing application that is highly parallel. We have studied several parallelisation schemes of this application and we could establish different optimisation techniques by adapting the software to the specific SIMD units of the Cell processor. We have also developped a library named CELL MPI that allows efficient communication and synchronisation over the processing elements, using a simplified and implicit programming interface. This work allowed us to develop a methodology that simplifies the design of a parallel algorithm on the Cell processor.We have designed a parallel programming tool named SKELL BE which is based on algorithmic skeletons. This programming model providesan original solution of a meta-programming based code generator. Using SKELL BE, we can obtain very high performances applications that uses the Cell architecture efficiently when compared to other tools that exist on the market.

Dû à la complexité des algorithmes de traitement d’images récents et dans le but d'accélérer la procédure de la conception des MPSoCs, méthodologies de prototypage rapide sont nécessaires pour fournir différents choix pour le programmeur de générer des programmes parallèles efficaces. Ce manuscrit présente les travaux menés pour proposer une méthodologie de prototypage rapide permettant la conception des architectures MPSOC ainsi que la génération automatique de système matériel / logiciel dédié un circuit reprogrammable (FPGA). Pour faciliter la programmation parallèle, l'approche MPSoC proposée est basée sur l’utilisation de Framework « CubeGen » qui permet la génération des différentes solutions envisageables pour réaliser des prototypes dans le domaine du traitement d’image. Ce document décrit une méthode basée sur le concept des squelettes générés en fonction des caractéristiques d'application afin d'exploiter tous les types de parallélisme des algorithmes réels. Un ensemble d’expérimentations utilisant des algorithmes courants permet d’évaluer les performances du flot de conception proposé équivalente à une architecture basé des processeurs hardcore et les solutions traditionnels basé sur cibles ASIC. / Due to the complexity of image processing algorithms and the restrictions imposed by MPSoC designs to reach their full potentials, automatic design methodologies are needed to provide guidance for the programmer to generate efficient parallel programs. In this dissertation, we present a MPSoC-based design methodology solution supporting automatic design space exploration, automatic performance evaluation, as well as automatic hardware/software system generation. To facilitate the parallel programming, the presented MPSoC approach is based on a CubeGen framework that permits the expression of different scenarios for architecture and algorithmic design exploring to reach the desired level of performance, resulting in short time development. The generated design could be implemented in a FPGA technology with an expected improvement in application performance and power consumption. Starting from the application, we have evolved our effective methodology to provide several parameterizable algorithmic skeletons in the face of varying application characteristics to exploit all types of parallelism of the real algorithms. Implementing such applications on our parallel embedded system shows that our advanced methods achieve increased efficiency with respect to the computational and communication requirements. The experimental results demonstrate that the designed multiprocessing architecture can be programmed efficiently and also can have an equivalent performance to a more powerful designs based hard-core processors and better than traditional ASIC solutions which are too slow and too expensive.

Les architectures parallèles sont désormais présentes dans tous les matériels informatiques, mais les programmeurs ne sont généralement pas formés à leur programmation dans les modèles explicites tels que MPI ou les Pthreads. Il y a un besoin important de modèles plus abstraits tels que les squelettes algorithmiques qui sont une approche structurée. Ceux-ci peuvent être vus comme des fonctions d’ordre supérieur synthétisant le comportement d’algorithmes parallèles récurrents que le développeur peut ensuite combiner pour créer ses programmes. Les développeurs souhaitent obtenir de meilleures performances grâce aux programmes parallèles, mais le temps de développement est également un facteur très important. Les approches par squelettes algorithmiques fournissent des résultats intéressants dans ces deux aspects. La bibliothèque Orléans Skeleton Library ou OSL fournit un ensemble de squelettes algorithmiques de parallélisme de données quasi-synchrones dans le langage C++ et utilise des techniques de programmation avancées pour atteindre une bonne efficacité. Nous avons amélioré OSL afin de lui apporter de meilleures performances et une plus grande expressivité. Nous avons voulu analyser le rapport entre les performances des programmes et l’effort de programmation nécessaire sur OSL et d’autres modèles de programmation parallèle. La comparaison rigoureuse entre des programmes parallèles dans OSL et leurs équivalents de bas niveau montre une bien meilleure productivité pour les modèles de haut niveau qui offrent une grande facilité d’utilisation tout en produisant des performances acceptables. / Parallel architectures have now reached every computing device, but software developers generally lackthe skills to program them through explicit models such as MPI or the Pthreads. There is a need for moreabstract models such as the algorithmic skeletons which are a structured approach. They can be viewed ashigher order functions that represent the behaviour of common parallel algorithms, and those are combinedby the programmer to generate parallel programs. Programmers want to obtain better performances through the usage of parallelism, but the development time implied is also an important factor. Algorithmic skeletons provide interesting results in both those fields. The Orléans Skeleton Library or OSL provides a set of algorithmic skeletons for data parallelism within the bulk synchronous parallel model for the C++ language. It uses advanced metaprogramming techniques to obtain good performances. We improved OSL in order to obtain better performances from its generated programs, and extended its expressivity. We wanted to analyze the ratio between the performance of programs and the development effort needed within OSL and other parallel programming models. The comparison between parallel programs written within OSL and their equivalents in low level parallel models shows a better productivity for high level models : they are easy to use for the programmers while providing decent performances.

Concevoir et implanter des programmes parallèles est une tâche complexe, sujette aux erreurs. La vérification des programmes parallèles est également plus difficile que celle des programmes séquentiels. Pour permettre le développement et la preuve de correction de programmes parallèles, nous proposons de combiner le langage parallèle fonctionnel quasi-synchrone BSML, les squelettes algorithmiques - qui sont des fonctions d'ordre supérieur sur des structures de données réparties offrant une abstraction du parallélisme - et l'assistant de preuve Coq, dont le langage de spécification est suffisamment riche pour écrire des programmes fonctionnels purs et leurs propriétés. Nous proposons un plongement des primitives BSML dans la logique de Coq sous une forme modulaire adaptée à l'extraction de programmes. Ainsi, nous pouvons écrire dans Coq des programmes BSML, raisonner dessus, puis les extraire et les exécuter en parallèle. Pour faciliter le raisonnement sur ceux-ci, nous formalisons le lien entre programmes parallèles, manipulant des structures de données distribuées, et les spécifications, manipulant des structures séquentielles. Nous prouvons ainsi la correction d'une implantation du squelette algorithmique BH, un squelette adapté au traitement de listes réparties dans le modèle de parallélisme quasi synchrone. Pour un ensemble d'applications partant d'une spécification d'un problème sous forme d'un programme séquentiel simple, nous dérivons une instance de nos squelettes, puis nous extrayons un programme BSML avant de l'exécuter sur des machines parallèles.

Les architectures parallèles sont désormais présentes dans tous les matériels informatiques, mais les pro- grammeurs ne sont généralement pas formés à leur programmation dans les modèles explicites tels que MPI ou les Pthreads. Il y a un besoin important de modèles plus abstraits tels que les squelettes algorithmiques qui sont une approche structurée. Ceux-ci peuvent être vus comme des fonctions d'ordre supérieur synthétisant le comportement d'algorithmes parallèles récurrents que le développeur peut ensuite combiner pour créer ses programmes. Les développeurs souhaitent obtenir de meilleures performances grâce aux programmes parallèles, mais le temps de développement est également un facteur très important. Les approches par squelettes algorithmiques fournissent des résultats intéressants dans ces deux aspects. La bibliothèque Orléans Skeleton Library ou OSL fournit un ensemble de squelettes algorithmiques de parallélisme de données quasi-synchrones dans le langage C++ et utilise des techniques de programmation avancées pour atteindre une bonne efficacité. Nous avons amélioré OSL afin de lui apporter de meilleures performances et une plus grande expressivité. Nous avons voulu analyser le rapport entre les performances des programmes et l'effort de programmation nécessaire sur OSL et d'autres modèles de programmation parallèle. La comparaison rigoureuse entre des programmes parallèles dans OSL et leurs équivalents de bas niveau montre une bien meilleure productivité pour les modèles de haut niveau qui offrent une grande facilité d'utilisation tout en produisant des performances acceptables.