Advanced digital signal processing systems require specialized high-performance embedded computer architectures. The term high-performance translates to large amounts of data and computations per time unit. The term embedded further implies requirements on physical size and power efficiency. Thus the requirements are of both functional and non-functional nature. This thesis addresses the development of high-performance digital signal processing systems relying on manycore technology. We propose building two-level hierarchical computer architectures for this domain of applications. Further, we outline a tool flow based on methods and analysis techniques for automated, multi-objective mapping of such applications on distributed memory manycore processors. In particular, the focus is put on how to provide a means for tunable strategies for mapping of task graphs on array structured distributed memory manycores, with respect to given application constraints. We argue for code mapping strategies based on predicted execution performance, which can be used in an auto-tuning feedback loop or to guide manual tuning directed by the programmer. Automated parallelization, optimisation and mapping to a manycore processor benefits from the use of a concurrent programming model as the starting point. Such a model allows the programmer to express different types and granularities of parallelism as well as computation characteristics of importance in the addressed class of applications. The programming model should also abstract away machine dependent hardware details. The analytical study of WCDMA baseband processing in radio base stations, presented in this thesis, suggests dataflow models as a good match to the characteristics of the application and as execution model abstracting computations on a manycore. Construction of portable tools further requires a manycore machine model and an intermediate representation. The models are needed in order to decouple algorithms, used to transform and map application software, from hardware. We propose a manycore machine model that captures common hardware resources, as well as resource dependent performance metrics for parallel computation and communication. Further, we have developed a multifunctional intermediate representation, which can be used as source for code generation and for dynamic execution analysis. Finally, we demonstrate how we can dynamically analyse execution using abstract interpretation on the intermediate representation. It is shown that the performance predictions can be used to accurately rank different mappings by best throughput or shortest end-to-end computation latency.

The ever-increasing functional and nonfunctional requirements in real-time safety-critical embedded systems call for new design flows that solve the specification, validation, and synthesis problems. Ensuring key properties, such as functional determinism and temporal predictability, has been the main objective of many embedded system design models. Dataflow models of computation (such as KPN, SDF, CSDF, etc.) are widely used to model stream-based embedded systems due to their inherent functional determinism. Since the introduction of the (C)SDF model, a considerable effort has been made to solve the static-periodic scheduling problem. Ensuring boundedness and liveness is the essence of the proposed algorithms in addition to optimizing some nonfunctional performance metrics (e.g. buffer minimization, throughput maximization, etc.). However, nowadays real-time embedded systems are so complex that real-time operating systems are used to manage hardware resources and host real-time tasks. Most of real-time operating systems rely on priority-driven scheduling algorithms (e.g. RM, EDF, etc.) instead of static schedules which are inflexible and difficult to maintain. This thesis addresses the real-time scheduling problem of dataflow graph specifications; i.e. transformation of the dataflow specification to a set of independent real-time tasks w.r.t. a given priority-driven scheduling policy such that the following properties are satisfied: (1) channels are bounded and overflow/underflow-free; (2) the task set is schedulable on a given uniprocessor (or multiprocessor) architecture. This problem requires the synthesis of scheduling parameters (e.g. periods, priorities, processor allocation, etc.) and channel capacities. Furthermore, the thesis considers two performance optimization problems: buffer minimization and throughput maximization.

Ce manuscrit présente une méthode de conception au niveau système reposant sur la programmation fonctionnelle typée et visant à atténuer certains des problèmes complexifiant le développement des systèmes numériques modernes, tels que leurs tailles importantes ou la grande variété des blocs les constituant. Nous proposons un ensemble de mécanismes permettant de mélanger au sein d'un même design plusieurs formalismes de description distincts («modèles de calcul») se situant potentiellement à des niveaux d'abstraction différents. De plus, nous offrons au concepteur la possibilité d'expliciter directement les paramètres explorables de chaque sous-partie du design, puis d'en déterminer des valeurs acceptables via une étape d'exploration partiellement ou totalement automatisée réalisée à l'échelle du système. Les gains qu'apportent ces stratégies nouvelles sont illustrés sur plusieurs exemples. / This work presents a novel system-level design method based on typed functional programming and aiming at mitigating some of the issues making the development of modern digital systems complex, such as their increasing sizes and the variety of their subcomponents. We propose a range of mechanisms allowing to mix within a single design several description formalisms (``models of computation''), possibly at different abstraction levels. Moreover, the designer is provided with means to directly express the explorable parameters of each part of their design, and to find acceptable values for them through a partially or totally automatic system-wide architectural exploration step. The advantages brought by those new strategies are illustrated on several examples.

