The macro-dataflow model of execution has been used in scheduling heuristics for directed acyclic graphs. Since this model was developed for the scheduling of parallel applications on distributed computing systems, it is inadequate when applied to the multicore shared-memory computers prevalent in the market today. The pulled-macro-dataflow model is put forth as an alternative to the macro-dataflow model, having been designed specifically to accurately describe the memory bandwidth limitations and request-driven nature of communications characteristic of today's machines. The performance of the common scheduling heuristics DSC and CASS-II are evaluated under the pulled-macro-dataflow model and it is shown that their poor performance motivates the development of a new scheduling heuristic. The Concurrent Tournament Reducer (ConTouR) is developed as a scheduling heuristic which operates well with the pulled-macro-dataflow model. ConTouR is compared to the existing heuristics Load Balancing and Communication Minimization in scheduling two programs. For both programs, the other reducers are shown to outperform ConTouR.

As metodologias clássicas de análise de desempenho de sistemas sobre silício (System on chip, SoC) geralmente são descritas em função do tempo de execução do pior-caso1 das tarefas a serem executadas. No entanto, nas aplicações do mundo real, o tempo de execução destas tarefas pode variar devido à presença dos diferentes eventos de entrada que ativam o sistema, colocando uma exigência diferente de execução sobre os recursos do sistema. Geralmente, um modelo da carga de trabalho é uma parte integrante de um modelo de desempenho utilizado para avaliar o desempenho de um sistema. O quão bom for um modelo de carga de trabalho determina em grande medida a qualidade das soluções do projeto e a precisão das estimativas de desempenho baseadas nele. Nesta tese, é abordado o problema de modelar a carga de trabalho para o projeto de sistemas de tempo-real cuja funcionalidade envolve processamento de fluxos de multimídia, isto é, fluxos de dados representando áudio, imagens ou vídeo. O problema de modelar a carga de trabalho é abordado sob a premissa de que uma caracterização acurada do comportamento temporal do software embarcado permite ao projetista identificar diversas exigências variáveis de execução, apresentadas para os diversos recursos de arquitetura do sistema, tanto na operação individual do conjunto de tarefas de software, assim como na execução global da aplicação, em fase de projeto. A caracterização do comportamento de cada tarefa foi definida a partir de uma análise temporal dos códigos de software associados às diferentes tarefas de uma aplicação, a fim de identificar os múltiplos modos de operação que o código pode apresentar dentro de um processador. Esta caracterização é feita através da realização de uma análise estática das rotas do código executável, de forma que para cada rota de execução encontrada, estimam-se os tempos extremos de execução (WCET e BCET)2, baseando-se na modelagem da microarquitetura de um processador on-chip. Desta forma, cada rota do código executável junto aos seus respectivos tempos de execução, constitui um modo de operação do código analisado. A fim de agrupar os diversos modos de operação que apresentam um grau de semelhança entre si de acordo a uma perspectiva da medida de processamento utilizado do processador modelado, foi utilizado o conceito de cenário, o qual diferencia o comportamento de cada tarefa em relação às entradas que a aplicação sob análise pode receber. Partindo desta caracterização temporal de cada tarefa de software, as exigências da execução global da aplicação são representadas através de um modelo analítico de eventos. O modelo considera as diferentes tarefas como atores temporais de um grafo de fluxo síncrono de dados, de modo que os diferentes cenários de operação da aplicação são definidos em função dos tempos variáveis de execução identificados previamente na caracterização de cada tarefa. Uma descrição matemática deste modelo, baseada na Álgebra de Max-Plus, permite caracterizar analiticamente os diferentes fluxos de eventos entre a entrada e a saída da aplicação, assim como os fluxos de eventos entre as diferentes tarefas, considerando as mudanças nas exigências de processamento associadas aos diversos cenários previamente identificados. Esta caracterização analítica dos diversos fluxos de eventos de entrada e saída é a base para um modelo de curvas de carga de trabalho baseada em cenários de aplicação, e um modelo de curvas de serviços baseada também em cenários, que dão lugar a caracterizar o dinamismo comportamental da aplicação analisada, determinado pela diversidade de eventos de entrada que podem ativar diferentes comportamentos do sistema em fase de execução. / Classical methods for performance analysis of Multiprocessor System-on-chip (MPSoCs) are usually described in terms of Worst-Case Execution Times (WCET) of the executed tasks. Nevertheless, in real-world applications the running time of tasks varies due to different input events that trigger the system, imposing a different workload on the system resources. Usually, a workload model is a part of a performance model used to evaluate the performance of a system. How good is a workload model largely determines the quality of design solutions and the accuracy of performance estimations based on it. This thesis addresses the problem of modeling the workload for the design of real-time systems which functionality involves multimedia streams processing, i.e, data streams representing audio, images or video. The workload modeling problem is addressed from the assumption that an accurate characterization of timing behavior of real-time embedded software enables the designer to identify several variable execution requirements that the individual operation of the software tasks and the overall execution of the application will present to the several system resources of an architecture, in design phase. The software task characterization was defined from a timing analysis of the source code in order to identify the multiple operating modes the code can exhibit within a processor. This characterization is done by performing a static path analysis on the code, so that for each given path the worst-case and bestcase execution times (WCET and BCET) were estimated, based on a microarchitectural modeling of an on-chip processor. Thus, every execution path of the code, with its estimated execution times, defines an operation mode of the analyzed code. In order to cluster the several operation modes that exhibit certain degree of similarity according to the required amount of processing in the modeled processor, the concept of scenario was used, which differentiates every task behavior with respect to the several inputs the application under analysis may receive. From this timing characterization of every application task, the global execution requirements of the application are represented by an analytical event model. It describes the tasks as timed actors of a synchronous dataflow graph, so that the multiple application scenarios are defined in terms of the variable execution times previously identified in the task characterization. A mathematical description of this model based on the Max-Plus Algebra allows one to characterize the different event sequences incoming to, and exiting from, the application as well as the event sequences between the different tasks, having in count changes in the processing requirements associated with the various scenarios previously identified. This analytical characterization between the input event sequences and the output event sequences states the basis for a model of scenario-based workload curves and a model of scenario-based service curves that allow characterizing the behavioral dynamism of the application determined by the several input events that activate several system behaviors, in the execution phase.

