L'arithmétique des ordinateurs est une branche de l'informatique qui traite des systèmes de représentation des nombres, des algorithmes arithmétiques et de leurs implantations matérielles ou logicielles. Cette thèse porte sur l'étude et l'implantation matérielle d'opérateurs pour l'évaluation de fonctions pour des applications spécifiques en traitement du signal et des images et en cryptographie. La première partie présente des opérateurs d'évaluation de fonctions basés sur des approximations polynomiales qui demandent peu de matériel. La seconde partie étudie la génération automatique d'opérateurs à base d'additions et décalages (type SRT) pour l'évaluation de certaines fonctions algébriques. Enfin, la dernière partie présente une implantation efficace et compacte des fonctions de hachage cryptographique de la famille SHA-2. Les différents opérateurs proposés dans cette thèse ont tous été validés sur des circuits FPGA.

Dans un contexte de compression d'images fixes, de nouvelles représentations implantées par des techniques de redressement (lifting) orienté ont été imaginées. Pour ce travail de thèse, trois variantes de ces transformées sont évaluées comparativement selon un critère de minimisation de l'énergie des hautes fréquences reconstruites et selon la direction de régularité locale. Cette direction de régularité est estimée par des approches basées extraction de contours ou minimisation d'une fonction de coût. Les deux approches proposées permettent de plus une classification de l'activité directionnelle des blocs de l'image. Ces représentations des caractéristiques géométriques de l'image utilisées pour guider le filtrage en ondelettes orientées, est codé pour être transmis au décodeur. Les coûts de ces différentes représentations sont comparés. Finalement une quantification adaptée est proposée pour tenir compte à la fois des différentes classes structurelles et de l'anisotropie de la représentation.

L'arithmétique des ordinateurs est une branche de l'informatique qui traite des systèmes de représentation des nombres, des algorithmes arithmétiques et de leurs implantations matérielles ou logicielles. Cette thèse porte sur l'étude et l'implantation matérielle d'opérateurs pour l'évaluation de fonctions en traitement du signal et des images. Sont présentés successivement un générateur d'opérateurs optimisés pour la division, des études portant sur un algorithme d'évaluation de fonctions au moyen d'approximations par fractions rationnelles, et des opérateurs d'évaluation de fonctions basés sur des approximations polynomiales qui demandent peu de matériel. Les différents opérateurs proposés dans cette thèse ont tous été validés sur des circuits FPGA.

La première partie est consacrée à la résolution de systèmes linéaires. Le chapitre 1 expose des résultats théoriques et numériques sur les méthodes proposées par Altman et précise le lien avec les méthodes de Krylov. Le chapitre 2 utilise des techniques d'extrapolation introduites par Brezinski pour obtenir une estimation du vecteur erreur. Plusieurs méthodes de projection sont retrouvées et de nouvelles procédures d'accélération données. Dans la deuxième partie, une nouvelle stratégie inspirée de la méthode de Cauchy-Barzilai-Borwein permet de définir de nouveaux schémas résolvant des problèmes de point fixe. Des résultats numériques sur un problème de bifurcation et un théorème de convergence sont donnés. Les chapitres 4, 5 et 6 sont consacrés à l'accélération de l'algorithme EM utilisé pour calculer des estimateurs du maximum de vraisemblance. Une classe de schémas itératifs basés sur la stratégie précédente est présentée, un théorème de convergence et une application à un problème de tomographie sont donnés. La dernière partie, fruit d'un projet du cemracs 2003, traite d'un problème issu de la physique des plasmas : l'amélioration des Codes Particles in Cell à l'aide d'une reconstruction de la densité basée sur une méthode d'ondelettes et sa validation numérique.

Dans cette thèse, nous étudierons les médianes d'une mesure de probabilité dans une variété riemannienne. Dans un premier temps, l'existence et l'unicité des médianes locales seront montrées. Afin de calculer les médianes aux cas pratiques, nous proposerons aussi un algorithme de sous-gradient et prouverons sa convergence. Ensuite, les médianes de Fréchet seront étudiées. Nous montrerons leur cohérence statistique et donnerons des estimations quantitatives de leur robustesse à l'aide de courbures. De plus, nous montrerons que, dans les variétés riemanniennes compactes, les médianes de Fréchet de données génériques sont toujours uniques. Des algorithmes stochastiques et déterministes seront proposés pour calculer les p-moyennes de Fréchet dans les variétés riemanniennes. Un lien entre les médianes et les problèmes de points fixes sera aussi montré. Finalement, nous appliquerons les médiane et la géométrie riemannienne des matrices de covariance Toeplitz à la détection de cible radar.

.