Modeling is a fundamental property in today’s development of embedded systems. Models of computation enable us to describe the functionality and characteristics of a system on a higher abstraction level which gives the designer great insight in the behavior of the final implemented system at a very early stage in the design process. The ForSyDe modeling framework is based on the Model-of-computation (MoC) theory. Synchronous data-flow (SDF) is one MoC that uses actors and tokens to describe the communication and behavior of a system. Currently, the ForSyDe input modeling language exists only as a Haskell implementation and a System C implementation. The main problem is that the ForSyDe tool ecosystem is implemented across different languages without proper connections between tools. However, a framework to make such connections exists, namely the ForSyDe IO Java supporting library. In addition, any language running on the JVM can already be connected to ForSyDe IO. Hence, the thesis explores how a modeling workbench can be designed as a domain specific language (DSL) in the JVM language Groovy using the Gradle environment. Since there are many modules in the ForSyDe modeling framework, one for each MoC, this thesis targets one module: SDF. This choice is enough to explore whether it is possible to achieve the same modeling that Haskell provides in a JVM language, without sacrificing the user experience while modeling. The resulting Groovy DSL can describe the Synchronous Data-Flow MoC with the purpose of modeling SDF graphs, often used in image processing applications. By using the produced DSL workbench, a designer can model SDF applications in an efficient way. There were some differences when comparing the Groovy DSL to the Haskell implementation, such as the methods for defining actors and connecting them. However, the core modeling concepts are the same. Combining Groovy and Gradle offered an easy way of designing a DSL using the concept of closures. The created Groovy DSL is the first member of a family of textual DSL’s for describing MoC’s and therefore acts as a foundation for future work within the ForSyDe modeling framework. It can be extended to support more modules and functions or to inspire others to develop new DSL’s. / Modellering av system är en grundsten i dagens utveckling av inbyggda system. Beräkningsmodeller möjliggör att beskriva systems egenskaper och funktioner på en hög abstraktionsnivå vilket underlättar den första tiden vid utvecklingen av ett nytt inbyggt system. ForSyDe är ett modelleringsspråk baserat på beräkbarhetsteori. Det synkrona dataflödet (SDF) är en beräkningsmodell som använder sig av aktörer och tokens för att beskriva ett systems kommunikation och bettend. ForSyDe är implementerat i programmeringsspråket Haskell och System C, men är i fortsatt utveckling och grenar ut till andra språk och miljöer. Det huvudsakliga Problemet med ForSyDe är att ramverket saknar bra kopplingar mellan verktygen som erbjuds. Ett ramverk som möjliggör kopplingen mellan verktygen är stöd biblioteket ForSyDe IO och dessutom kan ett språk som kör i Javas virtuella miljö redan kopplas med ForSyDe IO. Därför undersöker uppsatsen hur ett domänspecifikt språk kan skrivas i Groovy i utvecklingsmiljön gradle för att direkt extrahera en ForSyDe IO modell utan att behöva undersöka varje element i modellen. Det finns många moduler i ForSyDe ramverket, en för varje beräkningsmodell och därför menar uppsatsen att undersöka en modul: SDF. Att undersöka SDF modulen anses tillräckligt för att bestämma sig huruvida det är möjligt att uppnå liknande modellering som Haskell erbjuder fast i java miljön, utan att offra användarvänligheten då ett system modelleras. Resultatet blev en Groovy prototyp som kan beskriva SDF-modulen med syftet att modellera SDF-grafer vars funktion ofta används inom bildbehandling. En SDF-graf beskriver ett systems dataflöde och via det resulterande domänspecifika språket kan en utvecklare på ett tillfredsställande sätt beskriva dataflöden i javamiljön. Det visade sig att det resulterande domän specifika språket i Groovy skiljer sig en aning från Haskell i hur man specificerar aktörer och deras kopplingar, men det fundamentala konceptet är detsamma. Groovy i kombination med Gradle erbjöd ett smidigt sätt att programmera ett domänspecifikt språk med hjälp av closures vilket kan användas för framtida bruk inom utvecklingsområdet. Den skapade prototypen är den första medlemmen i en familj av framtida modelleringsspråk som beskriver beräkningsmodeller. Resultatet av projektet utgör en grund för ett fortsatt arbete med att bygga vidare på prototypen, men även för att kunna lägga till fler beräkningsmoduler som i sin tur bidrar med utbyggningen av ramverket ForSyDe.