As metodologias clássicas de análise de desempenho de sistemas sobre silício (System on chip, SoC) geralmente são descritas em função do tempo de execução do pior-caso1 das tarefas a serem executadas. No entanto, nas aplicações do mundo real, o tempo de execução destas tarefas pode variar devido à presença dos diferentes eventos de entrada que ativam o sistema, colocando uma exigência diferente de execução sobre os recursos do sistema. Geralmente, um modelo da carga de trabalho é uma parte integrante de um modelo de desempenho utilizado para avaliar o desempenho de um sistema. O quão bom for um modelo de carga de trabalho determina em grande medida a qualidade das soluções do projeto e a precisão das estimativas de desempenho baseadas nele. Nesta tese, é abordado o problema de modelar a carga de trabalho para o projeto de sistemas de tempo-real cuja funcionalidade envolve processamento de fluxos de multimídia, isto é, fluxos de dados representando áudio, imagens ou vídeo. O problema de modelar a carga de trabalho é abordado sob a premissa de que uma caracterização acurada do comportamento temporal do software embarcado permite ao projetista identificar diversas exigências variáveis de execução, apresentadas para os diversos recursos de arquitetura do sistema, tanto na operação individual do conjunto de tarefas de software, assim como na execução global da aplicação, em fase de projeto. A caracterização do comportamento de cada tarefa foi definida a partir de uma análise temporal dos códigos de software associados às diferentes tarefas de uma aplicação, a fim de identificar os múltiplos modos de operação que o código pode apresentar dentro de um processador. Esta caracterização é feita através da realização de uma análise estática das rotas do código executável, de forma que para cada rota de execução encontrada, estimam-se os tempos extremos de execução (WCET e BCET)2, baseando-se na modelagem da microarquitetura de um processador on-chip. Desta forma, cada rota do código executável junto aos seus respectivos tempos de execução, constitui um modo de operação do código analisado. A fim de agrupar os diversos modos de operação que apresentam um grau de semelhança entre si de acordo a uma perspectiva da medida de processamento utilizado do processador modelado, foi utilizado o conceito de cenário, o qual diferencia o comportamento de cada tarefa em relação às entradas que a aplicação sob análise pode receber. Partindo desta caracterização temporal de cada tarefa de software, as exigências da execução global da aplicação são representadas através de um modelo analítico de eventos. O modelo considera as diferentes tarefas como atores temporais de um grafo de fluxo síncrono de dados, de modo que os diferentes cenários de operação da aplicação são definidos em função dos tempos variáveis de execução identificados previamente na caracterização de cada tarefa. Uma descrição matemática deste modelo, baseada na Álgebra de Max-Plus, permite caracterizar analiticamente os diferentes fluxos de eventos entre a entrada e a saída da aplicação, assim como os fluxos de eventos entre as diferentes tarefas, considerando as mudanças nas exigências de processamento associadas aos diversos cenários previamente identificados. Esta caracterização analítica dos diversos fluxos de eventos de entrada e saída é a base para um modelo de curvas de carga de trabalho baseada em cenários de aplicação, e um modelo de curvas de serviços baseada também em cenários, que dão lugar a caracterizar o dinamismo comportamental da aplicação analisada, determinado pela diversidade de eventos de entrada que podem ativar diferentes comportamentos do sistema em fase de execução. / Classical methods for performance analysis of Multiprocessor System-on-chip (MPSoCs) are usually described in terms of Worst-Case Execution Times (WCET) of the executed tasks. Nevertheless, in real-world applications the running time of tasks varies due to different input events that trigger the system, imposing a different workload on the system resources. Usually, a workload model is a part of a performance model used to evaluate the performance of a system. How good is a workload model largely determines the quality of design solutions and the accuracy of performance estimations based on it. This thesis addresses the problem of modeling the workload for the design of real-time systems which functionality involves multimedia streams processing, i.e, data streams representing audio, images or video. The workload modeling problem is addressed from the assumption that an accurate characterization of timing behavior of real-time embedded software enables the designer to identify several variable execution requirements that the individual operation of the software tasks and the overall execution of the application will present to the several system resources of an architecture, in design phase. The software task characterization was defined from a timing analysis of the source code in order to identify the multiple operating modes the code can exhibit within a processor. This characterization is done by performing a static path analysis on the code, so that for each given path the worst-case and bestcase execution times (WCET and BCET) were estimated, based on a microarchitectural modeling of an on-chip processor. Thus, every execution path of the code, with its estimated execution times, defines an operation mode of the analyzed code. In order to cluster the several operation modes that exhibit certain degree of similarity according to the required amount of processing in the modeled processor, the concept of scenario was used, which differentiates every task behavior with respect to the several inputs the application under analysis may receive. From this timing characterization of every application task, the global execution requirements of the application are represented by an analytical event model. It describes the tasks as timed actors of a synchronous dataflow graph, so that the multiple application scenarios are defined in terms of the variable execution times previously identified in the task characterization. A mathematical description of this model based on the Max-Plus Algebra allows one to characterize the different event sequences incoming to, and exiting from, the application as well as the event sequences between the different tasks, having in count changes in the processing requirements associated with the various scenarios previously identified. This analytical characterization between the input event sequences and the output event sequences states the basis for a model of scenario-based workload curves and a model of scenario-based service curves that allow characterizing the behavioral dynamism of the application determined by the several input events that activate several system behaviors, in the execution phase.

