In this thesis, we investigate methods of finding a local minimum for unconstrained problems of non-convex functions with n variables, by following the solution curve of a system of ordinary differential equations. The motivation for this was the fact that existing methods (e.g. those based on Newton methods with line search) sometimes terminate at a non-stationary point when applied to functions f(x) that do not a have positive-definite Hessian (i.e. ∇²f → 0) for all x. Even when methods terminate at a stationary point it could be a saddle or maximum rather than a minimum. The only method which makes intuitive sense in non-convex region is the trust region approach where we seek a step which minimises a quadratic model subject to a restriction on the two-norm of the step size. This gives a well-defined search direction but at the expense of a costly evaluation. The algorithms derived in this thesis are gradient based methods which require systems of equations to be solved at each step but which do not use a line search in the usual sense. Progress along the Continuous Steepest Descent Path (CSDP) is governed both by the decrease in the function value and measures of accuracy of a local quadratic model. Numerical results on specially constructed test problems and a number of standard test problems from CUTEr [38] show that the approaches we have considered are more promising when compared with routines in the optimization tool box of MATLAB [46], namely the trust region method and the quasi-Newton method. In particular, they perform well in comparison with the, superficially similar, gradient-flow method proposed by Behrman [7].

Les processeurs multi-cœurs sont considérés de nos jours comme l'avenir des calculateurs et auront un impact important dans le calcul scientifique. Cette thèse présente une nouvelle approche de résolution des grands systèmes linéaires creux et denses, qui soit adaptée à l'exécution sur les futurs machines pétaflopiques et en particulier celles ayant un nombre important de cœurs. Compte tenu du coût croissant des communications comparé au temps dont les processeurs mettent pour effectuer les opérations arithmétiques, notre approche adopte le principe de minimisation des communications au prix de quelques calculs redondants et utilise plusieurs adaptations pour atteindre de meilleures performances sur les machines multi-cœurs. Nous décomposons le problème à résoudre en plusieurs phases qui sont ensuite mises en œuvre séparément. Dans la première partie, nous présentons un algorithme basé sur le partitionnement d'hypergraphe qui réduit considérablement le remplissage ("fill-in") induit lors de la factorisation LU des matrices creuses non symétriques. Dans la deuxième partie, nous présentons deux algorithmes de réduction de communication pour les factorisations LU et QR qui sont adaptés aux environnements multi-cœurs. La principale contribution de cette partie est de réorganiser les opérations de la factorisation de manière à réduire la sollicitation du bus tout en utilisant de façon optimale les ressources. Nous étendons ensuite ce travail aux clusters de processeurs multi-cœurs. Dans la troisième partie, nous présentons une nouvelle approche d'ordonnancement et d'optimisation. La localité des données et l'équilibrage des charges représentent un sérieux compromis pour le choix des méthodes d'ordonnancement. Sur les machines NUMA par exemple où la localité des données n'est pas une option, nous avons observé qu'en présence de perturbations systèmes (" OS noise"), les performances pouvaient rapidement se dégrader et devenir difficiles à prédire. Pour cela, nous présentons une approche combinant un ordonnancement statique et dynamique pour ordonnancer les tâches de nos algorithmes. Nos résultats obtenues sur plusieurs architectures montrent que tous nos algorithmes sont efficaces et conduisent à des gains de performances significatifs. Nous pouvons atteindre des améliorations de l'ordre de 30 à 110% par rapport aux correspondants de nos algorithmes dans les bibliothèques numériques bien connues de la littérature. / Multicore processors are considered to be nowadays the future of computing, and they will have an important impact in scientific computing. In this thesis, we study methods and algorithms for solving efficiently sparse and dense large linear systems on future petascale machines and in particular these having a significant number of cores. Due to the increasing communication cost compared to the time the processors take to perform arithmetic operations, our approach embrace the communication avoiding algorithm principle by doing some redundant computations and uses several adaptations to achieve better performance on multicore machines.We decompose the problem to solve into several phases that would be then designed or optimized separately. In the first part, we present an algorithm based on hypergraph partitioning and which considerably reduces the fill-in incurred in the LU factorization of sparse unsymmetric matrices. In the second part, we present two communication avoiding algorithms that are adapted to multicore environments. The main contribution of this part is to reorganize the computations such as to reduce bus contention and using efficiently resources. Then, we extend this work for clusters of multi-core processors. In the third part, we present a new scheduling and optimization approach. Data locality and load balancing are a serious trade-off in the choice of the scheduling strategy. On NUMA machines for example, where the data locality is not an option, we have observed that in the presence of noise, performance could quickly deteriorate and become difficult to predict. To overcome this bottleneck, we present an approach that combines a static and a dynamic scheduling approach to schedule the tasks of our algorithms.Our results obtained on several architectures show that all our algorithms are efficient and lead to significant performance gains. We can achieve from 30 up to 110% improvement over the corresponding routines of our algorithms in well known libraries.