Les systèmes sur puce sont de plus en plus complexes : ils intègrent des parties numériques, desparties analogiques et des capteurs ou actionneurs. SystemC et son extension SystemC AMSpermettent aujourd’hui de modéliser à haut niveau d’abstraction de tels systèmes. Ces outilsconstituent de véritables atouts dans une optique d’étude de faisabilité, d’exploration architecturale etde vérification du fonctionnement global des systèmes complexes hétérogènes et multiphysiques. Eneffet, les durées de simulation deviennent trop importantes pour envisager les simulations globales àbas niveau d’abstraction. De plus, les simulations basées sur l’utilisation conjointe de différents outilsprovoquent des problèmes de synchronisation. Les modèles de bas niveau, une fois crées par lesspécialistes des différents domaines peuvent toutefois être abstraits afin de générer des modèles dehaut niveau simulables sous SystemC/SystemC AMS en des temps de simulation réduits. Une analysedes modèles de calcul et des styles de modélisation possibles est d’abord présentée afin d’établir unlien avec les durées de simulation, ceci pour proposer un style de modélisation en fonction du niveaud’abstraction souhaité et de l’ampleur de la simulation à effectuer. Dans le cas des circuits analogiqueslinéaires, une méthode permettant de générer automatiquement des modèles de haut niveaud’abstraction à partir de modèles de bas niveau a été proposée. Afin d’évaluer très tôt dans le flot deconception la consommation d’un système, un moyen d’enrichir les modèles de haut niveaupréalablement générés est présenté. L’attention a ensuite été portée sur la modélisation à haut niveaudes systèmes multiphysiques. Deux méthodes y sont discutées : la méthode consistant à utiliser lecircuit équivalent électrique puis la méthode basée sur les bond graphs. En particulier, nous proposonsune méthode permettant de générer un modèle équivalent au bond graph à partir d’un modèle de basniveau. Enfin, la modélisation d’un système éolien est étudiée afin d’illustrer les différents conceptsprésentés dans cette thèse. / Systems on chip are more and more complex as they now embed not only digital and analog parts, butalso sensors and actuators. SystemC and its extension SystemC AMS allow the high level modeling ofsuch systems. These tools are efficient for feasibility study, architectural exploration and globalverification of heterogeneous and multiphysics systems. At low level of abstraction, the simulationdurations are too important. Moreover, synchronization problems appear when cosimulations areperformed. It is possible to abstract the low level models that are developed by the specialists of thedifferent domains to create high level models that can be simulated faster using SystemC/SystemCAMS. The models of computation and the modeling styles have been studied. A relation is shownbetween the modeling style, the model size and the simulation speed. A method that generatesautomatically the high level model of an analog linear circuit from its low level representation isproposed. Then, it is shown how to include in the high level model some information allowing thepower consumption estimation. After that, the multiphysics systems modeling is studied. Twomethods are discussed: firstly, the one that uses the electrical equivalent circuit, then the one based onthe bond graph approach. It is shown how to generate a bond graph equivalent model from a low levelrepresentation. Finally, the modeling of a wind turbine system is discussed in order to illustrate thedifferent concepts presented in this thesis.

Les systèmes temps-réel critiques sont de plus en plus complexes, et les exigences fonctionnelles et non-fonctionnelles ne cessent plus de croître. Le flot de conception de tels systèmes doit assurer, parmi d’autres propriétés, le déterminisme fonctionnel et la prévisibilité temporelle. Le déterminisme fonctionnel est inhérent aux modèles de calcul flot de données (ex. KPN, SDF, etc.) ; c’est pour cela qu’ils sont largement utilisés pour modéliser les systèmes embarqués de traitement de flux. Un effort considérable a été accompli pour résoudre le problème d’ordonnancement statique périodique et à mémoire de communication bornée des graphes flot de données. Cependant, les systèmes embarqués temps-réel optent de plus en plus pour l’utilisation de systèmes d’exploitation temps-réel et de stratégies d’ordonnancement dynamique pour gérer les tâches et les ressources critiques. Cette thèse aborde le problème d’ordonnancement temps-réel dynamique des graphes flot de données ; ce problème consiste à assigner chaque acteur dans un graphe à une tâche temps-réel périodique (i.e. calcul des périodes, des phases, etc.) de façon à : (1) assurer l’ordonnançabilité des tâches sur une architecture et pour une stratégie d’ordonnancement (ex. RM, EDF) données ; (2) exclure statiquement les exceptions d’overflow et d’underflow sur les buffers de communication ; et (3) optimiser les performances du système (ex. maximisation du débit, minimisation des tailles des buffers). / The ever-increasing functional and nonfunctional requirements in real-time safety-critical embedded systems call for new design flows that solve the specification, validation, and synthesis problems. Ensuring key properties, such as functional determinism and temporal predictability, has been the main objective of many embedded system design models. Dataflow models of computation (such as KPN, SDF, CSDF, etc.) are widely used to model stream-based embedded systems due to their inherent functional determinism. Since the introduction of the (C)SDF model, a considerable effort has been made to solve the static-periodic scheduling problem. Ensuring boundedness and liveness is the essence of the proposed algorithms in addition to optimizing some nonfunctional performance metrics (e.g. buffer minimization, throughput maximization, etc.). However, nowadays real-time embedded systems are so complex that real-time operating systems are used to manage hardware resources and host real-time tasks. Most of real-time operating systems rely on priority-driven scheduling algorithms (e.g. RM, EDF, etc.) instead of static schedules which are inflexible and difficult to maintain. This thesis addresses the real-time scheduling problem of dataflow graph specifications; i.e. transformation of the dataflow specification to a set of independent real-time tasks w.r.t. a given priority-driven scheduling policy such that the following properties are satisfied: (1) channels are bounded and overflow/underflow-free; (2) the task set is schedulable on a given uniprocessor (or multiprocessor) architecture. This problem requires the synthesis of scheduling parameters (e.g. periods, priorities, processor allocation, etc.) and channel capacities. Furthermore, the thesis considers two performance optimization problems: buffer minimization and throughput maximization.