1 |
Algorithmes SLAM : Vers une implémentation embarquée / SLAM Algorithms : Towards embedded implementationsAbouzahir, Mohamed 25 February 2017 (has links)
La navigation autonome est un axe de recherche principal dans le domaine de la robotique mobile. Dans ce contexte, le robot doit disposer des algorithmes qui lui permettent d’évoluer de manière autonome dans des environnements complexes et inconnus. Les algorithmes de SLAM permettent à un robot de cartographier son environnement tout en se localisant dans l’espace. Les algorithmes SLAM sont de plus en plus performants, mais aucune implémentation matérielle ou architecturale complète n’a eu. Une telle implantation d’architecture doit prendre en considération la consommation d’énergie, l’embarquabilité et la puissance de calcul. Ce travail scientifique vise à évaluer des systèmes embarqués impliquant de la localisation ou reconstruction de scène. La méthodologie adoptera une approche A3 (Adéquation Algorithme Architecture) pour améliorer l’efficacité de l’implantation des algorithmes plus particulièrement pour des systèmes à fortes contraintes. Le système SLAM embarqué doit disposer d’une architecture électronique et logicielle permettant d’assurer la production d’information pertinentes à partir de données capteurs, tout en assurant la localisation de l’embarquant dans son environnement. L’objectif est donc de définir, pour un algorithme choisi, un modèle d’architecture répondant aux contraintes de l’embarqué. Les premiers travaux de cette thèse ont consisté à explorer les différentes approches algorithmiques permettant la résolution du problème de SLAM. Une étude plus approfondie de ces algorithmes est réalisée. Ceci nous a permet d’évaluer quatre algorithmes de différente nature : FastSLAM2.0, ORB SLAM, RatSLAM et le SLAM linéaire. Ces algorithmes ont été ensuite évalués sur plusieurs architectures pour l’embarqué afin d’étudier leur portabilité sur des systèmes de faible consommation énergétique et de ressources limitées. La comparaison prend en compte les temps d’exécutions et la consistance des résultats. Après avoir analysé profondément les évaluations temporelles de chaque algorithme, le FastSLAM2.0 est finalement choisi, pour un compromis temps d’exécution-consistance de résultat de localisation, comme candidat pour une étude plus approfondie sur une architecture hétérogène embarquée. La second partie de cette thèse est consacré à l’étude d’un système embarqué implémentant le FastSLAM2.0 monoculaire dédié aux environnements larges. Une réécriture algorithmique du FastSLAM2.0 a été nécessaire afin de l’adapter au mieux aux contraintes imposées par les environnements de grande échelle. Dans une démarche A3, le FastSLAM2.0 a été implanté sur une architecture hétérogène CPU-GPU. Grâce à un partitionnement efficace, un facteur d’accélération global de l’ordre de 22 a été obtenu sur une architecture récente dédiée pour l’embarqué. La nature du traitement de l’algorithme FastSLAM2.0 pouvait bénéficier d’une architecture fortement parallèle. Une deuxième instance matérielle basée sur une architecture programmable FPGA est proposée. L’implantation a été réalisée en utilisant des outils de synthèse de haut-niveau afin de réduire le temps de développement. Une comparaison des résultats d’implantation sur cette architecture matérielle par rapport à des architectures à base de GPU a été réalisée. Les gains obtenus sont conséquent, même par rapport aux GPU haut-de-gamme avec un grand nombre de cœurs. Le système résultant peut cartographier des environnements larges tout en garantissant le compromis entre la consistance des résultats de localisation et le temps réel. L’utilisation de plusieurs calculateurs implique d’utiliser des moyens d’échanges de données entre ces derniers. Cela passe par des couplages forts. Ces travaux de thèse ont permis de mettre en avant l’intérêt des architectures hétérogènes parallèles pour le portage des algorithmes SLAM. Les architectures hétérogènes à base de FPGA peuvent particulièrement devenir des candidats potentiels pour porter des algorithmes complexes traitant des données massives. / Autonomous navigation is a main axis of research in the field of mobile robotics. In this context, the robot must have an algorithm that allow the robot to move autonomously in a complex and unfamiliar environments. Mapping in advance by a human operator is a tedious and time consuming task. On the other hand, it is not always reliable, especially when the structure of the environment changes. SLAM algorithms allow a robot to map its environment while localizing it in the space.SLAM algorithms are becoming more efficient, but there is no full hardware or architectural implementation that has taken place . Such implantation of architecture must take into account the energy consumption, the embeddability and computing power. This scientific work aims to evaluate the embedded systems implementing locatization and scene reconstruction (SLAM). The methodology will adopt an approach AAM ( Algorithm Architecture Matching) to improve the efficiency of the implementation of algorithms especially for systems with high constaints. SLAM embedded system must have an electronic and software architecture to ensure the production of relevant data from sensor information, while ensuring the localization of the robot in its environment. Therefore, the objective is to define, for a chosen algorithm, an architecture model that meets the constraints of embedded systems. The first work of this thesis was to explore the different algorithmic approaches for solving the SLAM problem. Further study of these algorithms is performed. This allows us to evaluate four different kinds of algorithms: FastSLAM2.0, ORB SLAM, SLAM RatSLAM and linear. These algorithms were then evaluated on multiple architectures for embedded systems to study their portability on energy low consumption systems and limited resources. The comparison takes into account the time of execution and consistency of results. After having deeply analyzed the temporal evaluations for each algorithm, the FastSLAM2.0 was finally chosen for its compromise performance-consistency of localization result and execution time, as a candidate for further study on an embedded heterogeneous architecture. The second part of this thesis is devoted to the study of an embedded implementing of the monocular FastSLAM2.0 which is dedicated to large scale environments. An algorithmic modification of the FastSLAM2.0 was necessary in order to better adapt it to the constraints imposed by the largescale environments. The resulting system is designed around a parallel multi-core architecture. Using an algorithm architecture matching approach, the FastSLAM2.0 was implemeted on a heterogeneous CPU-GPU architecture. Uisng an effective algorithme partitioning, an overall acceleration factor o about 22 was obtained on a recent dedicated architecture for embedded systems. The nature of the execution of FastSLAM2.0 algorithm could benefit from a highly parallel architecture. A second instance hardware based on programmable FPGA architecture is proposed. The implantation was performed using high-level synthesis tools to reduce development time. A comparison of the results of implementation on the hardware architecture compared to GPU-based architectures was realized. The gains obtained are promising, even compared to a high-end GPU that currently have a large number of cores. The resulting system can map a large environments while maintainingthe balance between the consistency of the localization results and real time performance. Using multiple calculators involves the use of a means of data exchange between them. This requires strong coupling (communication bus and shared memory). This thesis work has put forward the interests of parallel heterogeneous architectures (multicore, GPU) for embedding the SLAM algorithms. The FPGA-based heterogeneous architectures can particularly become potential candidatesto bring complex algorithms dealing with massive data.
|
2 |
Design and quality of service of mixed criticality systems in embedded architectures based on Network-on-Chip (NoC) / Dimensionnement et Qualité de Service pour les systèmes à criticité mixte dans les architectures embarquées à base de Network on Chip (NoC)Papastefanakis, Ermis 28 November 2017 (has links)
L'évolution de Systems-on-Chip (SoCs) est rapide et le nombre des processeurs augmente conduisant à la transition des les plates-formes Multi-core vers les Manycore. Dans telles plates-formes, l'architecture d'interconnexion a également décalé des bus traditionnels vers les Réseaux sur puce (NoC) afin de faire face à la mise en échelle. Les NoC permettent aux processeurs d'échanger des informations avec la mémoire et les périphériques lors de l'exécution d'une tâche et d'effectuer plusieurs communications en parallèle. Les plates-formes basées sur un NoC sont aussi présentes dans des systèmes embarqués, caractérisés par des exigences comme la prédictibilité, la sécurité et la criticité mixte. Afin de fournir telles fonctionnalités dans les plates-formes commerciales existantes, il faut prendre en considération le NoC qui est un élément clé ayant un impact important sur les performances d'un SoC. Une tâche échange des informations à travers du NoC et par conséquent, son temps d'exécution dépend du temps de transmission des flux qu'elle génère. En calculant le temps de transmission de pire cas (WCTT) des flux dans le NoC, une étape est faite vers le calcul du temps d'exécution de pire cas (WCET) d'une tâche. Ceci contribue à la prédictibilité globale du système. De plus, en prenant en compte les politiques d'arbitrage dans le NoC, il est possible de fournir des garanties de sécurité contre des tâches compromises qui pourraient essayer de saturer les ressources du système (attaque DoS). Dans les systèmes critiques de sécurité, une distinction des tâches par rapport à leur niveau de criticité, permet aux tâches de criticité mixte de coexister et d'exécuter en harmonie. De plus, ça permet aux tâches critiques de maintenir leurs temps d'exécution au prix de tâches de faible criticité qui seront ralenties ou arrêtées. Cette thèse vise à fournir des méthodes et des mécanismes dans le but de contribuer aux axes de prédictibilité, de sécurité et de criticité mixte dans les architectures Manycore basées sur Noc. En outre, l'incitation consiste à relever conjointement les défis dans ces trois axes en tenant compte de leur impact mutuel. Chaque axe a été étudié individuellement, mais très peu de recherche prend en compte leur interdépendance. Cette fusion des aspects est de plus en plus intrinsèque dans des domaines tels que Internet-of-Things, Cyber-Physical Systems (CPS), véhicules connectés et autonomes qui gagnent de l'élan. La raison en est leur haut degré de connectivité qui crée une grande surface d'exposition ainsi que leur présence croissante qui rend l'impact des attaques sévère et visible. Les contributions de cette thèse consistent en une méthode pour fournir une prédictibilité aux flux dans le NoC, un mécanisme pour la sécurité du NoC et une boîte à outils pour la génération de trafic utilisée pour l'analyse comparative. La première contribution est une adaptation de l'approche de la trajectoire traditionnellement utilisée dans les réseaux avioniques (AFDX) pour calculer le WCET. Dans cette thèse, nous identifions les différences et les similitudes dans l'architecture NoC et modifions l'approche de la trajectoire afin de calculer le WCTT des flux NoC. La deuxième contribution est un mécanisme qui permet de détecter les attaques de DoS et d'atténuer leur impact dans un ensemble des flux de criticité mixte. Plus précisément, un mécanisme surveille le NoC et lors de la détection d'un comportement anormal, un deuxième mécanisme d'atténuation s'active. Ce dernier applique des limites de trafic à la source et restreint le taux auquel le NoC est occupé. Cela atténuera l'impact de l'attaque, garantissant la disponibilité des ressources pour les tâches de haute criticité. Finalement NTGEN, est un outil qui peut générer automatiquement des jeux des flux aléatoires mais qui provoquent une occupation NoC prédéterminée. Ces ensembles sont ensuite injectés dans le NoC et les informations sont collectées en fonction de la latence / The evolution of Systems-on-Chip (SoCs) is rapid and the number of processors has increased transitioning from Multi-core to Manycore platforms. In such platforms, the interconnect architecture has also shifted from traditional buses to Networks-on-Chip (NoC) in order to cope with scalability. NoCs allow the processors to exchange information with memory and peripherals during task execution and enable multiple communications in parallel. NoC-based platforms are also present in embedded systems, characterized by requirements like predictability, security and mixed-criticality. In order to enable such features in existing commercial platforms it is necessary to take into consideration the NoC which is a key element with an important impact to a SoC's performance. A task exchanges information through the NoC and as a result, its execution time depends on the transmission time of the flows it generates. By calculating the Worst Case Transmission Time (WCTT) of flows in the NoC, a step is made towards the calculation of the Worst Case Execution Time (WCET) of a task. This contributes to the overall predictability of the system. Similarly by leveraging arbitration and traffic policies in the NoC it is possible to provide security guarantees against compromised tasks that might try to saturate the system's resources (DoS attack). In safety critical systems, a distinction of tasks in relation to their criticality level, allows tasks of mixed criticality to co-exist and execute in harmony. In addtition, it allows critical tasks to maintain their execution times at the cost of tasks of lower criticality that will be either slowed down or stopped. This thesis aims to provide methods and mechanisms with the objective to contribute in the axes of predictability, security and mixed criticality in NoC-based Manycore architectures. In addition, the incentive is to jointly address the challenges in these three axes taking into account their mutual impact. Each axis has been researched individually, but very little research takes under consideration their interdependence. This fusion of aspects is becoming more and more intrinsic in fields like the Internet-of-Things, Cyber-Physical Systems (CPSs), connected and autonomous vehicles which are gaining momentum. The reason being their high degree of connectivity which is creates great exposure as well as their increasing presence which makes attacks severe and visible. The contributions of this thesis consist of a method to provide predictability to a set of flows in the NoC, a mechanism to provide security properties to the NoC and a toolkit for traffic generation used for benchmarking. The first contribution is an adaptation of the trajectory approach traditionally used in avionics networks (AFDX) to calculate WCET. In this thesis, we identify the differences and similarities in NoC architecture and modify the trajectory approach in order to calculate the WCTT of NoC flows. The second contribution is a mechanism that detects DoS attacks and mitigates their impact in a mixed criticality set of flows. More specifically, a monitor mechanism will detect abnormal behavior, and activate a mitigation mechanism. The latter, will apply traffic shaping at the source and restrict the rate at which the NoC is occupied. This will limit the impact of the attack, guaranteeing resource availability for high criticality tasks. Finally NTGEN, is a toolkit that can automatically generate random sets of flows that result to a predetermined NoC occupancy. These sets are then injected in the NoC and information is collected related to latency
|
Page generated in 0.0882 seconds