La mémoire est considérée comme étant gloutonne en consommation d'énergie, un problème sensible, particulièrement dans les systèmes embarqués. L'optimisation globale de fonctions multimodales est également un problème délicat à résoudre du fait de la grande quantité d'optima locaux de ces fonctions. Dans ce mémoire, je présente différents nouveaux algorithmes hybrides et distribués afin de résoudre ces deux problèmes d'optimisation. Ces algorithmes sont comparés avec les méthodes classiques utilisées dans la littérature et les résultats obtenus sont encourageants. En effet, ces résultats montrent une réduction de la consommation d'énergie en mémoire d'environ 76% jusqu'à plus de 98% sur nos programmes tests, d'une part. D'autre part, dans le cas de l'optimisation globale de fonctions multimodales, nos algorithmes hybrides convergent plus souvent vers la solution optimale globale. Des versions distribuées et coopératives de ces nouveaux algorithmes hybrides sont également proposées. Elles sont, par ailleurs, plus rapides que leurs versions séquentielles respectives. / Résumé en anglais : Memory is considered to be greedy in energy consumption, a sensitive issue, especially in embedded systems. The global optimization of multimodal functions is also a difficult problem because of the large number of local optima of these functions. In this thesis report, I present various new hybrid and distributed algorithms to solve these two optimization problems. These algorithms are compared with conventional methods used in the literature and the results obtained are encouraging. Indeed, these results show a reduction in memory energy consumption by about 76% to more than 98% on our benchmarks on one hand. On the other hand, in the case of global optimization of multimodal functions, our hybrid algorithms converge more often to the global optimum solution. Distributed and cooperative versions of these new hybrid algorithms are also proposed. They are more faster than their respective sequential versions.

Cette thèse essaie d'apporter une solution au problème de l'automatisation de la production des générateurs de code. Elle propose une méthode formelle de génération basée sur une séparation nette entre les algorithmes de génération et les données relatives a la machine cible. Réservation d'un système capable de créer, a partir d'une description de la machine cible, un générateur de code basé sur cette méthode

