L'intérêt croissant pour les technologies Web génère de nouveaux défis. Le format XML s'est imposé comme une référence pour le stockage et l'échange de données. Certains documents XML ont acquis une taille telle, qu'il est inefficace voire impossible de les stocker en mémoire centrale. Cela amène à repenser les algorithmes prévus pour traiter ces documents. Une solution consiste à considérer un document XML comme un flux, qui correspond à une lecture unidirectionnelle de ce document. Ce flux est alors traité à la volée. Ainsi le document n'est jamais stocké en mémoire centrale, et uniquement les parties utiles y sont mémorisées. L'un des traitements effectués sur les fichiers XML est la sélection d'information par des requêtes. Ceci constitue une étape de base pour la transformation de documents XML, permettant ainsi à des applications utilisant différents schémas XML d'échanger des informations. Cette thèse étudie l'évaluation de requêtes sur des flux XML. Deux formalismes de requêtes sont considérés· le standard XPath, et les automates d'arbres Pour cela, une mesure de la faculté d'une requête à être évaluée sur des flux XML est introduite. A l'aune de cette mesure, les requêtes XPath et par automates ne sont pas adaptées à une évaluation de flux XML. Pour chacun des deux formalismes de requêtes, de larges fragments adaptés à ce type d'évaluation sont définis et étudiés. Pour les requêtes par automates d'arbres, deux autres critères liés à l'évaluation de flux XML sont montrés décidables en temps polynomial / The growing interest for Web technologies leads to new challenges. XML is now a reference for storing and exchanging data. Some XML documents are now so large, that il is inefficient or even impossible to store them in main memory. This calls for new paradigms to treat these data. One of them consists in considering an XML document as a stream, corresponding to a one-way reading of this document. This stream is then processed on-the-f1y. Hence the document is never stored in main memory, and only the useful parts are memorized. One task of XML processing is to retrieve information, using queries. This is the base step for XML document transformation, that allows applications using distinct XML schemas to exchange data. This thesis studies the query answering problem on XML streams. Two query classes are considered: the XPath standard, and tree automata. For this purpose, a measure of streamability of a query is introduced. This one shows that queries defined by XPath expressions or tree automata are not streamable. For both query formalisms, large streamable fragments are introduced and studied. For queries defined by tree automata, Iwo other streamability criteria are proved to be decidable in polynomial time.

Au cours de ces dernières années, un nouvel environnement s'est développé dans lequel les données doivent être collectées et traitées instantanément dès leur arrivée. La gestion de cette volumétrie nécessite la mise en place d'un nouveau modèle et de nouvelles techniques de traitements de l'information. Il s'agit du traitement des flux de données. Ces derniers ont la particularité d'être continus, évolutifs, volumineux et ne peuvent être stockés, dans leur intégralité, en tant que données persistantes. Plusieurs travaux de recherche se sont intéressés à cette problématique ce qui a engendré l'apparition des systèmes de gestion de flux de données (SGFD). Ces systèmes permettent d'exprimer des requêtes continues qui s'évaluent au fur et à mesure sur un flux ou sur des fenêtres (sous ensembles finis du flux). Toutefois, dans certaines applications, de nouveaux besoins peuvent apparaître après le passage des données. Dans ce cas, le système ne peut répondre aux requêtes posées car toutes les données n'appelant aucun traitement sont définitivement perdues. Il est ainsi nécessaire de conserver un résumé du flux de données. De nombreux algorithmes de résumé ont été développés. Le choix d'une méthode de résumé particulière dépend de la nature des données à traiter et de la problématique à résoudre. Dans ce manuscrit, nous nous intéressons en premier lieu à l'élaboration d'un résumé généraliste permettant de créer un compromis entre la vitesse de construction du résumé et la qualité du résumé conservé. Nous présentons une nouvelle approche de résumé qui se veut performance face à des requêtes portant sur des données du passé lointain. Nous nous focalisons par la suite sur l'exploitation et l'accès aux évènements du flux conservés dans ces résumés. Notre objectif consiste à intégrer les structures de résumés généralistes dans l'architecture des SGFD existantes de façon à étendre le champ de requêtes possibles. A cet effet, l'évaluation des requêtes qui font appel aux données du passé lointain d'un flux (i.e. données expirées de la mémoire du SGFD) serait possible au même titre que les requêtes posées sur le passé proche d'un flux de données. Nous présentons deux approches permettant d'atteindre cet objectif. Ces approches se différencient par le rôle que détient le module de résumé lors de l'évaluation d'une requêtes.

