Cette thèse cherche à exploiter le parallélisme dans le contexte des systèmes de gestion de bases de données à objet à d'autres niveaux d'abstraction que celui d'une requête SQL, à savoir le parallélisme intra-transaction et le parallélisme intra-application. Notre approche pour parallélisation des transactions considère un modèle de transactions classiques, ou une transaction est une séquence d'opérations. Le parallélisme intra-transaction consiste à transformer le code d'une transaction pour pouvoir exécuter ses opérations en parallèle. Notre approche pour l'exploitation du parallélisme intra-application étend tout d'abord le modèle de parallélisme intra-transaction de manière à considérer la transaction comme unité de parallélisation. Deuxièmement nous avons considéré l'exploitation du parallélisme intra-application dans un contexte ou le modèle de transactions fournit des transactions emboîtées. Nous avons développé un modèle de parallélisation des applications où nous associons le parallélisme offert par le modèle des transactions emboîtées avec le parallélisme par transformation de notre approche de parallélisation des transactions. Nous avons implanté un premier prototype qui met en oeuvre le modèle de parallélisation des transactions. Pour cela, nous avons utilisé le système de bases de données à objet O2. Notre prototype introduit le parallélisme par la création et la synchronisation des activités parallèles au sein du processus client O2 qui exécute une application. Le système étant développé sur une machine monoprocesseur, les fonctions liées au parallélisme utilisent de processus légers. Nous avons appliqué ensuite notre modèle de parallélisation au système de règles NAOS. Notre approche considère l'ensemble de règles d'un cycle d'exécution, dites règles candidates, pour la parallélisation. Nous construisons un plan d'exécution pour les règles candidates d'un cycle qui détermine l'exécution séquentielle ou parallèle des règles.

Cette thèse se concentre sur la notion de qualité représentative des traces obtenues par voie logicielle sur des exécutions de programmes parallèles communiquant par messages. Nous proposons une série de modèles permettant de réajuster la qualité d'une telle trace afin d'approcher la qualité des mesures obtenues sur un système de trace matériel. Nous étudions en détail le problème de datation physique dans un environnement d'exécution parallèle dépourvu d'une horloge physique globale. Après avoir rappelé le principe des méthodes statistiques de calcul de temps global, nous proposons une technique qui permet de réduire considérablement le temps d'échantillonnage des horloges. Cette méthode offre un accès suffisamment précis et confortable au temps global pour pouvoir rivaliser avec une solution matérielle. Nous abordons ensuite le problème de l'effet de sonde qui résulte du partage des ressources du système entre l'outil d'instrumentation logiciel et l'application instrumenteé. Nous présentons différents modèles de correction des perturbations, permettant de compenser l'effet de sonde par un traitement post-mortem des traces dans le but de retrouver la dynamique originale d'une exécution non-instrumentée. Nous présentons finalement l'outil de trace Tape/PVM, développé dans le cadre de cette thèse. Les méthodes de qualité de traces proposés ont été implémentées et validées dans Tape/PVM.

Cette thèse s'inscrit dans le cadre des travaux consacrés au développement des modèles sémantiques destinés aux langages de programmation concurrents. Une particularité de notre étude réside dans la considération explicite d'une récursivité au niveau des programmes parallèles. Pour ces programmes nous proposons une sémantique originale, dont nous étudions en détail les propriétés. Bien que le modèle proposé ne soit pas d'états finis, il est possible de le munir d'une structure de systèmes de transitions bien structurés au sens de Finkel ce qui établit la décidabilité de nombreux problèmes de vérification. Cette sémantique à la Plotkin permet de mieux comprendre le comportement des programmes récursifs-parallèles, d'analyser formellement certaines de leurs propriétés, de décrire la stratégie d'implémentation et d'énoncer en quel sens elle est correcte.

La résolution jusqu'à l'optimalité de problèmes d'optimisation combinatoire NP-difficiles nécessite une mise en oeuvre de méthodes de plus en plus complexes qui consomment de plus en plus de puissance de calcul. L'objectif de notre travail est de paralléliser un algorithme de "Branch and Cut" pour résoudre jusqu'à l'optimalité des instances difficiles du voyageur de commerce. Dans la première partie de notre travail, nous présentons les composantes principales de l'algorithme du "Branch and Cut". Nous étudions ensuite le problème du voyageur de commerce par une approche polyédrale. Nous donnons enfin une description détaillée de notre implémentation de l'algorithme du "Branch and Cut". Dans la deuxième partie, Nous commençons par une brève présentation du parallélisme, et un état de l'art des études menées sur la parallélisation de l'algorithme du "Branch and Bound". Puis, nous proposons plusieurs modèles de parallélisations de l'algorithme du "Branch and Cut". Nous décrivons ensuite la stratégie de contrôle de la recherche arborescente qu'on a adopté, les mécanismes de minimisation des coûts liés aux différentes étapes de la communication entre les processeurs et les stratégies d'équilibrages. Nous terminons en donnant les résultats obtenus sur le IBM-SP1.