Une grande variété de produits vendus, notamment de télécommunication et multimédia, proposent des fonctionnalités de plus en plus avancées. Celles-ci induisent une augmentation de la complexité de conception. Pour satisfaire un budget de performance et de consommation d'énergie, ces fonctionnalités peuvent être accélérées par l'utilisation d'accélérateurs matériels dédiés. Pour respecter les délais nécessaires de mise sur le marché et le prix de développement, les méthodes traditionnelles de conception de matériel ne sont plus suffisantes et l'utilisation d'outils de synthèse de haut niveau (HLS) est une alternative intéressante. Ces outils sont maintenant plus aboutis et permettent de générer des accélérateurs matériels possédant une structure interne optimisée, grâce à des techniques d'ordonnancement efficaces, de partage des ressources et de génération de machines d'états. Cependant, les interfacer avec le monde extérieur, c'est-à-dire intégrer des accélérateurs matériels générés automatiquement dans une conception complète, avec des communications optimisées pour atteindre le meilleur débit, reste une tâche très ardue, réservée aux concepteurs experts. Le leitmotiv de cette thèse était d'étudier et d'élaborer des stratégies source-à-source pour améliorer la conception de ces interfaces, en essayant d'envisager l'outil HLS comme back-end pour des transformations front-end plus avancées. Dans la première partie de la thèse, comme étude de cas, nous avons conçu à la main, en VHDL, une logique intelligente permettant l'interfaçage d'un accélérateur, calculant la multiplication de deux matrices, généré par l'outil de synthèse MMAlpha. En utilisant des informations sur les dépendances de données, nous avons implanté des techniques de double tampon et de calcul/transfert par bloc (pavage), pour des mémoires locales SRAM de type scratchpad, pour améliorer la réutilisation des données. Ceci a permis d'augmenter de manière significative les performances du système, mais a également exigé un effort important de développement. Nous avons ensuite montré, sur plusieurs applications de type multimédia, avec un autre outil de HLS, Spark, que le même avantage pouvait être obtenu avec une étape préliminaire semi-automatique de transformations source-à-source (ici de C vers C). Pour cela, nous avons utilisé le front-end d'un compilateur avancé, basé sur le compilateur Open64 et l'outil WRaP-IT de transformations polyédriques. Des améliorations significatives ont été présentées, en particulier pour la synthèse de la conversion de l'espace couleur (extrait d'un benchmark de MediaBench II), dont les données étaient transmises via une mémoire cache. Cette étude a démontré l'importance des transformations des boucles comme étape de pré-traitement pour les outils HLS, mais aussi la difficulté de les utiliser en fonction des caractéristiques de l'outil HLS pour exprimer les communications externes. Dans la deuxième partie de la thèse, en utilisant l'outil C2H HLS d'Altera qui peut synthétiser des accélérateurs matériels communiquant avec une mémoire externe DDR-SDRAM, nous avons montré qu'il était possible de restructurer automatiquement le code de l'application, de générer des processus de communication adéquats, écrits entièrement en C, et de les compiler avec C2H, afin que l'application résultante soit hautement optimisée, avec utilisation maximale de la bande passante mémoire. Ces transformations et optimisations, qui combinent des techniques telles que l'utilisation de double tampon, la contraction de tableaux, le pavage, le pipeline logiciel, entre autres, ont été intégrées dans un outil de transformation automatique source-à-source, appelé Chuba et basé sur la représentation du modèle polyédrique. Notre étude montre que ainsi qu'il est possible d'utiliser certains outils HLS comme des optimiseurs de niveau back-end pour les optimisations effectuées au niveau front-end, comme c'est le cas pour la compilation standard où des transformations de haut niveau sont développées en amont des optimiseurs au niveau assembleur. Nous pensons que ceci est la voie à suivre pour que les outils HLS deviennent viables.

Ce travail de recherche est réalisé dans le cadre d'une collaboration internationale entre l'Université Technique de Cluj-Napoca en Roumanie et l'Ecole Centrale de Lille en France. Cette thèse a comme premier objectif, de réduire l’ondulation de couple d’une machine triphasée 6/8 à réluctance variable grâce aux paramètres de contrôle dans le mode de fonctionnement moteur et générateur. Par conséquent, un modèle analytique a été développé et mis en œuvre dans un environnement de calcul numérique. Un outil d'optimisation permettant de trouver les meilleurs paramètres de contrôle a été utilisé. Toutefois, le processus d’optimisation est très lent.En conséquence, une stratégie pour réduire le temps du processus d'optimisation sans abaisser la précision des résultats est proposée. Une stratégie de ‘mapping’ est utilisée entre un modèle grossier mais rapide et un modèle fin mais lent. Un travail est mené sur le choix du modèle grossier, dans le cadre d’un modèle fournissant des valeurs en fonction du temps. Deux stratégies de ‘mapping’ ont été utilisées dans cette thèse : l’‘Output Space Mapping Proportional’(OSMP) et le Manifold Mapping (MM). Ces deux stratégies sont utilisées pour déterminer les paramètres de contrôle optimaux. Le problème d’optimisation est ensuite complété en ajoutant des variables géométriques au processus d’optimisation du contrôle. Les outils développés sont ensuite utilisés dans le cadre du dimensionnement par optimisation d’un alterno-démarreur automobile. Finalement, des expériences et des essais sur un prototype de Machine à RV sont menés afin de valider les résultats du processus d'optimisation en mode moteur et générateur. / The switched reluctance machine has a simple construction making it cheaper in execution but one of the drawbacks of this machine is the torque ripple. This thesis had as first target, the usage of an optimization tool to calculate the best control parameters to correct this major drawback in motor and generator operation modes. Hence, an analytical model that takes into account the machine geometry and that is able to be simulated in both operation modes by adjusting the commutation angles was provided and implemented in a calculation environment. The second target of this work is to investigate a method to reduce the optimization time without lowering the accuracy of the results. The strategy used in the optimization process is known in literature as the space mapping technique, more precisely for this thesis output space mapping proportional and manifold mapping were studied. After testing them on a mathematical model it was possible to continue the investigation on defining the optimal control parameters of a three-phases 6/8 SR machine prototype, being able that further to use this strategy in a much complicated process, i.e. defining the right geometry and control of a SR machine to be used in automotive integrated starter alternator systems. The final target of the thesis was to conduct experiments and tests on the existing prototype in order to partially validate the results of the optimization process.

