Optimization of the operation of a generator of memory hierarchies for embedded vision systems

Les recherches de cette thèse portent sur la mise en oeuvre des méthodes de la rechercheopérationnelle (RO) pour la conception de circuits numériques dans le domaine du traitementdu signal et de l’image, plus spécifiquement pour des applications multimédia et de visionembarquée.Face à la problématique de “Memory Wall”, les concepteurs de systèmes de vision embarquée,Mancini et al. (Proc.DATE, 2012), ont proposé un générateur de hiérarchies mémoiresad-hoc dénommé Memory Management Optimization (MMOpt). Cet atelier de conception estdestiné aux traitements non-linéaires afin d’optimiser la gestion des accès mémoires de cestraitements. Dans le cadre de l’outil MMOpt, nous abordons la problématique d’optimisationliée au fonctionnement efficace des circuits de traitement d’image générés par MMOpt visantl’amélioration des enjeux de performance (contrainte temps-réel), de consommation d’énergieet de coût de production (contrainte d’encombrement).Ce problème électronique a été modélisé comme un problème d’ordonnancement multiobjectif,appelé 3-objective Process Scheduling and Data Prefetching Problem (3-PSDPP), reflétantles 3 principaux enjeux électroniques considérés. À notre connaissance, ce problème n’apas été étudié avant dans la littérature de RO. Une revue de l’état de l’art sur les principaux travauxliés à cette thèse, y compris les travaux antérieurs proposés par Mancini et al. (Proc.DATE,2012) ainsi qu’un bref aperçu sur des problèmes voisins trouvés dans la littérature de RO,a ensuite été faite. En outre, la complexité de certaines variantes mono-objectif du problèmed’origine 3-PSDPP a été établie. Des approches de résolution, y compris les méthodes exactes(PLNE) et les heuristiques constructives, sont alors proposées. Enfin, la performance de cesméthodes a été comparée par rapport à l’algorithme actuellement utilisé dans l’outil MMOpt,sur des benchmarks disponibles dans la littérature ainsi que ceux fournis par Mancini et al.(Proc.DATE, 2012).Les solutions obtenues sont de très bonne qualité et présentent une piste prometteuse pouroptimiser les performances des hiérarchies mémoires produites par MMOpt. En revanche, vuque les besoins de l’utilisateur de l’outil sont contradictoires, il est impossible de parler d’unesolution unique en optimisant simultanément les trois critères considérés. Un ensemble debonnes solutions de compromis entre ces trois critères a été fourni. L’utilisateur de l’outilMMOpt peut alors décider de la solution qui lui est la mieux adaptée.The research of this thesis focuses on the application of the Operations Research (OR)methodology to design new optimization algorithms to enable low cost and efficient embeddedvision systems, or more generally devices for multimedia applications such as signal and imageprocessing.The design of embedded vision systems faces the “Memory Wall” challenge regarding thehigh latency of memories holding big image data. For the case of non-linear image accesses, onesolution has been proposed by Mancini et al. (Proc. DATE 2012) in the form of a software tool,called Memory Management Optimization (MMOpt), that creates an ad-hoc memory hierarchiesfor such a treatment. It creates a circuit called a Tile Processing Unit (TPU) that containsthe circuit for the treatment. In this context, we address the optimization challenge set by theefficient operation of the circuits produced by MMOpt to enhance the 3 main electronic designcharacteristics. They correspond to the energy consumption, performance and size/productioncost of the circuit.This electronic problem is formalized as a 3-objective scheduling problem, which is called3-objective Process Scheduling and Data Prefetching Problem (3-PSDPP), reflecting the 3 mainelectronic design characteristics under consideration. To the best of our knowledge, this problemhas not been studied before in the OR literature. A review of the state of the art, including theprevious work proposed by Mancini et al. (Proc.DATE, 2012) as well as a brief overview onrelated problems found in the OR literature, is then made. In addition, the complexity of someof the mono-objective sub-problems of 3-PSDPP problem is established. Several resolutionapproaches, including exact methods (ILP) and polynomial constructive heuristics, are thenproposed. Finally, the performance of these methods is compared, on benchmarks available inthe literature, as well as those provided by Mancini et al. (Proc.DATE, 2012), against the onecurrently in use in the MMOpt tool.The results show that our algorithms perform well in terms of computational efficiency andsolution quality. They present a promising track to optimize the performance of the TPUs producedby MMOpt. However, since the user’s needs of the MMOpt tool are contradictory, such aslow cost, low energy and high performance, it is difficult to find a unique and optimal solutionto optimize simultaneously the three criteria under consideration. A set of good compromisesolutions between these three criteria was provided. The MMOpt’s user can then choose thebest compromise solution he wants or needs