De nombreuses méthodes de calcul numérique parallèle sont développées pour utiliser les super-ordinateurs d'aujourd'hui, mais ces méthodes utilisent rarement les mécanismes de régulation et perdent en efficacité sur des problèmes non structurés. En particulier, la simulation numérique, par dynamique moléculaire (DM), du mouvement des atomes des protéines dans les structures biologiques est un de ces problèmes irréguliers qui demande beaucoup de puissance de calcul. Cette thèse, à travers la réalisation d'un programme parallèle de DM opérationnel pour l'étude des protéines, s'intéresse à montrer l'apport des processus légers pour la parallélisation de ce type d'application. Ce travail s'inscrit dans le projet INRIA-IMAG APACHE de réalisation du support d'exécution ATHAPASCAN pour les applications parallèles irrégulières et en collaboration avec le laboratoire BMC du CEA-Grenoble. Après une introduction sur la parallélisation d'applications, nous présentons les concepts de base de la parallélisation par des processus légers et des échanges de messages. La deuxième partie du document propose une synthèse des éléments du modèle de DM pour l'étude des protéines et présente la méthode du rayon de coupure pour l'approximation des forces. Dans la suite nous proposons une parallélisation de cette méthode du rayon de coupure par décomposition du domaine de simulation. Nous étudions plusieurs stratégies de placement des calculs afin de trouver le meilleur compromis entre l'équilibre de charge et la minimisation des communications. Puis nous montrons comment la multiprogrammation permet de recouvrir les communications par des calculs. Enfin nous terminons en proposant un mécanisme d'équilibre dynamique de la charge de calcul. De nombreuses mesures sur le IBM-SP1 et le CRAY-T3E sont présentées et montrent l'extensibilité de nos algorithmes parallèles.

Les ressources souterraines fournissent une part importante de l'eau douce de notre planète. Notre travail s'inscrit dans une démarche de protection de cette ressource vitale par la modélisation et la simulation numérique. Couplée aux études de terrains, la simulation numérique est en effet un outil indispensable, du fait de l'incertitude sur le milieu géologique. Cette incertitude conduit à une approche stochastique. Nous nous sommes concentrés sur les écoulements dans les réseaux de fractures générés aléatoirement. Pour permettre la résolution de ces écoulements par une méthode d'éléments finis mixte hybride, nous avons élaboré un algorithme de maillage spécifique aux fractures. Cette technique permet de construire le système linéaire quelle que soit la géométrie du réseau généré. Nous avons ensuite effectué une étude comparative de trois solveurs linéaires : un solveur direct, un multigrille algébrique et un Gradient Conjugué Préconditionné. Cette étude nous a conduit à proposer une méthode de résolution plus efficace pour ce problème. Nous avons alors étudié une méthode de décomposition de domaine de type Schur, qui permet d'allier les avantages du solveur direct et du Gradient Conjugué Préconditionné. Cette méthode consiste à réduire le problème à un problème aux interfaces, par une définition naturelle des fractures, ou paquets de fractures, comme sous-domaines. Nous avons proposé une approche originale d'optimisation de l'algorithme et un préconditionnement global de type déflation. Notre implémentation de cette méthode est compétitive. Elle permet de résoudre tous les cas tests étudiés et elle est plus rapide, dans la majorité des cas, que les trois autres solveurs.

Cette thèse d'Habilitation à Diriger des Recherches revient sur une dizaine d'années de contributions théoriques et pratiques à l'optimisation combinatoire, contributions dont le domaine d'application privilégié est l'optimisation des systèmes de télécommunications (principalement les autocommutateurs pour la téléphonie cellulaire) et informatiques (en particulier les architectures de processeur parallèles, dites multi-cœurs). Ces travaux se caractérisent également par la résolution bout-en-bout de nombreux cas d'applications industriels concrets et difficiles, de la modélisation mathématique initiale jusqu'à la mise en œuvre d'algorithmes de résolution opérationnels en passant par les développements théoriques nécessaires à leurs fondements.

Les nouvelles architectures de calcul intensif intègrent de plus en plus de microprocesseurs qui eux-mêmes intègrent un nombre croissant de cœurs de calcul. Cette multiplication des unités de calcul dans les architectures ont fait apparaître des topologies fortement hiérarchiques. Ces architectures sont dites NUMA. Les algorithmes de simulation numérique et les solveurs de systèmes linéaires qui en sont une brique de base doivent s'adapter à ces nouvelles architectures dont les accès mémoire sont dissymétriques. Nous proposons dans cette thèse d'introduire un ordonnancement dynamique adapté aux architectures NUMA dans le solveur PaStiX. Les structures de données du solveur, ainsi que les schémas de communication ont dû être modifiés pour répondre aux besoins de ces architectures et de l'ordonnancement dynamique. Nous nous sommes également intéressés à l'adaptation dynamique du grain de calcul pour exploiter au mieux les architectures multi-cœurs et la mémoire partagée. Ces développements sont ensuite validés sur un ensemble de cas tests sur différentes architectures.