Les travaux de cette thèse portent sur les prédérivées d'applications multivoques et la théorie de l'optimisation. Dans un premier temps, nous établissons des résultats d'existence de différents types de prédérivées pour certaines classes d'applications. Spécialement, pour des applications multivoques possédant certaines propriétés de convexité. Par la suite, nous appliquons ces résultats dans le cadre de la théorie de l'optimisation multivoque en établissant des conditions nécessaires et des conditions suffisantes d'optimalité. Sous des hypothèses de convexité, nous établissons des résultats naturels propres aux minimiseurs en optimisation convexe. Ensuite, nous appliquons quelques uns de nos résultats théoriques à un modèle de l'économie du bien-être en établissant notamment une équivalence entre les allocations optimales faibles de Pareto du modèle économique et les minimiseurs faibles d'un problème d'optimisation multivoque associé. D'autre part, en utilisant certaines notions d'intérieur généralisé existant dans la littérature, nous discutons dans un cadre unifié divers concepts de minimiseurs relaxés. En vue d'étudier leur stabilité, nous introduisons une topologie sur des espaces vectoriels ordonnés dont découle une notion de convergence nous permettant de définir deux concepts de convergence variationnelle qui sont ensuite utilisés pour établir la stabilité supérieure et la stabilité inférieure des ensembles de minimiseurs relaxés considérés dans ce travail. / This work is devoted to the study of prederivatives of set-valued maps and the theory of optimization. First, we establish results regarding the existence of several kinds of prederivatives for some classes set-valued maps. Specially for set-valued maps enjoying convexity properties. Subsequently, we apply our results in the framework of set optimization by establishing both necessary and sufficient optimality conditions, involving such prederivatives, for set optimization problems. Under convexity assumptions, we prove some natural results fitting the paradigm of minimizers in convex optimization. Then, we apply some of our theoretical results to a model of welfare economics by establishing in particular an equivalence between the weak Pareto optimal allocations of the model and the weak minimizes of a set optimization problem associated. Taking adventadge of several generalized interiority notions existing in the literature, we discuss in a unified way corresponding notions of relaxed minimizers In order to establish stability results, we introduce a topology on vector ordered spaces from which we derive a concept of convergence that we use to define two concepts of variational convergence that allow us to study both the upper and the lower stability of sets of relaxed minimizers we consider.

