Thèses sur le sujet « Optimisations for GPU »
Pour voir les autres types de publications sur ce sujet consultez le lien suivant : Optimisations for GPU.
Créez une référence correcte selon les styles APA, MLA, Chicago, Harvard et plusieurs autres
Consultez les 50 meilleures thèses pour votre recherche sur le sujet « Optimisations for GPU ».
À côté de chaque source dans la liste de références il y a un bouton « Ajouter à la bibliographie ». Cliquez sur ce bouton, et nous générerons automatiquement la référence bibliographique pour la source choisie selon votre style de citation préféré : APA, MLA, Harvard, Vancouver, Chicago, etc.
Vous pouvez aussi télécharger le texte intégral de la publication scolaire au format pdf et consulter son résumé en ligne lorsque ces informations sont inclues dans les métadonnées.
Parcourez les thèses sur diverses disciplines et organisez correctement votre bibliographie.
1
Romera, Thomas. « Adéquation algorithme architecture pour flot optique sur GPU embarqué ». Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS450.
Texte intégralRésumé :
Cette thèse porte sur l'optimisation et l'implémentation efficace d'algorithmes d'estimation du mouvement des pixels (flot optique) sur des processeurs graphiques (GPU) embarqués. Deux algorithmes itératifs ont été étudiés : la méthode de Variation Totale - L1 (TV-L1) et la méthode de Horn-Schunck. L’objectif est d’obtenir un traitement temps réel (moins de 40 ms par images) sur des plateformes embarquées à faible consommation énergétique, tout en gardant une résolution image et une qualité d’estimation du flot acceptable pour les applications visées. Différents niveaux de stratégies d'optimisation ont été explorés. Des transformations algorithmiques de haut niveau, telles que la fusion d'opérateurs et le pipeline d'opérateurs, ont été mises en œuvre pour maximiser la réutilisation des données et améliorer la localité spatiale/temporelle. De plus, des optimisations bas niveau spécifiques aux GPU, notamment l'utilisation d'instructions et de nombres vectoriels, ainsi qu'une gestion efficace de l'accès à la mémoire, ont été intégrées. L'impact de la représentation des nombres en virgule flottante (simple précision par rapport à demi-précision) a également été étudié. Les implémentations ont été évaluées sur les plateformes embarquées Nvidia Jetson Xavier, TX2 et Nano en termes de temps d'exécution, de consommation énergétique et de précision du flot optique. Notamment, la méthode TV-L1 présente une complexité et une intensité de calcul plus élevées par rapport à Horn-Schunck. Les versions les plus rapides de ces algorithmes atteignent ainsi un temps de traitement de 0,21 nanosecondes par pixel par itération en demi-précision sur la plate-forme Xavier. Cela représente une réduction du temps d'exécution de 22x par rapport aux versions CPU efficaces et parallèles. De plus, la consommation d'énergie est réduite d'un facteur x5,3. Parmi les cartes testées, la plate-forme embarquée Xavier, à la fois la plus puissante et la plus récente, offre systématiquement les meilleurs résultats en termes de vitesse et d'efficacité énergétique. La fusion d'opérateurs et le pipelining se sont avérés essentiels pour améliorer les performances sur GPU en favorisant la réutilisation des données. Cette réutilisation des données est rendue possible grâce à la mémoire Shared des GPU, une petite mémoire d'accès rapide permettant le partage de données entre les threads du même bloc de threads GPU. Bien que la fusion de plusieurs itérations apporte des gains de performance, elle est limitée par la taille de la mémoire Shared, nécessitant des compromis entre l'utilisation des ressources et la vitesse. L'utilisation de nombres en demi-précision accélère les algorithmes itératifs et permet d'obtenir une meilleure précision du flot optique dans le même laps de temps par rapport aux versions en simple-précision. Les implémentations en demi-précision convergent plus rapidement en raison de l'augmentation du nombre d'itérations réalisables dans un délai donné. Plus précisément, l'utilisation de nombres en demi-précision sur la meilleure architecture GPU accélère l'exécution jusqu'à 2,2x pour TV-L1 et 3,7x pour Horn-Schunck. Ces travaux soulignent l'importance des optimisations spécifiques aux GPU pour les algorithmes de vision par ordinateur, ainsi que l'utilisation et l'étude des nombres à virgule flottante de précision réduite. Ils ouvrent la voie à des améliorations futures grâce à des différentes transformations algorithmiques, à des formats numériques différents et à des architectures matérielles nouvelles. Cette approche peut également être étendue à d'autres familles d'algorithmes itératifsThis thesis focus on the optimization and efficient implementation of pixel motion (optical flow) estimation algorithms on embedded graphics processing units (GPUs). Two iterative algorithms have been studied: the Total Variation - L1 (TV-L1) method and the Horn-Schunck method. The primary objective of this work is to achieve real-time processing, with a target frame processing time of less than 40 milliseconds, on low-power platforms, while maintaining acceptable image resolution and flow estimation quality for the intended applications. Various levels of optimization strategies have been explored. High-level algorithmic transformations, such as operator fusion and operator pipelining, have been implemented to maximize data reuse and enhance spatial/temporal locality. Additionally, GPU-specific low-level optimizations, including the utilization of vector instructions and numbers, as well as efficient memory access management, have been incorporated. The impact of floating-point number representation (single-precision versus half-precision) has also been investigated. The implementations have been assessed on Nvidia's Jetson Xavier, TX2, and Nano embedded platforms in terms of execution time, power consumption, and optical flow accuracy. Notably, the TV-L1 method exhibits higher complexity and computational intensity compared to Horn-Schunck. The fastest versions of these algorithms achieve a processing rate of 0.21 nanoseconds per pixel per iteration in half-precision on the Xavier platform, representing a 22x time reduction over efficient and parallel CPU versions. Furthermore, energy consumption is reduced by a factor of x5.3. Among the tested boards, the Xavier embedded platform, being both the most powerful and the most recent, consistently delivers the best results in terms of speed and energy efficiency. Operator merging and pipelining have proven to be instrumental in improving GPU performance by enhancing data reuse. This data reuse is made possible through GPU Shared memory, which is a small, high-speed memory that enables data sharing among threads within the same GPU thread block. While merging multiple iterations yields performance gains, it is constrained by the size of the Shared memory, necessitating trade-offs between resource utilization and speed. The adoption of half-precision numbers accelerates iterative algorithms and achieves superior optical flow accuracy within the same time frame compared to single-precision counterparts. Half-precision implementations converge more rapidly due to the increased number of iterations possible within a given time window. Specifically, the use of half-precision numbers on the best GPU architecture accelerates execution by up to x2.2 for TV-L1 and x3.7 for Horn-Schunck. This work underscores the significance of both GPU-specific optimizations for computer vision algorithms, along with the use and study of reduced floating point numbers. They pave the way for future enhancements through new algorithmic transformations, alternative numerical formats, and hardware architectures. This approach can potentially be extended to other families of iterative algorithms
2
Fumero, Alfonso Juan José. « Accelerating interpreted programming languages on GPUs with just-in-time compilation and runtime optimisations ». Thesis, University of Edinburgh, 2017. http://hdl.handle.net/1842/28718.
Texte intégralRésumé :
Nowadays, most computer systems are equipped with powerful parallel devices such as Graphics Processing Units (GPUs). They are present in almost every computer system including mobile devices, tablets, desktop computers and servers. These parallel systems have unlocked the possibility for many scientists and companies to process significant amounts of data in shorter time. But the usage of these parallel systems is very challenging due to their programming complexity. The most common programming languages for GPUs, such as OpenCL and CUDA, are created for expert programmers, where developers are required to know hardware details to use GPUs. However, many users of heterogeneous and parallel hardware, such as economists, biologists, physicists or psychologists, are not necessarily expert GPU programmers. They have the need to speed up their applications, which are often written in high-level and dynamic programming languages, such as Java, R or Python. Little work has been done to generate GPU code automatically from these high-level interpreted and dynamic programming languages. This thesis presents a combination of a programming interface and a set of compiler techniques which enable an automatic translation of a subset of Java and R programs into OpenCL to execute on a GPU. The goal is to reduce the programmability and usability gaps between interpreted programming languages and GPUs. The first contribution is an Application Programming Interface (API) for programming heterogeneous and multi-core systems. This API combines ideas from functional programming and algorithmic skeletons to compose and reuse parallel operations. The second contribution is a new OpenCL Just-In-Time (JIT) compiler that automatically translates a subset of the Java bytecode to GPU code. This is combined with a new runtime system that optimises the data management and avoids data transformations between Java and OpenCL. This OpenCL framework and the runtime system achieve speedups of up to 645x compared to Java within 23% slowdown compared to the handwritten native OpenCL code. The third contribution is a new OpenCL JIT compiler for dynamic and interpreted programming languages. While the R language is used in this thesis, the developed techniques are generic for dynamic languages. This JIT compiler uniquely combines a set of existing compiler techniques, such as specialisation and partial evaluation, for OpenCL compilation together with an optimising runtime that compile and execute R code on GPUs. This JIT compiler for the R language achieves speedups of up to 1300x compared to GNU-R and 1.8x slowdown compared to native OpenCL.
3
Hopson, Benjamin Thomas Ken. « Techniques of design optimisation for algorithms implemented in software ». Thesis, University of Edinburgh, 2016. http://hdl.handle.net/1842/20435.
Texte intégralRésumé :
The overarching objective of this thesis was to develop tools for parallelising, optimising, and implementing algorithms on parallel architectures, in particular General Purpose Graphics Processors (GPGPUs). Two projects were chosen from different application areas in which GPGPUs are used: a defence application involving image compression, and a modelling application in bioinformatics (computational immunology). Each project had its own specific objectives, as well as supporting the overall research goal. The defence / image compression project was carried out in collaboration with the Jet Propulsion Laboratories. The specific questions were: to what extent an algorithm designed for bit-serial for the lossless compression of hyperspectral images on-board unmanned vehicles (UAVs) in hardware could be parallelised, whether GPGPUs could be used to implement that algorithm, and whether a software implementation with or without GPGPU acceleration could match the throughput of a dedicated hardware (FPGA) implementation. The dependencies within the algorithm were analysed, and the algorithm parallelised. The algorithm was implemented in software for GPGPU, and optimised. During the optimisation process, profiling revealed less than optimal device utilisation, but no further optimisations resulted in an improvement in speed. The design had hit a local-maximum of performance. Analysis of the arithmetic intensity and data-flow exposed flaws in the standard optimisation metric of kernel occupancy used for GPU optimisation. Redesigning the implementation with revised criteria (fused kernels, lower occupancy, and greater data locality) led to a new implementation with 10x higher throughput. GPGPUs were shown to be viable for on-board implementation of the CCSDS lossless hyperspectral image compression algorithm, exceeding the performance of the hardware reference implementation, and providing sufficient throughput for the next generation of image sensor as well. The second project was carried out in collaboration with biologists at the University of Arizona and involved modelling a complex biological system – VDJ recombination involved in the formation of T-cell receptors (TCRs). Generation of immune receptors (T cell receptor and antibodies) by VDJ recombination is an enormously complex process, which can theoretically synthesize greater than 1018 variants. Originally thought to be a random process, the underlying mechanisms clearly have a non-random nature that preferentially creates a small subset of immune receptors in many individuals. Understanding this bias is a longstanding problem in the field of immunology. Modelling the process of VDJ recombination to determine the number of ways each immune receptor can be synthesized, previously thought to be untenable, is a key first step in determining how this special population is made. The computational tools developed in this thesis have allowed immunologists for the first time to comprehensively test and invalidate a longstanding theory (convergent recombination) for how this special population is created, while generating the data needed to develop novel hypothesis.
4
Luong, Thé Van. « Métaheuristiques parallèles sur GPU ». Thesis, Lille 1, 2011. http://www.theses.fr/2011LIL10058/document.
Texte intégralRésumé :
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
5
Chrétien, Benjamin. « Optimisation semi-infinie sur GPU pour le contrôle corps-complet de robots ». Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT315/document.
Texte intégralRésumé :
Un robot humanoïde est un système complexe doté de nombreux degrés de liberté, et dont le comportement est sujet aux équations non linéaires du mouvement. Par conséquent, la planification de mouvement pour un tel système est une tâche difficile d'un point de vue calculatoire. Dans ce mémoire, nous avons pour objectif de développer une méthode permettant d'utiliser la puissance de calcul des GPUs dans le contexte de la planification de mouvement corps-complet basée sur de l'optimisation. Nous montrons dans un premier temps les propriétés du problème d'optimisation, et des pistes d'étude pour la parallélisation de ce dernier. Ensuite, nous présentons notre approche du calcul de la dynamique, adaptée aux architectures de calcul parallèle. Cela nous permet de proposer une implémentation de notre problème de planification de mouvement sur GPU: contraintes et gradients sont calculés en parallèle, tandis que la résolution du problème même se déroule sur le CPU. Nous proposons en outre une nouvelle paramétrisation des forces de contact adaptée à notre problème d'optimisation. Enfin, nous étudions l'extension de notre travail au contrôle prédictifA humanoid robot is a complex system with numerous degrees of freedom, whose behavior is subject to the nonlinear equations of motion. As a result, planning its motion is a difficult task from a computational perspective.In this thesis, we aim at developing a method that can leverage the computing power of GPUs in the context of optimization-based whole-body motion planning. We first exhibit the properties of the optimization problem, and show that several avenues can be exploited in the context of parallel computing. Then, we present our approach of the dynamics computation, suitable for highly-parallel processing architectures. Next, we propose a many-core GPU implementation of the motion planning problem. Our approach computes the constraints and their gradients in parallel, and feeds the result to a nonlinear optimization solver running on the CPU. Because each constraint and its gradient can be evaluated independently for each time interval, we end up with a highly parallelizable problem that can take advantage of GPUs. We also propose a new parametrization of contact forces adapted to our optimization problem. Finally, we investigate the extension of our work to model predictive control
6
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.
Texte intégralRésumé :
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.
7
Delevacq, Audrey. « Métaheuristiques pour l'optimisation combinatoire sur processeurs graphiques (GPU) ». Thesis, Reims, 2013. http://www.theses.fr/2013REIMS011/document.
Texte intégralRésumé :
Plusieurs problèmes d'optimisation combinatoire sont dits NP-difficiles et ne peuvent être résolus de façon optimale par des algorithmes exacts. Les métaheuristiques ont prouvé qu'elles pouvaient être efficaces pour résoudre un grand nombre de ces problèmes en leur trouvant des solutions approchées en un temps raisonnable. Cependant, face à des instances de grande taille, elles ont besoin d'un temps de calcul et d'une quantité d'espace mémoire considérables pour être performantes dans l'exploration de l'espace de recherche. Par conséquent, l'intérêt voué à leur déploiement sur des architectures de calcul haute performance a augmenté durant ces dernières années. Les approches de parallélisation existantes suivent généralement les paradigmes de passage de messages ou de mémoire partagée qui conviennent aux architectures traditionnelles à base de microprocesseurs, aussi appelés CPU (Central Processing Unit).Cependant, la recherche évolue très rapidement dans le domaine du parallélisme et de nouvelles architectures émergent, notamment les accélérateurs matériels qui permettent de décharger le CPU de certaines de ses tâches. Parmi ceux-ci, les processeurs graphiques ou GPU (Graphics Processing Units) présentent une architecture massivement parallèle possédant un grand potentiel mais aussi de nouvelles difficultés d'algorithmique et de programmation. En effet, les modèles de parallélisation de métaheuristiques existants sont généralement inadaptés aux environnements de calcul de type GPU. Certains travaux ont d'ailleurs abordé ce sujet sans toutefois y apporter une vision globale et fondamentale.L'objectif général de cette thèse est de proposer un cadre de référence permettant l'implémentation efficace des métaheuristiques sur des architectures parallèles basées sur les GPU. Elle débute par un état de l'art décrivant les travaux existants sur la parallélisation GPU des métaheuristiques et les classifications générales des métaheuristiques parallèles. Une taxonomie originale est ensuite proposée afin de classifier les implémentations recensées et de formaliser les stratégies de parallélisation sur GPU dans un cadre méthodologique cohérent. Cette thèse vise également à valider cette taxonomie en exploitant ses principales composantes pour proposer des stratégies de parallélisation originales spécifiquement adaptées aux architectures GPU. Plusieurs implémentations performantes basées sur les métaheuristiques d'Optimisation par Colonie de Fourmis et de Recherche Locale Itérée sont ainsi proposées pour la résolution du problème du Voyageur de Commerce. Une étude expérimentale structurée et minutieuse est réalisée afin d'évaluer et de comparer la performance des approches autant au niveau de la qualité des solutions trouvées que de la réduction du temps de calculSeveral combinatorial optimization problems are NP-hard and can only be solved optimally by exact algorithms for small instances. Metaheuristics have proved to be effective in solving many of these problems by finding approximate solutions in a reasonable time. However, dealing with large instances, they may require considerable computation time and amount of memory space to be efficient in the exploration of the search space. Therefore, the interest devoted to their deployment on high performance computing architectures has increased over the past years. Existing parallelization approaches generally follow the message-passing and shared-memory computing paradigms which are suitable for traditional architectures based on microprocessors, also called CPU (Central Processing Unit). However, research in the field of parallel computing is rapidly evolving and new architectures emerge, including hardware accelerators which offloads the CPU of some of its tasks. Among them, graphics processors or GPUs (Graphics Processing Units) have a massively parallel architecture with great potential but also imply new algorithmic and programming challenges. In fact, existing parallelization models of metaheuristics are generally unsuited to computing environments like GPUs. Few works have tackled this subject without providing a comprehensive and fundamental view of it.The general purpose of this thesis is to propose a framework for the effective implementation of metaheuristics on parallel architectures based on GPUs. It begins with a state of the art describing existing works on GPU parallelization of metaheuristics and general classifications of parallel metaheuristics. An original taxonomy is then designed to classify identified implementations and to formalize GPU parallelization strategies in a coherent methodological framework. This thesis also aims to validate this taxonomy by exploiting its main components to propose original parallelization strategies specifically tailored to GPU architectures. Several effective implementations based on Ant Colony Optimization and Iterated Local Search metaheuristics are thus proposed for solving the Travelling Salesman Problem. A structured and thorough experimental study is conducted to evaluate and compare the performance of approaches on criteria related to solution quality and computing time reduction
8
Quinto, Michele Arcangelo. « Méthode de reconstruction adaptive en tomographie par rayons X : optimisation sur architectures parallèles de type GPU ». Thesis, Grenoble, 2013. http://www.theses.fr/2013GRENT109/document.
Texte intégralRésumé :
La reconstruction tomographique à partir de données de projections est un problème inverse largement utilisé en imagerie médicale et de façon plus modeste pour le contrôle nondestructif. Avec un nombre suffisant de projections, les algorithmes analytiques permettentdes reconstructions rapides et précises. Toutefois, dans le cas d’un faible nombre de vues(imagerie faible dose) et/ou d’angle limité (contraintes spécifiques liées à l’installation), lesdonnées disponibles pour l’inversion ne sont pas complètes, le mauvais conditionnementdu problème s’accentue, et les résultats montrent des artefacts importants. Pour aborderces situations, une approche alternative consiste à discrétiser le problème de reconstruction,et à utiliser des algorithmes itératifs ou une formulation statistique du problème afinde calculer une estimation de l’objet inconnu. Ces méthodes sont classiquement basées surune discrétisation du volume en un ensemble de voxels, et fournissent des cartes 3D de ladensité de l’objet étudié. Les temps de calcul et la ressource mémoire de ces méthodesitératives sont leurs principaux points faibles. Par ailleurs, quelle que soit l’application, lesvolumes sont ensuite segmentés pour une analyse quantitative. Devant le large éventaild’outils de segmentation existant, basés sur différentes interprétations des contours et defonctionnelles à minimiser, les choix sont multiples et les résultats en dépendent.Ce travail de thèse présente une nouvelle approche de reconstruction simultanée àla segmentation des différents matériaux qui composent le volume. Le processus dereconstruction n’est plus basé sur une grille régulière de pixels (resp. voxels), mais sur unmaillage composé de triangles (resp. tétraèdres) non réguliers qui s’adaptent à la formede l’objet. Après une phase d’initialisation, la méthode se décompose en trois étapesprincipales que sont la reconstruction, la segmentation et l’adaptation du maillage, quialternent de façon itérative jusqu’à convergence. Des algorithmes itératifs de reconstructioncommunément utilisés avec une représentation conventionnelle de l’image ont étéadaptés et optimisés pour être exécutés sur des grilles irrégulières composées d’élémentstriangulaires ou tétraédriques. Pour l’étape de segmentation, deux méthodes basées surune approche paramétrique (snake) et l’autre sur une approche géométrique (level set)ont été mises en oeuvre afin de considérer des objets de différentes natures (mono- etmulti- matériaux). L’adaptation du maillage au contenu de l’image estimée est basée surles contours segmentés précédemment, pour affiner la maille au niveau des détails del’objet et la rendre plus grossière dans les zones contenant peu d’information. En finde processus, le résultat est une image classique de reconstruction tomographique enniveaux de gris, mais dont la représentation par un maillage adapté au contenu proposeidirectement une segmentation associée. Les résultats montrent que la partie adaptative dela méthode permet de représenter efficacement les objets et conduit à diminuer drastiquementla mémoire nécessaire au stockage. Dans ce contexte, une version 2D du calcul desopérateurs de reconstruction sur une architecture parallèle type GPU montre la faisabilitédu processus dans son ensemble. Une version optimisée des opérateurs 3D permet descalculs encore plus efficacesTomography reconstruction from projections data is an inverse problem widely used inthe medical imaging field. With sufficiently large number of projections over the requiredangle, the FBP (filtered backprojection) algorithms allow fast and accurate reconstructions.However in the cases of limited views (lose dose imaging) and/or limited angle (specificconstrains of the setup), the data available for inversion are not complete, the problembecomes more ill-conditioned, and the results show significant artifacts. In these situations,an alternative approach of reconstruction, based on a discrete model of the problem,consists in using an iterative algorithm or a statistical modelisation of the problem to computean estimate of the unknown object. These methods are classicaly based on a volumediscretization into a set of voxels and provide 3D maps of densities. Computation time andmemory storage are their main disadvantages. Moreover, whatever the application, thevolumes are segmented for a quantitative analysis. Numerous methods of segmentationwith different interpretations of the contours and various minimized energy functionalare offered, and the results can depend on their use.This thesis presents a novel approach of tomographic reconstruction simultaneouslyto segmentation of the different materials of the object. The process of reconstruction isno more based on a regular grid of pixels (resp. voxel) but on a mesh composed of nonregular triangles (resp. tetraedra) adapted to the shape of the studied object. After aninitialization step, the method runs into three main steps: reconstruction, segmentationand adaptation of the mesh, that iteratively alternate until convergence. Iterative algorithmsof reconstruction used in a conventionnal way have been adapted and optimizedto be performed on irregular grids of triangular or tetraedric elements. For segmentation,two methods, one based on a parametric approach (snake) and the other on a geometricapproach (level set) have been implemented to consider mono and multi materials objects.The adaptation of the mesh to the content of the estimated image is based on the previoussegmented contours that makes the mesh progressively coarse from the edges to thelimits of the domain of reconstruction. At the end of the process, the result is a classicaltomographic image in gray levels, but whose representation by an adaptive mesh toits content provide a correspoonding segmentation. The results show that the methodprovides reliable reconstruction and leads to drastically decrease the memory storage. Inthis context, the operators of projection have been implemented on parallel archituecturecalled GPU. A first 2D version shows the feasability of the full process, and an optimizedversion of the 3D operators provides more efficent compoutations
9
O'Connell, Jonathan F. « A dynamic programming model to solve optimisation problems using GPUs ». Thesis, Cardiff University, 2017. http://orca.cf.ac.uk/97930/.
Texte intégralRésumé :
This thesis presents a parallel, dynamic programming based model which is deployed on the GPU of a system to accelerate the solving of optimisation problems. This is achieved by simultaneously running GPU based computations, and memory transactions, allowing computation to never pause, and overcoming the memory constraints of solving large problem instances. Due to this some optimisation problems, which are currently not solved in an exact manner for real world sized instances due to their complexity, are moved into the solvable realm. The model is implemented to solve, a range of different test problems, where artificially constructed test data is used to ensure good performance even in the worst cases. Through this extensive testing, we can be confident the model will perform well when used to solve real world test cases. Testing of the model was carried out using a range of different implementation parameters in relation to deployment on the GPU, in order to identify both optimal implementation parameters, and how the model will operate when running on different systems. All problems, when implemented in parallel using the model, show run-time improvements compared to the sequential implementations, in some instances up to hundreds of times faster, but more importantly also show high efficiency metrics for the utilisation of GPU resources. Throughout testing emphasis has been placed on GPU based metrics to ensure the wider generic applicability of the model. Finally, the parallel model allows for new problems to be defined through the use of a simple file format, enabling wider usage of the model.
10
Pospíchal, Petr. « Akcelerace genetického algoritmu s využitím GPU ». Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2009. http://www.nusl.cz/ntk/nusl-236783.
Texte intégralRésumé :
This thesis represents master's thesis focused on acceleration of Genetic algorithms using GPU. First chapter deeply analyses Genetic algorithms and corresponding topics like population, chromosome, crossover, mutation and selection. Next part of the thesis shows GPU abilities for unified computing using both DirectX/OpenGL with Cg and specialized GPGPU libraries like CUDA. The fourth chapter focuses on design of GPU implementation using CUDA, coarse-grained and fine-grained GAs are discussed, and completed by sorting and random number generation task accelerated by GPU. Next chapter covers implementation details -- migration, crossover and selection schemes mapped on CUDA software model. All GA elements and quality of GPU results are described in the last chapter.
11
Avramidis, Eleftherios. « Optimisation and computational methods to model the oculomotor system with focus on nystagmus ». Thesis, University of Exeter, 2015. http://hdl.handle.net/10871/18291.
Texte intégralRésumé :
Infantile nystagmus is a condition that causes involuntary, bilateral and conjugate oscillations of the eyes, which are predominately restricted to the horizontal plane. In order to investigate the cause of nystagmus, computational models and nonlinear dynamics techniques have been used to model and analyse the oculomotor system. Computational models are important in making predictions and creating a quantitative framework for the analysis of the oculomotor system. Parameter estimation is a critical step in the construction and analysis of these models. A preliminary parameter estimation of a nonlinear dynamics model proposed by Broomhead et al. [1] has been shown to be able to simulate both normal rapid eye movements (i.e. saccades) and nystagmus oscillations. The application of nonlinear analysis to experimental jerk nystagmus recordings, has shown that the local dimensions number of the oscillation varies across the phase angle of the nystagmus cycle. It has been hypothesised that this is due to the impact of signal dependent noise (SDN) on the neural commands in the oculomotor system. The main aims of this study were: (i) to develop parameter estimation methods for the Broomhead et al. [1] model in order to explore its predictive capacity by fitting it to experimental recordings of nystagmus waveforms and saccades; (ii) to develop a stochastic oculomotor model and examine the hypothesis that noise on the neural commands could be the cause of the behavioural characteristics measured from experimental nystagmus time series using nonlinear analysis techniques. In this work, two parameter estimation methods were developed, one for fitting the model to the experimental nystagmus waveforms and one to saccades. By using the former method, we successfully fitted the model to experimental nystagmus waveforms. This fit allowed to find the specific parameter values that set the model to generate these waveforms. The types of the waveforms that we successfully fitted were asymmetric pseudo-cycloid, jerk and jerk with extended foveation. The fit of other types of nystagmus waveforms were not examined in this work. Moreover, the results showed which waveforms the model can generate almost perfectly and the waveform characteristics of a number of jerk waveforms which it cannot exactly generate. These characteristics were on a specific type of jerk nystagmus waveforms with a very extreme fast phase. The latter parameter estimation method allowed us to explore whether the model can generate horizontal saccades of different amplitudes with the same behaviour as observed experimentally. The results suggest that the model can generate the experimental saccadic velocity profiles of different saccadic amplitudes. However, the results show that best fittings of the model to the experimental data are when different model parameter values were used for different saccadic amplitude. Our parameter estimation methods are based on multi-objective genetic algorithms (MOGA), which have the advantage of optimising biological models with a multi-objective, high-dimensional and complex search space. However, the integration of these models, for a wide range of parameter combinations, is very computationally intensive for a single central processing unit (CPU). To overcome this obstacle, we accelerated the parameter estimation method by utilising the parallel capabilities of a graphics processing unit (GPU). Depending of the GPU model, this could provide a speedup of 30 compared to a midrange CPU. The stochastic model that we developed is based on the Broomhead et al. [1] model, with signal dependent noise (SDN) and constant noise (CN) added to the neural commands. We fitted the stochastic model to saccades and jerk nystagmus waveforms. It was found that SDN and CN can cause similar variability to the local dimensions number of the oscillation as found in the experimental jerk nystagmus waveforms and in the case of saccade generation the saccadic variability recorded experimentally. However, there are small differences in the simulated behaviour compared to the nystagmus experimental data. We hypothesise that these could be caused by the inability of the model to simulate exactly key jerk waveform characteristics. Moreover, the differences between the simulations and the experimental nystagmus waveforms indicate that the proposed model requires further expansion, and this could include other oculomotor subsystem(s).
12
Claustre, Jonathan. « Modèle particulaire 2D et 3D sur GPU pour plasma froid magnétisé : Application à un filtre magnétique ». Phd thesis, Université Paul Sabatier - Toulouse III, 2012. http://tel.archives-ouvertes.fr/tel-00796690.
Texte intégralRésumé :
La méthode PIC MCC (Particle-In-Cell Monte-Carlo Collision) est un outils très performant et efficace en ce qui concerne l'étude des plasmas (dans notre cas, pour des plasmas froids) car il permet de décrire l'évolution dans le temps et dans l'espace, des particules chargées sous l'effet des champs auto-consistants et des collisions. Dans un cas purement électrostatique, la méthode consiste à suivre les trajectoires d'un nombre représentatif de particules chargées, des électrons et des ions, dans l'espace des phases, et de décrire l'interaction collective de ces particules par la résolution de l'équation de Poisson. Dans le cas de plasmas froid, les trajectoires dans l'espace des phase sont déterminées par le champ électrique auto-consistant et par les collisions avec les atomes neutres ou les molécules et, pour des densités relativement importantes, par les collisions entre les particules chargées. Le coût des simulations pour ce type de méthode est très élevé en termes de ressources (CPU et mémoire). Ceci est dû aux fortes contraintes (dans les simulations PIC explicites) sur le pas de temps (plus petit qu'une fraction de la période plasma et inverse à la fréquence de giration électronique), sur le pas d'espace (de l'ordre de la longueur de Debye), et sur le nombre de particules par longueur de Debye dans la simulation (généralement de l'ordre de plusieurs dizaines). L'algorithme PIC MCC peut être parallélisé sur des fermes de calculs de CPU (le traitement de la trajectoires des particules est facilement parallélisable, mais la parallélisation de Poisson l'est beaucoup moins). L'émergence du GPGPU (General Purpose on Graphics Processing Unit) dans la recherche en informatique a ouvert la voie aux simulations massivement parallèle à faible coût et ceci par l'utilisation d'un très grand nombre de processeurs disponible sur les cartes graphiques permettant d'effectuer des opérations élémentaires (e.g. calcul de la trajectoires des particules) en parallèle. Un certain nombre d'outils numérique pour le calcul sur GPU ont été développés lors de ces 10 dernières années. De plus, le constructeur de cartes graphiques NVIDIA a développé un environnement de programmation appelé CUDA (Compute Unified Device Architecture) qui permet une parallélisation efficace des codes sur GPU. La simulation PIC avec l'utilisation des cartes graphiques ou de la combinaison des GPU et des CPU a été reporté par plusieurs auteurs, cependant les modèles PIC avec les collisions Monte-Carlo sur GPU sont encore en pleine étude. A l'heure actuelle, de ce que nous pouvons savoir, ce travail est le premier a montrer des résultats d'un code PIC MCC 2D et 3D entièrement parallélisé sur GPU et dans le cas de l'étude de plasma froid magnétisé. Dans les simulation PIC, il est relativement facile de suivre les particules lorsqu'il n'y a ni pertes ni création (e.g. limites périodiques ou pas d'ionisation) de particules au cours du temps. Cependant il devient nécessaire de réordonner les particules à chaque pas en temps dans le cas contraire (ionisation, recombinaison, absorption, etc). Cette Thèse met en lumière les stratégies qui peuvent être utilisées dans les modèles PIC MCC sur GPU permettant d'outre passer les difficultés rencontrées lors du réarrangement des particules après chaque pas de temps lors de la création et/ou des pertes. L'intérêt principal de ce travail est de proposer un algorithme implémenté sur GPU du modèle PIC MCC, de mesurer l'efficacité de celui-ci (parallélisation) et de le comparer avec les calculs effectués sur GPU et enfin d'illustrer les résultats de ce modèle par la simulation de plasma froid magnétisé. L'objectif est de présenter en détail le code utilisé en de montrer les contraintes et les avantages liées à la programmation de code PIC MCC sur GPU. La discussion est largement ciblé sur le cas en 2D, cependant un algorithme 3D a également été développé et testé comme il est montré à la fin de cette thèse.
13
Bachmann, Etienne. « Imagerie ultrasonore 2D et 3D sur GPU : application au temps réel et à l'inversion de forme d'onde complète ». Thesis, Toulouse 3, 2016. http://www.theses.fr/2016TOU30133/document.
Texte intégralRésumé :
Si les avancées majeures en imagerie ultrasonore ont longtemps été liées à la qualité de l'instrumentation, l'avènement de l'informatique a incontestablement changé la donne en introduisant des possibilités croissantes de traitement des données pour obtenir une meilleure image. Par ailleurs, les GPUs, composants principaux des cartes graphiques, offrent de par leur architecture des vitesses de calcul bien supérieures aux processeurs, y compris à des fins de calcul scientifique. Le but de cette thèse a été de tirer parti de ce nouvel outil de calcul, en ciblant deux applications complémentaires. La première est d'autoriser une imagerie en temps réel de meilleure qualité que les autres techniques d'imagerie échographique, en parallélisant le procédé d'imagerie FTIM (Fast Topological IMaging). La seconde est d'introduire l'imagerie quantitative et en particulier la reconstruction de la carte de vitesse du milieu inconnu, en utilisant l'inversion de la forme d'onde complèteIf the most important progresses in ultrasound imaging have been closely linked to the instrumentation's quality, the advent of computing science revolutionized this discipline by introducing growing possibilities in data processing to obtain a better picture. In addition, GPUs, which are the main components of the graphics cards deliver thanks to their architecture a significantly higher processing speed compared with processors, and also for scientific calculation purpose. The goal of this work is to take the best benefit of this new computing tool, by aiming two complementary applications. The first one is to enable real-time imaging with a better quality than other sonographic imaging techniques, thanks to the parallelization of the FTIM (Fast Tpological IMaging) imaging process. The second one is to introduce quantitative imaging and more particularly reconstructing the wavespeed map of an unknown medium, using Full Waveform Inversion
14
GASPARETTO, THOMAS. « Development of a computing farm for Cloud computing on GPU - Development and optimisation of data-analysis methodologies for the Cherenkov Telescope Array ». Doctoral thesis, Università degli Studi di Trieste, 2020. http://hdl.handle.net/11368/2963769.
Texte intégralRésumé :
L'attività di ricerca si è concentrata sulla creazione di pipeline di simulazione e analisi da utilizzare a diversi livelli nel contesto del Cherenkov Telescope Array.
Il lavoro si compone di due parti principali: la prima è dedicata alla ricostruzione degli eventi provenienti dalle simulazioni di Montecarlo utilizzando la libreria ctapipe, mentre una seconda parte è dedicata alla stima delle future performance di CTA nell'osservazione di fenomeni violenti come quelli che generano i Gamma Ray Bursts e le Onde Gravitazionali. La ricostruzione a basso livello dei dati grezzi è stata effettuata con una pipeline che utilizza l'analisi ImPACT, una tecnica basata su template con modelli derivati dalle simulazioni Montecarlo; ImPACT è stato utilizzato sia per ottenere grafici a risoluzione angolare ed energetica, ma anche completamente profilato per trovare i suoi colli di bottiglia, debuggato e accelerato. Il codice è stato usato per analizzare i dati provenienti dai diversi layout dei telescopi e rifatto per analizzare i dati per il prototipo del telescopio LST-1, lavorando in "modalità mono" invece della modalità stereo standard. L'analisi è stata reimplementata per provare in modo massiccio tutti i template sulla GPU in un unico passaggio. L'implementazione è stata fatta usando la libreria PyTorch, sviluppata per il Deep Learning.
È stata studiata la stima delle prestazioni dei telescopi nella cosiddetta "modalità di puntamento divergente": in questo scenario i telescopi hanno una direzione di puntamento leggermente diversa rispetto alla configurazione in parallelo, in modo che il campo visivo finale di tutto il sistema sia più ampio rispetto al puntamento in parallelo. Il codice di ricostruzione in ctapipe è stato adattato a questa particolare modalità di osservazione. La creazione di un visualizzatore 3D, realizzata con VTK, ha aiutato a comprendere il codice e a correggerlo di conseguenza.
Il modello di cielo extragalattico per il First CTA Data Challenge è stato creato selezionando fonti da diversi cataloghi. L'obiettivo del DC-1 era quello di consentire ai gruppi di lavoro scientifici del CTA Consortium Science Working Groups di derivare dei benchmark scientifici per i Key Science Projects del CTA e di coinvolgere più persone nelle analisi.
Al fine di effettuare le simulazioni e le analisi per i lavori del GRB e del GW Consortium, è stata creata una pipeline attorno alla libreria ctools: questa è composta da due parti gestite da file di configurazione, che si occupano sia del compito specifico da svolgere (simulazione in background, creazione del modello e la parte di simulazione che esegue il rilevamento e la stima del significato) sia della sottomissione dei job.
La ricerca è stata effettuata per 14 mesi (di cui 5 mesi coperti da una borsa di studio supplementare dell'Ambasciata francese) presso il "Laboratorie d'Annecy de Physique de Particules" (LAPP) di Annecy (Francia) nell'ambito di un programma di cotutela basato sul periodo di ricerca obbligatorio da trascorrere all'estero previsto dalla borsa di studio, finanziato dal Fondo Sociale Europeo.The research activity was focused on the creation of simulation and analysis pipelines to be used at different levels in the context of the Cherenkov Telescope Array. The work consists of two main parts: the first one is dedicated to the reconstruction of the events coming from the Monte Carlo simulations using the ctapipe library, whereas a second part is devoted to the estimation of the future performances of CTA in the observation of violent phenomena such as those generating Gamma Ray Bursts and Gravitational Waves. The low-level reconstruction of the raw data was done with a pipeline which uses the ImPACT analysis, a template-based technique with templates derived from Monte Carlo simulations; ImPACT was both used to obtain angular and energy resolution plots, but also fully profiled to find its bottlenecks, debugged and sped up. The code was used to analyse data from different telescopes’ layouts and refactored to analyse data for the prototype of the LST-1 telescope, working in “mono mode” instead of the standard stereo mode. The analysis was re-implemented in order to try massively all the templates on the GPU in one single step. The implementation is done using the PyTorch library, developed for Deep Learning. The estimation of the performances of the telescopes in the so-called “divergent pointing mode” was investigated: in this scenario the telescopes have a slightly different pointing direction with respect to the parallel configuration, so that the final hyper field-of-view of all the system is larger with respect to the parallel pointing. The reconstruction code in ctapipe was adapted to this particular observation mode. The creation of a 3D displayer, done using VTK, helped in understanding the code and in fixing it accordingly. The extragalactic sky model for the First CTA Data Challenge was created selecting sources from different catalogues. The goal of the DC-1 was to enable the CTA Consortium Science Working Groups to derive science benchmarks for the CTA Key Science Projects and get more people involved in the analyses. In order to do the simulations and analysis for the GRB and GW Consortium papers, a pipeline was created around the ctools library: this is made by two parts handled by configuration files, which take care both of the specific task to do (background simulation, model creation and the simulation part which performs the detection and estimate the significance) and the jobs submission. The research was done for 14 months (with 5 months covered by an additional scholarship from the French Ambassy) at the “Laboratorie d’Annecy de Physique de Particules” (LAPP) in Annecy (France) under a joint-supervision program based on the mandatory research period to spend abroad foreseen in the scholarship, funded from the European Social Fund.
15
Tanner, Michael. « BOR2G : Building Optimal Regularised Reconstructions with GPUs (in cubes) ». Thesis, University of Oxford, 2017. https://ora.ox.ac.uk/objects/uuid:1928c996-d913-4d7e-8ca5-cf247f90aa0f.
Texte intégralRésumé :
Robots require high-quality maps - internal representations of their operating workspace - to localise, path plan, and perceive their environment. Until recently, these maps were restricted to sparse, 2D representations due to computational, memory, and sensor limitations. With the widespread adoption of high-quality sensors and graphics processors for parallel processing, these restrictions no longer apply: dense 3D maps are feasible to compute in real time (i.e., at the input sensor's frame rate). This thesis presents the theory and system to create large-scale dense 3D maps (i.e., reconstruct continuous surface models) using only sensors found on modern autonomous automobiles: 2D laser, 3D laser, and cameras. In contrast to active RGB-D cameras, passive cameras produce noisy surface observations and must be regularised in both 2D and 3D to create accurate reconstructions. Unfortunately, straight-forward application of 3D regularisation causes undesired surface interpolation and extrapolation in regions unexplored by the robot. We propose a method to overcome this challenge by informing the regulariser of the specific subsets of 3D surfaces upon which to operate. When combined with a compressed voxel grid data structure, we demonstrate our system fusing data from both laser and camera sensors to reconstruct 7.3 km of urban environments. We evaluate the quantitative performance of our proposed method through the use of synthetic and real-world datasets - including datasets from Stanford's Burghers of Calais, University of Oxford's RobotCar, University of Oxford's Dense Reconstruction, and Karlsruhe Institute of Technology's KITTI - compared to ground-truth laser data. With only stereo camera inputs, our regulariser reduces the 3D reconstruction metric error between 27% to 36% with a final median accuracy ranging between 4 cm to 8 cm. Furthermore, by augmenting our system with object detection, we remove ephemeral objects (e.g., automobiles, bicycles, and pedestrians) from the input sensor data and target our regulariser to interpolate the occluded urban surfaces. Augmented with Kernel Conditional Density Estimation, our regulariser creates reconstructions with median errors between 5.64 cm and 9.24 cm. Finally, we present a machine-learning pipeline that learns, in an automatic fashion, to recognise the errors in dense reconstructions. Our system trains on image and laser data from a 3.8 km urban sequence. Using a separate 2.2 km urban sequence, our pipeline consistently identifies error-prone regions in the image-based dense reconstruction.
16
Chernoglazov, Alexander Igorevich. « Improving Visualisation of Large Multi-Variate Datasets : New Hardware-Based Compression Algorithms and Rendering Techniques ». Thesis, University of Canterbury. Computer Science and Software Engineering, 2012. http://hdl.handle.net/10092/7004.
Texte intégralRésumé :
Spectral computed tomography (CT) is a novel medical imaging technique that involves simultaneously counting photons at several energy levels of the x-ray spectrum to obtain a single multi-variate dataset. Visualisation of such data poses significant challenges due its extremely large size and the need for interactive performance for scientific and medical end-users. This thesis explores the properties of spectral CT datasets and presents two algorithms for GPU-accelerated real-time rendering from compressed spectral CT data formats. In addition, we describe an optimised implementation of a volume raycasting algorithm on modern GPU hardware, tailored to the visualisation of spectral CT data.
17
Beaugnon, Ulysse. « Efficient code generation for hardware accelerators by refining partially specified implementation ». Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLEE050.
Texte intégralRésumé :
Les compilateurs cherchant à améliorer l’efficacité des programmes doivent déterminer quelles optimisations seront les plus bénéfiques. Ce problème est complexe, surtout lors des premières étapes de la compilation où chaque décision influence les choix disponibles aux étapes suivantes. Nous proposons de représenter la compilation comme le raffinement progressif d’une implémentation partiellement spécifiée. Les décisions possibles sont toutes connues dès le départ et commutent. Cela permet de prendre les décisions les plus importantes en premier et de construire un modèle de performance capable d'anticiper les potentielles optimisations. Nous appliquons cette approche pour générer du code d'algèbre linéaire ciblant des GPU et obtenons des performances comparables aux bibliothèques optimisées à la mainCompilers looking for an efficient implementation of a function must find which optimizations are the most beneficial. This is a complex problem, especially in the early steps of the compilation process. Each decision may impact the transformations available in subsequent steps. We propose to represent the compilation process as the progressive refinement of a partially specified implementation. All potential decisions are exposed upfront and commute. This allows for making the most discriminative decisions first and for building a performance model aware of which optimizations may be applied in subsequent steps. We apply this approach to the generation of efficient GPU code for linear algebra and yield performance competitive with hand-tuned libraries
18
He, Guanlin. « Parallel algorithms for clustering large datasets on CPU-GPU heterogeneous architectures ». Electronic Thesis or Diss., université Paris-Saclay, 2022. http://www.theses.fr/2022UPASG062.
Texte intégralRésumé :
Clustering, qui consiste à réaliser des groupements naturels de données, est une tâche fondamentale et difficile dans l'apprentissage automatique et l'exploration de données. De nombreuses méthodes de clustering ont été proposées dans le passé, parmi lesquelles le clustering en k-moyennes qui est une méthode couramment utilisée en raison de sa simplicité et de sa rapidité.Le clustering spectral est une approche plus récente qui permet généralement d'obtenir une meilleure qualité de clustering que les k-moyennes. Cependant, les algorithmes classiques de clustering spectral souffrent d'un manque de passage à l'échelle en raison de leurs grandes complexités en nombre d'opérations et en espace mémoire nécessaires. Ce problème de passage à l'échelle peut être traité en appliquant des méthodes d'approximation ou en utilisant le calcul parallèle et distribué.L'objectif de cette thèse est d'accélérer le clustering spectral et de le rendre applicable à de grands ensembles de données en combinant l'approximation basée sur des données représentatives avec le calcul parallèle sur processeurs CPU et GPU. En considérant différents scénarios, nous proposons plusieurs chaînes de traitement parallèle pour le clustering spectral à grande échelle. Nous concevons des algorithmes et des implémentations parallèles optimisés pour les modules de chaque chaîne proposée : un algorithme parallèle des k-moyennes sur CPU et GPU, un clustering spectral parallèle sur GPU avec un format de stockage creux, un filtrage parallèle sur GPU du bruit dans les données, etc. Nos expériences variées atteignent de grandes performances et valident le passage à l'échelle de chaque module et de nos chaînes complètesClustering, which aims at achieving natural groupings of data, is a fundamental and challenging task in machine learning and data mining. Numerous clustering methods have been proposed in the past, among which k-means is one of the most famous and commonly used methods due to its simplicity and efficiency.Spectral clustering is a more recent approach that usually achieves higher clustering quality than k-means. However, classical algorithms of spectral clustering suffer from a lack of scalability due to their high complexities in terms of number of operations and memory space requirements. This scalability challenge can be addressed by applying approximation methods or by employing parallel and distributed computing.The objective of this thesis is to accelerate spectral clustering and make it scalable to large datasets by combining representatives-based approximation with parallel computing on CPU-GPU platforms. Considering different scenarios, we propose several parallel processing chains for large-scale spectral clustering. We design optimized parallel algorithms and implementations for each module of the proposed chains: parallel k-means on CPU and GPU, parallel spectral clustering on GPU using sparse storage format, parallel filtering of data noise on GPU, etc. Our various experiments reach high performance and validate the scalability of each module and the complete chains
19
Mokos, Athanasios Dorotheos. « Multi-phase modelling of violent hydrodynamics using Smoothed Particle Hydrodynamics (SPH) on Graphics Processing Units (GPUs) ». Thesis, University of Manchester, 2014. https://www.research.manchester.ac.uk/portal/en/theses/multiphase-modelling-of-violent-hydrodynamics-using-smoothed-particle-hydrodynamics-sph-on-graphics-processing-units-gpus(a82b8187-f81a-400b-8bd2-9a74c502a953).html.
Texte intégralRésumé :
This thesis investigates violent air-water flows in two and three dimensions using a smoothed particle hydrodynamics (SPH) model accelerated using the parallel architecture of graphics processing units (GPUs). SPH is a meshless Lagrangian technique for CFD simulations, whose major advantage for multi-phase flows is that the highly nonlinear behaviour of the motion of the interface can be implicitly captured with a sharp interface. However, prior to this thesis performing multi-phase simulations of large scale air-water flows has been prohibitive due to the inherent high computational cost. The open source code DualSPHysics, a hybrid central processing unit (CPU) and GPU code, is heavily modified in order to be able to handle flows with multiple fluids by implementing a weakly compressible multi-phase model that is simple to implement on GPUs. The computational runtime shows a clear improvement over a conventional serial code for both two- and three dimensional cases enabling simulations with millions of particles. An investigation into different GPU algorithms focuses on optimising the multi-phase SPH implementation for the first time, leading to speedups of up to two orders of magnitude compared to a CPU-only simulation. Detailed comparison of different GPU algorithms reveals a further 12% improvement on the computational runtime. Enabling the modelling of cases with millions of fluid particles demonstrates some previously unreported problems regarding the simulation of the air phase. A new particle shifting algorithm has been proposed for multi-phase flows enabling the air, initially simulated as a highly compressible liquid, to expand rapidly as a gas and prevent the formation of unphysical voids. The new shifting algorithm is validated using dam break flows over a dry bed where good agreement is obtained with experimental data and reference solutions published in the literature. An improvement over a corresponding single-phase SPH simulation is also shown. Results for dam break flows over a wet bed are shown for different resolutions performing simulations that were unfeasible prior to the GPU multi-phase SPH code. Good agreement with the experimental results and a clear improvement over the single-phase model are obtained with the higher resolution showing closer agreement with the experimental results. Sloshing inside a rolling tank was also examined and was found to be heavily dependent on the viscosity model and the speed of sound of the phases. A sensitivity analysis was performed for a range of different values comparing the results to experimental data with the emphasis on the pressure impact on the wall. Finally, a 3-D gravity-driven flow where water is impacting an obstacle was studied comparing results with published experimental data. The height of the water at different points in the domain and the pressure on the side of the obstacle are compared to a state-of-the-art single-phase GPU SPH simulation. The results obtained were generally in good agreement with the experiment with closer results obtained for higher resolutions and showing an improvement on the single-phase model.
20
Monnier, Nicolas. « ExaSKA : Parallelization on a High Performance Computing server for the exascale radiotelescope SKA ». Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG036.
Texte intégralRésumé :
Les radio interféromètres simulent un grand télescope via un réseau d'antennes. L'imagerie reconstruit une image du ciel observé via les signaux reçus par les antennes, qui sont dans le domaine spatial, mais dont les données, les visibilités, sont situées dans le domaine de Fourier. Ce problème de reconstruction est "mal-posé" car les mesures ne couvrent pas l'entièreté du plan de Fourier et sont corrompues par les effets de la propagation des signaux dans l'atmosphère terrestre.Les algorithmes itératifs utilisent de l'information a priori sur le ciel pour la reconstruction, mais nécessitent une interpolation des visibilités sur une grille uniforme pour utiliser des algorithmes de transformée de Fourier rapide. Dans le modèle "backward", l'interpolation, appelée gridding, étale les visibilités sur une grille uniforme en utilisant un noyau de convolution. Dans le modèle "forward", l'interpolation, appelée degridding, est l'opération adjointe qui regroupe l'information sur une zone centrée sur la position de la visibilité.Le traitement et la conservation des visibilités sont très coûteux en raison du débit de données extrêmement important généré par les radiotélescopes, en particulier avec la nouvelle génération d'interféromètres. La reconstruction d'image est un défi majeur en raison du coût calculatoire élevé des opérateurs d'interpolation, le gridding et degridding, et des algorithmes de reconstruction qui sont un goulot d'étranglement.Cette thèse se concentre sur la réduction du temps de calcul des méthodes d'imagerie en se concentrant sur deux aspects: l'aspect algorithmique et l'implémentation hardware avec une parallélisation à grain fin et à gros grain. Une méthode de réduction du coût calculatoire des opérateurs de gridding et degridding est présentée en les fusionnant en un opérateur unique, nommé Grid to Grid (G2G), qui s'appuie sur la succession des deux opérateurs ainsi que sur l'approximation des coordonnées des visibilités sur la grille de Fourier. Les implémentations CPU et GPU de cette méthode montrent que G2G réduit considérablement le coût calculatoire et l'empreinte mémoire sans pénaliser la qualité de la reconstruction. Le facteur de suréchantillonnage sert d'équilibre entre la réduction du coût calculatoire et la précision de l'interpolation.Une distribution multi-coeur multi-node sur serveur HPC du framework d'imagerie DDFacet est également présentée. La parallélisation est divisée en plusieurs niveaux: une parallélisation multi-cœur pour systèmes à mémoire partagée basée sur l'indépendance des calculs entre les facettes, et une parallélisation multi-nœud pour système à mémoire distribuée basée sur l'indépendance des calculs du gridding et degridding entre les différentes fréquences d'observation. Cette double parallélisation réduit considérablement le temps d'exécution et l'accélération n'est pas linéaire, permettant de choisir un optimum entre l'accélération et les ressources de calculs utiliséesRadio interferometers simulate a large telescope via a network of antennas. Imaging reconstructs an image of the observed sky using signals received by the antennas, which are in the spatial domain but whose data and visibilities are located in the Fourier domain. This reconstruction problem is "ill-posed" because the measurements do not cover the entire Fourier plane and are corrupted by the effects of signal propagation in the Earth's atmosphere.Iterative algorithms use a priori information about the sky for reconstruction but require interpolation of visibilities onto a uniform grid to use fast Fourier transform algorithms. In the "backward" model, interpolation, called gridding, spreads visibilities onto a uniform grid using a convolution kernel. In the "forward" model, interpolation, called degridding, is the adjoint operation that gathers information on an area centered on the visibility position.The processing and storage of visibilities are computationally expensive due to the extremely large data rates generated by radio telescopes, especially with the new generation of interferometers. Image reconstruction is a major challenge due to the high computational cost of interpolation operators, gridding and degridding, and reconstruction algorithms that are a bottleneck.This thesis focuses on reducing the computation time of imaging methods by focusing on two aspects: the algorithmic aspect and the hardware implementation with fine-grained and coarse-grained parallelization. A method for reducing the computational cost of gridding and degridding operators is presented by merging them into a single operator, named Grid to Grid (G2G), which relies on the succession of the two operators as well as the approximation of the visibility coordinates on the Fourier grid. CPU and GPU implementations of this method show that G2G significantly reduces the computational cost and memory footprint without penalizing reconstruction quality. The oversampling factor serves as a balance between reducing computational cost and interpolation accuracy.A multi-core multi-node distribution on an HPC server of the DDFacet imaging framework is also presented. Parallelization is divided into several levels: multi-core parallelization for shared-memory systems based on the independence of calculations between facets and multi-node parallelization for distributed-memory systems based on the independence of gridding and degridding calculations between different observation frequencies. These two levels of parallelization significantly reduce execution time, and acceleration is not linear, allowing for an optimum choice between acceleration and computational resources used
21
Zhang, Naiyu. « Cellular GPU Models to Euclidean Optimization Problems : Applications from Stereo Matching to Structured Adaptive Meshing and Traveling Salesman Problem ». Thesis, Belfort-Montbéliard, 2013. http://www.theses.fr/2013BELF0215/document.
Texte intégralRésumé :
Le travail présenté dans ce mémoire étudie et propose des modèles de calcul parallèles de type cellulaire pour traiter différents problèmes d’optimisation NP-durs définis dans l’espace euclidien, et leur implantation sur des processeurs graphiques multi-fonction (Graphics Processing Unit; GPU). Le but est de pouvoir traiter des problèmes de grande taille tout en permettant des facteurs d’accélération substantiels à l’aide du parallélisme massif. Les champs d’application visés concernent les systèmes embarqués pour la stéréovision de même que les problèmes de transports définis dans le plan, tels que les problèmes de tournées de véhicules. La principale caractéristique du modèle cellulaire est qu’il est fondé sur une décomposition du plan en un nombre approprié de cellules, chacune comportant une part constante de la donnée, et chacune correspondant à une unité de calcul (processus). Ainsi, le nombre de processus parallèles et la taille mémoire nécessaire sont en relation linéaire avec la taille du problème d’optimisation, ce qui permet de traiter des instances de très grandes tailles.L’efficacité des modèles cellulaires proposés a été testée sur plateforme parallèle GPU sur quatre applications. La première application est un problème d’appariement d’images stéréo. Elle concerne la stéréovision couleur. L’entrée du problème est une paire d’images stéréo, et la sortie une carte de disparités représentant les profondeurs dans la scène 3D. Le but est de comparer des méthodes d’appariement local selon l’approche winner-takes-all et appliquées à des paires d’images CFA (color filter array). La deuxième application concerne la recherche d’améliorations de l’implantation GPU permettant de réaliser un calcul quasi temps-réel de l’appariement. Les troisième et quatrième applications ont trait à l’implantation cellulaire GPU des réseaux neuronaux de type carte auto-organisatrice dans le plan. La troisième application concerne la génération de maillages structurés appliquée aux cartes de disparité afin de produire des représentations compressées des surfaces 3D. Enfin, la quatrième application concerne le traitement d’instances de grandes tailles du problème du voyageur de commerce euclidien comportant jusqu’à 33708 villes.Pour chacune des applications, les implantations GPU permettent une accélération substantielle du calcul par rapport aux versions CPU, pour des tailles croissantes des problèmes et pour une qualité de résultat obtenue similaire ou supérieure. Le facteur d’accélération GPU par rapport à la version CPU est d’environ 20 fois plus vite pour la version GPU sur le traitement des images CFA, cependant que le temps de traitement GPU est d’environ de 0,2s pour une paire d’images de petites tailles de la base Middlebury. L’algorithme amélioré quasi temps-réel nécessite environ 0,017s pour traiter une paire d’images de petites tailles, ce qui correspond aux temps d’exécution parmi les plus rapides de la base Middlebury pour une qualité de résultat modérée. La génération de maillages structurés est évaluée sur la base Middlebury afin de déterminer les facteurs d’accélération et qualité de résultats obtenus. Le facteur d’accélération obtenu pour l’implantation parallèle des cartes auto-organisatrices appliquée au problème du voyageur de commerce et pour l’instance avec 33708 villes est de 30 pour la version parallèleThe work presented in this PhD studies and proposes cellular computation parallel models able to address different types of NP-hard optimization problems defined in the Euclidean space, and their implementation on the Graphics Processing Unit (GPU) platform. The goal is to allow both dealing with large size problems and provide substantial acceleration factors by massive parallelism. The field of applications concerns vehicle embedded systems for stereovision as well as transportation problems in the plane, as vehicle routing problems. The main characteristic of the cellular model is that it decomposes the plane into an appropriate number of cellular units, each responsible of a constant part of the input data, and such that each cell corresponds to a single processing unit. Hence, the number of processing units and required memory are with linear increasing relationship to the optimization problem size, which makes the model able to deal with very large size problems.The effectiveness of the proposed cellular models has been tested on the GPU parallel platform on four applications. The first application is a stereo-matching problem. It concerns color stereovision. The problem input is a stereo image pair, and the output a disparity map that represents depths in the 3D scene. The goal is to implement and compare GPU/CPU winner-takes-all local dense stereo-matching methods dealing with CFA (color filter array) image pairs. The second application focuses on the possible GPU improvements able to reach near real-time stereo-matching computation. The third and fourth applications deal with a cellular GPU implementation of the self-organizing map neural network in the plane. The third application concerns structured mesh generation according to the disparity map to allow 3D surface compressed representation. Then, the fourth application is to address large size Euclidean traveling salesman problems (TSP) with up to 33708 cities.In all applications, GPU implementations allow substantial acceleration factors over CPU versions, as the problem size increases and for similar or higher quality results. The GPU speedup factor over CPU was of 20 times faster for the CFA image pairs, but GPU computation time is about 0.2s for a small image pair from Middlebury database. The near real-time stereovision algorithm takes about 0.017s for a small image pair, which is one of the fastest records in the Middlebury benchmark with moderate quality. The structured mesh generation is evaluated on Middlebury data set to gauge the GPU acceleration factor and quality obtained. The acceleration factor for the GPU parallel self-organizing map over the CPU version, on the largest TSP problem with 33708 cities, is of 30 times faster
22
Cui, Beibei. « Image processing applications in object detection and graph matching : from Matlab development to GPU framework ». Thesis, Bourgogne Franche-Comté, 2020. http://www.theses.fr/2020UBFCA002.
Texte intégralRésumé :
Déterminer des mises en correspondance d’objet, ou de caractéristiques d’objet, dans des images présente un grand intérêt pour beaucoup d’applications telles que la détection et le suivi de cible, l’estimation du flot optique, l’identification, et d’autres tâches dérivées. Dans cette thèse, nous abordons le problème de mise en correspondance dans le cadre général de l’optimisation de l’appariement de graphe, dans le but de contribuer, comme résultat final, au développement de nouveaux algorithmes parallèles implémentés sur plateforme GPU (Graphics Processing Unit). Le problème d’appariement de graphe peut être décliné de diverses manières suivant l’application considérée. Nous observons un fossé entre les applications basées sur des fonctions de coût locales et les applications avec des fonctions de coût d’ordre supérieur, évaluant la similarité entre les arêtes du graphe, ou les hyperliens lorsqu’il s’agit d’un hypergraphe. La première classe d’applications comporte des algorithmes de résolution basés sur des calculs de convolution et possède déjà des implémentations parallèles sur GPU. La deuxième classe d’applications met l’accent sur les relations géométriques entre caractéristiques extraites de l’image, transformant le problème de mise en correspondance en un programme quadratique en nombre entiers avec contraintes, pour lequel nous n’avons pas trouvé de solution GPU accessible actuellement.Deux types d’approche ont été adoptées pour contribuer à la problématique d’appariement de graphe sur GPU. Premièrement, nous étudions différentes déclinaisons de cette problématique via l’utilisation de la plateforme Matlab afin de pouvoir réutiliser et fournir des solutions représentatives de l’état de l’art, ainsi que des protocoles d’expérimentation et des données d’entrée nécessaires pour une plateforme GPU dédiée à l’évaluation et la comparaison avec les algorithmes séquentiels sur Matlab. Ainsi, une première partie du travail concerne trois contributions respectivement, aux techniques de soustraction d’arrière-plan et de différence d’image pour la détection, au problème d’extraction de caractéristiques pour la mise en correspondance, et au problème général d’appariement de graphe, toutes basées sur la combinaison de méthodes issues de l’environnement Matlab. Deuxièmement, nous proposons une infrastructure logicielle GPU nouvelle, écrite en CUDA C++, spécifiquement adaptée au problème d’appariement de graphe géométrique, proposant de nouveaux algorithmes parallèles de complexité calculatoire plus réduite, tels que les cartes auto-organisatrices dans le plan, des algorithmes de cluster qui en sont dérivés, et des recherches locales distribuées. Ces algorithmes parallèles sont évalués et comparés aux approches de l’état de l’art pour le problème d’appariement de graphe, en suivant un protocole d’expérimentation identique. Cette plateforme GPU constitue notre principale proposition pour contribuer à combler le fossé entre développement GPU et son application au problème général d’appariement de grapheAutomatically finding correspondences between object features in images is of main interest for several applications, as object detection and tracking, flow velocity estimation, identification, registration, and many derived tasks. In this thesis, we address feature correspondence within the general framework of graph matching optimization and with the principal aim to contribute, at a final step, to the design of new and parallel algorithms and their implementation on GPU (Graphics Processing Unit) systems. Graph matching problems can have many declinations, depending on the assumptions of the application at hand. We observed a gap between applications based on local cost objective functions, and those applications with higher-order cost functions, that evaluate similarity between edges of the graphs, or hyperedges when considering hypergraphs. The former class provides convolution-based algorithms already having parallel GPU implementations. Whereas, the latter class puts the emphasis on geometric inter-feature relationships, transforming the correspondence problem to a purely geometric problem stated in a high dimensional space, generally modeled as an integer quadratic programming, for which we did not find GPU implementations available yet.Two complementary approaches were adopted in order to contribute to addressing higher-order geometric graph matching on GPU. Firstly, we study different declinations of feature correspondence problems by the use of the Matlab platform, in order to reuse and provide state-of-the-art solution methods, as well as experimental protocols and input data necessary for a GPU platform with evaluation and comparison tools against existing sequential algorithms, most of the time developed in Matlab framework. Then, the first part of this work concerns three contributions, respectively, to background and frame difference application, to feature extraction problem from images for local correspondences, and to the general graph matching problem, all based on the combination of methods derived from Matlab environment. Secondly, and based on the results of Matlab developments, we propose a new GPU framework written in CUDA C++ specifically dedicated to geometric graph matching but providing new parallel algorithms, with lower computational complexity, as the self-organizing map in the plane, derived parallel clustering algorithms, and distributed local search method. These parallel algorithms are then evaluated and compared to the state-of-the-art methods available for graph matching and following the same experimental protocol. This GPU platform constitutes our final and main proposal to contribute to bridging the gap between GPU development and higher-order graph matching
23
Codol, Jean-Marie. « Hybridation GPS/Vision monoculaire pour la navigation autonome d'un robot en milieu extérieur ». Thesis, Toulouse, INSA, 2012. http://www.theses.fr/2012ISAT0060/document.
Texte intégralRésumé :
On assiste aujourd'hui à l'importation des NTIC (Nouvelles Technologies de l'Information et de la Télécommunication) dans la robotique. L'union de ces technologies donnera naissance, dans les années à venir, à la robotique de service grand-public.Cet avenir, s'il se réalise, sera le fruit d'un travail de recherche, amont, dans de nombreux domaines : la mécatronique, les télécommunications, l'automatique, le traitement du signal et des images, l'intelligence artificielle ... Un des aspects particulièrement intéressant en robotique mobile est alors le problème de la localisation et de la cartographie simultanée. En effet, dans de nombreux cas, un robot mobile, pour accéder à une intelligence, doit nécessairement se localiser dans son environnement. La question est alors : quelle précision pouvons-nous espérer en terme de localisation? Et à quel coût?Dans ce contexte, un des objectifs de tous les laboratoires de recherche en robotique, objectif dont les résultats sont particulièrement attendus dans les milieux industriels, est un positionnement et une cartographie de l'environnement, qui soient à la fois précis, tous-lieux, intègre, bas-coût et temps-réel. Les capteurs de prédilection sont les capteurs peu onéreux tels qu'un GPS standard (de précision métrique), et un ensemble de capteurs embarquables en charge utile (comme les caméras-vidéo). Ce type de capteurs constituera donc notre support privilégié, dans notre travail de recherche. Dans cette thèse, nous aborderons le problème de la localisation d'un robot mobile, et nous choisirons de traiter notre problème par l'approche probabiliste. La démarche est la suivante, nous définissons nos 'variables d'intérêt' : un ensemble de variables aléatoires. Nous décrivons ensuite leurs lois de distribution, et leur modèles d'évolution, enfin nous déterminons une fonction de coût, de manière à construire un observateur (une classe d'algorithme dont l'objectif est de déterminer le minimum de notre fonction de coût). Notre contribution consistera en l'utilisation de mesures GPS brutes GPS (les mesures brutes - ou raw-datas - sont les mesures issues des boucles de corrélation de code et de phase, respectivement appelées mesures de pseudo-distances de code et de phase) pour une navigation bas-coût précise en milieu extérieur suburbain. En utilisant la propriété dite 'entière' des ambiguïtés de phase GPS, nous étendrons notre navigation pour réaliser un système GPS-RTK (Real Time Kinematic) en mode différentiel local précise et bas-coût. Nos propositions sont validées par des expérimentations réalisées sur notre démonstrateur robotiqueWe are witnessing nowadays the importation of ICT (Information and Communications Technology) in robotics. These technologies will give birth, in upcoming years, to the general public service robotics. This future, if realised, shall be the result of many research conducted in several domains: mechatronics, telecommunications, automatics, signal and image processing, artificial intelligence ... One particularly interesting aspect in mobile robotics is hence the simultaneous localisation and mapping problem. Consequently, to access certain informations, a mobile robot has, in many cases, to map/localise itself inside its environment. The following question is then posed: What precision can we aim for in terms of localisation? And at what cost?In this context, one of the objectives of many laboratories indulged in robotics research, and where results impact directly the industry, is the positioning and mapping of the environment. These latter tasks should be precise, adapted everywhere, integrated, low-cost and real-time. The prediction sensors are inexpensive ones, such as a standard GPS (of metric precision), and a set of embeddable payload sensors (e.g. video cameras). These type of sensors constitute the main support in our work.In this thesis, we shed light on the localisation problem of a mobile robot, which we choose to handle with a probabilistic approach. The procedure is as follows: we first define our "variables of interest" which are a set of random variables, and then we describe their distribution laws and their evolution models. Afterwards, we determine a cost function in such a manner to build up an observer (an algorithmic class where the objective is to minimize the cost function).Our contribution consists of using brute GPS measures (brute measures or raw datas are measures issued from code and phase correlation loops, called pseudo-distance measures of code and phase, respectively) for a low-cost navigation, which is precise in an external suburban environment. By implementing the so-called "whole" property of GPS phase ambiguities, we expand the navigation to achieve a GPS-RTK (Real-Time Kinematic) system in a precise and low-cost local differential mode.Our propositions has been validated through experimentations realized on our robotic demonstrator
24
Mantell, Rosemary Genevieve. « Accelerated sampling of energy landscapes ». Thesis, University of Cambridge, 2017. https://www.repository.cam.ac.uk/handle/1810/267990.
Texte intégralRésumé :
In this project, various computational energy landscape methods were accelerated using graphics processing units (GPUs). Basin-hopping global optimisation was treated using a version of the limited-memory BFGS algorithm adapted for CUDA, in combination with GPU-acceleration of the potential calculation. The Lennard-Jones potential was implemented using CUDA, and an interface to the GPU-accelerated AMBER potential was constructed. These results were then extended to form the basis of a GPU-accelerated version of hybrid eigenvector-following. The doubly-nudged elastic band method was also accelerated using an interface to the potential calculation on GPU. Additionally, a local rigid body framework was adapted for GPU hardware. Tests were performed for eight biomolecules represented using the AMBER potential, ranging in size from 81 to 22\,811 atoms, and the effects of minimiser history size and local rigidification on the overall efficiency were analysed. Improvements relative to CPU performance of up to two orders of magnitude were obtained for the largest systems. These methods have been successfully applied to both biological systems and atomic clusters. An existing interface between a code for free energy basin-hopping and the SuiteSparse package for sparse Cholesky factorisation was refined, validated and tested. Tests were performed for both Lennard-Jones clusters and selected biomolecules represented using the AMBER potential. Significant acceleration of the vibrational frequency calculations was achieved, with negligible loss of accuracy, relative to the standard diagonalisation procedure. For the larger systems, exploiting sparsity reduces the computational cost by factors of 10 to 30. The acceleration of these computational energy landscape methods opens up the possibility of investigating much larger and more complex systems than previously accessible. A wide array of new applications are now computationally feasible.
25
Weber, Bruno. « Optimisation de code Galerkin discontinu sur ordinateur hybride : application à la simulation numérique en électromagnétisme ». Thesis, Strasbourg, 2018. http://www.theses.fr/2018STRAD046/document.
Texte intégralRésumé :
Nous présentons dans cette thèse les évolutions apportées au solveur Galerkin Discontinu Teta-CLAC, issu de la collaboration IRMA-AxesSim, au cours du projet HOROCH (2015-2018). Ce solveur permet de résoudre les équations de Maxwell en 3D, en parallèle sur un grand nombre d'accélérateurs OpenCL. L'objectif du projet HOROCH était d'effectuer des simulations de grande envergure sur un modèle numérique complet de corps humain. Ce modèle comporte 24 millions de mailles hexaédriques pour des calculs dans la bande de fréquences des objets connectés allant de 1 à 3 GHz (Bluetooth). Les applications sont nombreuses : téléphonie et accessoires, sport (maillots connectés), médecine (sondes : gélules, patchs), etc. Les évolutions ainsi apportées comprennent, entre autres : l'optimisation des kernels OpenCL à destination des CPU dans le but d'utiliser au mieux les architectures hybrides ; l'expérimentation du runtime StarPU ; le design d'un schéma d'intégration à pas de temps local ; et bon nombre d'optimisations permettant au solveur de traiter des simulations de plusieurs millions de maillesIn this thesis, we present the evolutions made to the Discontinuous Galerkin solver Teta-CLAC – resulting from the IRMA-AxesSim collaboration – during the HOROCH project (2015-2018). This solver allows to solve the Maxwell equations in 3D and in parallel on a large amount of OpenCL accelerators. The goal of the HOROCH project was to perform large-scale simulations on a complete digital human body model. This model is composed of 24 million hexahedral cells in order to perform calculations in the frequency band of connected objects going from 1 to 3 GHz (Bluetooth). The applications are numerous: telephony and accessories, sport (connected shirts), medicine (probes: capsules, patches), etc. The changes thus made include, among others: optimization of OpenCL kernels for CPUs in order to make the best use of hybrid architectures; StarPU runtime experimentation; the design of an integration scheme using local time steps; and many optimizations allowing the solver to process simulations of several millions of cells
26
Crestetto, Anaïs. « Optimisation de méthodes numériques pour la physique des plasmas : application aux faisceaux de particules chargées ». Phd thesis, Université de Strasbourg, 2012. http://tel.archives-ouvertes.fr/tel-00735569.
Texte intégralRésumé :
Cette thèse propose différentes méthodes numériques permettant de simuler le comportement des plasmas ou des faisceaux de particules chargées à coût réduit. Le mouvement de particules chargées soumises à un champ électromagnétique est régi par l'équation de Vlasov. Celle-ci est couplée aux équations de Maxwell pour le champ électromagnétique ou à l'équation de Poisson dans un cas simplifié. Plusieurs types de modèles existent pour résoudre ce système. Dans les modèles cinétiques, les particules sont représentées par une fonction de distribution f(x,v,t) qui vérifie l'équation de Vlasov. Dans le cas général tridimensionnel (3D), le système fait apparaître 7 variables. Les calculs sur ordinateur deviennent rapidement très lourds. Les modèles fluides de plasma s'intéressent quant à eux à des quantités macroscopiques déduites de f par des intégrales en vitesse, telles que la densité, la vitesse moyenne et la température. Ces quantités ne dépendent que de la position x et du temps t. Le coût numérique est ainsi réduit, mais la précision s'en trouve altérée. Dans la première partie de cette thèse, une méthode multi-fluides est utilisée pour la résolution du système de Vlasov-Poisson 1D. Elle est basée sur la connaissance a priori de la forme prise par la fonction de distribution f. Deux possibilités sont étudiées : une somme de masse de Dirac et le modèle multi-water-bag. Ce type de méthodes est plutôt adapté aux systèmes restant proches de l'état d'équilibre. La deuxième partie propose de décomposer f en une partie d'équilibre et une perturbation. L'équilibre est résolu par une méthode fluide alors que la perturbation est résolue par une méthode cinétique. On construit notamment un schéma préservant l'asymptotique pour le système de Vlasov-Poisson-BGK, basé sur une telle décomposition. On étudie dans la troisième partie la méthode Particle-In-Cell (PIC) en géométrie 2D axisymétrique. Un travail basé sur l'analyse isogéométrique est présenté, ainsi qu'un code PIC - Galerkin Discontinu parallélisé sur carte graphique (GPU). Cette architecture permet de réduire de manière significative les temps de calculs.
27
Lalami, Mohamed Esseghir. « Contribution à la résolution de problèmes d'optimisation combinatoire : méthodes séquentielles et parallèles ». Phd thesis, Université Paul Sabatier - Toulouse III, 2012. http://tel.archives-ouvertes.fr/tel-00748546.
Texte intégralRésumé :
Les problèmes d'optimisation combinatoire sont souvent des problèmes très difficiles dont la résolution par des méthodes exactes peut s'avérer très longue ou peu réaliste. L'utilisation de méthodes heuristiques permet d'obtenir des solutions de bonne qualité en un temps de résolution raisonnable. Les heuristiques sont aussi très utiles pour le développement de méthodes exactes fondées sur des techniques d'évaluation et de séparation. Nous nous sommes intéressés dans un premier temps à proposer une méthode heuristique pour le problème du sac à dos multiple MKP. L'approche proposée est comparée à l'heuristique MTHM et au solveur CPLEX. Dans un deuxième temps nous présentons la mise en œuvre parallèle d'une méthode exacte de résolution de problèmes d'optimisation combinatoire de type sac à dos sur architecture GPU. La mise en œuvre CPU-GPU de la méthode de Branch and Bound pour la résolution de problèmes de sac à dos a montré une accélération de 51 sur une carte graphique Nvidia Tesla C2050. Nous présentons aussi une mise en œuvre CPU-GPU de la méthode du Simplexe pour la résolution de problèmes de programmation linéaire. Cette dernière offre une accélération de 12.7 sur une carte graphique Nvidia Tesla C2050. Enfin, nous proposons une mise en œuvre multi-GPU de l'algorithme du Simplexe, mettant à contribution plusieurs cartes graphiques présentes dans une même machine (2 cartes Nvidia Tesla C2050 dans notre cas). Outre l'accélération obtenue par rapport à la mise en œuvre séquentielle de la méthode du Simplexe, une efficacité de 96.5 % est obtenue, en passant d'une carte à deux cartes graphiques.
28
Bramas, Bérenger. « Optimization and parallelization of the boundary element method for the wave equation in time domain ». Thesis, Bordeaux, 2016. http://www.theses.fr/2016BORD0022/document.
Texte intégralRésumé :
La méthode des éléments frontières pour l’équation des ondes (BEM) est utilisée en acoustique eten électromagnétisme pour simuler la propagation d’une onde avec une discrétisation en temps(TD). Elle permet d’obtenir un résultat pour plusieurs fréquences à partir d’une seule résolution.Dans cette thèse, nous nous intéressons à l’implémentation efficace d’un simulateur TD-BEM sousdifférents angles. Nous décrivons le contexte de notre étude et la formulation utilisée qui s’exprimesous la forme d’un système linéaire composé de plusieurs matrices d’interactions/convolutions.Ce système est naturellement calculé en utilisant l’opérateur matrice/vecteur creux (SpMV). Nousavons travaillé sur la limite du SpMV en étudiant la permutation des matrices et le comportementde notre implémentation aidé par la vectorisation sur CPU et avec une approche par bloc surGPU. Nous montrons que cet opérateur n’est pas approprié pour notre problème et nous proposonsde changer l’ordre de calcul afin d’obtenir une matrice avec une structure particulière.Cette nouvelle structure est appelée une matrice tranche et se calcule à l’aide d’un opérateur spécifique.Nous décrivons des implémentations optimisées sur architectures modernes du calculhaute-performance. Le simulateur résultant est parallélisé avec une approche hybride (mémoirespartagées/distribuées) sur des noeuds hétérogènes, et se base sur une nouvelle heuristique pouréquilibrer le travail entre les processeurs. Cette approche matricielle a une complexité quadratiquesi bien que nous avons étudié son accélération par la méthode des multipoles rapides (FMM). Nousavons tout d’abord travaillé sur la parallélisation de l’algorithme de la FMM en utilisant différentsparadigmes et nous montrons comment les moteurs d’exécution sont adaptés pour relâcher le potentielde la FMM. Enfin, nous présentons des résultats préliminaires d’un simulateur TD-BEMaccéléré par FMMThe time-domain BEM for the wave equation in acoustics and electromagnetism is used to simulatethe propagation of a wave with a discretization in time. It allows to obtain several frequencydomainresults with one solve. In this thesis, we investigate the implementation of an efficientTD-BEM solver using different approaches. We describe the context of our study and the TD-BEMformulation expressed as a sparse linear system composed of multiple interaction/convolutionmatrices. This system is naturally computed using the sparse matrix-vector product (SpMV). Wework on the limits of the SpMV kernel by looking at the matrix reordering and the behavior of ourSpMV kernels using vectorization (SIMD) on CPUs and an advanced blocking-layout on NvidiaGPUs. We show that this operator is not appropriate for our problem, and we then propose toreorder the original computation to get a special matrix structure. This new structure is called aslice matrix and is computed with a custom matrix/vector product operator. We present an optimizedimplementation of this operator on CPUs and Nvidia GPUs for which we describe advancedblocking schemes. The resulting solver is parallelized with a hybrid strategy above heterogeneousnodes and relies on a new heuristic to balance the work among the processing units. Due tothe quadratic complexity of this matrix approach, we study the use of the fast multipole method(FMM) for our time-domain BEM solver. We investigate the parallelization of the general FMMalgorithm using several paradigms in both shared and distributed memory, and we explain howmodern runtime systems are well-suited to express the FMM computation. Finally, we investigatethe implementation and the parametrization of an FMM kernel specific to our TD-BEM, and weprovide preliminary results
29
Balestra, Julien. « Caractérisation de la source des séismes par inversion des données sismologiques et géodésiques : mécanismes au foyer, optimisation des modèles de vitesse, distribution du glissement cosismique ». Thesis, Université Côte d'Azur (ComUE), 2017. http://www.theses.fr/2017AZUR4020/document.
Texte intégralRésumé :
La caractérisation de la source d’un séisme se fait à partir de l’analyse des mesures des déplacements transitoires et statiques du sol, et dépend de la quantité et de la qualité de ces mesures. Nous avons travaillé sur la détermination des mécanismes au foyer des répliques du séisme de Saintes (MW 6.4, 2004), et sur la détermination de la distribution spatio-temporelle du glissement cosismique des séismes de L’Aquila (Mw 6.3, 2009), et de Miyagi-Oki (Mw 7.2, 2005) et de Sanriku-Oki (Mw 7.3, 2011). Ces travaux se sont basés sur des méthodes d’inversions, et différents jeux de données (accélérométriques, large-bandes, GPS et InSAR) accessibles ou non selon le séisme considéré. La seule diversité des mesures n’est pas suffisante pour décrire la rupture. La modélisation des données se confronte à des difficultés, comme par exemple la pertinence des modèles de vitesses sismiques pour la modélisation des données accélérométriques. Une autre problématique récurrente est la non-unicité de la meilleure solution déterminée par les méthodes d’inversions pour décrire les données. Pour répondre à ces deux problématiques, nous avons d‘une part développé une procédure d’exploration de modèles de vitesse pour déterminer les valeurs optimales capables de décrire au mieux les données accélérométriques du séisme de L’Aquila. D’autre part, nous avons développé une procédure de construction d’un modèle de source moyen que nous avons appliqué pour la détermination du glissement cosismique des séismes de L’Aquila, de Miyagi-Oki, et de Sanriku-Oki. L’ensemble de ces travaux et les réponses aux problèmes soulevés sont présentés dans ce travail de thèseStudies of the earthquake source are based on observations of seismic ground motions. They also depend on the quality and the density of measurements. In this present work we will present studies of the determination of focal mechanism of main aftershocks of the Les Saintes (MW 6.4, 2004) earthquake, and the determination of the coseismic slip of the L’Aquila (MW 6.3, 2009), the Miyagi-Oki (MW 7.2, 2005), ant the Sanriku-Oki (MW 7.3, 2011) earthquakes. These studies were based on two inversion methods. Different kinds of data were available (strong motion, broadband teleseismic, GPS and InSAR) depending on the earthquake studied. But the multiplicity of data is not sufficient to well describe rupture process. There are others difficulties as the data modeling of strong motion. Seismic velocity models are used to describe the characteristics of layers crossed by seismic waves. The quality of the modeling is depending on the pertinence of these seismic velocity models. The description of the rupture process is also depending on the non-uniqueness of the best solution given by global inversion methods. We propose two procedures in order to take into account these two classic issues. First, we developed a velocity model exploration procedure to obtain optimized 1D velocity models in order to improve the strong motion modeling of the L’Aquila earthquake. Then we developed a procedure to build an average rupture model from the combined results of several joint inversions, which was applied to the L’Aquila, the Miyagi-Oki, and the Sanriku-Oki earthquake. This thesis presents all these works and answers to the raised issues
30
Heiries, Vincent. « Optimisation d'une chaîne de réception pour signaux de radionavigation à porteuse à double décalage (BOC) retenus pour les systèmes GALILEO et GPS modernisé ». Toulouse, ISAE, 2007. http://www.theses.fr/2007ESAE0018.
Texte intégralRésumé :
Avec le développement de nombreux systèmes de navigation, la nécessité de partager efficacement la bande spectrale allouée aux nombreux signaux de ces futurs systèmes est apparue. Dans ce souci, la sous-modulation BOC a été retenue pour un grand nombre de signaux GNSS. Cette sous-modulation présente non seulement de très bonnes propriétés en terme de séparation spectrale, mais apporte aussi une meilleure précision et une robustesse accrue vis à vis des multitrajets. Néanmoins, l'utilisation de cette sous-modulation BOC rend l'acquisition des signaux plus complexe. Ce travail de thèse concerne l'optimisation d'une chaîne de réception de signaux BOC, et des signaux composites dérivés du BOC. Nous avons analysé les problèmes que pose l'utilisation de cette modulation lors de l'acquisition du signal, celle-ci étant rendue ambiguë. Plusieurs algorithmes résolvant ce problème d'ambiguïté ont été évalué. Les résultats ont été validés grâce à un simulateur de récepteur. Ensuite, l'étude s'est focalisée sur l'acquisition des signaux BOC en présence de multitrajets. Après une analyse approfondie de l'impact des multitrajets sur le traitement des signaux BOC, une étude visant à obtenir une forme optimisée du discriminateur de boucle de code a été menée. Utilisant au mieux les caractéristiques des signaux BOC, ce discriminateur a été recherché sous la contrainte de lutter le plus efficacement possible contre les multitrajets sans pour autant dégrader la robustesse face au bruit. Une autre méthode originale de réduction de l'erreur due aux multitrajets basée sur un concept différent a été proposée et analysée. Cette méthode très simple affiche de très bonnes performances.
31
Petit, Eric. « Vers un partitionnement automatique d'applications en codelets spéculatifs pour les systèmes hétérogènes à mémoires distribuées ». Phd thesis, Université Rennes 1, 2009. http://tel.archives-ouvertes.fr/tel-00445512.
Texte intégralRésumé :
Devant les difficultés croissantes liées au coût en développement, en consommation, en surface de silicium, nécessaires aux nouvelles optimisations des architectures monocœur, on assiste au retour en force du parallélisme et des coprocesseurs spécialisés dans les architectures. Cette technique apporte le meilleur compromis entre puissance de calcul élevée et utilisations des ressources. Afin d'exploiter efficacement toutes ces architectures, il faut partitionner le code en tâches, appelées codelet, avant de les distribuer aux différentes unités de calcul. Ce partionnement est complexe et l'espace des solutions est vaste. Il est donc nécessaire de développer des outils d'automatisation efficaces pour le partitionnement du code séquentiel. Les travaux présentés dans cette thèse portent sur l'élaboration d'un tel processus de partitionnement. L'approche d'Astex est basée sur la spéculation, en effet les codelets sont construits à partir des profils d'exécution de l'application. La spéculation permet un grand nombre d'optimisations inexistantes ou impossibles statiquement. L'élaboration, la gestion dynamique et l'usage que l'on peut faire de la spéculation sont un vaste sujet d'étude. La deuxième contribution de cette thèse porte sur l'usage de la spéculation dans l'optimisation des communications entre processeur et coprocesseur et traite en particulier du cas du GPGPU, i.e. l'utilisation d'un processeur graphique comme coprocesseur de calcul intensif.
32
Besch, Guillaume. « Optimisation du contrôle glycémique en chirurgie cardiaque : variabilité glycémique, compliance aux protocoles de soins, et place des incrétino-mimétiques ». Thesis, Bourgogne Franche-Comté, 2017. http://www.theses.fr/2017UBFCE016/document.
Texte intégralRésumé :
L’hyperglycémie de stress et la variabilité glycémique, consécutives à la réaction inflammatoire péri opératoire, sont associées à une morbidité et une mortalité accrues en chirurgie cardiaque. L’insulinothérapie intraveineuse administrée à l’aide de protocoles complexes, dits « dynamiques », constitue à l’heure actuelle le traitement de référence de l’hyperglycémie de stress. L’intérêt du contrôle glycémique péri-opératoire est admis par tous, sans qu’il existe de consensus véritable quant aux objectifs à atteindre, et reste très exigeant en termes de charge de soins. Dans la 1ère partie de ce travail, nous avons voulu vérifier si, 7 ans après sa mise en place, l’observance du protocole d’insulinothérapie utilisé dans notre Unité de Soins Intensifs de Chirurgie Cardiaque était conforme à celle mesurée lors de son implantation. Nous avons constaté des dérives majeures dans l’application du protocole qui ont pu être corrigées par la mise en place de mesures correctrices simples. Dans une 2ème partie du travail, nous avons cherché à évaluer si, à l’instar de la chirurgie cardiaque classique, une variabilité glycémique accrue était associée à une altération du pronostic des patients bénéficiant d’une procédure moins invasive (remplacement valvulaire aortique percutané ou TAVI). Nous avons ainsi analysé les données des patients ayant bénéficié d’un TAVI dans notre centre, et inclus dans les registres multicentriques français France et France-2. Nos résultats suggèrent une association entre une augmentation de la variabilité glycémique et un risque accru de complications cardiovasculaires majeures dans les 30 premiers jours, indépendamment de la qualité du contrôle glycémique obtenu. Enfin, dans une 3ème partie nous avons voulu savoir si exenatide, analogue de synthèse de GLP-1, permettait d’améliorer le contrôle glycémique péri opératoire en chirurgie cardiaque. Nous avons conduit un essai randomisé contrôlé de phase II/III montrant que l’administration intraveineuse (IV) d’exenatide, ne permettait pas d’améliorer la qualité du contrôle glycémique ou de réduire la variabilité glycémique par rapport à l’insuline IV, mais permettait de retarder l’administration d’insuline et de diminuer la quantité d’insuline administrée. Notre étude suggère également une diminution de la charge en soins. Du fait des données rapportées chez l’animal et dans l’infarctus du myocarde, nous avons également conduit une étude ancillaire suggérant l’absence d’effets cardioprotecteurs majeurs d’exenatide sur les lésions d’ischémie-reperfusion myocardiques, ne permettant pas d’améliorer la fonction cardiaque gauche à court et à moyen terme. L’optimisation du contrôle glycémique en chirurgie cardiaque nécessite ainsi la recherche de stratégies visant à améliorer l’observance des protocoles de soins et à réduire la variabilité glycémique. La place des analogues du GLP-1 reste à définir dans cette indicationStress hyperglycemia and glycemic variability are associated with increased morbidity and mortality in cardiac surgery patients. Intravenous (IV) insulin therapy using complex dynamic protocols is the gold standard treatment for stress hyperglycemia. If the optimal blood glucose target range remains a matter of debate, blood glucose control using IV insulin therapy protocols has become part of the good clinical practices during the postoperative period, but implies a significant increase in nurse workload. In the 1st part of the thesis, we aimed at checking the nurse-compliance to the insulin therapy protocol used in our Cardiac Surgery Intensive Care Unit 7 years after its implementation. Major deviations have been observed and simple corrective measures have restored a high level of nurse compliance. In the 2nd part of this thesis, we aimed at assessing whether blood glucose variability could be related to poor outcome in transcatheter aortic valve implantation (TAVI) patients, as reported in more invasive cardiac surgery procedures. The analysis of data from patients who undergone TAVI in our institution and included in the multicenter France and France-2 registries suggested that increased glycemic variability is associated with a higher rate of major adverse events occurring between the 3rd and the 30th day after TAVI, regardless of hyperglycemia. In the 3rd part if this thesis, we conducted a randomized controlled phase II/III trial to investigate the clinical effectiveness of IV exenatide in perioperative blood glucose control after coronary artery bypass graft surgery. Intravenous exenatide failed to improve blood glucose control and to decrease glycemic variability, but allowed to delay the start in insulin infusion and to lower the insulin dose required. Moreover, IV exenatide could allow a significant decrease in nurse workload. The ancillary analysis of this trial suggested that IV exenatide did neither provide cardio protective effect against myocardial ischemia-reperfusion injuries nor improve the left ventricular function by using IV exenatide. Strategies aiming at improving nurse compliance to insulin therapy protocols and at reducing blood glucose variability could be suitable to improve blood glucose control in cardiac surgery patients. The use of the analogues of GLP-1 in cardiac surgery patients needs to be investigated otherwise
33
Jaeger, Julien. « Transformations source-à-source pour l'optimisation de codes irréguliers et multithreads ». Phd thesis, Université de Versailles-Saint Quentin en Yvelines, 2012. http://tel.archives-ouvertes.fr/tel-00842177.
Texte intégralRésumé :
Dans cette thèse, nous montrons que les optimisations source-à-source sont un moyen efficace pour générer des programmes irréguliers ou parallèles performants à partir d'une implémentation. Après avoir présenté l'évolution des architectures des processeurs, nous proposons deux méthodes distinctes. La première pour extraire des codelets d'un programme irréguliers, les optimiser et prédire les performances du programme modifié. L'autre pour limiter l'impact des problèmes d'alignements dus à la vectorisation ou aux conflits de bancs. Nous présentons aussi différentes techniques de parallélisation, l'une générant des codelets parallèles, l'autre ordonnançant un graphe de taches sur un système hétérogène.
34
Xia, Liang. « Towards optimal design of multiscale nonlinear structures : reduced-order modeling approaches ». Thesis, Compiègne, 2015. http://www.theses.fr/2015COMP2230/document.
Texte intégralRésumé :
L'objectif principal est de faire premiers pas vers la conception topologique de structures hétérogènes à comportement non-linéaires. Le deuxième objectif est d’optimiser simultanément la topologie de la structure et du matériau. Il requiert la combinaison des méthodes de conception optimale et des approches de modélisation multi-échelle. En raison des lourdes exigences de calcul, nous avons introduit des techniques de réduction de modèle et de calcul parallèle. Nous avons développé tout d’abord un cadre de conception multi-échelle constitué de l’optimisation topologique et la modélisation multi-échelle. Ce cadre fournit un outil automatique pour des structures dont le modèle de matériau sous-jacent est directement régi par la géométrie de la microstructure réaliste et des lois de comportement microscopiques. Nous avons ensuite étendu le cadre en introduisant des variables supplémentaires à l’échelle microscopique pour effectuer la conception simultanée de la structure et de la microstructure. En ce qui concerne les exigences de calcul et de stockage de données en raison de multiples réalisations de calcul multi-échelle sur les configurations similaires, nous avons introduit: les approches de réduction de modèle. Nous avons développé un substitut d'apprentissage adaptatif pour le cas de l’élasticité non-linéaire. Pour viscoplasticité, nous avons collaboré avec le Professeur Felix Fritzen de l’Université de Stuttgart en utilisant son modèle de réduction avec la programmation parallèle sur GPU. Nous avons également adopté une autre approche basée sur le potentiel de réduction issue de la littérature pour améliorer l’efficacité de la conception simultanéeHigh-performance heterogeneous materials have been increasingly used nowadays for their advantageous overall characteristics resulting in superior structural mechanical performance. The pronounced heterogeneities of materials have significant impact on the structural behavior that one needs to account for both material microscopic heterogeneities and constituent behaviors to achieve reliable structural designs. Meanwhile, the fast progress of material science and the latest development of 3D printing techniques make it possible to generate more innovative, lightweight, and structurally efficient designs through controlling the composition and the microstructure of material at the microscopic scale. In this thesis, we have made first attempts towards topology optimization design of multiscale nonlinear structures, including design of highly heterogeneous structures, material microstructural design, and simultaneous design of structure and materials. We have primarily developed a multiscale design framework, constituted of two key ingredients : multiscale modeling for structural performance simulation and topology optimization forstructural design. With regard to the first ingredient, we employ the first-order computational homogenization method FE2 to bridge structural and material scales. With regard to the second ingredient, we apply the method Bi-directional Evolutionary Structural Optimization (BESO) to perform topology optimization. In contrast to the conventional nonlinear design of homogeneous structures, this design framework provides an automatic design tool for nonlinear highly heterogeneous structures of which the underlying material model is governed directly by the realistic microstructural geometry and the microscopic constitutive laws. Note that the FE2 method is extremely expensive in terms of computing time and storage requirement. The dilemma of heavy computational burden is even more pronounced when it comes to topology optimization : not only is it required to solve the time-consuming multiscale problem once, but for many different realizations of the structural topology. Meanwhile we note that the optimization process requires multiple design loops involving similar or even repeated computations at the microscopic scale. For these reasons, we introduce to the design framework a third ingredient : reduced-order modeling (ROM). We develop an adaptive surrogate model using snapshot Proper Orthogonal Decomposition (POD) and Diffuse Approximation to substitute the microscopic solutions. The surrogate model is initially built by the first design iteration and updated adaptively in the subsequent design iterations. This surrogate model has shown promising performance in terms of reducing computing cost and modeling accuracy when applied to the design framework for nonlinear elastic cases. As for more severe material nonlinearity, we employ directly an established method potential based Reduced Basis Model Order Reduction (pRBMOR). The key idea of pRBMOR is to approximate the internal variables of the dissipative material by a precomputed reduced basis computed from snapshot POD. To drastically accelerate the computing procedure, pRBMOR has been implemented by parallelization on modern Graphics Processing Units (GPUs). The implementation of pRBMOR with GPU acceleration enables us to realize the design of multiscale elastoviscoplastic structures using the previously developed design framework inrealistic computing time and with affordable memory requirement. We have so far assumed a fixed material microstructure at the microscopic scale. The remaining part of the thesis is dedicated to simultaneous design of both macroscopic structure and microscopic materials. By the previously established multiscale design framework, we have topology variables and volume constraints defined at both scales
35
Selmi, Ikhlas. « Optimisation de l'infrastructure d'un système de positionnement indoor à base de transmetteurs GNSS ». Electronic Thesis or Diss., Evry, Institut national des télécommunications, 2013. http://www.theses.fr/2013TELE0024.
Texte intégralRésumé :
Dans le but de fournir un service GNSS (Global Navigation Satellite System) de localisation continu et disponible partout, les systèmes utilisant des pseudolites et des répéteurs semblent être des solutions pertinentes pour la localisation en indoor. Le système à répélites, inspiré de ces deux méthodes (répéteurs et pseudolites), est aussi proposé pour résoudre cette problématique. Les répélites sont des transmetteurs locaux qui, installés en intérieur, formeront une constellation locale. Ils émettent tous un signal GNSS unique mais déphasé par un délai spécifique à chacun d’eux. Ces délais sont nécessaires pour distinguer les différents signaux reçus au niveau du récepteur. Les travaux de cette thèses sont réalisés dans le cadre du système à répélites et dans l’objectif d’améliorer son architecture et de réduire ses interférences inter-système. En effet, l’architecture du système (un peu encombrante) et les interférences éventuelles avec les signaux satellitaires reçus par un récepteur placé à l’extérieur font partie des inconvénients de ce système. On cherche donc à traiter ces deux difficultés de façon à minimiser leurs effets. Dans une première partie, on étudie les différents codes GNSS existants dans la littérature ainsi que les techniques de modulation employées. Ceci nous mène à proposer des codes ayant un niveau d’interférence équivalent à la référence GPS (obtenue entre deux codes GPS) pour les bandes L1 de GPS et G1 de Glonass. Dans une seconde étape, on développe la modulation IMBOC (Indoor Modified Binary Offset Carrier) pour générer de nouveaux codes caractérisés par des niveaux d’interférence réduits (comparés à la référence GPS). Parmi ces codes il y a deux catégories : ceux qui sont adaptés aux systèmes à répélites (émettant un code unique) et ceux qui sont adaptés aux systèmes pseudolites. Une étude théorique et des simulations des niveaux d’interférences pour les codes émis dans la bande GPS et Glonass sont réalisées pour déterminer les gains en termes de niveaux de bruit. Ce gain (par rapport à la référence GPS) en puissance d’interférence s’élève à 16 dB pour Glonass et 20 dB pour GPS. Pour valider les performances de ces codes, on génère les signaux IMBOC et on observe les interférences réelles qu’ils induisent sur un récepteur GPS recevant un signal satellitaire. Dans la deuxième partie, on utilise la fibre optique pour transmettre le signal du générateur jusqu’aux répélites et pour créer les délais initiaux par propagation du signal dans des bobines de fibre. Ainsi on remplace les câbles coaxiaux et les montages électroniques (de déphasage) par des bobines de fibres plus légères, facile à installer et à faible perte de puissance. Il reste cependant à évaluer avec une précision centimétrique les délais réels induits sur chaque signal dans le but de garantir une précision de localisation inférieure au mètre. Cette précision semble en effet représenter un bon compromis entre complexité globale du système de localisation et réponse à un ensemble suffisant de besoins des utilisateurs potentiels. On développe alors une technique d’estimation des délais basée sur la mesure de déphasage (entre deux signaux sinusoïdaux) et une analyse statistique des séries de mesures. Pour finir, on présente quelques résultats de localisation obtenus avec notre système à répélites déployé dans un environnement indoor typiqueIn order to make the GNSS positioning service continuous and available when going from an outdoor to an indoor environment, pseudolite and repeater based systems have been developed. A new system called repealite is a combination of both pseudolites and repeaters. It is based on transmitting a single signal through a set of transmitters (thus creating the local constellation). In order to avoid interference between the repealite signals and to distinguish between them at the receiver’s end, each signal is shifted with a specific delay. The research carried out in this PhD aims at optimizing two aspects of the repealite based system. Firstly, we need to mitigate the effect of the interference caused on the satellite signals received outdoors. So we decided to design new codes characterized by low interference levels with outdoor signals. Secondly, we worked on the infrastructure part in order to simplify it and to make it easier to install: this is mainly achieved through the use of optical fibers. In the first part, we study the codes and the modulation techniques currently used in the GNSS systems. Then, we propose a few codes having an interference level equivalent to that of the GPS (obtained when computing two GPS codes). These new codes are compatible with the GPS L1 or the Glonass G1 bands. In a second step, we focus on the modulation techniques and create the so-called IMBOC (Indoor Modified Binary Offset Carrier) that aims at minimizing the interference levels with outdoor signals. With this modulation, we propose new IMBOC codes capable of much lower interference levels than the GPS reference. In order to evaluate the performance of the proposed codes, we carried out a theoretical study, simulations and experimental tests. The interference gain reached about 20 dB on the GPS band and 16 dB on the Glonass one. The proposed codes are divided into two categories: those reserved to the repealite system (using a single code) and families of codes suited to pseudolite–based systems. Finally, we generated the IMBOC signals modulated by the new codes and tested the real interference induced on an outdoor receiver tracking the satellite signals. In the second part, we use optical fibers in order to replace the coaxial cables used to transmit signals from the GNSS-like signal generator to the repealites. In addition, the initial delay needed for each repealite is added by propagating the signals through rolls of fibers. Indeed, optical fiber offers advantages such as lightness, flexibility and low power loss that make it suitable to simplify the infrastructure of the system. In order to evaluate the real delays of these various fibers, we develop an estimating method based on phase shift measurements (between two sinusoidal signals) and statistical analysis of the series of measurements. This method should have uncertainties lower than one centimeter in order to insure a sub-meter precision (in absolute positioning with the repealite positioning system). In order to validate this method, we compare it to a GNSS based calibration approach. Finally, we carry out a few positioning tests with the repealite positioning system deployed in a typical indoor environment. These tests deal with absolute and relative positioning and give an idea about the system’s performance
36
Seznec, Mickaël. « From the algorithm to the targets, optimization flow for high performance computing on embedded GPUs ». Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG074.
Texte intégralRésumé :
Les algorithmes de traitement numérique actuels nécessitent une puissance de calcul accrue pour obtenir des résultats plus précis et traiter des données plus volumineuses. Dans le même temps, les architectures matérielles se spécialisent, avec des accélérateurs très efficaces pour des tâches spécifiques. Dans ce contexte, le chemin du déploiement de l'algorithme à l'implémentation est de plus en plus complexe. Il est donc crucial de déterminer comment les algorithmes peuvent être modifiés pour tirer parti des capacités du matériel. Dans notre étude, nous nous sommes intéressé aux unités graphiques (GPU), un type de processeur massivement parallèle. Notre travail a consisté à l'adaptation entre l'algorithme et le matériel d'exécution. À l'échelle d'un opérateur mathématique, nous avons modifié un algorithme de convolution d'images pour utiliser les tensor cores et montré qu'on peut en doubler les performances pour de grands noyaux de convolution. Au niveau méthode, nous avons évalué des solveurs de systèmes linéaires pour l'estimation de flux optique afin de trouver le plus adéquat sur GPU. Grâce à ce choix et après de nouvelles optimisations spécifiques, comme la fusion d'itérations ou la réutilisation de zones mémoire, la méthode est deux fois plus rapide que l'implémentation initiale, fonctionnant à 60 images par seconde sur plateforme embarquée (30W). Enfin, nous avons également montré l'intérêt, dans le cadre des réseaux de neurones profonds, de cette méthode de conception d'algorithmes adaptée au matériel. Avec pour exemple l'hybridation entre un réseau conçu pour le flux optique avec une autre architecture préentrainée et conçue pour être efficace sur des cibles à faible puissance de calculCurrent digital processing algorithms require more computing power to achieve more accurate results and process larger data. In the meantime, hardware architectures are becoming more specialized, with highly efficient accelerators designed for specific tasks. In this context, the path of deployment from the algorithm to the implementation becomes increasingly complex. It is, therefore, crucial to determine how algorithms can be modified to take advantage of new hardware capabilities. Our study focused on graphics processing units (GPUs), a massively parallel processor. Our algorithmic work was done in the context of radio-astronomy or optical flow estimation and consisted of finding the best adaptation of the software to the hardware. At the level of a mathematical operator, we modified the traditional image convolution algorithm to use the matrix units and showed that its performance doubles for large convolution kernels. At a broader method level, we evaluated linear solvers for the combined local-global optical flow to find the most suitable one on GPU. With additional optimizations, such as iteration fusion or memory buffer re-utilization, the method is twice as fast as the initial implementation, running at 60 frames per second on an embedded platform (30 W). Finally, we also pointed out the interest of this hardware-aware algorithm design method in the context of deep neural networks. For that, we showed the hybridization of a convolutional neural network for optical flow estimation with a pre-trained image classification network, MobileNet, that was initially designed for efficient image classification on low-power platforms
37
Selmi, Ikhlas. « Optimisation de l'infrastructure d'un système de positionnement indoor à base de transmetteurs GNSS ». Phd thesis, Institut National des Télécommunications, 2013. http://tel.archives-ouvertes.fr/tel-00919772.
Texte intégralRésumé :
Dans le but de fournir un service GNSS (Global Navigation Satellite System) de localisation continu et disponible partout, les systèmes utilisant des pseudolites et des répéteurs semblent être des solutions pertinentes pour la localisation en indoor. Le système à répélites, inspiré de ces deux méthodes (répéteurs et pseudolites), est aussi proposé pour résoudre cette problématique. Les répélites sont des transmetteurs locaux qui, installés en intérieur, formeront une constellation locale. Ils émettent tous un signal GNSS unique mais déphasé par un délai spécifique à chacun d'eux. Ces délais sont nécessaires pour distinguer les différents signaux reçus au niveau du récepteur. Les travaux de cette thèses sont réalisés dans le cadre du système à répélites et dans l'objectif d'améliorer son architecture et de réduire ses interférences inter-système. En effet, l'architecture du système (un peu encombrante) et les interférences éventuelles avec les signaux satellitaires reçus par un récepteur placé à l'extérieur font partie des inconvénients de ce système. On cherche donc à traiter ces deux difficultés de façon à minimiser leurs effets. Dans une première partie, on étudie les différents codes GNSS existants dans la littérature ainsi que les techniques de modulation employées. Ceci nous mène à proposer des codes ayant un niveau d'interférence équivalent à la référence GPS (obtenue entre deux codes GPS) pour les bandes L1 de GPS et G1 de Glonass. Dans une seconde étape, on développe la modulation IMBOC (Indoor Modified Binary Offset Carrier) pour générer de nouveaux codes caractérisés par des niveaux d'interférence réduits (comparés à la référence GPS). Parmi ces codes il y a deux catégories : ceux qui sont adaptés aux systèmes à répélites (émettant un code unique) et ceux qui sont adaptés aux systèmes pseudolites. Une étude théorique et des simulations des niveaux d'interférences pour les codes émis dans la bande GPS et Glonass sont réalisées pour déterminer les gains en termes de niveaux de bruit. Ce gain (par rapport à la référence GPS) en puissance d'interférence s'élève à 16 dB pour Glonass et 20 dB pour GPS. Pour valider les performances de ces codes, on génère les signaux IMBOC et on observe les interférences réelles qu'ils induisent sur un récepteur GPS recevant un signal satellitaire. Dans la deuxième partie, on utilise la fibre optique pour transmettre le signal du générateur jusqu'aux répélites et pour créer les délais initiaux par propagation du signal dans des bobines de fibre. Ainsi on remplace les câbles coaxiaux et les montages électroniques (de déphasage) par des bobines de fibres plus légères, facile à installer et à faible perte de puissance. Il reste cependant à évaluer avec une précision centimétrique les délais réels induits sur chaque signal dans le but de garantir une précision de localisation inférieure au mètre. Cette précision semble en effet représenter un bon compromis entre complexité globale du système de localisation et réponse à un ensemble suffisant de besoins des utilisateurs potentiels. On développe alors une technique d'estimation des délais basée sur la mesure de déphasage (entre deux signaux sinusoïdaux) et une analyse statistique des séries de mesures. Pour finir, on présente quelques résultats de localisation obtenus avec notre système à répélites déployé dans un environnement indoor typique
38
Ahmed, Bacha Adda Redouane. « Localisation multi-hypothèses pour l'aide à la conduite : conception d'un filtre "réactif-coopératif" ». Thesis, Evry-Val d'Essonne, 2014. http://www.theses.fr/2014EVRY0051/document.
Texte intégralRésumé :
“ Lorsqu'on utilise des données provenant d'une seule source,C'est du plagiat;Lorsqu'on utilise plusieurs sources,C'est de la fusion de données ”Ces travaux présentent une approche de fusion de données collaborative innovante pour l'égo-localisation de véhicules routiers. Cette approche appelée filtre de Kalman optimisé à essaim de particules (Optimized Kalman Particle Swarm) est une méthode de fusion de données et de filtrage optimisé. La fusion de données est faite en utilisant les données d'un GPS à faible coût, une centrale inertielle, un compteur odométrique et un codeur d'angle au volant. Ce travail montre que cette approche est à la fois plus robuste et plus appropriée que les méthodes plus classiques d'égo-localisation aux situations de conduite urbaine. Cette constatation apparait clairement dans le cas de dégradations des signaux capteurs ou des situations à fortes non linéarités. Les méthodes d'égo-localisation de véhicules les plus utilisées sont les approches bayésiennes représentées par le filtre de Kalman étendu (Extended Kalman Filter) et ses variantes (UKF, DD1, DD2). Les méthodes bayésiennes souffrent de sensibilité aux bruits et d'instabilité pour les cas fortement non linéaires. Proposées pour couvrir les limitations des méthodes bayésiennes, les approches multi-hypothèses (à base de particules) sont aussi utilisées pour la localisation égo-véhiculaire. Inspiré des méthodes de simulation de Monte-Carlo, les performances du filtre à particules (Particle Filter) sont fortement dépendantes des ressources en matière de calcul. Tirant avantage des techniques de localisation existantes et en intégrant les avantages de l'optimisation méta heuristique, l'OKPS est conçu pour faire face aux bruits, aux fortes dynamiques, aux données non linéaires et aux besoins d'exécution en temps réel. Pour l'égo-localisation d'un véhicule, en particulier pour les manœuvres très dynamiques sur route, un filtre doit être robuste et réactif en même temps. Le filtre OKPS est conçu sur un nouvel algorithme de localisation coopérative-réactive et dynamique inspirée par l'Optimisation par Essaim de Particules (Particle Swarm Optimization) qui est une méthode méta heuristique. Cette nouvelle approche combine les avantages de la PSO et des deux autres filtres: Le filtre à particules (PF) et le filtre de Kalman étendu (EKF). L'OKPS est testé en utilisant des données réelles recueillies à l'aide d'un véhicule équipé de capteurs embarqués. Ses performances sont testées en comparaison avec l'EKF, le PF et le filtre par essaim de particules (Swarm Particle Filter). Le filtre SPF est un filtre à particules hybride intéressant combinant les avantages de la PSO et du filtrage à particules; Il représente la première étape de la conception de l'OKPS. Les résultats montrent l'efficacité de l'OKPS pour un scénario de conduite à dynamique élevée avec des données GPS endommagés et/ou de qualité faible“ When we use information from one source,it's plagiarism;Wen we use information from many,it's information fusion ”This work presents an innovative collaborative data fusion approach for ego-vehicle localization. This approach called the Optimized Kalman Particle Swarm (OKPS) is a data fusion and an optimized filtering method. Data fusion is made using data from a low cost GPS, INS, Odometer and a Steering wheel angle encoder. This work proved that this approach is both more appropriate and more efficient for vehicle ego-localization in degraded sensors performance and highly nonlinear situations. The most widely used vehicle localization methods are the Bayesian approaches represented by the EKF and its variants (UKF, DD1, DD2). The Bayesian methods suffer from sensitivity to noises and instability for the highly non-linear cases. Proposed for covering the Bayesian methods limitations, the Multi-hypothesis (particle based) approaches are used for ego-vehicle localization. Inspired from monte-carlo simulation methods, the Particle Filter (PF) performances are strongly dependent on computational resources. Taking advantages of existing localization techniques and integrating metaheuristic optimization benefits, the OKPS is designed to deal with vehicles high nonlinear dynamic, data noises and real time requirement. For ego-vehicle localization, especially for highly dynamic on-road maneuvers, a filter needs to be robust and reactive at the same time. The OKPS filter is a new cooperative-reactive localization algorithm inspired by dynamic Particle Swarm Optimization (PSO) metaheuristic methods. It combines advantages of the PSO and two other filters: The Particle Filter (PF) and the Extended Kalman filter (EKF). The OKPS is tested using real data collected using a vehicle equipped with embedded sensors. Its performances are tested in comparison with the EKF, the PF and the Swarm Particle Filter (SPF). The SPF is an interesting particle based hybrid filter combining PSO and particle filtering advantages; It represents the first step of the OKPS development. The results show the efficiency of the OKPS for a high dynamic driving scenario with damaged and low quality GPS data
39
Adnan, S. « Ultra-wideband antenna design for microwave imaging applications. Design, optimisation and development of ultra-wideband antennas for microwave near-field sensing tools, and study the matching and radiation purity of these antennas within near field environment ». Thesis, University of Bradford, 2012. http://hdl.handle.net/10454/5750.
Texte intégralRésumé :
Near field imaging using microwave in medical applications has gain much attention recently as various researches show its high ability and accuracy in illuminating object comparing to the well-known screening tools such as Magnetic Resonance Imaging (MRI), digital mammography, ultrasound etc. This has encourage and motivate scientists continue to exploit the potential of microwave imaging so that a better and more powerful sensing tools can be developed.
This thesis documents the development of antenna design for microwave imaging application such as breast cancer detection. The application is similar to the concept of Ground Penetrating Radar (GPR) but operating at higher frequency band. In these systems a short pulse is transmitted from an antenna to the medium and the backscattered response is investigated for diagnose. In order to accommodate such a short pulse, a very wideband antenna with a minimal internal reflection is required. Printed monopole and planar metal plate antenna is implemented to achieve the necessary operating wide bandwidth.
The development of new compact printed planar metal plate ultra wide bandwidth antenna is presented. A generalized parametric study is carried out using two well-known software packages to achieve optimum antenna performance. The Prototype antennas are tested and analysed experimentally, in which a reasonable agreement was achieved with the simulations. The antennas present an excellent relative wide bandwidth of 67% with acceptable range of power gain between 3.5 to 7 dBi.
A new compact size air-dielectric microstrip patch-antenna designs proposed for breast cancer detection are presented. The antennas consist of a radiating patch mounted on two vertical plates, fed by coaxial cable. The antennas show a wide bandwidth that were verified by the simulations and also confirmed experimentally. The prototype antennas show excellent performance in terms the input impedance and radiation performance over the target range bandwidth from 4 GHz to 8 GHz. A mono-static model with a homogeneous dielectric box having similar properties to human tissue is used to study the interaction of the antenna with tissue. The numerical results in terms the matching required of new optimised antennas were promising.
An experimental setup of sensor array for early-stage breast-cancer detection is developed. The arrangement of two elements separated by short distance that confined equivalent medium of breast tissues were modelled and implemented. The operation performances due to several orientations of the antennas locations were performed to determine the sensitivity limits with and without small size equivalent cancer cells model.
In addition, a resistively loaded bow tie antenna, intended for applications in breast cancer detection, is adaptively modified through modelling and genetic optimisation is presented. The required wideband operating characteristic is achieved through manipulating the resistive loading of the antenna structure, the number of wires, and their angular separation within the equivalent wire assembly. The results show an acceptable impedance bandwidth of 100.75 %, with a VSWR < 2, over the interval from 3.3 GHz to 10.0 GHz. Feasibility studies were made on the antenna sensitivity for operation in a tissue equivalent dielectric medium. The simulated and measured results are all in close agreement.
40
Adnan, Shahid. « Ultra-wideband antenna design for microwave imaging applications : design, optimisation and development of ultra-wideband antennas for microwave near-field sensing tools, and study the matching and radiation purity of these antennas within near field environment ». Thesis, University of Bradford, 2012. http://hdl.handle.net/10454/5750.
Texte intégralRésumé :
Near field imaging using microwave in medical applications has gain much attention recently as various researches show its high ability and accuracy in illuminating object comparing to the well-known screening tools such as Magnetic Resonance Imaging (MRI), digital mammography, ultrasound etc. This has encourage and motivate scientists continue to exploit the potential of microwave imaging so that a better and more powerful sensing tools can be developed. This thesis documents the development of antenna design for microwave imaging application such as breast cancer detection. The application is similar to the concept of Ground Penetrating Radar (GPR) but operating at higher frequency band. In these systems a short pulse is transmitted from an antenna to the medium and the backscattered response is investigated for diagnose. In order to accommodate such a short pulse, a very wideband antenna with a minimal internal reflection is required. Printed monopole and planar metal plate antenna is implemented to achieve the necessary operating wide bandwidth. The development of new compact printed planar metal plate ultra wide bandwidth antenna is presented. A generalized parametric study is carried out using two well-known software packages to achieve optimum antenna performance. The Prototype antennas are tested and analysed experimentally, in which a reasonable agreement was achieved with the simulations. The antennas present an excellent relative wide bandwidth of 67% with acceptable range of power gain between 3.5 to 7 dBi. A new compact size air-dielectric microstrip patch-antenna designs proposed for breast cancer detection are presented. The antennas consist of a radiating patch mounted on two vertical plates, fed by coaxial cable. The antennas show a wide bandwidth that were verified by the simulations and also confirmed experimentally. The prototype antennas show excellent performance in terms the input impedance and radiation performance over the target range bandwidth from 4 GHz to 8 GHz. A mono-static model with a homogeneous dielectric box having similar properties to human tissue is used to study the interaction of the antenna with tissue. The numerical results in terms the matching required of new optimised antennas were promising. An experimental setup of sensor array for early-stage breast-cancer detection is developed. The arrangement of two elements separated by short distance that confined equivalent medium of breast tissues were modelled and implemented. The operation performances due to several orientations of the antennas locations were performed to determine the sensitivity limits with and without small size equivalent cancer cells model. In addition, a resistively loaded bow tie antenna, intended for applications in breast cancer detection, is adaptively modified through modelling and genetic optimisation is presented. The required wideband operating characteristic is achieved through manipulating the resistive loading of the antenna structure, the number of wires, and their angular separation within the equivalent wire assembly. The results show an acceptable impedance bandwidth of 100.75 %, with a VSWR < 2, over the interval from 3.3 GHz to 10.0 GHz. Feasibility studies were made on the antenna sensitivity for operation in a tissue equivalent dielectric medium. The simulated and measured results are all in close agreement.
41
Turcanu, Vasile. « Valorisation des granulats recyclés dans les bétons soumis au gel/dégel sans saturation (classes d’exposition F et R) ». Mémoire, Université de Sherbrooke, 2017. http://hdl.handle.net/11143/10479.
Texte intégralRésumé :
Cette étude consiste à analyser les propriétés du béton destiné aux applications résidentielles dans lesquelles une partie des granulats naturels (GN) sont remplacés par des granulats recyclés (GR). On analyse les impacts sur la résistance, la durabilité et la microstructure du béton en fonction du taux de remplacement. Trois différents types des GR sont étudiés. Les essais de caractérisation des granulats recyclés, tels que la densité, l’absorption, la granulométrie, la teneur en impuretés, en matières organiques et en ions chlorure sont effectués. Les essais réalisés sur les bétons se résument essentiellement aux essais de la résistance à la compression, du retrait de séchage, de la résistance aux cycles de gels-dégels, de la perméabilité aux ions chlorure et de la résistivité électrique. Dans le but d’identifier l’effet des granulats fins recyclés sur le comportement des bétons, les analyses thermogravimétriques (ATG) et le pH des mortiers à base des granulats recyclés sont également déterminés.
Les bétons évalués dans le cadre de cette étude de classes d’exposition « F-2 » et « R » sont destinés pour la construction résidentielle et des petits bâtiments. Compte tenu de critère de résistance plus sévère, le béton choisi pour les essais est de classe F-2 selon la classification de la norme CSA A23.1-14 (annexe 1 et 40). La norme prévoit que le béton soit soumis aux cycles de gels-dégels dans des conditions non saturées, mais ne soit pas exposé aux ions chlorure. À titre d’exemples, on peut nommer les murs et les poteaux extérieurs. La norme CSA établit les propriétés minimales pour un béton de classe F-2 (annexe 2). Ainsi, la formulation vise un rapport eau/liant (E/L) de 0.55 et une teneur en air de 4 à 6% selon le diamètre maximal du gros granulat utilisé (annexe 3).
Les formules des bétons sont déterminées par la méthode des volumes absolus (CAN-A23.1-94 et ACI 211.1-74). Dans cette étude, le liant utilisé est le ciment de type GU, le ciment binaire à base de laitier et les ciments ternaires à base de laitier et fumée de silice ou à base de cendres volantes et fumée de silice.
Les GR sont composés de gros granulats et de granulats fins. Le remplacement du GN par le granulat recyclé est effectué de la manière suivante : une proportion des granulats fins recyclés remplace le sable et une partie des gros granulats recyclés remplace les gros granulats naturels. Les proportions massiques des granulats naturels dans le mélange sont effectuées suite à une optimisation granulaire des matériaux par rapport à la courbe visée de Fuller et Thompson (Gagné et Aïtcin, 2014).
Bien que certaines propriétés des bétons aux GR et ciment GU soient plus faibles, comparativement aux propriétées des bétons aux granulats naturels, il est possible d’obtenir la résistance à la compression minimale de 25 MPa à 28 jours, recommandée par la norme CSA A23.1-14 (bétons de classe F2), en optimisant le taux de remplacement des granulats recyclés de 15% pour un béton formulé avec du ciment GU et de 45% pour un béton formulé avec du ciment binaire au laitier.
Mots-clés : Béton résidentiel, ciment binaire, ciment de type GU, ciment ternaire, durabilité, granulats recyclés, méthode des volumes absolus, optimisation des granulats, résistance.
42
Dubois, Clémence. « Optimisation du traitement du cancer du sein Triple-Négatif : développement des modèles de culture cellulaire en trois dimensions, efficacité de l'Olaparib (anti-PARP1) en combinaison avec la radiothérapie et chimiorésistance instaurée par les protéines Multi Drug Résistance ». Thesis, Université Clermont Auvergne (2017-2020), 2018. http://www.theses.fr/2018CLFAS018/document.
Texte intégralRésumé :
Le cancer du sein est une maladie complexe et difficile à caractériser. Parmi les différents sous-types moléculaires, les tumeurs du sein Triple-Négatives (TN) sont particulièrement agressives et de mauvais pronostic. Elles sont caractérisées par une absence d’expression des récepteurs aux œstrogènes (ER), à la progestérone (PR), l’absence de surexpression du récepteur Human Epidermal growth factor 2 (HER2) et de fréquentes mutations sur les gènes BRCA1/2 (profil « BRCAness »). En absence de thérapies ciblées efficaces, de nombreux traitements ciblés notamment les inhibiteurs de poly-ADP-ribose polymérases (anti-PARPs) sont actuellement en cours de développement, en recherche préclinique et clinique. Basés sur le principe de létalité synthétique, les anti-PARPs ciblent les propriétés BRCAness des tumeurs TN. Dans ce contexte, ces travaux de recherche ont été orientés sur le développement d’outils diagnostics afin d’optimiser l’efficacité des anti-PARPs sur des tumeurs TN. Pour ce faire, dans un premier temps, des cultures cellulaires en 3D via la technique Liquid Overlay ainsi que des tests de cytotoxicités associés ont été développés, à partir des lignées cellulaires MDA-MB-231 et SUM1315 de phénotype TN. Ces deux modèles de sphéroïdes ont ensuite été optimisés/normalisés dans un milieu de culture synthétique intitulé OPTIPASS (BIOPASS). Dans un deuxième temps, l’efficacité d’un co-traitement combinant l’anti-PARP1 Olaparib à faibles et à fortes doses et la radiothérapie fractionnée (5x2 Gy) a été modélisée sur les deux lignées MDA-MB-231 et SUM1315, en conditions 2D et 3D. Ces expériences ont clairement mis en évidence un effet potentialisateur de l’Olaparib sur la radiothérapie (i) en présence de faibles doses de cet anti-PARP (5 µM ou inférieur) (ii) à long terme et (iii) en présence d’un fractionnement maximum (5x2 Gy). De plus, les lignées tumorales TN étudiées présentaient des différences de sensibilité vis-à-vis du co-traitement. Ainsi, une analyse transcriptomique in silico a mis en évidence des profils très différents de ces lignées hautement métastatiques et très agressives. Notamment, la lignée SUM1315 semblait présenter un engagement neuronal, suggérant son origine métastatique cérébrale. Ces résultats encourageants pourraient ouvrir de nouvelles perspectives pour le traitement des métastases cérébrales de tumeurs mammaires TN, très fréquentes chez ce sous-type. Dans un troisième temps, afin de mieux caractériser le mode d’action de l’Olaparib sur ces modèles de sphéroïdes, un dérivé fluorescent de l’Olaparib, l’Ola-FL, a été synthétisé et caractérisé. L’analyse de la pénétration et de la distribution de l’Ola-FL au sein des sphéroïdes MDA-MB-231 et SUM1315 a mis en évidence une distribution rapide et homogène du composé ainsi que sa persistance après 3h d’incubation, dans toute la profondeur des sphéroïdes et notamment dans les zones hypoxiques centrales. Enfin, l’analyse de la co-expression de deux pompes Multidrug Resistance (MDR) majeures, la MRP7 et la P-gp après le traitement des deux lignées TN avec l’Olaparib, a mis en évidence sur les cultures 2D, une expression de type relai de la MRP7 et la P-gp. Sur les sphéroïdes traités avec une faible dose d’Olaparib à long terme, une expression basale de la MRP7 et une surexpression de la P-gp ont été détectées, au sein des cellules résiduelles périphériques des sphéroïdes. Ces résultats mettent clairement en évidence l’implication des pompes d’efflux dans les mécanismes de résistances à l’Olaparib, dans ces tumeurs agressives. L’ensemble des résultats issus de la modélisation de l’action de l’Olaparib sur des sphéroïdes MDA-MB-231 et SUM1315 laissent supposer sa plus grande efficacité à faible dose et à long-terme, notamment dans les zones hypoxiques des sphéroïdes, probablement aussi à l’origine de son effet potentialisateur avec la radiothérapieBreast cancer is a very complex and heterogeneous disease. Among the different molecular subtypes, Triple-Negative (TN) breast cancers are particularly aggressive and of poor prognosis. TN tumours are characterized by a lack of estrogen receptors expression (ER), progesterone receptors expression (PR), the absence of Human Epidermal growth factor receptor 2 overexpression (HER2) of the frequent mutations on BRCA1 / 2 genes ("BRCAness" phenotype). In the absence of effective targeted therapies, many targeted therapies including poly-ADP-ribose polymerase inhibitors (anti-PARPs) are currently under development in preclinical and clinical studies. Based on the synthetic lethality concept, the anti-PARPs specifically target the BRCAness properties of TN tumors. In this context, these works were focused on the development of diagnostic tools for the optimization of TN tumours treatment with anti-PARPs. For this, firstly, 3D cell cultures formed with the Liquid Overlay technique as well as associated cytotoxicity tests were developed, from the TN breast cancer cell lines MDA-MB-231 and SUM1315. These two spheroid models were then optimized and standardized in a synthetic culture medium called OPTIPASS (BIOPASS). Secondly, the efficacy of a co-treatment combining anti-PARP1 Olaparib at low and high doses and fractioned radiotherapy (5x2 Gy) was analyzed on the two cell lines MDA-MB-231 and SUM1315 cultured in 2D and 3D conditions. These experiments clearly demonstrated a potentiating effect of Olaparib on radiotherapy (i) in presence of low doses of this anti-PARP (5 μM or inferior) (ii) at long term and (iii) in presence of the maximum fractionation (5x2 Gy). In addition, these two TN cell lines showed a heterogeneous sensitivity to the co-treatment. Thus, an in silico transcriptomic analysis revealed very different profiles of these highly metastatic and highly aggressive cell lines. Notably, the SUM1315 cell line presented a neuronal commitment, suggesting its cerebral metastatic origin. These promising results could open up new perspectives for the treatment of TN tumours brain metastases, which are very common in this subtype. Thirdly, in order to better characterize the mode of action of Olaparib on these spheroid models, a fluorescent derivative of Olaparib, Ola-FL, was synthesized and characterized. The analysis of Ola-FL penetration and distribution in MDA-MB-231 and SUM1315 spheroids showed a rapid and homogeneous distribution of the compound as well as its persistence after 3h of incubation, in all the depth of the spheroids and especially in the central hypoxic zones. Finally, the analysis of the co-expression of two major Multidrug Resistance (MDR) pumps, MRP7 and P-gp after the treatment of the two TN lines with Olaparib, revealed on 2D cultures, a relay type expression of the MRP7 and the P-gp. On spheroids treated with a low dose of Olaparib art long term (10 days), a basal expression of MRP7 and an overexpression of P-gp were detected in the peripheral residual cells of the spheroids. These results clearly highlighted the involvement of these efflux pumps in Olaparib resistance mechanisms, in these aggressive tumors. All the results resulting from the modeling of the action of Olaparib on MDA-MB-231 and SUM1315 spheroids suggest its greater efficacy at low dose and at long-term, especially in the hypoxic zones of the spheroids. This parameter might be probably at the origin of its potentiating effect with radiotherapy
43
Lalami, Mohamed Esseghir. « Contribution à la résolution de problèmes d'optimisation combinatoire : méthodes séquentielles et parallèles ». Phd thesis, Toulouse 3, 2012. http://thesesups.ups-tlse.fr/1916/.
Texte intégralRésumé :
Les problèmes d'optimisation combinatoire sont souvent des problèmes très difficiles dont la résolution par des méthodes exactes peut s'avérer très longue ou peu réaliste. L'utilisation de méthodes heuristiques permet d'obtenir des solutions de bonne qualité en un temps de résolution raisonnable. Les heuristiques sont aussi très utiles pour le développement de méthodes exactes fondées sur des techniques d'évaluation et de séparation. Nous nous sommes intéressés dans un premier temps à proposer une méthode heuristique pour le problème du sac à dos multiple MKP. L'approche proposée est comparée à l'heuristique MTHM et au solveur CPLEX. Dans un deuxième temps nous présentons la mise en oeuvre parallèle d'une méthode exacte de résolution de problèmes d'optimisation combinatoire de type sac à dos sur architecture GPU. La mise en oeuvre CPU-GPU de la méthode de Branch and Bound pour la résolution de problèmes de sac à dos a montré une accélération de 51 sur une carte graphique Nvidia Tesla C2050. Nous présentons aussi une mise en oeuvre CPU-GPU de la méthode du Simplexe pour la résolution de problèmes de programmation linéaire. Cette dernière offre une accélération de 12. 7 sur une carte graphique Nvidia Tesla C2050. Enfin, nous proposons une mise en oeuvre multi-GPU de l'algorithme du Simplexe, mettant à contribution plusieurs cartes graphiques présentes dans une même machine (2 cartes Nvidia Tesla C2050 dans notre cas). Outre l'accélération obtenue par rapport à la mise en oeuvre séquentielle de la méthode du Simplexe, une efficacité de 96. 5 % est obtenue, en passant d'une carte à deux cartes graphiquesCombinatorial optimization problems are difficult problems whose solution by exact methods can be time consuming or not realistic. The use of heuristics permits one to obtain good quality solutions in a reasonable time. Heuristics are also very useful for the development of exact methods based on branch and bound techniques. The first part of this thesis concerns the Multiple Knapsack Problem (MKP). We propose here a heuristic called RCH which yields a good solution for the MKP problem. This approach is compared to the MTHM heuristic and CPLEX solver. The second part of this thesis concerns parallel implementation of an exact method for solving combinatorial optimization problems like knapsack problems on GPU architecture. The parallel implementation of the Branch and Bound method via CUDA for knapsack problems is proposed. Experimental results show a speedup of 51 for difficult problems using a Nvidia Tesla C2050 (448 cores). A CPU-GPU implementation of the simplex method for solving linear programming problems is also proposed. This implementation offers a speedup around 12. 7 on a Tesla C2050 board. Finally, we propose a multi-GPU implementation of the simplex algorithm via CUDA. An efficiency of 96. 5% is obtained when passing from one GPU to two GPUs
44
Marak, Laszlo. « On continuous maximum flow image segmentation algorithm ». Phd thesis, Université Paris-Est, 2012. http://tel.archives-ouvertes.fr/tel-00786914.
Texte intégralRésumé :
In recent years, with the advance of computing equipment and image acquisition techniques, the sizes, dimensions and content of acquired images have increased considerably. Unfortunately as time passes there is a steadily increasing gap between the classical and parallel programming paradigms and their actual performance on modern computer hardware. In this thesis we consider in depth one particular algorithm, the continuous maximum flow computation. We review in detail why this algorithm is useful and interesting, and we propose efficient and portable implementations on various architectures. We also examine how it performs in the terms of segmentation quality on some recent problems of materials science and nano-scale biology
45
Bahi, Mouad. « High Performance by Exploiting Information Locality through Reverse Computing ». Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00768574.
Texte intégralRésumé :
The main resources for computation are time, space and energy. Reducing them is the main challenge in the field of processor performance.In this thesis, we are interested in a fourth factor which is information. Information has an important and direct impact on these three resources. We show how it contributes to performance optimization. Landauer has suggested that independently on the hardware where computation is run information erasure generates dissipated energy. This is a fundamental result of thermodynamics in physics. Therefore, under this hypothesis, only reversible computations where no information is ever lost, are likely to be thermodynamically adiabatic and do not dissipate power. Reversibility means that data can always be retrieved from any point of the program. Information may be carried not only by the data but also by the process and input data that generate it. When a computation is reversible, information can also be retrieved from other already computed data and reverse computation. Hence reversible computing improves information locality.This thesis develops these ideas in two directions. In the first part, we address the issue of making a computation DAG (directed acyclic graph) reversible in terms of spatial complexity. We define energetic garbage as the additional number of registers needed for the reversible computation with respect to the original computation. We propose a reversible register allocator and we show empirically that the garbage size is never more than 50% of the DAG size. In the second part, we apply this approach to the trade-off between recomputing (direct or reverse) and storage in the context of supercomputers such as the recent vector and parallel coprocessors, graphical processing units (GPUs), IBM Cell processor, etc., where the gap between processor cycle time and memory access time is increasing. We show that recomputing in general and reverse computing in particular helps reduce register requirements and memory pressure. This approach of reverse rematerialization also contributes to the increase of instruction-level parallelism (Cell) and thread-level parallelism in multicore processors with shared register/memory file (GPU). On the latter architecture, the number of registers required by the kernel limits the number of running threads and affects performance. Reverse rematerialization generates additional instructions but their cost can be hidden by the parallelism gain. Experiments on the highly memory demanding Lattice QCD simulation code on Nvidia GPU show a performance gain up to 11%.
46
Zehendner, Elisabeth. « Operations management at container terminals using advanced information technologies ». Phd thesis, Ecole Nationale Supérieure des Mines de Saint-Etienne, 2013. http://tel.archives-ouvertes.fr/tel-00972071.
Texte intégralRésumé :
Container terminals use intelligent freight technologies (e.g., EDI, RFID and GPS) to exchange data with their partners, to locate containers and equipment within the terminal, and to automate tasks. This thesis illustrated, via two examples, how this data may be used to optimize operations at the terminal.The first part uses information on announced volumes to allocate internal handling equipment. The objective is to minimize overall delays at the terminal. The problem is represented as a network flow problem and implemented as a linear mixed integer programming model. A case study for a terminal at the Grand Port Maritime de Marseille is carried out. We also showed that combining the allocation problem with the dimensioning of a truck appointment system may reduce overall delays at the terminal. The second part uses information on announced container retrievals and container positions to improve retrieval operations. The objective is to retrieve containers from a bay in a given sequence with a minimum number of parasite relocations. We improve an existing binary programming model and introduce an exact branch and price approach - with a binary subproblem and two variants of an enumerative subproblem - and a heuristic branch and price approach - with a heuristic subproblem. The exact approach solves only small instances; the heuristic approach performs well on several instances, but should be improved further. We also deal with a dynamic version of the problem where the retrieval order becomes revealed over time and evaluate different relocation strategies for this case.
47
Watson, Francis Maurice. « Better imaging for landmine detection : an exploration of 3D full-wave inversion for ground-penetrating radar ». Thesis, University of Manchester, 2016. https://www.research.manchester.ac.uk/portal/en/theses/better-imaging-for-landmine-detection-an-exploration-of-3d-fullwave-inversion-for-groundpenetrating-radar(720bab5f-03a7-4531-9a56-7121609b3ef0).html.
Texte intégralRésumé :
Humanitarian clearance of minefields is most often carried out by hand, conventionally using a a metal detector and a probe. Detection is a very slow process, as every piece of detected metal must treated as if it were a landmine and carefully probed and excavated, while many of them are not. The process can be safely sped up by use of Ground-Penetrating Radar (GPR) to image the subsurface, to verify metal detection results and safely ignore any objects which could not possibly be a landmine. In this thesis, we explore the possibility of using Full Wave Inversion (FWI) to improve GPR imaging for landmine detection. Posing the imaging task as FWI means solving the large-scale, non-linear and ill-posed optimisation problem of determining the physical parameters of the subsurface (such as electrical permittivity) which would best reproduce the data. This thesis begins by giving an overview of all the mathematical and implementational aspects of FWI, so as to provide an informative text for both mathematicians (perhaps already familiar with other inverse problems) wanting to contribute to the mine detection problem, as well as a wider engineering audience (perhaps already working on GPR or mine detection) interested in the mathematical study of inverse problems and FWI.We present the first numerical 3D FWI results for GPR, and consider only surface measurements from small-scale arrays as these are suitable for our application. The FWI problem requires an accurate forward model to simulate GPR data, for which we use a hybrid finite-element boundary-integral solver utilising first order curl-conforming N\'d\'{e}lec (edge) elements. We present a novel `line search' type algorithm which prioritises inversion of some target parameters in a region of interest (ROI), with the update outside of the area defined implicitly as a function of the target parameters. This is particularly applicable to the mine detection problem, in which we wish to know more about some detected metallic objects, but are not interested in the surrounding medium. We may need to resolve the surrounding area though, in order to account for the target being obscured and multiple scattering in a highly cluttered subsurface. We focus particularly on spatial sensitivity of the inverse problem, using both a singular value decomposition to analyse the Jacobian matrix, as well as an asymptotic expansion involving polarization tensors describing the perturbation of electric field due to small objects. The latter allows us to extend the current theory of sensitivity in for acoustic FWI, based on the Born approximation, to better understand how polarization plays a role in the 3D electromagnetic inverse problem. Based on this asymptotic approximation, we derive a novel approximation to the diagonals of the Hessian matrix which can be used to pre-condition the GPR FWI problem.
48
Bistaffa, Filippo. « Constraint Optimisation Techniques for Real-World Applications ». Doctoral thesis, 2016. http://hdl.handle.net/11562/939118.
Texte intégralRésumé :
L'ottimizzazione a vincoli rappresenta una tecnica fondamentale che e stata applicata con successo nell'ambito dei Sistemi Multi-Agente (MAS), con lo scopo di risolvere numerosi problemi di coordinamento tra gli agenti.In questa tesi affrontiamo il problema della Formazione di Coalizioni (CF), uno degli approcci chiave per affrontare problemi di coordinamento nei MAS. In particolare, CF ha l'obiettivo di formare gruppi che massimizzano una funzione obiettivo (e.g., formare macchine condivise da piu agenti in modo da minimizzare i costi di trasporto).Ci concentriamo su un caso particolare di CF denominato CF su Grafi (GCCF), dove una rete tra gli agenti vincola la formazione delle coalizioni. Questo problema si riscontra in molte applicazioni realistiche, ad esempio nel caso di reti di comunicazione o di relazioni sociali. Nello specifico, i contributi principali della tesi sono i seguenti. Proponiamo un nuovo modo di formalizzare il problema GCCF, e un algoritmo efficiente (denominato CFSS) per risolverlo. CFSS e stato testato in contesti realistici quali il collective energy purchasing e il social ridesharing, utilizzando dati reali (i.e., profili di consumo energetico domestico del Regno Unito, GeoLife per le coordinate di spostamento nell'ambito del ridesharing, e Twitter come rete sociale). CFSS e il primo algoritmo in grado di risolvere GCCF su larga scala fornendo buone garanzie di qualita.In aggiunta, affrontiamo il problema di dividere il valore associato ad ogni coalizione tra i suoi membri, in modo da garantire che siano ricompensati adeguatamente per il contributo apportato al gruppo. Questo aspetto di CF, chiamato calcolo dei pagamenti, e cruciale in ambiti caratterizzati da agenti con un comportamento razionale, quali il collective energy purchasing e il social ridesharing. Questo problema e risolto tramite il nostro algoritmo denominato PRF, il primo metodo in grado di risolvere questo problema su larga scala. In aggiunta, i pagamenti calcolati soddisfano la proprieta derivante dalla teoria dei giochi chiamata stabilita, che garantisce che tali pagamenti siano considerati imparziali dagli agenti.Infine, proponiamo un metodo alternativo per la soluzione del problema GCCF, sfruttando la relazione tra GCCF e i problemi di ottimizzazione a vincoli (COP). In particolare, consideriamo Bucket Elimination (BE), uno dei framework piu importanti per la risoluzione dei COP, e proponiamo CUBE, un implementazione parallela di BE su GPU. CUBE adotta uno schema della gestione della memoria innovativo, che porta notevoli benefici dal punto di vista delle performance e permette a CUBE di non essere limitato dal quantitativo di memoria della GPU, cosi da poter risolvere problemi di carattere reale. CUBE e stato testato su SPOT5, un dataset realistico che contiene problemi di coordinamento tra satelliti modellati tramite COP. Inoltre, CUBE e stato usato per risolvere COP-GCCF, la nostra formalizzazione tramite COP del problema GCCF. COP-GCCF e il primo modello che comprende un numero lineare di vincoli rispetto al numero di agenti, caratteristica fondamentale per garantire la scalabilita della nostra tecnica risolutiva. I nostri esperimenti, che utilizzano Twitter come dataset reale, dimostrano che COP-GCCF apporta numerosi vantaggi rispetto allo stato dell'arte, sia in termini di memoria e di runtime.In generale, questa tesi propone una nuova prospettiva su importanti tecniche nell'ambito dei MAS, quali CF e l'ottimizzazione a vincoli, permettendo di risolvere per la prima volta problemi di carattere reale su larga scala.Constraint optimisation represents a fundamental technique that has been successfully employed in Multi-Agent Systems (MAS) in order to face a number of multi-agent coordination challenges. In this thesis we focus on Coalition Formation (CF), one of the key approaches for coordination in MAS. CF aims at the formation of groups that maximise a particular objective functions (e.g., arrange shared rides among multiple agents in order to minimise travel costs). Specifically, we discuss a special case of CF known as Graph-Constrained CF (GCCF) where a network connecting the agents constrains the formation of coalitions. We focus on this type of problem given that in many real-world applications, agents may be connected by a communication network or only trust certain peers in their social network. In particular, the contributions of this thesis are the following.We propose a novel representation of this problem and we design an efficient solution algorithm, i.e., CFSS. We evaluate CFSS on GCCF scenarios like collective energy purchasing and social ridesharing using realistic data (i.e., energy consumption profiles from households in the UK, GeoLife for spatial data, and Twitter as social network).Results show that CFSS outperforms state of the art GCCF approaches both in terms of runtime and scalability. CFSS is the first algorithm that provides solutions with good quality guarantees for large-scale GCCF instances with thousands of agents (i.e., more that 2700).In addition, we address the problem of computing the transfer or payment to each agent to ensure it is fairly rewarded for its contribution to its coalition. This aspect of CF, denoted as payment computation, is of utmost importance in scenario characterised by agents with rational behaviours, such as collective energy purchasing and social ridesharing. In this perspective, we propose PRF, the first method to compute payments in large-scale GCCF scenarios that are also stable in a game-theoretic sense.Finally, we provide an alternative method for the solution of GCCF, by exploiting the close relation between such problem and Constraint Optimisation Problems (COPs).We consider Bucket Elimination (BE), one of the most important algorithmic frameworks to solve COPs, and we propose CUBE, a highly-parallel GPU implementation of the most computationally intensive operations of BE. CUBE adopts an efficient memory layout that results in a high computational throughput. In addition, CUBE is not limited by the amount of memory of the GPU and, hence, it can cope with problems of realistic nature. CUBE has been tested on the SPOT5 dataset, which contains several satellite management problems modelled as COPs.Moreover, we use CUBE to solve COP-GCCF, the first COP formalisation of GCCF that results in a linear number of constraints with respect to the number of agents. This property is crucial to ensure the scalability of our approach.Results show that COP-GCCF produces significant improvements with respect to state of the art algorithms when applied to a realistic graph topology (i.e., Twitter), both in terms of runtime and memory.Overall, this thesis provides a novel perspective on important techniques in the context of MAS (such as CF and constraint optimisation), allowing to solve realistic problems involving thousands of agents for the first time.
49
Grenier, Julie. « Optimisation de l'utilisation des techniques de modélisation dans le passage de l'étape pré-clinique à clinique du développement d'un médicament ». Thèse, 2008. http://hdl.handle.net/1866/6686.
Texte intégral
50
(5929916), Sudhir B. Kylasa. « HIGHER ORDER OPTIMIZATION TECHNIQUES FOR MACHINE LEARNING ». Thesis, 2019.
Trouver le texte intégralRésumé :
First-order methods such as Stochastic Gradient Descent are methods of choice for solving non-convex optimization problems in machine learning. These methods primarily rely on the gradient of the loss function to estimate descent direction. However, they have a number of drawbacks, including converging to saddle points (as opposed to minima), slow convergence, and sensitivity to parameter tuning. In contrast, second order methods that use curvature information in addition to the gradient, have been shown to achieve faster convergence rates, theoretically. When used in the context of machine learning applications, they offer faster (quadratic) convergence, stability to parameter tuning, and robustness to problem conditioning. In spite of these advantages, first order methods are commonly used because of their simplicity of implementation and low per-iteration cost. The need to generate and use curvature information in the form of a dense Hessian matrix makes each iteration of second order methods more expensive.
In this work, we address three key problems associated with second order methods – (i) what is the best way to incorporate curvature information into the optimization procedure; (ii) how do we reduce the operation count of each iteration in a second order method, while maintaining its superior convergence property; and (iii) how do we leverage high-performance computing platforms to significant accelerate second order methods. To answer the first question, we propose and validate the use of Fisher information matrices in second order methods to significantly accelerate convergence. The second question is answered through the use of statistical sampling techniques that suitably sample matrices to reduce per-iteration cost without impacting convergence. The third question is addressed through the use of graphics processing units (GPUs) in distributed platforms to deliver state of the art solvers.
Through our work, we show that our solvers are capable of significant improvement over state of the art optimization techniques for training machine learning models. We demonstrate improvements in terms of training time (over an order of magnitude in wall-clock time), generalization properties of learned models, and robustness to problem conditioning.