Les travaux présentés dans ce mémoire s'inscrivent dans la problématique dite d'adéquation algorithme architecture. Ils concernent la conception et le développement d'outils logiciels permettant de faire du prototypage rapide d'applications parallèles de vision artificielle sur des architectures de type MIMD à mémoire distribuée. De tels outils ont pour objectif de faciliter l'évaluation rapide d'un ensemble de solutions vis à vis d'un problème donné en diminuant de manière drastique les temps de cycle conception-implantation-validation des applications. L'outil SKiPPER développé dans le cadre de ces travaux est basé sur le concept des squelettes de parallélisation. Ceux-ci représentent des constructeurs génériques de haut niveau encapsulant des formes communes de parallélisme tout en dissimulant les détails relatifs à l'exploitation de ce parallélisme sur la plate-forme cible. Au niveau langage, la spécification des squelettes est réalisée au sein du langage fonctionnel Caml sous la forme de fonctions d'ordre supérieur. Ainsi, la spécification d'une application est un programme purement fonctionnel dans lequel l'expression du parallélisme est limitée au choix et à l'instanciation des squelettes choisis dans une base pré-définie. L'environnement de développement SKiPPER est organisé autour de trois modules réalisant respectivement l'expansion du code fonctionnel en un graphe flot de données (outil Dromadaire), le placement-ordonnancement de ce graphe sur l'architecture matérielle (outil SynDEx développé à l'INRIA) et la génération de code cible final pour l'architecture cible (la machine Transvision du LASMEA dans notre cas). L'applicabilité des concepts mis en \oe uvre dans SKiPPER et des outils développés conjointement est démontrée également dans les travaux présentés dans ce mémoire. Diverses applications de complexité réaliste (étiquetage en composantes connexes, détection et suivi de signalisation horizontale autoroutière) ont été parallélisées automatiquement par l'environnement SKiPPER validant ainsi l'objectif initial de prototypage rapide d'applications parallèles de vision artificielle à fortes contraintes temporelles sur architecture dédiée.

Les applications dans le domaine des communications numériques deviennent de plus en plus complexes et diversifiées. En témoigne l'apparition des turbo-communications qui représentent la généralisation du principe de processus itératif introduit par les turbocodes. La mise en œuvre de systèmes de turbo-communications, communément appelés turbo- récepteurs, est devenue primordiale pour atteindre les performances aujourd'hui exigées en terme de qualité de transmission. Des architectures matérielles dédiées implantant ces systèmes ont déjà vu le jour dans plusieurs équipes de recherches académiques et industrielles. Cependant, pour des exigences de flexibilité de l'implantation (pour supporter les évolutions d'une norme ou des applications multi-standards), de qualité de transmission et de haut débit de communication, des architectures multiprocesseurs adéquates deviennent incontournables. Le sujet de cette thèse porte sur la mise en œuvre d'une plate-forme architecturale multiprocesseur générique adaptée aux turbo-récepteurs et plus particulièrement aux turbo-décodeurs convolutifs. Ainsi, le sujet gravite autour de deux axes de recherche : un axe algorithmique autour des systèmes de turbo-décodage et un autre autour de la conception numérique ces derniers. Sur l'axe algorithmique, ces travaux présentent une étude approfondie des algorithmes de turbo-décodage autour des techniques de parallélisme. Les fondations de cette étude reposent sur une classification des parallélismes existants qui distingue les parallélismes selon leurs granularités et leurs pouvoirs d'accélération. L'analyse de cette classification a révélé la nécessité d'investiguer les parallélismes de sous-bloc et de décodeur composant pour améliorer l'efficacité de leur mise en œuvre. Les recherches menées mettent en évidence que le parallélisme de sous-bloc s'avère plus efficace avec la technique d'initialisation par passage de message. Nous avons également montré que le parallélisme de décodeur composant, grâce à la technique du décodage combiné ou « shuffled decoding » , améliore l'efficacité des architectures de turbo-décodeur fortement parallèles et que cette dernière peut être optimisée en contraignant la conception de l'entrelaceur du turbocode. Sur l'axe architectural, ces avancées algorithmiques ont été mises à profit dans une plate-forme multiprocesseur qui exploite au mieux les compromis matériel/logiciel (i .e. performance/flexibilité) tant au niveau du calcul qu'au niveau des communications. Au niveau du calcul, un processeur ASIP (Application-Specific Instruction-set Processor) dédié au décodage des codes convolutifs a été proposé et conçu de manière à ne fournir que la flexibilité désirée, tout en conservant des performances élevées grâce à un chemin de données fortement parallélisé. Au niveau des communications, la plate-forme a été dotée de réseaux sur puce dédiés pour assurer la bande passante nécessaire aux échanges itératifs d'information. Cette plate-forme multi-ASIP flexible a été prototypée sur une carte d'émulation intégrant des circuits FPGA. La flexibilité de la plate-forme proposée autorise le support de tous les standards de turbocodes convolutifs actuels et émergeants et peut trouver un intérêt industriel dans les domaines des télécommunications mobiles et satellitaires, de la diffusion de contenu ou de l'Internet haut-débit.