Méthodologie de prototypage rapide pour systèmes embarqués parallèles : modélisation des systèmes et amélioration des heuristiques d'ordonnancement de tâches

Computer architectures have come into an era of multiprocessor for parallel computing. Modern embedded systems also tend to consist of multiple processors like multicore DSP (Digital Signal Processor) or MPSoC (Multiprocessor System-on-Chip). Meanwhile, algorithms of signal and image processing applications become more and more complicated. Implementing such applications on a parallel embedded system with multiple heterogeneous components is not straightforward. Rapid prototyping and hardware/software co-design are usually used to facilitate this work. The task scheduling problem is discussed in this thesis as an important step of rapid prototyping for developing parallel embedded systems. We aim at task scheduling models by accurately considering communications between computations. The algorithm of an application is modeled as a Directed Acyclic Graph (DAG) for task scheduling, and we propose an advanced architecture model to appropriately describe a parallel embedded system. After formalizing the task scheduling problem with the advanced architecture model, we also propose list scheduling heuristics with advanced techniques to improve the scheduling performance. Experimental results show that our methods usually accelerate an application in the case of medium or high communication. Since the communication cost is increasing in modern applications like digital communication and video compression, our advanced methods are suitable for efficiently implementing these applications on parallel embedded systems. Our methods are integrated in PREESM that is an Eclipse-based open source rapid prototyping framework.L'architecture des ordinateurs est maintenant dans l'ère des multiprocesseurs permettant le calcul en parallèle. Les systèmes embarqués les plus récents s'appuient sur plusieurs processeurs DSP (Digital Signal Processor) ou MPSoC (Multiprocessor System-on-Chip). Corrélativement, les algorithmes des applications de traitement du signal et de l'image deviennent de plus en plus sophistiqués. La mise en oeuvre de telles applications sur un système embarqué devient complexe. Aussi, les approches de prototypage rapide et de co-conception matérielle/logicielle sont souvent utilisées pour faciliter ce travail. Le problème de l'ordonnancement des tâches, étape importante du prototypage rapide, est discuté et traité dans cette thèse. Nous cherchons des modèles d'ordonnancement des tâches en considérant précisément les communications entre les tâches. Nous modélisons ainsi l'algorithme de l'application comme un graphe acyclique orienté (Directed Acyclic Graph ou DAG), et nous proposons un modèle avancé décrivant de façon appropriée l'architecture du système embarqué parallèle. Après la formalisation du problème de l'ordonnancement des tâches avec ce modèle d'architecture, nous présentons plusieurs heuristiques d'ordonnancement basées sur la méthode de la liste (list scheduling) pour améliorer les performances de l'ordonnancement. Nos résultats expérimentaux attestent d'une accélération de l'application dans un contexte de moyenne ou de forte communication. Comme le poids des communications va en croissant dans les applications les plus récentes, que ce soient en communication numérique ou en compression vidéo, nos méthodes s'avèrent efficaces dans la mise en oeuvre de ces applications sur systèmes embarqués parallèles. Nos méthodes d'ordonnancement sont intégrées dans PREESM, environnement de prototypage rapide basé sur Eclipse en "open source"