| Přispěvatelé: |
Sound Programming of Adaptive Dependable Embedded Systems (SPADES), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Laboratoire d'Informatique de Grenoble (LIG), Université Grenoble - Alpes, Pascal Fradet(Pascal.Fradet@inria.fr), Alain Girault |
| Popis: |
Dataflow Models of Computation (MoCs) are used to model stream processing applications in a concurrent fashion. Those MoCs are widely used in domains such digital signal processing, multimedia processing, telecommunications, and automatic control. In a dataflow MoC, an application is specified as a graph of actors connected by data channels. Actors model computation units consuming and producing the data flowing on channels. Actors can run concurrently and be scheduled according to different scheduling policies. One of the most popular dataflow MoCs is Synchronous Dataflow (SDF). It provides static analyses to guarantee that an application can execute in bounded memory and that no deadlock occurs during the execution. However, SDF lacks the capability to express the dynamism needed by modern streaming applications. Extensions of SDF have been proposed to be able to change the graph at runtime. However, all of those MoCs must foresee all the different graphs at design time. As a result, the number of different topologies of an application must remain small. We address this shortcoming by proposing a new MoC called Reconfigurable Dataflow (RDF). RDF extends SDF with programs that specify when and how the topology of a graph is changed at runtime. A program consists of transformation rules specifying how the toplogy is modified and conditions specifying when these reconfigurations take place. Starting from an initial RDF graph and a set of transformation rules, an arbitrary number of new RDF graphs can be generated at runtime. An RDF application can still be statically analyzed to guarantee that all possible graphs generated at runtime will execute in bounded memory without deadlocks. The impact of RDF transformation rules on the throughput and latency can also be estimated.. In this thesis, we introduce the RDF MoC, describe its static analyses and performance analyses. We also present a prototype implementation of RDF, we evaluate the reconfiguration costs and finally demonstrate the use of RDF on a case study.; Les modèles de calcul flot de données sont utilisés pour modéliser les applications de traitement de flux de façon parallèle. Ces modèles sont très utilisés dans le traitement de signal, les applications multimédia, de télécommunication ou de contrôle. Un modèle flot de données modélise une application comme un graphe d'acteurs connectés par des canaux de communication. Les acteurs sont des unités de calcul consommant et produisant des données sur leurs canaux d'entrée et de sortie. Les acteurs s'exécutent en parallèle et peuvent s'ordonnancer selon différentes politiques. Le modèle le plus connu est le modèle SDF (Synchronous DataFlow). Il permet des analyses statiques qui garantissent que les applications SDF s'exécutent en mémoire bornée et sans blocage. Un graphe SDF est statique et est spécifié une fois pour toute à la compilation. Des extensions ont été proposées pour permettent un peu de dynamisme à l'exécution. Pourtant, tous les modèles doivent prévoir l'ensemble des graphes possibles. En conséquence, le nombre de topologies différentes d'une application doit rester petit. Nous adressons ce problème en proposant un nouveau modèle de calcul nommé RDF (pour Reconfigurable DataFlow). RDF étend SDF avec des programmes spécifiant comment et quand changer la topologie à l'exécution. Un programme est composé de règles de transformation de graphe décrivant comment le graphe est modifié et de conditions spécifiant quand ces reconfigurations doivent avoir lieu. En partant d'un graphe initial et d'un petit nombre de règles de transformation, un nombre arbitraire de graphes peuvent être générés à l'exécution. Une application RDF peut toujours être analysée afin de garantir de tous les graphes générés dynamiquement s'exécuteront en mémoire bornée et sans blocage. L'impact des règles de transformation sur le débit et la latence peut également être estimé. Dans cette thèse, nous introduisons le modèle RDF, décrivons les analyses statiques de sûreté et de performance associées. Nous présentons également notre implémentation de RDF qui nous a permis d'évaluer les coûts de reconfiguration et de traiter une étude de cas. |