L'industrie a des besoins croissants en systèmes dits intelligents, capable d'analyserles signaux acquis par des capteurs et prendre une décision en conséquence. Cessystèmes sont particulièrement utiles pour des applications de vidéo-surveillanceou de contrôle de qualité. Pour des questions de coût et de consommation d'énergie,il est souhaitable que la prise de décision ait lieu au plus près du capteur. Pourrépondre à cette problématique, une approche prometteuse est d'utiliser des méthodesdites bio-inspirées, qui consistent en l'application de modèles computationels issusde la biologie ou des sciences cognitives à des problèmes industriels. Les travauxmenés au cours de ce doctorat ont consisté à choisir des méthodes d'extractionde caractéristiques bio-inspirées, et à les optimiser dans le but de les implantersur des plateformes matérielles dédiées pour des applications en vision par ordinateur.Tout d'abord, nous proposons un algorithme générique pouvant être utilisés dans différentscas d'utilisation, ayant une complexité acceptable et une faible empreinte mémoire.Ensuite, nous proposons des optimisations pour une méthode plus générale, baséesessentiellement sur une simplification du codage des données, ainsi qu'une implantationmatérielle basées sur ces optimisations. Ces deux contributions peuvent par ailleurss'appliquer à bien d'autres méthodes que celles étudiées dans ce document. / Industry has growing needs for so-called “intelligent systems”, capable of not only ac-quire data, but also to analyse it and to make decisions accordingly. Such systems areparticularly useful for video-surveillance, in which case alarms must be raised in case ofan intrusion. For cost saving and power consumption reasons, it is better to perform thatprocess as close to the sensor as possible. To address that issue, a promising approach isto use bio-inspired frameworks, which consist in applying computational biology modelsto industrial applications. The work carried out during that thesis consisted in select-ing bio-inspired feature extraction frameworks, and to optimize them with the aim toimplement them on a dedicated hardware platform, for computer vision applications.First, we propose a generic algorithm, which may be used in several use case scenarios,having an acceptable complexity and a low memory print. Then, we proposed opti-mizations for a more global framework, based on precision degradation in computations,hence easing up its implementation on embedded systems. Results suggest that whilethe framework we developed may not be as accurate as the state of the art, it is moregeneric. Furthermore, the optimizations we proposed for the more complex frameworkare fully compatible with other optimizations from the literature, and provide encourag-ing perspective for future developments. Finally, both contributions have a scope thatgoes beyond the sole frameworks that we studied, and may be used in other, more widelyused frameworks as well.

This project describes a concept of a library architecture that will enable to hide platform-specific behaviour of different MCUs under an united API that will enable the developers to develop portable applications. After a short summary of the current situation, the report describes the main principles of the library-to-be followed by definitions of behaviour of each module that can be controlled using the library. Then this report describes techniques used in the implementation and platform specifics. In the conclusion there is an idea of the direction in which the development could continue.

Sur des architectures récentes, un programme numérique peut donner des réponses différentes en fonction du hardware et du compilateur. Ces incohérences des résultats viennent du fait que chaque calcul en virgule flottante est effectué avec des précisions différentes. Le but de cette thèse est de prouver formellement des propriétés des programmes opérant sur des nombres flottants en prenant en compte l’architecture et le compilateur. Pour le faire, nous avons proposé deux approches différentes. La première approche est de prouver des propriétés des programmes en virgule flottante qui sont vraies sur plusieurs architectures et compilateurs. Cette approche ne considère que les erreurs d’arrondi qui doivent être validées quels que soient l’environnement matériel et le choix du compilateur. Elle est implantée dans la plate-forme Frama-C pour l’analyse statique de code C. La deuxième approche consiste à prouver des propriétés des programmes en analysant leur code assembleur. Nous nous concentrons sur des problèmes et des pièges qui apparaissent sur des calculs en virgule flottante. L’analyse directe du code assembleur nous permet de considérer des caratéristiques dépendant de l’architecture ou du compilateur telle que l’utilisation des registres en précision étendue. Cette approche est implantée comme une sur-couche de la plate-forme Why pour la vérification déductive. / On some recently developed architectures, a numerical program may give different answers depending on the execution hardware and the compilation. These discrepancies of the results come from the fact that each floating-point computation is calculated with different precisions. The goal of this thesis is to formally prove properties about numerical programs while taking the architecture and the compiler into account. In order to do that, we propose two different approaches. The first approach is to prove properties of floating-point programs that are true for multiple architectures and compilers. This approach states the rounding error of each floating-point computation whatever the environment and the compiler choices. It is implemented in the Frama-C platform for static analysis of C code. The second approach is to prove behavioral properties of numerical programs by analyzing their compiled assembly code. We focus on the issues and traps that may arise on floating-point computations. Direct analysis of the assembly code allows us to take into account architecture- or compiler-dependent features such as the possible use of extended precision registers. It is implemented above the Why platform for deductive verification