Aujourd'hui encore, certains systèmes embarqués n'intègrent pas leur propre unité flottante, pour des contraintes de surface, de coût et de consommation d'énergie. Cependant, ce type d'architecture est largement utilisé dans des domaines d'application extrêmement exigeants en calculs flottants (le multimédia, l'audio et la vidéo ou les télécommunications). Pour compenser le fait que l'arithmétique flottante ne soit pas implantée en matériel, elle doit être émulée efficacement à travers une implantation logicielle. Cette thèse traite de la conception et de l'implantation d'un support logiciel efficace pour l'arithmétique virgule flottante IEEE 754 aux processeurs entiers embarqués. Plus spécialement, elle propose de nouveaux algorithmes et outils pour la génération efficace de programmes à la fois rapides et certifiés, permettant notamment d'obtenir des codes C de très faibles latences pour l'évaluation polynomiale en arithmétique virgule fixe. Comparés aux implantations complètement écrites à la main, ces outils permettent de réduire de manière significative le temps de développement d'opérateurs flottants. La première partie de la thèse traite de la conception d'algorithmes optimisés pour certains opérateurs flottants en base 2, et donne des détails sur leur implantation logicielle pour le format virgule flottante binary32 et pour certains processeurs VLIW entiers embarqués comme ceux de la famille ST200 de STMicroelectronics. En particulier, nous proposons ici une approche uniforme pour l'implantation correctement arrondie des racines et de leur inverse, ainsi qu'une extension à la division. Notre approche, qui repose sur l'évaluation d'un seul polynôme bivarié, permet d'exprimer un plus haut degré de parallélisme d'instruction (ILP) que les méthodes précédentes, et s'avère particulièrement efficace en pratique. Ces travaux nous ont permis de fournir une version complètement remaniée de la bibliothèque FLIP, entraînant des gains significatifs par rapport à la version précédente. La deuxième partie de la thèse présente une méthodologie pour générer automatiquement et efficacement des codes C rapides et certifiés pour l'évaluation de polynômes bivariés en arithmétique virgule fixe. En particulier, elle consiste en un ensemble d'heuristiques pour calculer des schémas d'évaluation très parallèles et de faible latence, ainsi qu'un ensemble de techniques pour vérifier si ces schémas restent efficaces sur une architecture cible réelle et suffisamment précis pour garantir l'arrondi correct de l'implantation des opérateurs sous-jacente. Cette approche a été implantée dans l'environnement logiciel CGPE (Code Generation for Polynomial Evaluation). Nous avons ainsi utilisé notre outil pour générer et certifier rapidement des parties significatives des codes de la bibliothèque FLIP.

La première partie de ce travail traite de la modélisation et de la simulation de l'hydrodynamique et du transfert de matière dans les réacteurs à lit fixe arrosés. Le milieu poreux a été considéré comme un continuum par prise de moyenne des équations de transport microscopiques. Différents modèles prenant en compte l'effet de paroi de notre système ont été proposés, résolus et confrontés à des résultats expérimentaux. Les résultats obtenus sont assez satisfaisants, et ont permis de choisir les modèles les plus appropriés. Des modèles plus complexes, établis grâce aux résultats expérimentaux, devraient permettre d'améliorer la qualité des simulations. Dans une seconde partie, l'étude locale de l'hydrodynamique a été menée, essentiellement à l'aide de microélectrodes insérées dans un pore, qui permettent la mesure par voie électrochimique des gradients de vitesse. En écoulement de liquide seul, les limites des régimes d'écoulement ont été déterminées. On a pu confirmer le comportement turbulent à fort débit et caractériser l'écoulement du fluide au sein d'un pore, notamment à l'aide des auto- et intercorrélations des mesures. Enfin, nous avons utilisé un modèle de renouvellement de surface couplé à la méthode VITA (Variable Interval Time Averaging) pour calculer le gradient de vitesse moyen. En écoulement gaz-liquide, la technique électrochimique est moins intéressante. Nous avons par contre pu caractériser les écoulements pulsés à l'aide de sondes de pression en paroi.

Reproduction de : Thèse de doctorat : Mathématiques appliquées : Lille 1 : 2005. / N° d'ordre (Lille 1) : 3627. 1 article en anglais intégré dans le texte. Titre provenant de la page de titre du document numérisé. Bibliogr. p. [125]-132.

La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d'origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d'ordonnancement cumulatif. Un problème d'ordonnancement consiste à déterminer les dates de débuts et de fins d'un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l'on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l'on restreint le nombre maximum de couleurs distinctes prises par les tâches. Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l'aide d'algorithmes dédiés et de métaheuristiques. Par exemple, l'utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d'ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches. Pour atteindre cet objectif, nous utilisons l'idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d'accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appelées à chaque nœud de l'arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d'un million de tâches et 64 ressources cumulatives. Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes déplacement et d'ordonnancement.Mots-clés : Programmation par contraintes, ordonnancement, cumulatif, passage à l'échelle, point fixe, contraintes de ressources multidimensionelles, balayage synchronisé.