Ces dernières années ont vu apparaître de nombreuses applications traitant des données générées en continu et à de grandes vitesses. Ces données sont désormais connues sous le nom de flux de données. Leurs quantités de données potentiellement infinies ainsi que les contraintes qui en dérivent posent de nombreux problèmes de traitement. Parmi ces contraintes, citons par exemple l'impossibilité de bloquer un flux de données, ou encore le besoin de produire des résultats en temps réel. Néanmoins, les multiples domaines d'application de ces traitements (comme les transactions bancaires, l'usage du Web, la surveillance des réseaux, etc) ont suscité beaucoup d'intérêt tant dans les milieux industriels qu'académiques. Ces quantités potentiellement infinies de données interdisent tout espoir de stockage complet ; toutefois, on a besoin de pouvoir interroger l'historique des flux. Cela a conduit au compromis des « résumés » des flux de données et des résultats « approximatifs ». Aujourd'hui, un grand nombre de méthodes propose différents types de résumés des flux de données. Mais le développement incessant de la technologie et des applications afférentes demande un développement au moins équivalent des méthodes d'analyse et de résumé. De plus, l'extraction de motifs séquentiels y est encore peu étudiée: au commencement de cette thèse, il n'existait aucune méthode d'extraction de motifs séquentiels dans les flux de données. Motivés par ce contexte, nous nous sommes intéressés à une méthode qui résume les flux de données d'une manière efficace et fiable et qui permet principalement d'en extraire des motifs séquentiels. Dans cette thèse, nous proposons l'approche CLARA (CLAssification, Résumés et Anomalies). CLARA permet d'obtenir des clusters à partir d'un flux de séquences d'itemsets, de calculer et gérer des résumés de ces clusters et d'y détecter des anomalies. Les différentes contributions détaillées dans ce mémoire concernent: - La classification non supervisée de séquences d'itemsets sous forme de flux. A notre connaissance, cette technique est la première à permettre une telle classification. - Les résumés de flux de données à l'aide de l'extraction de motifs. Les résumés de CLARA sont composés de motifs séquentiels alignés représentant les clusters associés à leur historique dans le flux. L'ensemble de ces motifs permet de résumer le flux de manière fiable à un instant t. La gestion de l'historique de ces motifs est un point essentiel dans l'analyse des flux. CLARA introduit une nouvelle gestion de la granularité temporelle afin d'optimiser cet historique. - La détection d'anomalies. Cette détection, quand elle concerne les flux, doit être rapide et fiable. En particulier, les contraintes liées aux flux interdisent de consulter l'utilisateur final pour ajuster des paramètres (une anomalie détectée trop tard peut avoir de graves conséquences). Avec CLARA, cette détection est automatique et auto-adaptative. Nous proposerons également un cas d'étude sur des données réelles, réalisé en collaboration avec Orange Labs.

Ces dernières années, sont apparues de nombreuses applications, utilisant des données en nombre potentiellement illimité, provenant de façon continue de capteurs distribués afin d'alimenter un serveur central. Les données sont utilisées à des fins de surveillance, de supervision, de déclenchement d'alarmes en temps réel, ou plus généralement à la production de synthèses d'aide à la décision à partir de plusieurs flux. Le volume des données collectées est généralement trop grand pour être entièrement stocké. Les systèmes de gestion de flux de données (SGFD) permettent de gérer facilement, et de façon générique les flux de données : les données sont traitées au fil de l'eau sans les archiver. Toutefois, dans certaines applications, on ne souhaite pas perdre complètement l'ensemble des flux de données afin de pouvoir analyser les données du passé et du présent. Il faut donc prévoir un stockage de l'historique du flux. Nous considérons dans cette thèse, un environnement distribué décrit par une collection de plusieurs capteurs distants qui envoient des flux de données numériques et unidimensionnelles à un serveur central unique. Ce dernier a un espace de stockage limité mais doit calculer des agrégats, comme des sommes ou des moyennes, à partir des données de tout sous-ensemble de capteurs et sur un large horizon temporel. Deux approches sont étudiées pour construire l'historique des flux de données :(1) Echantillonnage spatial en ne considérant qu'un échantillon aléatoire des sources qu'on observe dans le temps ; (2) Echantillonnage temporel en considérant toutes les sources mais en échantillonnant les instants observés de chaque capteur. Nous proposons une méthode générique et optimisée de construction de résumés à partir de flux de données distribués : A partir des flux de données observés à une période de temps t -1, nous déterminons un modèle de collecte de données à appliquer aux capteurs de la période t. Le calcul des agrégats se base sur l'inférence tatistique dans le cas de l'échantillonnage spatial et sur l'interpolation dans le cas de l'échantillonnage temporel. A notre connaissance, il n'existe pas de méthodes d'interpolation qui estiment les erreurs à tout instant et qui prennent en compte le flux de données ou courbe à interpoler et son intégrale. Nous proposons donc deux approches : la première se base sur le passé des courbes pour l'interpolation (approche naive) ; et la seconde utilise à un processus stochastique pour modéliser l'évolution des courbes (approche stochastique).

L'apprentissage statistique propose un vaste ensemble de techniques capables de construire des modèles prédictifs à partir d'observations passées. Ces techniques ont montré leurs capacités à traiter des volumétries importantes de données sur des problèmes réels. Cependant, de nouvelles applications génèrent de plus en plus de données qui sont seulement visibles sous la forme d'un flux et doivent être traitées séquentiellement. Parmi ces applications on citera : la gestion de réseaux de télécommunications, la modélisation des utilisateurs au sein d'un réseau social, le web mining. L'un des défis techniques est de concevoir des algorithmes permettant l'apprentissage avec les nouvelles contraintes imposées par les flux de données. Nous proposons d'abord ce problème en proposant de nouvelles techniques de résumé de flux de données dans le cadre de l'apprentissage supervisé. Notre méthode est constituée de deux niveaux. Le premier niveau utilise des techniques incrémentales de résumé en-ligne pour les flux qui prennent en compte les ressources mémoire et processeur et possèdent des garanties en termes d'erreur. Le second niveau utilise les résumés de faible taille, issus du premier niveau, pour construire le résumé final à l'aide d'une méthode supervisée performante hors-ligne. Ces résumés constituent un prétraitement qui nous permet de proposer de nouvelles versions du classifieur bayésien naïf et des arbres de décision fonctionnant en-ligne sur flux de données. Les flux de données peuvent ne pas être stationnaires mais comporter des changements de concept. Nous proposons aussi une nouvelle technique pour détecter ces changements et mettre à jour nos classifieurs.

Une tendance importante dans le domaine de l’embarqué est l’intégration de plus en plus d’éléments de calcul dans les systèmes multiprocesseurs sur puce (MPSoC). Cette tendance est due en partie aux limitations des puissances individuelles de ces éléments causées par des considérations de consommation d’énergie. Dans le même temps, en raison de leur sophistication croissante, les applications de traitement du signal ont des besoins en puissance de calcul de plus en plus dynamique. Dans la conception et le développement d’applications de traitement de signal multicoeur, l’un des principaux défis consiste à répartir efficacement les différentes tâches sur les éléments de calcul disponibles, tout en tenant compte des changements dynamiques des fonctionnalités de l’application et des ressources disponibles. Une utilisation inefficace peut conduire à une durée de traitement plus longue et/ou une consommation d’énergie plus élevée, ce qui fait de la répartition des tâches sur un système multicoeur une tâche difficile à résoudre. Les modèles de calcul (MoC) flux de données sont communément utilisés dans la conception de systèmes de traitement du signal. Ils décomposent la fonctionnalité de l’application en acteurs qui communiquent exclusivement par l’intermédiaire de canaux. L’interconnexion des acteurs et des canaux de communication est modélisée et manipulée comme un graphe orienté, appelé un graphique de flux de données. Il existe différents MoCs de flux de données qui offrent différents compromis entre la prédictibilité et l’expressivité. Ces modèles de calculs sont communément utilisés dans la conception de systèmes de traitement du signal en raison de leur analysabilité et leur expressivité naturelle du parallélisme de l’application. Dans cette thèse, une nouvelle méthode de répartition de tâches est proposée afin de répondre au défi que propose la programmation multicoeur. Cette méthode de répartition de tâches prend ses décisions en temps réel afin d’optimiser le temps d’exécution global de l’application. Les applications sont décrites en utilisant le modèle paramétrée et interfacé flux de données (PiSDF). Ce modèle permet de décrire une application paramétrée en autorisant des changements dans ses besoins en ressources de calcul lors de l’exécution. A chaque exécution, le modèle de flux de données paramétré est déroulé en un modèle intermédiaire faisant apparaitre toute les tâches de l’application ainsi que leurs dépendances. Ce modèle est ensuite utilisé pour répartir efficacement les tâches de l’application. La méthode proposé a été testée et validé sur plusieurs applications des domaines de la vision par ordinateur, du traitement du signal et du multimédia. / An important trend in embedded processing is the integration of increasingly more processing elements into Multiprocessor Systemson- Chip (MPSoC). This trend is due in part to limitations in processing power of individual elements that are caused by power consumption considerations. At the same time, signal processing applications are becoming increasingly dynamic in terms of their hardware resource requirements due to the growing sophistication of algorithms to reach higher levels of performance. In design and implementation of multicore signal processing systems, one of the main challenges is to dispatch computational tasks efficiently onto the available processing elements while taking into account dynamic changes in application functionality and resource requirements. An inefficient use can lead to longer processing times and higher energy consumption, making multicore task scheduling a very difficult problem to solve. Dataflow process network Models of Computation (MoCs) are widely used in design of signal processing systems. It decomposes application functionality into actors that communicate data exclusively through channels. The interconnection of actors and communication channels is modeled and manipulated as a directed graph, called a dataflow graph. There are different dataflow MoCs which offer different trade-off between predictability and expressiveness. These MoCs are widely used in design of signal processing systems due to their analyzability and their natural parallel expressivity. In this thesis, we propose a novel scheduling method to address multicore scheduling challenge. This scheduling method determines scheduling decisions strategically at runtime to optimize the overall execution time of applications onto heterogeneous multicore processing resources. Applications are described using the Parameterized and Interfaced Synchronous DataFlow (PiSDF) MoC. The PiSDF model allows describing parameterized application, making possible changes in application’s resource requirement at runtime. At each execution, the parameterized dataflow is then transformed into a locally static one used to efficiently schedule the application with an a priori knowledge of its behavior. The proposed scheduling method have been tested and benchmarked on multiple state-of-the-art applications from computer vision, signal processing and multimedia domains.

Le travail de recherche exposé dans cette thèse concerne le développement d'approches à base de growing neural gas (GNG) pour le clustering de flux de données massives. Nous proposons trois extensions de l'approche GNG : séquentielle, distribuée et parallèle, et une méthode hiérarchique; ainsi qu'une nouvelle modélisation pour le passage à l'échelle en utilisant le paradigme MapReduce et l'application de ce modèle pour le clustering au fil de l'eau du jeu de données d'assurance. Nous avons d'abord proposé la méthode G-Stream. G-Stream, en tant que méthode "séquentielle" de clustering, permet de découvrir de manière incrémentale des clusters de formes arbitraires et en ne faisant qu'une seule passe sur les données. G-Stream utilise une fonction d'oubli an de réduire l'impact des anciennes données dont la pertinence diminue au fil du temps. Les liens entre les nœuds (clusters) sont également pondérés par une fonction exponentielle. Un réservoir de données est aussi utilisé an de maintenir, de façon temporaire, les observations très éloignées des prototypes courants. L'algorithme batchStream traite les données en micro-batch (fenêtre de données) pour le clustering de flux. Nous avons défini une nouvelle fonction de coût qui tient compte des sous ensembles de données qui arrivent par paquets. La minimisation de la fonction de coût utilise l'algorithme des nuées dynamiques tout en introduisant une pondération qui permet une pénalisation des données anciennes. Une nouvelle modélisation utilisant le paradigme MapReduce est proposée. Cette modélisation a pour objectif de passer à l'échelle. Elle consiste à décomposer le problème de clustering de flux en fonctions élémentaires (Map et Reduce). Ainsi de traiter chaque sous ensemble de données pour produire soit les clusters intermédiaires ou finaux. Pour l'implémentation de la modélisation proposée, nous avons utilisé la plateforme Spark. Dans le cadre du projet Square Predict, nous avons validé l'algorithme batchStream sur les données d'assurance. Un modèle prédictif combinant le résultat du clustering avec les arbres de décision est aussi présenté. L'algorithme GH-Stream est notre troisième extension de GNG pour la visualisation et le clustering de flux de données massives. L'approche présentée a la particularité d'utiliser une structure hiérarchique et topologique, qui consiste en plusieurs arbres hiérarchiques représentant des clusters, pour les tâches de clustering et de visualisation. / The research outlined in this thesis concerns the development of approaches based on growing neural gas (GNG) for clustering of data streams. We propose three algorithmic extensions of the GNG approaches: sequential, distributed and parallel, and hierarchical; as well as a model for scalability using MapReduce and its application to learn clusters from the real insurance Big Data in the form of a data stream. We firstly propose the G-Stream method. G-Stream, as a “sequential" clustering method, is a one-pass data stream clustering algorithm that allows us to discover clusters of arbitrary shapes without any assumptions on the number of clusters. G-Stream uses an exponential fading function to reduce the impact of old data whose relevance diminishes over time. The links between the nodes are also weighted. A reservoir is used to hold temporarily the distant observations in order to reduce the movements of the nearest nodes to the observations. The batchStream algorithm is a micro-batch based method for clustering data streams which defines a new cost function taking into account that subsets of observations arrive in discrete batches. The minimization of this function, which leads to a topological clustering, is carried out using dynamic clusters in two steps: an assignment step which assigns each observation to a cluster, followed by an optimization step which computes the prototype for each node. A scalable model using MapReduce is then proposed. It consists of decomposing the data stream clustering problem into the elementary functions, Map and Reduce. The observations received in each sub-dataset (within a time interval) are processed through deterministic parallel operations (Map and Reduce) to produce the intermediate states or the final clusters. The batchStream algorithm is validated on the insurance Big Data. A predictive and analysis system is proposed by combining the clustering results of batchStream with decision trees. The architecture and these different modules from the computational core of our Big Data project, called Square Predict. GH-Stream for both visualization and clustering tasks is our third extension. The presented approach uses a hierarchical and topological structure for both of these tasks.

L'accroissement rapide de la puissance des calculateurs actuels et leur interconnexion en grappes et grilles de calcul à l'aide de réseaux rapides, permettent d'envisager, en mode de production, l'utilisation de plusieurs codes de calculs numériques couplés pour la simulation de phénomènes physiques plus complexes. Dans le but d'obtenir des résultats toujours plus précis, un nouveau type de simulation numérique, dont l'objectif est de simuler plusieurs<br />physiques en même temps, est apparu. Ce type d'application est appelé "couplage de code". En effet, plusieurs codes (physiques) sont couplés ou interconnectés an qu'ils communiquent pour réaliser la simulation.<br />Cette thèse s'intéresse aux problématiques liées au couplage à hautes performances de codes parallèles et distribués. L'obtention des performances repose sur la conception d'applications distribuées dont certains composants sont parallélisés et dont les communications sont efcaces. L'idée de bas de cette thèse est d'utiliser un langage de programmation parallèle orienté flot de données (ici Athapascan) dans deux modèles de conception d'applications distribuées ; "modèle appel de procédure à distance (RPC)" et "modèle orienté flux de données (stream-oriented)". Les contributions apportées par ce travail de recherche sont les suivants :<br /><br />- Utilisation d'un langage de flot de données dans un grille RPC de calcul ;<br />Dans le cadre de projet HOMA, les extensions au modèle RPC ont porté d'une part sur la sémantique de contrôle et de communication et d'autre part sur les supports exécutifs pour mieux exploiter le parallélisme. Les résultats théoriques de ces extensions pour une implantation sur le bus logiciel CORBA à l'aide du moteur exécutif KAAPI d'Athapascan et pour l'architecture homogène comme grappe de PC, sont présentés sous la forme d'un modèle de coût d'exécution. Les expériences (élémentaires et sur une application réelle) ont validé ce modèle de coût.<br /><br />- Extension d'un modèle mémoire partagée pour couplage de codes ;<br />An d'étendre la sémantique d'accès aux données partagées du langage Athapascan, nous avons proposé la notion de "collection temporelle". Ce concept permet de décrire la sémantique d'accès de type flux de données. La "collection spatiale" permet de mieux exploiter les données parallèles. Pour préciser la sémantique associée à ces nouvelles notions, nous avons donné une nouvelle définition pour la donnée partagée. Puis dans le cadre de cette définition, nous avons défini trois types de données partagées ; "séquentielle", "collection temporelle" et "collection spatiale".

Face au défi que représente la programmation des architectures multi-cœurs/processeurs, il est devenu nécessaire de proposer aux développeurs des outils adaptés permettant d'abstraire les notions inhérentes au parallélisme et facilitant le portage d'une application sur différentes architectures. La méthodologie AAA (Adéquation Algorithme Architecture) propose au développeur d'automatiser les étapes de partitionnement, ordonnancement à partir d'une description haut niveau de l'application et de l'architecture. Cette méthodologie permet donc le prototypage rapide d'une application sur différentes architectures avec un minimum d'effort et un résultat approchant l'optimal. Les apports de cette thèse se situent à la fois au niveau du modèle de spécification et de ses optimisations relatives au contexte des architectures parallèles. Le modèle flux de données répond aux problèmes de modélisation des applications fortement synchronisées par les données. Le sous-ensemble SDF (Synchronous Data Flow), limite l'expressivité du modèle mais apporte un complément d'information permettant une optimisation efficace et garantissant l'intégrité du calcul dans tous les contextes. Les travaux développés dans ce mémoire introduisent un nouveau modèle de hiérarchie dans SDF afin d'améliorer l'expressivité tout en préservant les propriétés du modèle initial. Ce modèle basé sur des interfaces, permet une approche plus naturelle pour le développeur accoutumé au langage C. Ce nouveau modèle apportant un complément d'information, nous proposons également un ensemble de traitement améliorant la prise en charge des motifs de répétition imbriqués. En effet le modèle de hiérarchie introduit en première partie permet la spécification de motifs dit de " nids de boucles " pouvant masquer le parallélisme potentiel. Il est donc nécessaire d'associer au modèle des traitements permettant de révéler ce parallélisme tout en préservant l'aspect factorisé du calcul. Les méthodes présentées sont adaptées du contexte des compilateurs pour supercalculateurs et de l'univers des réseaux systoliques.

Le développement d’applications de traitement du signal pour des architectures multi-coeurs embarquées est une tâche complexe qui nécessite la prise en compte de nombreuses contraintes. Parmi ces contraintes figurent les contraintes temps réel, les limitations énergétiques, ou encore la quantité limitée des ressources matérielles disponibles. Pour satisfaire ces contraintes, une connaissance précise des caractéristiques des applications à implémenter est nécessaire. La caractérisation des besoins en mémoire d’une application est primordiale car cette propriété a un impact important sur la qualité et les performances finales du système développé. En effet, les composants de mémoire d’un système embarqué peuvent occuper jusqu’à 80% de la surface totale de silicium et être responsable d’une majeure partie de la consommation énergétique. Malgré cela, les limitations mémoires restent une contrainte forte augmentant considérablement les temps de développements. Les modèles de calcul de type flux de données sont couramment utilisés pour la spécification, l’analyse et l’optimisation d’applications de traitement du signal. La popularité de ces modèles est due à leur bonne analysabilité ainsi qu’à leur prédisposition à exprimer le parallélisme des applications. L’abstraction de toute notion de temps dans les diagrammes flux de données facilite l’exploitation du parallélisme offert par les architectures multi-coeurs hétérogènes. Dans cette thèse, nous présentons une méthode complète pour l’étude des caractéristiques mémoires d’applications de traitement du signal modélisées par des diagrammes flux de données. La méthode proposée couvre la caractérisation théorique d’applications, indépendamment des architectures ciblées, jusqu’à l’allocation quasi-optimale de ces applications en mémoire partagée d’architectures multi-coeurs embarquées. L’implémentation de cette méthode au sein d’un outil de prototypage rapide permet son évaluation sur des applications récentes de vision par ordinateur, de télécommunication, et de multimédia. Certaines applications de traitement du signal au comportement très dynamique ne pouvant être modélisé par le modèle de calcul supporté par notre méthode, nous proposons un nouveau méta-modèle de type flux de données répondant à ce besoin. Ce nouveau méta-modèle permet la modélisation d’applications reconfigurables et modulaires tout en préservant la prédictibilité, la concision et la lisibilité des diagrammes de flux de données. / The development of embedded Digital Signal Processing (DSP) applications for Multiprocessor Systems-on-Chips (MPSoCs) is a complex task requiring the consideration of many constraints including real-time requirements, power consumption restrictions, and limited hardware resources. To satisfy these constraints, it is critical to understand the general characteristics of a given application: its behavior and its requirements in terms of MPSoC resources. In particular, the memory requirements of an application strongly impact the quality and performance of an embedded system, as the silicon area occupied by the memory can be as large as 80% of a chip and may be responsible for a major part of its power consumption. Despite the large overhead, limited memory resources remain an important constraint that considerably increases the development time of embedded systems. Dataflow Models of Computation (MoCs) are widely used for the specification, analysis, and optimization of DSP applications. The popularity of dataflow MoCs is due to their great analyzability and their natural expressivity of the parallelism of a DSP application. The abstraction of time in dataflow MoCs is particularly suitable for exploiting the parallelism offered by heterogeneous MPSoCs. In this thesis, we propose a complete method to study the important aspect of memory characteristic of a DSP application modeled with a dataflow graph. The proposed method spans the theoretical, architecture-independent memory characterization to the quasi-optimal static memory allocation of an application on a real shared-memory MPSoC. The proposed method, implemented as part of a rapid prototyping framework, is extensively tested on a set of state-of-the-art applications from the computer-vision, the telecommunication, and the multimedia domains. Then, because the dataflow MoC used in our method is unable to model applications with a dynamic behavior, we introduce a new dataflow meta-model to address the important challenge of managing dynamics in DSP-oriented representations. The new reconfigurable and composable dataflow meta-model strengthens the predictability, the conciseness and the readability of application descriptions.