To see the other types of publications on this topic, follow the link: Optimisation de codes parallèles.
Dissertations / Theses on the topic 'Optimisation de codes parallèles'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Optimisation de codes parallèles.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Benmouhoub, Farah. "Optimisation de la précision numérique des codes parallèles." Thesis, Perpignan, 2022. http://www.theses.fr/2022PERP0009.
Full textAbstract:
Les nombres flottants sont utilisés à la place des nombres réels pour les calculs sur ordinateurs. L'utilisation de ces nombres introduit des erreurs d'arrondi qui sont en général acceptables dans la mesure où le résultat produit par la machine est proche de celui que l'on aurait obtenu en utilisant des nombres réels. Cependant, elles peuvent aussi être amplifiées par propagation, dénuant de sens le résultat d'un calcul, ce qui peut avoir des conséquences catastrophiques dans de nombreux domaines d'application comme par exemple l'aéronautique ou la finance. La précision des calculs en nombres flottants dépend de nombreux facteurs: types d'opérations effectuées, valeurs et types de données employés, ordinateurs utilisés. En outre, la précision des calculs dépend fortement de l'ordre dans lequel sont effectuées les opérations et le parallélisme démultiplie les ordonnancements possibles. Le sujet de thèse proposé concerne ce dernier point : améliorer la précision de codes de calcul scientifique massivement parallèles tels que ce que l'on trouve dans le domaine du HPC (High Performance Computing) Ces dernières années, des techniques automatiques ont été mises au point afin de valider et réécrire les codes de calcul scientifique afin de les rendre plus précis. Ces techniques rencontrent un vif intérêt tant scientifique qu'industriel. Cependant les techniques existantes acceptent uniquement des programmes séquentiels ce qui exclut les nombreux codes de calcul intensif développés dans le domaine du HPC. Or ces codes parallèles, utilisés pour réaliser des simulations numériques complexes dans de nombreux domaines scientifiques et techniques, sont particulièrement sujets aux erreurs introduites par les nombres flottants car le parallélisme modifie l'ordre dans lequel sont effectués les calculs, voire rend cet ordre aléatoire. Les résultats obtenus peuvent alors être altérés ou non reproductibles (plusieurs si mulations identiques donnant des résultats différents)In high performance computing, nearly all the implementations and published experiments use foating-point arithmetic. However, since foating-point numbers are finite approximations of real numbers, it may result in hazards because of the accumulated errors.These round-off errors may cause damages whose gravity varies depending on the critical level of the application. Parallelism introduces new numerical accuracy problems due to the order of operations in this kind of systems. The proposed thesis subject concerns this last point: improving the precision of massively parallel scientific computing codes such as those found in the field of HPC (High Performance Computing)
2
Laguzet, Florence. "Etude et optimisation d'algorithmes pour le suivi d'objets couleur." Thesis, Paris 11, 2013. http://www.theses.fr/2013PA112197.
Full textAbstract:
Les travaux de cette thèse portent sur l'amélioration et l'optimisation de l'algorithme de suivi d'objet couleur Mean-Shift à la fois d’un point de vue robustesse du suivi et d’un point de vue architectural pour améliorer la vitesse d’exécution. La première partie des travaux a consisté en l'amélioration de la robustesse du suivi. Pour cela, l'impact des espaces de représentation couleur a été étudié, puis une méthode permettant la sélection de l'espace couleur représentant le mieux l'objet à suivre a été proposée. L'environnement de la cible changeant au cours du temps, une stratégie est mise en place pour resélectionner un espace couleur au moment opportun. Afin d'améliorer la robustesse dans le cas de séquences particulièrement difficile, le Mean-Shift avec stratégie de sélection a été couplé avec un autre algorithme plus coûteux en temps d'exécution : le suivi par covariance. L’objectif de ces travaux est d’obtenir un système complet fonctionnant en temps réel sur processeurs multi-cœurs SIMD. Une phase d’étude et d'optimisation a donc été réalisée afin de rendre les algorithmes paramétrables en complexité pour qu’ils puissent s’exécuter en temps réel sur différentes plateformes, pour différentes tailles d’images et d’objets suivi. Dans cette optique de compromis vitesse / performance, il devient ainsi possible de faire du suivi temps-réel sur des processeurs ARM type Cortex A9The work of this thesis focuses on the improvement and optimization of the Mean-Shift color object tracking algorithm, both from a theoretical and architectural point of view to improve both the accuracy and the execution speed. The first part of the work consisted in improving the robustness of the tracking. For this, the impact of color space representation on the quality of tracking has been studied, and a method for the selection of the color space that best represents the object to be tracked has been proposed. The method has been coupled with a strategy determining the appropriate time to recalculate the model. Color space selection method was also used in collaboration with another object tracking algorithm to further improve the tracking robustness for particularly difficult sequences : the covariance tracking which is more time consuming. The objective of this work is to obtain an entire real time system running on multi-core SIMD processors. A study and optimization phase has been made in order to obtain algorithms with a complexity that is configurable so that they can run in real time on different platforms, for various sizes of images and object tracking. In this context of compromise between speed and performance, it becomes possible to do real-time tracking on processors like ARM Cortex A9
3
Fang, Juing. "Décodage pondère des codes en blocs et quelques sujets sur la complexité du décodage." Paris, ENST, 1987. http://www.theses.fr/1987ENST0005.
Full textAbstract:
Etude de la compléxité théorique du décodage des codes en blocs à travers une famille d'algorithmes basée sur le principe d'optimisation combinatoire. Puis on aborde un algorithme parallèle de décodage algébrique dont la complexitré est liée au niveau de bruit du canal. Enfin on introduit un algorithme de Viterbi pour les applications de traitement en chaînes.
4
Raulet, Mickaël. "Optimisations mémoire dans la méthodologie AAA pour code embarqué sur architecture parallèles." Rennes, INSA, 2006. https://tel.archives-ouvertes.fr/tel-00124276v2.
Full textAbstract:
Dans le domaine de l'électronique embarquée, les applications de communications numériques et de traitement d'images imposent des contraintes de temps très fortes tout en admettant une limitation en ressources et performances des unités de traitement. La restriction quant à la mémoire utilisable peut être préjudiciable pour des domaines tels que le codage vidéo. Une solution pour atteindre les objectifs d'implantation temps-réel peut passer par une distribution sur une architecture matérielle parallèle. Cette problématique constitue le cadre de ces travaux. Plus précisément, il s'agit de développer un processus de prototypage rapide dédié aux architectures parallèles à base de plusieurs processeurs de traitement numérique du signal de dernière génération (FPGA, DSP). L'aspect optimisation du point de vue de la mémoire allouée est abordé ici de manière plus précise. La chaîne de prototypage a été élaborée autour de SynDEx, outil développé à l'INRIA basé sur la méthodologie AAA. Cette dernière vise à améliorer l'implantation d'un algorithme sur une architecture multi-processeurs en déterminant une distribution et ordonnancement optimaux. SynDEx réalise la phase d'adéquation proprement dite, et génère un exécutif indépendant de la cible. Nous avons dans un premier temps contribué à l'automatisation du processus sur cible multi-processeurs, en rajoutant d'une couche fonctionnelle, et en développant de nouveaux noyaux spécifiques pour des processeurs de traitement numérique du signal. Dans un contexte embarqué, nos préoccupations se sont ensuite penchées sur la minimisation de la mémoire pour le code généré. C'est un problème encore très ouvert pour des architectures multi-composants. La solution trouvée, grâce aux algorithmes de coloriage de graphe, aboutit à une amélioration significative des résultats d'implantation distribuée. Le portage vers des plates-formes multi-composants est aujourd'hui automatique, notamment en intégrant directement dans l'outil SynDEx l'optimisation mémoire. Une autre partie importante de ces travaux a concerné le développement et l'intégration, à travers notre processus de prototypage, d'applications conséquentes dans les domaines du traitement des images (MPEG-4, LAR) et celui des télécommunications (MC-CDMA, UMTS). Les résultats obtenus valident l'ensemble du processus proposé, et démontrent son adaptation à des systèmes globalement orientés traitement de l'information. Le mémoire se conclut en ouvrant sur de nouvelles perspectives, en s'intéressant notamment à des systèmes multi-couches réunissant des couches " transport " de télécommunication numériques et des couches " services " de traitement des imagesIn the field of embedded electronics, the applications of digital communications and image processing induce very strong time constraints while allowing a limitation in resources and performances of the computation units. The restriction of the memory usable can be in opposite of fields such as video coding. A solution to achieve a real-time implementation can be reached through a distribution on a parallel architecture. These problems are the framework of this work. More precisely, that is why we developed a process of rapid prototyping dedicated to the parallel architectures with several processors of digital signal processing of the last generation (FPGA, DSP). The optimization aspect of the allocated memory is performed here in a more precise way. The prototyping process was elaborate around SynDEx, a tool developed with the INRIA, based on the AAA methodology. This process aims at improving the implementation of an algorithm on a multi-component architecture by determining an optimal distribution and scheduling. SynDEx carries out the adequation phase itself, and generates an executive independent of the target. We initially contributed to the automation of the process on multiprocessors target, by adding a functional layer, and by developing new specific kernels for processors of digital signal. In an embedded context, our concerns are then the minimization of the memory for the generated code. It is still a problem very open for multi-component architectures. The found solution, thanks to the algorithms of colouring of graph, leads to a significant improvement of the results of distributed implementation. The rapid prototyping towards multi-component platforms is automatic today, and memory optimizations are directly integrated in the SynDEx tool. Another part of this work related to the development and integration, through our prototyping process, of consequent applications in the fields both of the image processing (MPEG-4, LAR) and both of the telecommunications (MC-CDMA, UMTS). Results validate the whole process, and show its adaptation to systems oriented data processing. The report is concluded on new perspectives, while being interested in particular in multi-layer systems linking together several layers: a “transport” layer of telecommunication and a “service” layer of image processing
5
Surós, Rina. "Modélisation et optimisation de systèmes parallèles." Paris 11, 1988. http://www.theses.fr/1988PA112188.
Full textAbstract:
Ln part 1 of this thesis we consider parallel computer pro grams whose structure is governed by certain stochastic laws. Such programs are modeled by a random graph structure. An exact mathematical expression is given for the distribution of computing time with an infinite number of processors. A simulation validates the analytical model results. Ln part 2, a new method is proposed in order to optimize systolic networks for certains matrix computation. Its advantage is the improvement of processors utilization through halving the size of matrices. This improvement is exploited in an implementation of the Parallel Shooting, numerical method to solve two point differential equations. Interconnection network organization as well as algorithm execution are presented.
6
Raulet, Mickaël. "Optimisations Mémoire dans la méthodologie « Adéquation Algorithme Architecture » pour Code Embarqué sur Architectures Parallèles." Phd thesis, INSA de Rennes, 2006. http://tel.archives-ouvertes.fr/tel-00124276.
Full textAbstract:
Dans le domaine de l'électronique embarquée, les applications de communications numériques et de traitement d'images imposent des contraintes de temps très fortes tout en admettant une limitation en ressources et performances des unités de traitement. La restriction quant à la mémoire utilisable peut être préjudiciable pour des domaines tels que le codage vidéo. Une solution pour atteindre les objectifs d'implantation temps-réel peut passer par une distribution sur une architecture matérielle parallèle. Cette problématique constitue le cadre de ces travaux. Plus précisément, il s'agit de développer un processus de prototypage rapide dédié aux architectures parallèles à base de plusieurs processeurs de traitement numérique du signal de dernière génération (FPGA, DSP). L'aspect optimisation du point de vue de la mémoire allouée est abordé ici de manière plus précise.La chaîne de prototypage a été élaborée autour de SynDEx, outil développé à l'INRIA basé sur la méthodologie AAA. Cette dernière vise à améliorer l'implantation d'un algorithme sur une architecture multi-processeurs en déterminant une distribution et ordonnancement optimaux. SynDEx réalise la phase d'adéquation proprement dite, et génère un exécutif indépendant de la cible. Nous avons dans un premier temps contribué à l'automatisation du processus sur cible multi-processeurs, en rajoutant d'une couche fonctionnelle, et en développant de nouveaux noyaux spécifiques pour des processeurs de traitement numérique du signal.
Dans un contexte embarqué, nos préoccupations se sont ensuite penchées sur la minimisation de la mémoire pour le code généré. C'est un problème encore très ouvert pour des architectures multi-composants. La solution trouvée, grâce aux algorithmes de coloriage de graphe, aboutit à une amélioration significative des résultats d'implantation distribuée. Le portage vers des plates-formes multi-composants est aujourd'hui automatique, notamment en intégrant directement dans l'outil SynDEx l'optimisation mémoire.
Une autre partie importante de ces travaux a concerné le développement et l'intégration, à travers notre processus de prototypage, d'applications conséquentes dans les domaines du traitement des images (MPEG-4, LAR) et celui des télécommunications (MC-CDMA, UMTS). Les résultats obtenus valident l'ensemble du processus proposé, et démontrent son adaptation à des systèmes globalement orientés traitement de l'information. Le mémoire se conclut en ouvrant sur de nouvelles perspectives, en s'intéressant notamment à des systèmes multi-couches réunissant des couches « transport » de télécommunication numériques et des couches « services » de traitement des images.
7
Alba-Gomez, Ofélia. "Optimisation de trajectoires de robots parallèles redondants." Nantes, 2007. http://www.theses.fr/2007NANT2126.
Full textAbstract:
Les études ont pour objectifs la définition d'indices de performance de robot pleinement parallèle 3·RRR et la détermination d'une méthode de planification de trajectoires optimales pour éviter les configurations singulières et optimiser les perfonnances cinétostatiques. On développe une analyse des conditions d'isotropie pour calculer une longueur caractéristique pertinente en vue de l'homogénéisation de la matrice jacobienne parallèle. On définit un nouvel indice de performance comme mesure de la distance d'une configuration par rapport à une singularité parallèle. La valeur optimale de cet indice est atteinte par une configuration isotrope idéale. Puis, nous proposons un second indice de performance en utilisant une interprétation géométrique des conditions de singularités parallèle. L'équivalence des deux indices est vérifiée. Pour notre robot cinématiquement redondant nous proposons une méthode de planification automatique de trajectoires pour l'optimisation des performances lors de l'exécution d'une tâche spécifiée. Cette méthode a été inspirée d'un algorithme de planification de trajectoires de véhicules de navigation autonome. Plusieurs cas d'étude sont analysés pour valider l'efficacité de nos méthodes dans des environnements sans et avec obstacles. Un scénario additionnel est finalement étudié : celui d'une tâche qui peut être exécutée seulement si le manipulateur utilise deux modes de fonctionnement. Le manipulateur est donc obligé de passer par une singularité sérielle lors de la réalisation de la tâche. Ce cas nécessite la formulation d'une nouvelle procédure qui est aussi développée et testée avec un cas d'étudeThe aims of studies in tbis thesis are the definition of perfonnance indices of3-RRR parallel robots and the formulation of a method for trajectory planning in order to avoid singular configurations and optimize the kinetostatic performances of the manipulator. By using the isotropy conditions we define a characteristic length in order to homogenize the parallel Jacobian matrix. Thus, a consistent performance index is defined by using such a matrix as the distance of a configuration to parallel singularities. The optimum value of this index is determined an ideal isotropic configuration. Then, another index of the manipulator is defined by using a geometric interpretation of conditions of parallel singularities. An additional study allows us to verify the equivalence of the two proposed indices. Then, for our kinematically redundant robot, a method for automatic trajectory planning is proposed which optimizes the manipulator performances during the execution of a specified task. This method is inspired from an algorithm of trajectory planning for auto-guided vehicles. Several cases of study are analyzed in order to validate the effectiveness of our method in environments without and with obstacles. We consider a scenario in which the accessibility to the whole path is not possible using only one working mode; thus, we propose a supplementary formulation in order to achieve a suitable change of working mode to complete the task
8
Leguay-Durand, Sylvie. "Conception et optimisation de mécanismes parallèles à mobilités restreintes." Toulouse, ENSAE, 1998. http://www.theses.fr/1998ESAE0014.
Full textAbstract:
La synthèse de manipulateurs à structure parallèle se décompose en deux étapes complémentaires. La première porte sur la conception même de la structure. Après des rappels sur les notions utilisées en robotique et les outils mathématiques nécessaires, deux conditions sur les torseurs cinématiques des liaisons sont établies de manière infinitésimale. La méthode de conception développée conduit à spécifier la nature et l'agencement géométrique des articulations dans les chaînes cinématiques série qui composeront le mécanisme, en fonction du mouvement désiré de l'organe terminal. Les contraintes imposées par la mise en parallèle de plusieurs chaînes permettent alors de décider de leur positionnement entre une base fixe et la plate-forme mobile. Cette méthode est appliquée à la conception de deux mécanismes basés sur la chaîne cinématique cardan-glissière-cardan. La seconde étape concerne l'optimisation des paramètres géométriques pour une utilisation donnée. Un état de l'art des mesures de performance existantes est présenté ; optimiser nécessite de définir des critères mesurant par exemple la dextérité, l'inertie ou le volume de l'espace de travail. Ces mesures sont calculées localement en chaque point de l'espace de travail ou globalement pour un prototype particulier ; ceci a conduit à montrer l'intérêt de l'utilisation des quaternions dans le cas du mouvement de rotation sphérique. Les différents modèles et l'optimisation globale de plusieurs manipulateurs parallèles existants ou en cours de réalisation sont ensuite présentés.
9
Legaux, Joeffrey. "Squelettes algorithmiques pour la programmation et l'exécution efficaces de codes parallèles." Phd thesis, Université d'Orléans, 2013. http://tel.archives-ouvertes.fr/tel-00990852.
Full textAbstract:
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.
10
Mattoussi, Ferdaouss. "Conception et optimisation de codes AL-FEC : les codes GLDPC- Staircase." Phd thesis, Université de Grenoble, 2014. http://tel.archives-ouvertes.fr/tel-00969573.
Full textAbstract:
Ce travail est consacré à la conception, l'analyse et l'optimisation des codes correcteurs d'effacements de niveau applicatif (AL-FEC). Nous nous intéressons à une famille des codes LDPC généralisés (GLDPC), nommés les codes GLDPC-Staircase, qui sont com- posés d'un code LDPC-Staircase (code de base) ainsi que des codes Reed-Solomon (RS) (codes externes). Dans la première partie de cette thèse, nous commençons par montrer que les codes RS ayant une construction basée sur la matrice "quasi" Hankel sont les codes MDS les plus appropriés pour obtenir la structure des codes GLDPC-Staircase. Ensuite, nous proposons un nouveau type de décodage à ces codes, baptisé le décodage hybride (IT/RS/ML), pour atteindre les caspacités de correction du décodage par maximum de vraisemblance (ML) avec de faible complexité. Afin d'étudier l'impact de la structure des codes GLDPC- Staircase sur le décodage, nous proposons une autre construction : ils se diffèrent sur la nature des symboles de redondance LDPC générés. Puis, pour prédire le seuil de décodage et les écarts par rapport à la limite de Shannon des codes GLDPC-Staircase, nous élaborons une analyse asymptotique en fonction de la technique d'évolution de densité (DE), la technique EXIT (Extrinsic Information Transfer) et le théorème d'air. Finalement, en se basant sur l'analyse à taille finie et l'analyse asymptotique, nous ajustons les différentes paramètres internes de ces codes pour obtenir la configuration optimale sous le décodage hybride (IT/RS/ML). La deuxième partie de la thèse est consacrée à l'étude des codes GLDPC-Staircase dans diverses situations. Tout d'abord, nous montrons que ces codes ont des performances asymptotiquement très proches de la limite de Shannon. En plus, à taille finie, ils permet- tent d'atteindre d'excellentes capacités de correction d'effacements (i.e., très proches de celles des codes MDS) peu importe la taille des objets : très faible overhead de décodage, faible plancher d'erreur, et une zone "waterfall" raide. Nous montrons aussi que les performances de ces codes sont trés proches des codes RaptorQ et surpassent celles des codes Raptor, les codes LDPC-Staircase, et un autre code GLDPC avec une construction différente. Finalement, nous proposons une méthodologie générale pour étudier l'impact de l'ordonnancement des paquets envoyés sur les performances des codes GLDPC-Staircase sur un grand nombre des canaux à effacements (avec des pertes en rafale ou pas). Cette étude montre le meilleur ordonnancement de paquets. Tous les résultats mentionnés ci-dessus montrent que les codes GLDPC-Staircase peuvent considérés comme des codes AL-FEC universels.
11
Liu, Zhen. "Modèles d'exécutions parallèles sur des systèmes multiprocesseurs : analyse et optimisation." Paris 11, 1989. http://www.theses.fr/1989PA112011.
Full textAbstract:
Cette thèse est consacrée aux problèmes de la modélisation, de l'analyse, et de l'optimisation des performances soulevés par des systèmes multiprocesseurs exécutants des programmes parallèles. Dans nos modèles, les systèmes multiprocesseurs sont considérés comme un ensemble de processeurs connectés par un réseau d'interconnexion, les programmes parallèles sont représentés par des graphes orientés acycliques. Des méthodes d'analyse exactes et approchées sont élaborées pour divers modèles d'exécutions parallèles. Des mesures de performances telles que les temps de réponse des programmes parallèles, le débit et la condition de stabilité du système, etc. . . , sont étudiées. Des techniques d'ordonnancement de processus sont également proposées avec pour objectif l'optimisation du temps total d'achèvement des processus. En complément des études théoriques, le logiciel d'analyse de performances SPEC (Système d'évaluation de Performances d'Exécutions Concurrentes), conçu et réalisé par l'auteur, est décrit de manière succincte. Ce logiciel contient des outils d'analyse et de simulationThe main concerns of this thesis are the modeling, analysis and optimization problems arising in multiprocessor systems with concurrent tasks. Multiprocessor systems are modeled by a set of processors connected by an interconnection network, parallel programs by directed acyclic graphs. Both exact and approximate methods are proposed for various parallel processing models. The performance measures such as program response time, system throughput, and stability condition, etc. . . , are analyzed. Scheduling algorithm that minimize makespan are also considered. New heuristics are provided together with simple illustrative examples. Besides theoretical studies, the performance evaluation software package SPEC (Software package for Performances Evaluation of Concurrent systems), designed and implemented by the author, is described concisely. This software package contains analytical and simulation tools
12
Piskorski, Stéphane. "Optimisation de codes multimédias pour systèmes embarqués." Paris 11, 2009. http://www.theses.fr/2009PA112215.
Full textAbstract:
Les algorithmes de traitement d’images requièrent des puissances de calculs de plus en plus grandes pour satisfaire des applications toujours plus gourmandes. Afin d’être capable de traiter efficacement un flux vidéo en temps réel, un système à microprocesseur embarqué doit être optimisé avec le plus grand soin. Cette thèse se propose d’étudier ces optimisations à plusieurs niveaux. Tout d’abord au plus proche du matériel à travers la modification du jeu d’instructions et des unités de calcul d’un processeur, pour que celui-ci travaille de façon efficace pour un ajout minimal de matériel et une consommation électrique maîtrisée. Un cas d’ application est présenté pour des algorithmes de localisation embarqués robustes faisant appel au calcul par intervalles. Ensuite par l’étude de la génération de blocs matériels pour processeurs logiciels sur FPGA, capables d’accélérer non plus seulement une instruction mais toute une fonction de calcul. Enfin à l’échelle d’un traitement complet, un outil de génération de code de filtres bas-niveau – IPLG – est présenté. Celui-ci permet de trouver automatiquement la forme optimale d’un code C de traitement systématique à base de stencils, en explorant les possibilités de fusion de nids de boucle de calcul, et en appliquant les techniques de rotation de variables, de déroulage de boucles et d’optimisation de la localité des données au code crééImage processing algorithms tend to become more and more computation-power hungry, while video applications ask for greater amounts of data to process. In order to be able to sustain real-time video streams, microprocessor-based embedded systems have to be carefully tuned. This thesis focuses on studying the required optimizations on several scales. Firstly by modifying the instruction set and computation units of a processor, to improve its computation efficiency at a reasonable hardware cost, leading to interesting electrical consumption results. An applicative example is given through the implementation of a robust embedded localization algorithm based on interval analysis. Secondly by studying the best way to generate hardware modules for soft-core processors on FPGA, in order to not simply accelerate a few instructions but a complete computation bloc. Finally, at a complete treatment scale, a low-level image-processing code generation tool – IPLG – is proposed. This tool automatically generates optimally written stencil-based C code, by exploring all possible computation-loop fusions, and by applying variable rotation, loop-unrolling and data-locality improvement techniques
13
Luong, Thé Van. "Métaheuristiques parallèles sur GPU." Thesis, Lille 1, 2011. http://www.theses.fr/2011LIL10058/document.
Full textAbstract:
Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leurdéploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on ComputersReal-world optimization problems are often complex and NP-hard. Their modeling is continuously evolving in terms of constraints and objectives, and their resolution is CPU time-consuming. Although near-optimal algorithms such as metaheuristics (generic heuristics) make it possible to reduce the temporal complexity of their resolution, they fail to tackle large problems satisfactorily. Over the last decades, parallel computing has been revealed as an unavoidable way to deal with large problem instances of difficult optimization problems. The design and implementation of parallel metaheuristics are strongly influenced by the computing platform. Nowadays, GPU computing has recently been revealed effective to deal with time-intensive problems. This new emerging technology is believed to be extremely useful to speed up many complex algorithms. One of the major issues for metaheuristics is to rethink existing parallel models and programming paradigms to allow their deployment on GPU accelerators. Generally speaking, the major issues we have to deal with are: the distribution of data processing between CPU and GPU, the thread synchronization, the optimization of data transfer between the different memories, the memory capacity constraints, etc. The contribution of this thesis is to deal with such issues for the redesign of parallel models of metaheuristics to allow solving of large scale optimization problems on GPU architectures. Our objective is to rethink the existing parallel models and to enable their deployment on GPUs. Thereby, we propose in this document a new generic guideline for building efficient parallel metaheuristics on GPU. Our challenge is to come out with the GPU-based design of the whole hierarchy of parallel models.In this purpose, very efficient approaches are proposed for CPU-GPU data transfer optimization, thread control, mapping of solutions to GPU threadsor memory management. These approaches have been exhaustively experimented using five optimization problems and four GPU configurations. Compared to a CPU-based execution, experiments report up to 80-fold acceleration for large combinatorial problems and up to 2000-fold speed-up for a continuous problem. The different works related to this thesis have been accepted in a dozen of publications, including the IEEE Transactions on Computers journal
14
Bachelet, Vincent. "Métaheuristiques parallèles hybrides : application au problème d'affection quadratique." Lille 1, 1999. https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/1999/50376-1999-397.pdf.
Full textAbstract:
Ce mémoire présente une étude sur la conception de méthodes hybrides efficaces pour l'optimisation combinatoire. Nous avons mené cette étude sur trois fronts : - la structure intrinsèque des instances du QAP (problème d'affectation quadratique) ; - les métaheuristiques sur environnements distribués ; - les mécanismes d'hybridation et de coévolution. Pour analyser les instances, nous avons étudié leurs paysages de fitness. Nous avons adopté une démarche basée sur le comportement d'une méthode de descente et avons proposé des indicateurs qui font ressortir trois tendances : type I - un paysage plat et rugueux ; type II - regroupement central des optima locaux constituant un massif ; type III - plusieurs massifs d'optima locaux éparpillés. Cette taxinomie originale rejoint d'autres classements obtenus de manière empirique. Pour étudier les métaheuristiques parallèles, nous avons distingué les recherches locales des méthodes à population. Pour les deux cas, nous avons proposé un modèle et avons sélectionné différentes formes de parallélisation. Pour les exécutions, nous avons utilisé diverses plates-formes parallèles. Nous avons constaté que les recherches locales sont plus efficaces sur les instances uniformes (type I) et qu'à l'inverse, les méthode à population sont plus performantes sur les instances structurées (type II). Ces constatations nous ont amené à considérer l'hybridation pour résoudre les instances de type III. Dans notre présentation des métaheuristiques hybrides, outre une taxinomie originale, nous avons proposé une méthode hybride parallèle qui associe puissance de calcul et coévolution. Cet hybride repose sur la coévolution d'agents de recherche locale, de diversification, et d'intensification. Ces agents coopèrent à travers une mémoire adaptative. Nous avons appliqué ce modèle coévolutionniste au QAP, et avons égalé, pour de nombreuses instances du QAP, les meilleurs résultats connus.
15
Mellouli, Racem. "Ordonnancement sur machines parallèles avec contraintes d'indisponibilité." Troyes, 2007. http://www.theses.fr/2007TROY0022.
Full textAbstract:
Les travaux de cette thèse sont articulés autour du problème d’ordonnancement sur machines parallèles identiques avec contraintes d’indisponibilité pour la minimisation du flow time. Nous avons étudié trois modèles de ce problème. L’objectif est de proposer des méthodes théoriques d’optimisation qui permettent une résolution efficace. Les approches développées sont variées : des heuristiques qui ont amélioré des méthodes classiques de la littérature, trois types d’approches exactes basées sur la programmation linéaire à variables mixtes, branch-and-bound utilisant différents schémas de séparation et programmation dynamique. Nous avons proposé des bornes inférieures constructives et itératives. Celles basées sur la relaxation lagrangienne étaient combinées avec différents outils de la recherche opérationnelle tels que l méthode de sous-gradient, la programmation dynamique et le splitting des travaux. Une méthode de génération de colonnes a été développée. La résolution des problèmes auxiliaires a été réalisée avec une méthode heuristique et une méthode exacte par programmation dynamique. Par ailleurs, nous avons prouvé des propriétés mathématiques et proposé de nouvelles bornes inférieures pour un modèle traité en littérature. Enfin, nous avons élaboré des analyses de performance au pire pour des méthodes heuristiques et une borne inférieureThis thesis is devoted to parallel machine scheduling with availability constraints for minimizing the flow time. We studied three theoretical models of this problem. The objective is to propose theoretical optimization methods that effectively solve these problems. We develop various approaches. Indeed, we proposed heuristic methods that improved classical methods from literature. Three types of exact approaches were considered : methods based on mixes integer linear programming, branch-and-bound methods using different branching schemes and methods based on dynamic programming. We also proposed constructive and iterative lower bounding schemes. In particular, lower bounds based on Lagrangian relaxation are combined with different tools from operational research, such as the subgradient method, dynamic programming and job splitting. Moreover, a method based on column generation has been developed based on a particular formulation of the problem. Auxiliary problems are solves with a heuristic method and an exact method using the dynamic programming. Furthermore, we proved several mathematical properties and proposed new lower bounds for a model already studied in the literature. Finally, we have studied worst-case performance for simple heuristics and a lower bound
16
Perez-Seva, Jean-Paul. "Les optimisations d'algorithmes de traitement de signal sur les architectures modernes parallèles et embarquées." Phd thesis, Université de Nice Sophia-Antipolis, 2009. http://tel.archives-ouvertes.fr/tel-00610865.
Full textAbstract:
Cette thèse s'intéresse aux méthodologies d'optimisation d'algorithmes de traitement de signal sur les architectures parallèles de processeurs embarqués. L'état de l'art des différentes architectures destinées au milieu embarqué permet de mettre en évidence les différents outils d'optimisation mis à disposition par les concepteurs de processeurs. L'accent est particulièrement mis sur les solutions bénéfiques aux calculs flottants intensifs, tout en notifiant les points communs et les divergences entre les différents processeurs. Le choix de l'algorithme de transformée de Fourier, comme algorithme représentatif des applications de traitement de signal, permet de détailler étape par étape les différents choix d'optimisation dans le cas d'une implémentation sur un PowerPC 970FX. Nous montrons comment à partir d'un algorithme radix-2, il est possible de réduire au plus prés du minimum la complexité de calcul grâce à l'usage de l'instruction de multiplication addition fusionnée. Nous proposons enfin une méthodologie de programmation multi-architectures utilisant le retour d'expérience précédent afin d'optimiser l'ordonnancement des instructions constituant l'algorithme.
17
Saidani, Tarik. "Optimisation multi-niveau d'une application de traitement d'images sur machines parallèles." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00776111.
Full textAbstract:
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.
18
Saidani, Tarik. "Optimisation multi-niveau d’une application de traitement d’images sur machines parallèles." Thesis, Paris 11, 2012. http://www.theses.fr/2012PA112268/document.
Full textAbstract:
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 processeurThis 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
19
Diallo, Amadou Tidiane. "Caractérisation analytique et optimisation de codes source-canal conjoints." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00748545.
Full textAbstract:
Les codes source-canal conjoints sont des codes réalisant simultanément une compression de données et une protection du train binaire généré par rapport à d'éventuelles erreurs de transmission. Ces codes sont non-linéaires, comme la plupart des codes de source. Leur intérêt potentiel est d'offrir de bonnes performances en termes de compression et de correction d'erreur pour des longueurs de codes réduites.La performance d'un code de source se mesure par la différence entre l'entropie de la source à compresser et le nombre moyen de bits nécessaire pour coder un symbole de cette source. La performance d'un code de canal se mesure par la distance minimale entre mots de codes ou entre suite de mots de codes, et plus généralement à l'aide du spectre des distances. Les codes classiques disposent d'outils pour évaluer efficacement ces critères de performance. Par ailleurs, la synthèse de bons codes de source ou de bons codes de canal est un domaine largement exploré depuis les travaux de Shannon. Par contre des outils analogues pour des codes source-canal conjoints, tant pour l'évaluation de performance que pour la synthèse de bons codes restaient à développer, même si certaines propositions ont déjà été faites dans le passé.Cette thèse s'intéresse à la famille des codes source-canal conjoints pouvant être décrits par des automates possédant un nombre fini d'états. Les codes quasi-arithmétiques correcteurs d'erreurs et les codes à longueurs variables correcteurs d'erreurs font partie de cette famille. La manière dont un automate peut être obtenu pour un code donné est rappelée.A partir d'un automate, il est possible de construire un graphe produit permettant de décrire toutes les paires de chemins divergeant d'un même état et convergeant vers un autre état. Nous avons montré que grâce à l'algorithme de Dijkstra, il est alors possible d'évaluer la distance libre d'un code conjoint avec une complexité polynomiale.Pour les codes à longueurs variables correcteurs d'erreurs, nous avons proposé des bornes supplémentaires, faciles à évaluer. Ces bornes constituent des extensions des bornes de Plotkin et de Heller aux codes à longueurs variables. Des bornes peuvent également être déduites du graphe produit associé à un code dont seule une partie des mots de codes a été spécifiée.Ces outils pour borner ou évaluer exactement la distance libre d'un code conjoint permettent de réaliser la synthèse de codes ayant des bonnes propriétés de distance pour une redondance donnée ou minimisant la redondance pour une distance libre donnée.Notre approche consiste à organiser la recherche de bons codes source-canal conjoints à l'aide d'arbres. La racine de l'arbre correspond à un code dont aucun bit n'est spécifié, les feuilles à des codes dont tous les bits sont spécifiés, et les nœuds intermédiaires à des codes partiellement spécifiés. Lors d'un déplacement de la racine vers les feuilles de l'arbre, les bornes supérieures sur la distance libre décroissent, tandis que les bornes inférieures croissent. Ceci permet d'appliquer un algorithme de type branch-and-prune pour trouver le code avec la plus grande distance libre, sans avoir à explorer tout l'arbre contenant les codes. L'approche proposée a permis la construction de codes conjoints pour les lettres de l'alphabet. Comparé à un schéma tandem équivalent (code de source suivi d'un code convolutif), les codes obtenus ont des performances comparables (taux de codage, distance libre) tout en étant moins complexes en termes de nombre d'état du décodeur.Plusieurs extensions de ces travaux sont en cours : 1) synthèse de codes à longueurs variables correcteurs d'erreurs formalisé comme un problème de programmation linéaire mixte sur les entiers ; 2) exploration à l'aide d'un algorithme de type A* de l'espace des codes de à longueurs variables correcteur d'erreurs.
20
Haddou, Mounir. "Contribution à l'étude des méthodes de décomposition et de barrières en optimisation convexe." Clermont-Ferrand 2, 1995. http://www.theses.fr/1995CLF21729.
Full textAbstract:
Cette thèse se compose de trois parties principales indépendantes. Dans la première partie, nous proposons une méthode de décomposition parallèle pour résoudre une grande classe de problèmes d'optimisation convexe (problèmes convexes a cout fortement convexe). Nous établissons des résultats de convergence globale pour cette méthode et présentons une série de résultats et comparaisons numériques effectues sur une machine du type cm-5. Dans la deuxième partie, nous étendons le champ d'application des méthodes entropie-proximales (qui ne s'appliquaient qu'aux problèmes d'optimisation convexe sur l'orthant positif) aux problèmes d'optimisation convexe sous contraintes linéaires et aux problèmes d'inégalités variationnelles sur des polyèdres. De plus, en programmation linéaire, nous donnons un résultat de convergence quadratique et présentons quelques résultats numériques. La dernière partie est consacrée à l'étude d'une grande classe de méthodes de pénalités et de barrières recouvrant la plupart des méthodes existantes. Nous donnons des moyens systématiques pour obtenir de telles fonctions et analysons l'existence des séquences primales et duales générées par ces méthodes. Ensuite, nous étudions la convergence de ces séquences vers les ensembles de solutions du problème primal et du problème dual. Dans le cas de programmation linéaire, nous montrons que ces séquences convergent vers des limites uniques et présentons quelques résultats numériques
21
Van, Luong Thé. "Métaheuristiques parallèles sur GPU." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2011. http://tel.archives-ouvertes.fr/tel-00638820.
Full textAbstract:
Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leur déploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on Computers.
22
Cougo, Bernardo. "Dimensionnement et Optimisation de Transformateurs Inter-Cellules pour les Convertisseurs Multicellulaires Parallèles." Phd thesis, Institut National Polytechnique de Toulouse - INPT, 2010. http://tel.archives-ouvertes.fr/tel-00578130.
Full textAbstract:
Les convertisseurs multicellulaires parallèles permettent de traiter des puissances importantes et de profiter d'une certaine standardisation des équipements. Ces dernières années, ces structures ont connu un regain d'intérêt lié notamment à la possibilité de couplage magnétique des inductances. Ce couplage aboutit à un composant magnétique aux propriétés très différentes appelé Transformateur Inter-Cellules (ICT) ; il ne modifie pas le courant de sortie, par contre il réduit l'ondulation de courant dans les bobines et l'ondulation de flux dans certaines parties du noyau. On peut montrer que ce couplage entraîne une réduction des pertes Joules dans les conducteurs et des pertes magnétiques dans le noyau. La réduction de l'ondulation de courant diminue également le courant efficace dans les semiconducteurs ce qui réduit les pertes par conduction, et la différence entre le courant à l'amorçage et au blocage des interrupteurs, ce qui permet la diminution des pertes dans les semiconducteurs lorsque les pertes au blocage sont supérieures aux pertes à l'amorçage. Le dimensionnement d'un ICT n'est pas fondamentalement différent de celui fait pour d'autres composants magnétiques en ce sens qu'il est basé sur le respect de certaines valeurs limites (induction, température) ce qui suppose une évaluation des différentes pertes et l'élaboration d'un modèle thermique. Par contre, la manière d'évaluer ces différentes grandeurs est tout à fait spécifique et n'a que quelques points communs avec les méthodes de calcul des inductances et des transformateurs Dans ce travail de thèse, on montre comment dimensionner ces ICTs en considérant plusieurs topologies et méthodes différentes, correspondant à différents niveaux de sophistication et de complexité. L'explication de ce dimensionnement est divisée en quatre parties : Pertes Cuivre, Pertes Fer, Densité de Flux de Saturation et Aspects Thermiques. L'évaluation des pertes cuivre liées aux composantes alternatives des ICTs constituent un point particulièrement délicat dans la mesure où elles résultent de la combinaison de deux facteurs eux-mêmes difficiles à évaluer ; l'inductance de fuite qui détermine l'amplitude des courants alternatifs mais dépend des flux principalement non canalisés et circulant dans l'air (volume d'étude important, effets 3D...), et la résistance équivalente des bobinages qui en haute fréquence est sujette à des phénomènes complexes comme les effets de peau et de proximité. En se basant sur l'utilisation d'un logiciel simple mais néanmoins robuste et fiable pour calculer précisément les résistances en haute fréquence et les inductances de fuite des ICTs, plusieurs astuces permettant de réduire les pertes cuivre non seulement des ICTs mais aussi des transformateurs et des inductances sont suggérées. Des tableaux simples sont développés pour aider le concepteur de transformateurs à identifier la meilleur configuration de conducteurs dans une fenêtre de bobinage en prenant en compte la forme d'onde du courant, le nombre de tours des enroulements, la fréquence des courants et les paramètres géométriques. Des formules analytiques et des outils de calcul adéquats ont ensuite été utilisés pour développer des routines d'optimisation ayant pour but la réduction de la masse, du volume, des pertes ou du coût des ICTs. Des interpolations multidimensionnelles des valeurs présimulées des résistances et inductances de fuite en haute fréquence sont utilisées afin de réduire le temps d'exécution de la routine d'optimisation. Plusieurs dimensionnements des ICTs ont été comparées vis-à-vis des matériaux du noyau et des conducteurs, du nombre de cellules de commutation et de la fréquence de découpage. Des comparaisons avec des selfs ont également été faites afin de montrer les avantages de ces ICTs. Des aspects de la commande des convertisseurs multi-niveaux triphasés ont également été étudiés vis-à- vis du flux circulant dans les ICTs. Des homopolaires, spécifiques pour chaque stratégie MLI et chaque topologie convertisseur/charge, sont créées afin de minimiser le flux dans les ICTs et par conséquent de réduire davantage la masse et la taille de ces composants. Des comparaisons entre différentes méthodes de MLI sont effectuées et vérifiées expérimentalement.
23
Briot, Sébastien. "Analyse et Optimisation d'une Nouvelle Famille de Manipulateurs Parallèles aux Mouvements Découplés." Phd thesis, INSA de Rennes, 2007. http://tel.archives-ouvertes.fr/tel-00327414.
Full textAbstract:
Il est bien connu que, parmi les nombreux avantages des manipulateurs parallèles par rapport aux robots sériels, on peut citer des vitesses et accélérations plus élevées, et une plus grande capacité de charge. Cependant, il existe des inconvénients, comme un volume de travail restreint, de forts couplages cinématiques et des singularités plus contraignantes. Afin d'améliorer leurs performances, des travaux ont été menés concernant le découplage des mouvements des robots parallèles. Le projet de thèse porte sur la conception, l'optimisation et l'amélioration d'une nouvelle famille de manipulateurs parallèles de 3 à 6 degrés de libertés partiellement découplés appelés PAMINSA (PArallel Manipulator of the I.N.S.A.). La deuxième partie de ce manuscrit présente la particularité de ces architectures qui est le découplage entre les mouvements de la plateforme dans le plan horizontal et les translations suivant l'axe vertical. Dans une troisième partie, nous faisons l'analyse des singularités de ces manipulateurs. Cette analyse est nécessaire pour choisir le manipulateur qui a le plus grand espace de travail sans singularité. Dans les parties 4 et 5, nous proposons des méthodes permettant d'augmenter la taille de leur espace de travail sans singularité. La première solution est basée sur l'utilisation de mécanismes à structure variable, c'est-à-dire des mécanismes dont les paramètres structurels peuvent être changés. Cette solution permet d'augmenter l'espace de travail sans singularité jusqu'à 100% de l'espace de travail total. La deuxième solution porte sur une optimisation des paramètres dynamiques des manipulateurs qui permet de traverser les singularités lors de déplacements de la plate-forme. Enfin, dans une sixième partie, une nouvelle méthode performante et rapide permettant de calculer la précision des manipulateurs PAMINSA ainsi que des solutions pour améliorer leurs caractéristiques fonctionnelles sontproposées.
24
Franche, Jean-François. "Optimisation d’algorithmes de codage vidéo sur des plateformes à plusieurs processeurs parallèles." Mémoire, École de technologie supérieure, 2011. http://espace.etsmtl.ca/1130/1/FRANCHE_Jean%2DFran%C3%A7ois.pdf.
Full textAbstract:
H.264 est le standard de codage vidéo le plus récent et le plus puissant. Ce standard permet, par rapport à ses prédécesseurs, d’augmenter le taux de compression par un facteur d’au moins deux, mais au prix d’une complexité plus élevée. Pour réduire le temps d’encodage, plusieurs encodeurs H.264 utilisent une approche parallèle. Dans le cadre de ce travail de recherche, notre objectif premier est de concevoir une approche offrant une meilleure accélération que l’approche implémentée dans l’encodeur H.264 d’Intel livré en code d’exemple dans sa librairie IPP.
Nous présentons notre approche d’encodage vidéo parallèle multi-trames et multi-tranches (MTMT) et ses modes d’estimation de mouvement qui offrent un compromis entre l’accélération et la perte de qualité visuelle. Le premier mode, le plus rapide, mais dégradant le plus la qualité, restreint la région de recherche de l'estimation de mouvement à l'intérieur des limites de la tranche courante. Le second mode, moins rapide, mais dégradant moins la qualité que le premier, élargit la région de recherche aux tranches voisines, quand les tranches de référence y correspondant ont été traitées. Le troisième mode, moins rapide que le second, mais dégradant moins la qualité, rend une tranche prête à l'encodage seulement quand les tranches de référence couvrant la région de recherche ont été traitées.
Nos expériences montrent que le premier mode de notre approche offre une accélération moyenne environ 55 % plus élevée que celle obtenue par l’approche d’Intel. Nos expériences montrent aussi que nous obtenons une accélération comparable à celle obtenue par l’état de l’art sans l’inconvénient de forcer l’utilisation des trames B. De plus, notre approche s’implémente rapidement dans un encodeur H.264 qui, comme l’encodeur H.264 d’Intel, est basé sur une approche multi-tranches.
25
Mannoni, Valérian. "Optimisation des codes LDPC pour les communications multi-porteuses." Reims, 2004. http://theses.univ-reims.fr/exl-doc/GED00000536.pdf.
Full textAbstract:
Un des inconvénients des transmissions OFDM est lié à l'émission de symboles à travers des sous-bandes fortement atténuées. En effet, ces symboles sont intrinsèquement affectés par un taux d'erreur binaire important nécessitant l'utilisation d'un codage canal performant (COFDM). Les codes correcteurs d'erreur que nous avons utilisés sont les codes LDPC. Nous en effectuons une large présentation incluant les notations et les outils algorithmiques indispensables. Afin de tenir compte de la non-stationnarité du canal OFDM sélectif en fréquence, nous avons alors généralisé la paramétrisation de ceux-ci en introduisant la notion de profil d'irrégularité. La chaîne de transmission COFDM (avec et sans allocation de bits) a été ensuite présentée, ainsi que les principales caractéristiques des canaux OFDM sélectifs en fréquence. La capacité de Shannon d'un tel système pour des entrées MAQ a été dérivée. Nous avons ensuite étudié le comportement asymptotique par évolution de densité des codes LDPC lors de transmissions OFDM à travers un canal sélectif en fréquence. Pour ce faire, nous montrons qu'il est possible de vérifier les hypothèses nécessaires à ce type d'analyse (symétrie du canal, indépendance des messages). Afin de pouvoir optimiser la structure des codes LDPC pour l'OFDM, une approximation Gaussienne de l'évolution de densité a alors été dérivée. Deux critères d'optimisation ont ensuite été introduis, l'un permettant d'obtenir le code présentant les meilleures performances asymptotiques (minimisation du seuil), et un critère original, mieux adapté aux hypothèses pratiques, basé sur la minimisation de la probabilité d'erreur sur les bits d'informationThe major drawback of OFDM transmissions is that some symbols might be subject to strong attenuations. Hence, these symbols are potentially affected by an important bit error rate which involves the use of channel coding. The channel codes used are LDPC codes for which we have presented the main notations and a decoding algorithm. Considering the nostationarity of the OFDM frequency selective channel, we introduced a more general description of LDPC codes that we call irregularity profile. The COFDM communication system is then presented (without and with bit allocation) as well as the main characteristics of OFDM frequency selective channels. The channel capacity of this OFDM system with discrete MAQ input has been derived. We have then studied the asymptotic behaviour of LDPC codes with density evolution for OFDM transmissions through a frequency selective channel. In order to make possible this analysis, we have shown that the necessary conditions (messages independence and channel symmetry) are checked for the OFDM channel. A Gaussian approximation of the density evolution has then been presented and used for the optimization of LDPC codes. Two optimization criteria have been introduced, one based on the minimization of the LDPC decoding threshold and another one based on the minimization of the bit error probability at a given SNR. The later criterion has shown better performances for practical applications
26
Mannoni, Valérian Delaunay Georges. "Optimisation des codes LDPC pour les communications multi-porteuses." Reims : S.C.D. de l'Université, 2004. http://scdurca.univ-reims.fr/exl-doc/GED00000536.pdf.
Full text
27
Hadi, Ammar. "Optimisation and analysis of polar codes in communication systems." Thesis, University of Manchester, 2018. https://www.research.manchester.ac.uk/portal/en/theses/optimisation-and-analysis-of-polar-codes-in-communication-systems(eb4cfc8a-86b5-465c-9231-4e02a3c2723c).html.
Full textAbstract:
Polar codes were invented as the first error-correcting codes to achieve the capacity for the discrete channels with relatively low-complexity for encoding and decoding. However, this is only possible with significantly large code lengths which are not practical for many systems. Meanwhile, the performance of the finite-lengths polar codes is not competitive with other modern error-correcting codes. This can be attributed to the suboptimality of the decoding process and the relatively poor minimum Hamming distances. This thesis aims to improve the performance of polar codes. The contributions include improving the performance of the conventional successive cancellation decoder. This is based on a novel technique, namely one-step decision delay, which incorporates some extra computational nodes to the code tree. Also, this thesis presents two methods for increasing the Hamming distances of polar codes; in the first, the code rate remains unchanged, while in the second, that produces superior performance, a modest reduction in the code rate occurs. Both methods enhance the performance with using belief propagation decoder. In addition, the latency of the decoding process is reduced by applying the fast Hadamard transform decoder on polar codes for the first time. In this regard, a method to modify the encoder is presented for some lengths that are not normally compatible with the proposed decoder. Interestingly, this modification method has another advantage that in the sense that it increases the minimum Hamming distances of the codes. Furthermore, this thesis presents the utilisation of polar codes in some practical communication systems. Firstly, polar codes are examined over power line communication systems. In this respect, the construction of polar codes is analysed by using three different methods. Additionally, the practical performance of polar codes is illustrated for both single-carrier and multi-carrier channels. Secondly, this thesis explores polar codes for unequal error protection by partitioning the information sets into a number of subsets with different reliabilities. JPEG2000, which is an image compression method, is used for validating the advantages of the proposed technique. Moreover, a new joint source channel decoding is proposed from the combination of the polar decoder and JPEG2000 decoder in order to enhance the quality of the compressed images. Finally, polar codes are investigated for the energy transfer by presenting new subcodes that are chosen according to the weights of the produced codewords. In this context, two modes of energy transfer are presented. The proposed modes can successfully extend the lifetime of the receiver's battery.
28
Bhatt, Rishabh. "Algorithmes parallèles en temps pour l'assimilation de données." Electronic Thesis or Diss., Université Grenoble Alpes, 2023. http://www.theses.fr/2023GRALM066.
Full textAbstract:
L'assimilation variationnelle de données (4DVAR), basée sur des algorithmes d'optimisation, est utilisée par les principales institutions météorologiques pour initialiser les modèles climatiques numériques. La condition initiale optimale est trouvée en minimisant une fonction de coût qui prend en compte les écarts entre la trajectoire du modèle et les observations du système sur une période donnée. Dans sa formulation incrémentale, l'intégration de la version directe et adjointe du modèle original est nécessaire pour calculer le gradient. Un problème courant dans l'identification de la condition initiale est la très grande taille de la variable d'état (10^9), ce qui rend très couteuse la tâche de minimisation. De plus, la technique 4DVAR est un algorithme intrinsèquement séquentiel et, pour l'utiliser dans des architectures parallèles, les modèles sont généralement parallélisés uniquement dans la dimension spatiale. ceci limite l'accélération (scalabilité) possible une fois que la saturation spatiale est atteinte et ainsi le nombre maximal de cœurs de calcul pouvant être utilisés est également restreint. L'objectif de cette thèse est d'introduire une parallélisation supplémentaire de la dimension temporell dans le cadre de l'assimilation de données en utilisant la méthode Parareal. Notre approche est utilisée ici pour l'intégration directe. Nous utilisons une version modifiée de la méthode du gradient conjugué inexact où les multiplications matrice-vecteur sont effectuées par l'algorithme parareal et ne sont donc pas exactes. Les conditions de convergence associées du gradient conjugué inexact nous permettent d'utiliser l'algorihtme Parareal de manière adaptative en régulant les erreurs dans le produit matrice-vecteur et en obtenant les mêmes niveaux de précision qu'avec la méthode du gradient conjugué avec gradient exact. Pour garantir la faisabilité et une mise en œuvre pratique, les normes intervenant dans la méthode du gradient conjugué inexact sont remplacées par des approximations facilement calculables. Les résultats sont démontrés en considérant un modèle en eau peu profonde en dimension 1 et 2. Ils sont présentés en termes de précision (en comparaison avec la méthode exacte du gradient conjugué) et du nombre d'itérations requises par l'algorithme Parareal. Pour le modèle en dimension 2, plus complexe, nous utilisons la technique de sous-espaces de Krylov afin d'accélèrer la convergence du parareal et réduire le nombre d'itérations. Enfin, les moyens de paralléliser temporellement la version adjointe sont discutés comme une voie de recherche supplémentaireFour dimensional variational data assimilation (4DVAR) which is based on optimisation algorithms is used by the leading meteorological institutions as a means of initialising the numerical climate models. The optimal initial condition is found by minimisng a cost function which accounts for the misfits of the model trajectory with the observations of the system over a given time window. In its incremental formulation, the integration of the forward and adjoint version of the original model is required in order to compute the gradient. A common issue in the retrieval of the initial condition is the enormous size of the state variable(10^9) which makes the minimisation an expensive and time consuming task. Moreover 4DVAR is an inherently sequential algorithm and to use it in parallel architectures, the models are classically parallelised only in the spatial dimension. This limits the scope of further speed up once spatial saturation is reached and also the maximum number of computing cores that one can use. The objective of this PhD is tointroduce an additional time-paralllelisation in the data assimilation framework by using the well known parareal method. Our approach is used here for running the forward integration. We use a modified version of the inexact conjugate gradient method where the matrix-vector multiplications are supplied through the parareal and thus are not exact. The associated convergence conditions of the inexact conjugate gradient allows us to use parareal adaptively by monitoring the errors in the matrix-vector product and obtaining the same levels of accuracy as with the usual conjugate gradient method at the same time. To ensure the feasibility and a practical implementation, all the norms which are hard to compute are replaced by the easily computable approximations. The results are demonstrated by considering the one and two dimensional shallow water model. They are presented in terms of the accuracy (in comparison with the original exact conjugate gradient) and in terms of the number of required iterations of the parareal algorithm. For the more complex two dimensional model we use a Krylov enhanced subspace parareal version which accelerates the convergence of the parareal and brings down the number of iterations. In the end, the ways to time-parallelisethe adjoint version is discussed as a further avenue for research
29
Maher, Rebai. "Ordonnancement des tâches de production et de maintenance préventive sur machines parallèles." Troyes, 2011. http://www.theses.fr/2011TROY0003.
Full textAbstract:
Dans plusieurs domaines, comme la télécommunication, l’informatique, le transport et l’administration, la fonction « ordonnancement » contribue considérablement dans le contrôle et la maîtrise des coûts et des délais de mise à disposition. Cette fonction est considérée comme base fondamentale de toute opération de planification. Dans cette thèse, nous nous sommes intéressés au problème d’ordonnancement d'un ensemble de N tâches de production sur M machines parallèles identiques où chaque machine doit être arrêtée pour des raisons de maintenance préventive. Nous avons supposé dans notre étude que les ressources assurant la maintenance préventive sont insuffisantes et que la maintenance doit commencer au début de l’horizon de planification. Nos travaux effectués se sont articulés autour de deux principaux problèmes : Le premier problème concerne l’ordonnancement de tâches de maintenance préventive. Notre objectif dans ce problème est de trouver une séquence pour les tâches de maintenance préventive ayant un coût de maintenance minimal. Le second problème traite l’ordonnancement intégré des tâches de production et celles de maintenance sur un ensemble de machines. Différentes méthodes exactes et approchées sont proposées pour résoudre ces deux problèmesIn several areas, such as telecommunications, computer science, transportation and administration, scheduling contributes in the monitoring and the reduction of the production costs and the delays. Indeed, scheduling is considered as the fundamental basis of any planning operation. In this thesis, we studied the problem of scheduling a set of N production tasks on M identical parallel machines where every machine must be stopped during the planning horizon for reasons of preventive maintenance. We assume in our study that the resources ensuring the preventive maintenance are limited in capacity. We also assume that the maintenance should begin at time zero. Our work is related to two main problems: The first one concerns the scheduling of preventive maintenance tasks. In this problem, we aim to find a sequence for the preventative maintenance tasks having a minimal maintenance cost. The second one deals with the integrated scheduling of production and maintenance tasks on a set of parallel machines. Different exact and heuristic methods are developed to solve these two problems
30
Vander-Swalmen, Pascal. "Aspects parallèles des problèmes de satisfaisabilité." Phd thesis, Université de Reims - Champagne Ardenne, 2009. http://tel.archives-ouvertes.fr/tel-00545657.
Full textAbstract:
Malgré sa complexité de résolution, le problème de SATisfaisabilité est une excellente et compétitive approche pour résoudre un large éventail de problèmes. Cela génère une forte demande pour une résolution de SAT haute performance de la part des industriels. Au fil du temps, de nombreuses approches et optimisations différentes ont été développées pour résoudre le problème plus efficacement. Ces innovations ont été faites sans prendre en compte le développement des micro processeurs actuels qui voient le nombre de leur cœurs de calcul augmenter. Cette thèse présente un nouveau type d'algorithme parallèle basé sur une forte collaboration où un processus riche est en charge de l'évaluation de l'arbre de recherche et où des processus pauvres fournissent des informations partielles ou globales, heuristiques ou logiques afin de simplifier la tâche du riche. Pour concrétiser ce solveur et le rendre efficace, nous avons étendu la notion de chemin de guidage à celle d'arbre de guidage. L'arbre de recherche est totalement partagé en mémoire centrale et tous les processeurs peuvent y travailler en même temps. Ce nouveau solveur est appelé MTSS pour Multi-Threaded SAT Solver. De plus, nous avons implémenté une tâche pour les processus riche et pauvres qui leur permet d'exécuter un solveur SAT externe, et cela, avec ou sans échange de lemmes afin de paralléliser tous types de solveurs (dédiés aux formules industrielles ou aléatoires). Ce nouvel environnement facilite la parallélisation des futures implémentations pour SAT. Quelques exemples et expérimentations, avec ou sans échange de lemmes, de parallélisation de solveurs externes sont présentées, mais aussi des résultats sur les performances de MTSS. Il est intéressant de noter que certaines accélérations sont super linéaires.
31
Khouri, Antoun. "Optimisation et mise en oeuvre d'algorithmes parallèles pour la reconnaissance de la parole." Avignon, 1995. http://www.theses.fr/1995AVIG0110.
Full textAbstract:
Le but de cette these est de realiser une machine puissante, economique, facile a utiliser, sur laquelle il est possible d'implanter et d'evaluer les modules et sous-modules de calcul de l'algorithme de la rap, dans l'esprit d'une independance maximale avec cet algorithme pour qu'il ne soit pas necessaire de modifier la conception electronique ou architecturale du systeme a chaque modification logicielle apportee. Pour atteindre cet objectif, nous utilisons un reseau de processeurs (transputers) sur lequel nous appliquons notre algorithme parallele. Nous presentons les principes generaux et problemes lies a la rap. Les choix effectues pour la determination des differents niveaux d'action de notre systeme de rap. Puis nous decrivons les modules logiciels du rap et leur fonctionnement. Ensuite, nous presentons l'environnement de travail pour une machine parallele et les outils logiciels qui nous ont permis la mise en oeuvre de notre algorithme et la configuration de notre reseau. Puis, nous presentons les algorithmes paralleles, le parallelisme, et les difficultes de programmation et de mise en application d'un algorithme parallele. Nous abordons ensuite les aspects materiels et les topologies de reseaux parmi lesquelles se portera le choix d'une architecture specifique adaptee a notre application. Nous terminons en faisant le point sur l'application realisee dans le cadre de cette these et sur les performances obtenues
32
Chardon, Marc. "Ordonnancement non préemptif à machines parallèles avec contraintes d'indisponibilité." Compiègne, 2003. http://www.theses.fr/2003COMP1487.
Full textAbstract:
Cette thèse traite de l'ordonnancement non préemptif à machines parallèles avec contraintes d'indisponibilité des machines. Les applications à ce genre de problèmes sont particulièrement nombreuses dans le cadre de l'informatique parallèle et également en gestion d'atelier de production. Dans cette thèse, nous définissons une nouvelle classe d'ordre, la classe des ordres sur-intervalles qui généralise les classes d'ordres intervalles et quasi-intervalles. Nous nous intéressons particulièrement à résoudre le problème d'ordonnancement non préemptif de tâches de durées unitaires (UET) grâce à une méthode de résolution exacte. Nous nous penchons ensuite sur la résolution du problème non UET que nous résolvons grâce à une méthode tabouThis thesis deals with the scheduling of tasks on parallel machines with unavailability constraints. Such a problem might be encountered in parallel computing, or in management of a production floor. The unitary execution time tasks scheduling problem is fundamental because it can be solving very efficiency. It is useful for the resolution of arbitrary duration tasks scheduling problem. There is a narrowest gap between the preemptive unitary execution time tasks scheduling problem and the arbitrary execution time tasks scheduling problem. If the durations of the tasks are bounded, we can use it to find lower bound for the general problem
33
Bird, Robert F. "Performance modelling and optimisation of inertial confinement fusion simulation codes." Thesis, University of Warwick, 2016. http://wrap.warwick.ac.uk/78677/.
Full textAbstract:
Legacy code performance has failed to keep up with that of modern hardware. Many new hardware features remain under-utilised, with the majority of code bases still unable to make use of accelerated or heterogeneous architectures. Code maintainers now accept that they can no longer rely solely on hardware improvements to drive code performance, and that changes at the software engineering level need to be made. The principal focus of the work presented in this thesis is an analysis of the changes legacy Inertial Confinement Fusion (ICF) codes need to make in order to efficiently use current and future parallel architectures. We discuss the process of developing a performance model, and demonstrate the ability of such a model to make accurate predictions about code performance for code variants on a range of architectures. We build on the knowledge gained from such a process, and examine how Particle-in-Cell (PIC) codes must change in order to move towards the required levels of portable and future-proof performance needed to leverage the capabilities of modern hardware. As part of this investigation, we present an OpenCL port of the legacy code EPOCH, as well as a fully featured mini-app representing EPOCH. Finally, as a direct consequence of these investigations, we directly apply these performance optimisations to the production version EPOCH, culminating in a speedup of over 2x for the core algorithm.
34
Detchart, Jonathan. "Optimisation de codes correcteurs d’effacements par application de transformées polynomiales." Thesis, Toulouse, ISAE, 2018. http://www.theses.fr/2018ESAE0031/document.
Full textAbstract:
Les codes correcteurs d’effacements sont aujourd’hui une solution bien connueutilisée pour fiabiliser les protocoles de communication ou le stockage distribué desdonnées. La plupart de ces codes sont basés sur l’arithmétique des corps finis, définissantl’addition et la multiplication sur un ensemble fini d’éléments, nécessitantsouvent des opérations complexes à réaliser. En raison de besoins en performancetoujours plus importants, ces codes ont fait l’objet de nombreuses recherches dans lebut d’obtenir de meilleures vitesses d’exécution, tout en ayant la meilleure capacitéde correction possible. Nous proposons une méthode permettant de transformer les éléments de certains corps finis en éléments d’un anneau afin d’y effectuer toutes les opérations dans lebut de simplifier à la fois le processus de codage et de décodage des codes correcteursd’effacements, sans aucun compromis sur les capacités de correction. Nous présentonségalement une technique de réordonnancement des opérations, permettant deréduire davantage le nombre d’opérations nécessaires au codage grâce à certainespropriétés propres aux anneaux utilisés. Enfin, nous analysons les performances decette méthode sur plusieurs architectures matérielles, et détaillons une implémentationsimple, basée uniquement sur des instructions xor et s’adaptant beaucoupplus efficacement que les autres implémentations à un environnement d’exécutionmassivement parallèleErasure codes are widely used to cope with failures for nearly all of today’snetworks communications and storage systems. Most of these codes are based onfinite field arithmetic, defining the addition and the multiplication over a set offinite elements. These operations can be very complex to perform. As a matter offact, codes performance improvements are still an up to date topic considering thecurrent data growth explosion. We propose a method to transform the elements of some finite fields into ring elements and perform the operations in this ring to simplify both coding and decoding of erasure codes, without any threshold on the correction capacities.We also present a scheduling technique allowing to reduce the number of operations thanks to some particular properties of the ring structure. Finally, we analyse the performance ofsuch a method considering several hardware architectures and detail a simple implementation, using only xor operations, fully scalable over a multicore environment
35
Lalam, Massinissa. "Optimisation de la concaténation de codes spatio-temporels et de codes correcteurs d'erreurs dans une transmission MIMO." Télécom Bretagne, 2006. http://www.theses.fr/2006TELB0022.
Full textAbstract:
Cette thèse traite du codage correcteur d'erreurs, du codage spatio-temporel ainsi que de l'utilisation conjointe de ces deux techniques dans un contexte à plusieurs antennes d'émission/réception ou contexte MIMO. L'objectif est de pouvoir améliorer le débit utile tout en conservant une bonne qualité de transmission. Dans un premier temps, les codes correcteurs d'erreurs algébriques binaires BCH et q-aires RS sont abordés. Le nouvel algorithme de la fenêtre d’encodage glissante est présenté et ses performances sont illustrées sur canal gaussien. Son impact sur le décodage et la vitesse de convergence des turbo codes en bloc est également mis en avant, de même que ses limites. Dans un second temps, les principales structures de codage MIMO sont décrites : les codes spatio-temporels en bloc orthogonaux (STBO) et les architectures en couche. Le modèle de canal retenu est celui du canal de Rayleigh sans mémoire invariant par bloc. L'utilisation des codes de RS en tant que codes spatio-temporels est également proposée et leurs performances par rapport à celles des codes STBO classiques sont exposées. Enfin dans un troisième temps, les codes spatio-temporels correcteurs d'erreurs sont introduits pour deux antennes d'émission. Ces codes utilisent les propriétés de linéarité des codes correcteurs d'erreurs afin de créer une corrélation spatio-temporelle exploitable en réception. Leurs performances sont comparées à celles de structures classiques combinant codage correcteur d'erreurs et codage STBO, laissant entrevoir le potentiel de la solution proposée. Exploitant la redondance, la notion de poinçonnage est également introduite afin d'augmenter l’efficacité spectrale.
36
Leclerc, Catherine. "Analyse et optimisation des mécanismes parallèles entraînés par câbles : application au simulateur de vol." Thesis, Université Laval, 2009. http://www.theses.ulaval.ca/2009/25926/25926.pdf.
Full textAbstract:
Ce projet de recherche vise à l’élaboration de nouveaux outils de détermination de l’espace atteignable d’un mécanisme à câbles, pour une application de simulateur de vol. On introduit d’abord la théorie des simulateurs de vol afin de bien saisir les besoins en terme de plate-forme de génération de mouvement. Ensuite, on présente brièvement les mécanismes à câbles comme solution potentielle aux lacunes des simulateurs de vol actuels. S’en suit le développement de plusieurs outils d’évaluation des mécanismes à câbles, puis l’utilisation de ces outils à l’intérieur d’une optimisation multicritérielle visant à déterminer une architecture optimale. On présente l’architecture ainsi obtenue et enfin, on discute du prototype fabriqué au Laboratoire de Robotique de l’Université Laval.
37
Barreteau, Michel. "Optimisation du placement des scans et des réductions pour machines parallèles à mémoire répartie." Versailles-St Quentin en Yvelines, 1998. http://www.theses.fr/1998VERS0001.
Full textAbstract:
L' @atout majeur des machines parallèles à mémoire répartie réside dans leur rapport coût/performance. Bénéficiant du concept d'extensibilité, leurs performances sont néanmoins étroitement liées à la notion de placement. En effet, ces multiprocesseurs sont extrêmement sensibles aux communications distantes ou plus exactement aux coûts qu'elles induisent. L'objectif du placement est de minimiser les communications. Or ces machines offrent des primitives de communications globales adaptées à leur architecture (réseau d'interconnexion) telles que les scans et les réductions ; leur coût étant très faible compte tenu de celui d'une communication point à point. Cette thèse propose un algorithme de placement automatique du code et des données dans un espace multidimensionnel, qui considère ces opérations globales. Basée sur la localité des données, cette méthode s'applique à décomposer le placement des calculs et des données. Elle remédie aussi à la contrainte logicielle classique dont souffrent les primitives associées ; à savoir que le calcul s'effectue impérativement suivant l'un des axes canoniques de la grille des processeurs virtuels. Enfin, on considère l'interaction des scans de façon à éviter toute redistribution superflue et coûteuse. Le fait de tenir compte des caractéristiques de la machine cible contribue à optimiser le placement et par la même occasion à exécuter efficacement des programmes scientifiques. Ainsi, on peut tirer profit des primitives de communication disponibles sur de telles architectures pour améliorer les performances.
38
Moukrim, Aziz. "Génération automatique de codes parallèles et nouvelles heuristiques d'ordonnancement pour les machines à passage de messages." Clermont-Ferrand 2, 1995. http://www.theses.fr/1995CLF21755.
Full textAbstract:
L'objet de cette these est la generation automatique de codes paralleles pour machines a passage de messages, et l'elaboration de nouvelles heuristiques d'ordonnancement avec delais de communication. Dans la premiere partie nous proposons un systeme de generation automatique de codes paralleles pour machines a passage de messages, descartes//, decompose en trois sous-systemes: sum//, ergo//et cogito//selon un niveau d'abstraction croissant. Nous avons procede a la realisation de sum//dont le langage d'entree permet deja a l'utilisateur de ne plus se soucier ni de la declaration ni de la gestion des canaux de communication dans les machines a passage de messages grace a la notion de classe de taches et tache copiee. Ensuite, nous avons propose un processus de traduction du sous-syteme ergo//en trois phases: partitionnement de l'algorithme d'entree et generation de scenarios, placement des taches et routage des donnees developpes en deuxieme partie de la these, et reconstitution des processus et gestion de leur traces sur les differents processuers sollicites. Dans la deuxieme partie, nous avons elabore de nouvelles heuristiques de placement des taches prenant en compte l'architecture reelle de la machine et considerant en meme temps le probleme de routage des donnees. Le gain moyen, obtenu par comparaison avec l'heuristique mcp utilisee dans le systeme hypertool et suivie d'une procedure de routage, est tres significatif. Enfin, nous avons etudie le probleme de l'encadrement du nombre optimal de processeurs necessaires pour l'obtention d'un ordonnancement optimal. Nous avons calcule une borne superieure dans le cas des arborescences et propose une heuristique pour l'evaluer dans le cas general. Une etude specifique a ete egalement menee pour les graphes de precedence sct
39
Upadrasta, Ramakrishna. "Sub-Polyhedral Compilation using (Unit-)Two-Variables-Per-Inequality Polyhedra." Phd thesis, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00818764.
Full textAbstract:
The goal of this thesis is to design algorithms that run with better complexity when compiling or parallelizing loop programs. The framework within which our algorithms operate is the polyhedral model of compilation which has been successful in the design and implementation of complex loop nest optimizers and parallelizing compilers. The algorithmic complexity and scalability limitations of the above framework remain one important weakness. We address it by introducing sub-polyhedral compilation by using (Unit-)Two-Variable-Per-Inequality or (U)TVPI Polyhedra, namely polyhedrawith restricted constraints of the type ax_{i}+bx_{j}\le c (\pm x_{i}\pm x_{j}\le c). A major focus of our sub-polyhedral compilation is the introduction of sub-polyhedral scheduling, where we propose a technique for scheduling using (U)TVPI polyhedra. As part of this, we introduce algorithms that can be used to construct under-aproximations of the systems of constraints resulting from affine scheduling problems. This technique relies on simple polynomial time algorithms to under approximate a general polyhedron into (U)TVPI polyhedra. The above under-approximation algorithms are generic enough that they can be used for many kinds of loop parallelization scheduling problems, reducing each of their complexities to asymptotically polynomial time. We also introduce sub-polyhedral code-generation where we propose algorithms to use the improved complexities of (U)TVPI sub-polyhedra in polyhedral code generation. In this problem, we show that the exponentialities associated with the widely used polyhedral code generators could be reduced to polynomial time using the improved complexities of (U)TVPI sub-polyhedra. The above presented sub-polyhedral scheduling techniques are evaluated in an experimental framework. For this, we modify the state-of-the-art PLuTo compiler which can parallelize for multi-core architectures using permutation and tiling transformations. We show that using our scheduling technique, the above under-approximations yield polyhedra that are non-empty for 10 out of 16 benchmarks from the Polybench (2.0) kernels. Solving the under-approximated system leads to asymptotic gains in complexity, and shows practically significant improvements when compared to a traditional LP solver. We also verify that code generated by our sub-polyhedral parallelization prototype matches the performance of PLuTo-optimized code when the under-approximation preserves feasibility.
40
Delprat, Sébastien. "Evaluation de stratégies de commande pour véhicules hybrides parallèles." Valenciennes, 2002. https://ged.uphf.fr/nuxeo/site/esupversions/493eb7bd-f6c9-4d5c-a6ba-13e8b9f0c855.
Full textAbstract:
La propulsion des véhicules hybrides est généralement assurée par un ou plusieurs moteurs électriques associés à un moteur thermique. La première partie décrit les grandes familles d'architectures et le prototype réalisé au LAMIH au cours de travaux précédents. La deuxième partie est consacrée à l'étude des straté̀gies de commande qui choisissent à chaque instant la répartition de puissance entre les deux chaînes de traction. Cette répartition de puissance est ensuite écrite sous la forme d'un problème d'optimisation globale sous contraintes. Plusieurs algorithmes basés sur la théorie de la commande optimale sont alors proposés. Enfin, les résultats obtenus sont utilisés pour proposer deux nouvelles strtégies de commande temps réel. Des critères permettant de caractériser les cycles de vitesses et les performances des stratégies de commande sont utilisés pour valider les nouvelles stratégiesHybrid vehicles are usually propelled by one or two electric motor and an internal combustion engine. The first part of this study presents some classical mechanical arrangements and describes the prototype built at the LAMIH during a previous project. Then algorithms, called control strategy, are described. They choose at each sampling time the power split between the engine and the motor. Then this power split is written into the form of an optimization under constraint problem. Several algorithms based on the optimal control theory are proposed. Two new control strategy are proposed, based on the analysis of the global optimization results. Several criterions are proposed in order to characterize speed cycles, to evaluate control strategies
41
Alabau, Miguel. "Une expression des algorithmes massivement parallèles à structure de données irrégulières." Bordeaux 1, 1994. http://www.theses.fr/1994BOR10569.
Full textAbstract:
Les applications massivement parallèles dans lesquelles le partage d'informations se fait sans mémoire commune rendent difficiles la gestion manuelle de la synchronisation et de la communication, du fait du grand nombre de processus mis en jeu. La programmation directe des processus communicants, la parallélisation automatique des programmes séquentiels, et l'utilisation de langages à parallélisme des données sont les réponses apportées à l'heure actuelle à ce problème. Les deux dernières approches, bien que très répandues, ont des difficultés à prendre en compte des problèmes mettant en jeu des données irrégulières. Dans ce document nous présentons un mode d'expression oriente parallélisme des données dans lequel le graphe est utilisé comme structure de données de base. Nous restreignons ce mode d'expression de façon à produire un langage compilable, base sur une expression en termes de graphes. Nous décrivons ensuite un schéma de compilation dans lequel les communications introduites ne peuvent provoquer aucun inter blocage des processus de l'application parallèle, même dans le cas ou les communications sont bloquantes. Nous proposons enfin une optimisation portant sur le nombre des communications
42
Cavalec-Amis, Karine. "Optimisation des turbo codes pour les systèmes à grande efficacité spectrale." Rennes 1, 2001. http://www.theses.fr/2001REN10096.
Full text
43
Cayrel, Pierre-Louis. "Construction et optimisation de cryptosystèmes basés sur les codes correcteurs d'erreurs." Limoges, 2008. https://aurore.unilim.fr/theses/nxfile/default/46aac3f7-1539-4684-bef6-9b1ae632c183/blobholder:0/2008LIMO4026.pdf.
Full textAbstract:
Dans cette thèse, on s’intéresse à l’étude de systèmes de chiffrement ainsi que de schémas de signature dont la sécurité repose sur des problèmes difficiles de théorie des codes correcteurs d’erreurs. Ces activités de recherche ont été motivées, d’une part d’un point de vue théorique par la création de nouveaux schémas de signature avec des propriétés spéciales ainsi que d’une manière de réduire la taille de clés du schéma de McEliece, et d’autre part, d’un point de vue pratique visant à utiliser des propriétés structurelles afin d’obtenir des implémentations effectives d’un schéma de signature fondé sur les codes correcteurs d’erreurs. Comme l’indique son titre, cette thèse traite de la construction et de l’optimisation des cryptosystèmes basés sur des codes correcteurs d’erreurs et plus particulièrement de cinq nouveaux protocoles. On présente ici une version sécurisée du schéma de Stern dans un environnement à faibles ressources, une nouvelle construction du schéma de Kabatianski, Krouk et Smeets, un schéma de signature basé sur l’identité prouvé sûr dans le modèle de l’oracle aléatoire, un schéma de signature de cercle à seuil et enfin une réduction de la taille de clés du schéma de McEliece à l’aide de codes alternants quasi-cycliques. En annexe, on présente un travail traitant des attaques algébriques de registre à décalage avec mémoire. On présente aussi brièvement une étude des codes cycliques sur des anneaux de matricesIn this thesis, we are interested in the study of encryption systems as well as signature schemes whose security relies on difficult problems of error-correcting codes. These research activities have been motivated, a part of a theoretical point of view by creating : new signature schemes with special properties and a way of reducing the size of the key of the McEliece scheme, and on the other hand, a practical point of view to use structural properties to obtain effective implementations of a signature scheme which is based on error-correcting codes. As its title indicates, this thesis deals with the construction and optimization of cryptosystems based on error-correcting codes and more particularly five new protocols. It presents a secure version of the Stern scheme in a low-resources environment, a new construction of the Kabatianski, Krouk and Smeets scheme, a signature scheme based on the identity proved secure in the random oracle model, a threshold ring signature scheme and a reduction of the size of the key of the McEliece scheme using quasi-cyclic alternant codes. In the annex, this work deals with algebraic attacks against linear feedback shift register with memory. It also presents a brief study of cyclic codes on rings of matrices
44
Donadio, Sébastien. "Optimisation itérative de bibliothèques de calculs par division hiérarchique de codes." Versailles-St Quentin en Yvelines, 2007. http://www.theses.fr/2007VERS0009.
Full textAbstract:
The increasing complexity of hardware features incorporated in modern processors makes high performance code generation very challenging. Library generators such as ATLAS, FFTW and SPIRAL overcome this issue by empirically searching in the space of possible program versions for the one that performs the best. This thesis explores fully automatic solution to adapt a compute-intensive application to the target architecture. We show that generative programming is a practical tool to implement a new hierarchical compilation approach for the generation of high performance code. Our general-purpose approach can be applied to generic loop structures. Our approach relies on the decomposition of the original loop nest into simpler kernels. These kernels are much simpler to optimize and furthermore, using such codes makes the performance trade off problem much simpler to express and to solve. We propose a new approach for the generation of performance libraries based on this decomposition methodLa complexité grandissante des architectures ne simplifie pas la tâche des compilateurs à générer du code performant. Les générateurs de bibliothèques comme ATLAS, FFTW et SPIRAL ont réussi à intégrer cette difficulté par l'utilisation de recherche itérative. Cette dernière génère différentes versions de programmes et sélectionne la meilleure d'entre elles. Cette thèse explore une solution automatique pour adapter les applications de calculs intensifs à l'architecture complexe des machines. Nous montrerons qu'une approche générative peut être un outil utile à l'implémentation d'une nouvelle approche de compilation hiérarchique pour la génération de code efficace. Cette approche, non spécifique, peut être appliquée sur des structures de boucle générales qu'elle divisera en des fragments de code plus simples à optimiser pour un compilateur. Nous proposerons une nouvelle approche de génération de bibliothèques qui s'appuiera sur la recomposition de ces codes avec un modèle très simplifié
45
Grishchenko, Dmitry. "Optimisation proximale avec réduction automatique de dimension." Thesis, Université Grenoble Alpes, 2020. http://www.theses.fr/2020GRALM055.
Full textAbstract:
Dans cette thèse, nous proposons des algorithmes proximaux, avec réduction de dimension automatique, pour des problèmes d’optimisation avec solutions parcimonieuses. Dans un premier temps, nous proposons une méthode générale de réduction de dimension, exploitant la propriété d’identification proximale, par des projections adaptées à la structure de l’itéré courant. Dans le cas parcimonieux, cet algorithme permet de travailler dans des sous-espaces aléatoires de petites dimensions plutôt que dans l’espace entier, possiblement de très grande dimension. Dans un deuxième temps, nous nous plaçons dans un cadre d’optimisation distribuée asynchrone et utilisons la méthode précédente pour réduire la taille des communications entre machines. Nous montrons tout d’abord, que l’application directe de notre méthode de réduction dimension dans ce cadre fonctionne si le problème est bien conditionné. Pour attaquer les problèmes généraux, nous proposons ensuite un reconditionnement proximal donnant ainsi un algorithme avec garanties théorétiques de convergence et de réduction de communications. Des experiences numériques montrent un gain important pour des problèmes classiques fortement parcimonieuxIn this thesis, we develop a framework to reduce the dimensionality of composite optimization problems with sparsity inducing regularizers. Based on the identification property of proximal methods, we first develop a ``sketch-and-project'' method that uses projections based on the structure of the correct point. This method allows to work with random low-dimensional subspaces instead of considering the full space in the cases when the final solution is sparse. Second, we place ourselves in the context of the delay-tolerant asynchronous proximal methods and use our dimension reduction technique to decrease the total size of communications. However, this technique is proven to converge only for well-conditioned problems both in theory in practice.Thus, we investigate wrapping it up into a proximal reconditioning framework. This leads to a theoretically backed algorithm that is guaranteed to cost less in terms of communications compared with a non-sparsified version; we show in practice that it implies faster runtime convergence when the sparsity of the problem is sufficiently big
46
El, Baz Abdessamad. "Décodage conjoint source-canal : optimisation d'une chaîne de transmission pour images fixes." Brest, 2002. http://www.theses.fr/2002BRES2008.
Full textAbstract:
Dans cette thèse nous avons considéré l'optimisation d'un système de transmission pour images fixes sur un canal bruité. Le système de transmission adopte la quantification vectorielle comme codeur de source. Le dictionnaire utilisé est construit avec la méthode de Kohonen qui confère une organisation topologique à ses vecteurs. Ces derniers sont associés de manière optimale aux points de la constellation de la modulation MAQ-16 utilisée pour transmettre les données. Par cette association le système devient robuste aux erreurs de transmission. Nous avons ensuite introduit un codeur correcteur d'erreur de type BCH tout en préservant la robustesse du système de transmission aux erreurs. Ainsi nous avons contraint les paramètres du codeur de canal. Une contrainte supplémentaire est imposée à ce même codeur pour exploiter les statistiques de la source. Nous avons tenu compte dans la règle de décision pour le décodage du code BCH de la loi de probabilité des vecteurs générés par la source que nous avons considéré dans un premier temps comme indépendants mais non équiprobables, et dans un deuxième temps comme formant une chaîne de Markov d'ordre 1. Les gains obtenus en termes de TEB et de PSNR de l'image décodée sue le canal de Gauss et le canal de Rayleigh que nous avons traités, sont appréciables. Nous avons ensuite remplacé le codeur BCH par un turbo code en bloc. Nous avons tenu compte de la statistique de la source dans le calcul de la règle de décision et de l'information extrinsèque. Le gain en PSNR de l'image Lenna décodée par les nouveaux algorithmes atteint les 11dB pour certains rapport signal sur bruit. De nombreuses images ont été étudiées dans ce cadre, les résultats dépendent des caractéristiques de ces images mais restent supérieurs aux algorithmes classiquesIn this thesis we considered the optimisation of a still image transmission system over noisy channel. The transmission system adopts a vector quantizer as a source encoder. The codebook used is built using kohonen's self organisation feature map algorithm which confers a topological organisation to the codebook vectors. Those vectors are associated in an optimal way to the constellation points of 16-QAM modulation used to transmit the data. By this association, the system becomes robust to the transmission errors. We then introduced a BCH forward error correction (FEC) code without altering the transmission system robustness to the errors. For this reason we have constrained the channel encoder. An additional constraint is imposed to this encoder to exploit the statistics of the source. When computing the BCH decoding decision rule, we take into account the probability distribution of the vectors generated by the source which we first regarded as independent but with non uniform distribution, and which we modelled in a second step as a first order Markov chain. The gain obtained in terms of BER and PSNR of the decoded image over the Gaussian channel and Rayleigh channel which we considered, are appreciable. We then replaced BCH FEC code by a BCH block turbo code. We took into account the statistics of the source in the calculation of the decision rule and the extrinsic information. The additional gain obtained in terms of PSNR of Lenna image decoded when using the new algorithms approaches the 11dB for low signal noise ratios, as compared to the classical algorithms. Many other images have been considered and the results show that the gain is highly dependent of the characteristics of the images but remains superior to classical algorithms
47
Chan, Evelyn Yu-San. "Heuristic optimisation for the minimum distance problem." Thesis, Nottingham Trent University, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.324569.
Full text
48
Schmitt, Maxime. "Génération automatique de codes adaptatifs." Thesis, Strasbourg, 2019. http://www.theses.fr/2019STRAD029.
Full textAbstract:
Dans cette thèse nous proposons une interface de programmation pour aider les développeurs dans leur tâche d'optimisation de programme par calcul approché. Cette interface prend la forme d'extensions aux langages de programmation pour indiquer au compilateur quelles parties du programme peuvent utiliser ce type de calcul. Le compilateur se charge alors de transformer les parties du programme visées pour rendre l'application adaptative, allouant plus de ressources aux endroits où une précision importante est requise et utilisant des approximations où la précision peut être moindre. Nous avons automatisé la découverte des paramètres d'optimisation que devrait fournir l'utilisateur pour les codes à stencil, qui sont souvent rencontrés dans des applications de traitement du signal, traitement d'image ou simulation numérique. Nous avons exploré des techniques de compression automatique de données pour compléter la génération de code adaptatif. Nous utilisons la transformée en ondelettes pour compresser les données et obtenir d'autres informations qui peuvent être utilisées pour trouver les zones avec des besoins en précision plus importantesIn this thesis we introduce a new application programming interface to help developers to optimize an application with approximate computing techniques. This interface is provided as a language extension to advise the compiler about the parts of the program that may be optimized with approximate computing and what can be done about them. The code transformations of the targeted regions are entirely handled by the compiler to produce an adaptive software. The produced adaptive application allocates more computing power to the locations where more precision is required, and may use approximations where the precision is secondary. We automate the discovery of the optimization parameters for the special class of stencil programs which are common in signal/image processing and numerical simulations. Finally, we explore the possibility of compressing the application data using the wavelet transform and we use information found in this basis to locate the areas where more precision may be needed
49
Weill-Duflos, Christine. "Optimisation de méthodes de résolution itératives de grands systèmes linéaires creux sur machines massivement parallèles." Paris 6, 1994. http://www.theses.fr/1994PA066284.
Full textAbstract:
Avec le développement des architectures parallèles et l'adaptation d'algorithmes sur ces machines, les champs d'application deviennent de plus en plus importants, les tailles des problèmes plus grandes et les structures plus complexes. Nous avons étudié la parallélisation de la méthode du gradient conjugué pré conditionné selon un modèle de programmation data parallèle pour des structures de données irrégulières avec deux familles de pré conditionnement: polynomiaux et ilu. Nous explicitons la méthodologie de programmation, ce qui nous permet ensuite de définir et d'étudier différentes complexités. Les expériences numériques réalisées sur cm-2 et cm-5 ont permis de mettre en évidence l'importance du placement des données sur les processeurs. Nous montrons aussi les relations entre les patrons des matrices et les performances des communications générales. Les performances des pré conditionnements mettent en évidence la dualité entre efficacité numérique et efficacité en mflops. Nous proposons pour prendre en compte ces facteurs un pré conditionnement hybride qui introduit un paramètre qui permet de réduire les communications. Nous avons aussi pu comparer les deux cm et leurs langages. Néanmoins, nous devons constater que la gestion des structures creuses irrégulières est laissée au programmeur. Les bonnes performances de notre approche pour des structures de données irrégulières, nous ont permis de définir des spécifications pour intégrer le calcul creux sur de telles structures dans un environnement de programmation data parallèle: help. Pour conclure, nous évoquons le problème des choix de compromis pour les pré conditionnements parallèles et les perspectives futures pour la programmation data-parallèle sur des structures de données irrégulières
50
Paugam-Moisy, Hélène. "Optimisation des réseaux de neurones artificiels : analyse et mises en œuvre sur ordinateurs massivement parallèles." Lyon 1, 1992. http://www.theses.fr/1992LYO10018.
Full textAbstract:
Nos travaux se rapportent a deux themes en plein essor: les reseaux de neurones artificiels, et les ordinateurs massivement paralleles. Le fil conducteur est l'optimisation des modeles connexionnistes, et plus specialement des reseaux multicouches. Apres avoir etudie les modeles classiques et leurs implantations, nous cherchons, dans un cadre theorique, a optimiser l'architecture des perceptrons multicouches. Nous analysons leur puissance de realisation, en termes de nombre de couches et de cellules cachees, et nous cherchons a construire des reseaux minimaux. Plus concretement, nous construisons ensuite un outil de recherche automatique de bons parametres, pour une application donnee. Son principe est fonde sur l'observation de reseaux qui apprennent en parallele. Cet outil est implante sur un multiprocesseur mimd et permet de dresser des cartes de performances, ainsi que de selectionner des reseaux optimaux. Plusieurs experiences ont ete menees, sur des applications industrielles. L'acceleration de l'apprentissage et de la reconnaissance est un autre moyen d'optimiser les reseaux neuronaux. Nous avons implante et modelise des parallelisations de ces deux phases. L'impact de la parallelisation sur l'algorithme de retro-propagation est mis en valeur. Des lois experimentales sont etablies pour l'algorithme du gradient par blocs