Cette thèse propose un nouveau paradigme de représentation d’applications pour les machines virtuelles, capable d’abstraire l’architecture des systèmes informatiques. Les machines virtuelles actuelles reposent sur un modèle unique de représentation d’application qui abstrait les instructions des machines et sur un modèle d’exécution qui traduit le fonctionnement de ces instructions vers les machines cibles. S’ils sont capables de rendre les applications portables sur une vaste gamme de systèmes, ces deux modèles ne permettent pas en revanche d’exprimer la concurrence sur les instructions. Or, celle-ci est indispensable pour optimiser le traitement des applications selon les ressources disponibles de la plate-forme cible. Nous avons tout d’abord développé une représentation « universelle » d’applications pour machine virtuelle fondée sur la modélisation par graphe flux de données. Une application est ainsi modélisée par un graphe orienté dont les sommets sont des unités de calcul (les acteurs) et dont les arcs représentent le flux de données passant au travers de ces sommets. Chaque unité de calcul peut être traitée indépendamment des autres sur des ressources distinctes. La concurrence sur les instructions dans l’application est alors explicite. Exploiter ce nouveau formalisme de description d'applications nécessite de modifier les règles de programmation. A cette fin, nous avons introduit et défini le concept de « Représentation Canonique et Minimale » d’acteur. Il se fonde à la fois sur le langage de programmation orienté acteur CAL et sur les modèles d’abstraction d’instructions des machines virtuelles existantes. Notre contribution majeure qui intègre les deux nouvelles représentations proposées, est le développement d’une « Machine Virtuelle Universelle » (MVU) dont la spécificité est de gérer les mécanismes d’adaptation, d’optimisation et d’ordonnancement à partir de l’infrastructure de compilation Low-Level Virtual Machine. La pertinence de cette MVU est démontrée dans le contexte normatif du codage vidéo reconfigurable (RVC). En effet, MPEG RVC fournit des applications de référence de décodeurs conformes à la norme MPEG-4 partie 2 Simple Profile sous la forme de graphe flux de données. L’une des applications de cette thèse est la modélisation par graphe flux de données d’un décodeur conforme à la norme MPEG-4 partie 10 Constrained Baseline Profile qui est deux fois plus complexe que les applications de référence MPEG RVC. Les résultats expérimentaux montrent un gain en performance en exécution de deux pour des plates-formes dotées de deux cœurs par rapport à une exécution mono-cœur. Les optimisations développées aboutissent à un gain de 25% sur ces performances pour des temps de compilation diminués de moitié. Les travaux effectués démontrent le caractère opérationnel et universel de cette norme dont le cadre d’utilisation dépasse le domaine vidéo pour s’appliquer à d’autres domaine de traitement du signal (3D, son, photo…) / This thesis proposes a new paradigm that abstracts the architecture of computer systems for representing virtual machines’ applications. Current applications are based on abstraction of machine’s instructions and on an execution model that reflects operations of these instructions on the target machine. While these two models are efficient to make applications portable across a wide range of systems, they do not express concurrency between instructions. Expressing concurrency is yet essential to optimize processing of application as the number of processing units is increasing in computer systems. We first develop a “universal” representation of applications for virtual machines based on dataflow graph modeling. Thus, an application is modeled by a directed graph where vertices are computation units (the actors) and edges represent the flow of data between vertices. Each processing units can be treated apart independently on separate resources. Concurrency in the instructions is then made explicitly. Exploit this new description formalism of applications requires a change in programming rules. To that purpose, we introduce and define a “Minimal and Canonical Representation” of actors. It is both based on actor-oriented programming and on instructions ‘abstraction used in existing Virtual Machines. Our major contribution, which incorporates the two new representations proposed, is the development of a “Universal Virtual Machine” (UVM) for managing specific mechanisms of adaptation, optimization and scheduling based on the Low-Level Virtual Machine (LLVM) infrastructure. The relevance of the MVU is demonstrated on the MPEG Reconfigurable Video Coding standard. In fact, MPEG RVC provides decoder’s reference application compliant with the MPEG-4 part 2 Simple Profile in the form of dataflow graph. One application of this thesis is a new dataflow description of a decoder compliant with the MPEG-4 part 10 Constrained Baseline Profile, which is twice as complex as the reference MPEG RVC application. Experimental results show a gain in performance close to double on a two cores compare to a single core execution. Developed optimizations result in a gain on performance of 25% for compile times reduced by half. The work developed demonstrates the operational nature of this standard and offers a universal framework which exceeds the field of video domain (3D, sound, picture...)